Research › Analysis

EGO-Planner: An ESDF-Free Gradient-Based Local Planner for Quadrotors

Zhou, X., Wang, Z., Xu, C. & Gao, F. · IEEE Robot. Autom. Lett. 6, 478–485 (2021) · Paper · Code

Q2 Computing analysis. All mathematical results and empirical findings are attributed to the original authors. We present our reading of the work as it relates to robotic automation.

What this paper solves

Gradient-based trajectory optimizers need to know two things about every point on a trajectory: is it in collision, and which direction moves it out fastest. The standard answer is an Euclidean Signed Distance Field (ESDF): a precomputed 3D grid where every voxel stores its distance to the nearest obstacle and the gradient pointing away from it. ESDF works well but is expensive. Updating the field after sensor observations takes 20–100ms and touches the entire map volume, most of which the trajectory never visits.

EGO-Planner eliminates the ESDF entirely. Instead of asking the map for distances, it asks a much cheaper question: for each trajectory control point that is currently in collision, where is the nearest point on a collision-free guiding path? The answer to that question is all the gradient information the optimizer needs, and it can be computed in milliseconds without touching the rest of the map.

Key mathematical framework

B-spline trajectory representation

The trajectory is represented as a uniform B-spline of degree p over control points $Q = {q_{0}, q_{1}, \dots, q_{n}}$ :

T (t) = i \sum B_{i, p} (t) \cdot q_{i}

where $B_{i, p}$ are the B-spline basis functions. A degree-5 B-spline gives $C^{2}$ continuity (continuous position, velocity, and acceleration) by construction, which means the trajectory is dynamically smooth without explicit smoothness constraints on every intermediate waypoint. Velocity and acceleration at any point are linear combinations of the control points, so their gradients are constant matrices and no numerical differentiation is required.

ESDF-free collision penalty

For each control point $q_{i}$ that lies inside an occupied voxel, EGO-Planner constructs a guiding path: a collision-free path segment near $q_{i}$ found by ray-casting through the occupied region. Let $g_{i}$ be the nearest point on this guiding path to $q_{i}$ . The collision cost for that control point is:

J_{c} (q_{i}) = \frac{1}{2} ∥ q_{i} - g_{i} ∥^{2}

The gradient $\nabla J_{c} = q_{i} - g_{i}$ points directly from the collision point toward the guiding path, replacing the ESDF gradient entirely. The guiding path is only computed for control points that are actually in collision. The planner touches no map information outside the trajectory's immediate vicinity.

Smoothness cost

The smoothness penalty operates on the finite differences of control points, which correspond to velocity, acceleration, and jerk under the B-spline parameterization:

J_{s} = λ_{v} \sum ∥ v_{i} ∥^{2} + λ_{a} \sum ∥ a_{i} ∥^{2} + λ_{j} \sum ∥ j_{i} ∥^{2}

where $v_{i}, a_{i}, j_{i}$ are the velocity, acceleration, and jerk vectors at each knot.

Dynamic feasibility via time reallocation

Rather than penalizing dynamic constraint violations inside the cost function, EGO-Planner handles feasibility as a post-optimization correction. After each optimization step, if any velocity or acceleration bound is violated, the time allocation is scaled:

T_{new} = T_{old} \cdot max \frac{∥ v _{i} ∥}{v _{max}}, \frac{∥ a _{i} ∥}{a _{max}}

Scaling up $T$ uniformly reduces all velocities and accelerations proportionally while preserving the trajectory shape. An anisotropic curve-fitting step then adjusts higher-order derivatives independently per axis to recover smoothness without distorting the spatial path.

Total optimization objective

J = λ_{s} \cdot J_{smooth} + λ_{c} \cdot J_{collision}

Minimized via L-BFGS over the control point positions. Dynamic feasibility is enforced by the time reallocation step outside the gradient loop, keeping the optimization landscape well-conditioned and making feasibility a hard guarantee rather than a soft preference.

Empirical observations

Planning time: EGO-Planner completed replanning cycles in 2–6ms on an Intel NUC (i7, 8th gen). ESDF-based baselines required 20–100ms for equivalent map sizes, a 10–20x speedup
Flight speed: Real-world experiments confirmed stable autonomous flight at up to 7.4 m/s in cluttered indoor environments without collision
Trajectory quality: Benchmark comparisons showed EGO-Planner produced trajectories with comparable smoothness and safety margins to ESDF-based methods despite not computing the field
Hardware target: Successfully deployed on embedded platforms including the NVIDIA Jetson TX2, confirming the method is viable on the class of hardware Q2 targets for edge deployment
Replanning frequency: The sub-10ms planning time enabled replanning at 10–20Hz, sufficient for real-time obstacle avoidance at the tested flight speeds
Robustness: Experiments in both simulated and real environments with dynamic obstacles confirmed the guiding-path gradient remains stable when the trajectory crosses new obstacles mid-flight

What this means for robotic automation

The ESDF removal is the transferable result. Any gradient-based motion planner that currently maintains a distance field to compute collision gradients is paying a computational tax proportional to map volume. EGO-Planner shows that the only information the optimizer actually needs is local to the trajectory itself. The insight scales to ground robots, robotic arms, and any system doing real-time trajectory optimization in a changing environment.

The time-reallocation approach to dynamic feasibility is also worth noting. Encoding feasibility as a penalty term competing with smoothness and collision terms creates poorly conditioned optimization landscapes. Separating it into a deterministic post-processing step keeps the optimizer working on a cleaner problem and makes feasibility a hard guarantee rather than a soft preference.