EGO-Planner: An ESDF-free Gradient-based Local Planner for Quadrotors

Xin Zhou, Zhepei Wang, Chao Xu, Fei Gao

Abstract

Gradient-based planners are widely used for quadrotor local planning, in which a Euclidean Signed Distance Field (ESDF) is crucial for evaluating gradient magnitude and direction. Nevertheless, computing such a field has much redundancy since the trajectory optimization procedure only covers a very limited subspace of the ESDF updating range. In this paper, an ESDF-free gradient-based planning framework is proposed, which significantly reduces computation time. The main improvement is that the collision term in the penalty function is formulated by comparing the colliding trajectory with a collision-free guiding path. The resulting obstacle information will be stored only if the trajectory hits new obstacles, making the planner only extract necessary obstacle information. Then, we lengthen the time allocation if dynamical feasibility is violated. An anisotropic curve fitting algorithm is introduced to adjust higher-order derivatives of the trajectory while maintaining the original shape. Benchmark comparisons and real-world experiments verify its robustness and high-performance. The source code is released as ROS packages.

Introduction

Autonomous quadrotor navigation requires local motion planners that are smooth, fast, and collision-free. Gradient-based planners are popular because they use numerical optimization to "push" trajectories away from obstacles. Traditionally, these planners rely on a Euclidean Signed Distance Field (ESDF)—a 3D map where every point stores its distance to the nearest obstacle.

However, building and updating an ESDF is a massive computational bottleneck, often consuming up to 70% of the total processing time. Furthermore, most of that computation is wasted; a drone only needs distance information for the tiny slice of space it is actually flying through, not the entire room. EGO-Planner addresses this by eliminating the need for a global ESDF, calculating obstacle gradients directly and only when needed.

The trajectory optimization procedure covers only a limited subspace of the ESDF updating range, leading to significant computational redundancy.

Methods

The EGO-Planner framework replaces the global ESDF with a demand-driven gradient estimation. Key components include:

ESDF-free Gradient Estimation

When a trajectory is found to collide with an obstacle, the planner performs an A* search to find a "guiding path" around it. It then generates "anchor points" on the obstacle surface and repulsive vectors. The optimization process uses these specific points to calculate collision costs, effectively "rebounding" the trajectory out of the obstacle without needing a full distance map. This "force projection" approach allows the planner to wrap the path around obstacles dynamically.

B-spline Parameterization and Optimization

The trajectory is modeled as a uniform B-spline, leveraging its "convex hull property" to ensure safety if control points are safe. The optimization follows a two-stage process:

  1. Rebound Planning: The trajectory is iteratively optimized using the L-BFGS algorithm to escape obstacles. L-BFGS was chosen for its balance between speed and accuracy in estimating the optimization space's curvature.
  2. Refinement: If the path violates dynamical feasibility (e.g., too sharp for the motors), the planner re-allocates time. An anisotropic curve fitting algorithm is used here, penalizing radial displacement more heavily than axial displacement to maintain safety while improving agility.

Results

The system was evaluated through simulations with varying obstacle densities and real-world flights in cluttered indoor offices and dense outdoor forests.

Performance Benchmarks

EGO-Planner was compared against state-of-the-art planners like EWOK and Fast-Planner. By eliminating the ESDF update step, which typically takes 4–6ms, EGO-Planner achieved a total planning time of approximately 0.81ms—over an order of magnitude faster than traditional methods.

Comparison of ESDF updating time and planning time across different frameworks. EGO-Planner (Proposed) eliminates ESDF update time and minimizes planning time.

Real-world Robustness

In experimental tests, the quadrotor achieved speeds of 3.56 m/s indoors and successfully navigated complex forest environments with swaying branches. The planner maintained a success rate of around 89% in challenging scenarios, comparable to ESDF-based methods but with a significantly lower computational footprint.

Conclusion and Future Work

EGO-Planner demonstrates that global distance maps are largely unnecessary for local planning. By extracting obstacle information only where collisions occur, it achieves high-speed navigation with minimal overhead. While the A* guiding path helps avoid local minima, future work aims to improve performance in extremely complex geometries and extend the framework to handle dynamic obstacles and topological path exploration.

Summary updated

Abstract

Gradient-based planners are widely used for quadrotor local planning, in which a Euclidean Signed Distance Field (ESDF) is crucial for evaluating gradient magnitude and direction. Nevertheless, computing such a field has much redundancy since the trajectory optimization procedure only covers a very limited subspace of the ESDF updating range. In this paper, an ESDF-free gradient-based planning framework is proposed, which significantly reduces computation time. The main improvement is that the collision term in the penalty function is formulated by comparing the colliding trajectory with a collision-free guiding path. The resulting obstacle information will be stored only if the trajectory hits new obstacles, making the planner only extract necessary obstacle information. Then, we lengthen the time allocation if dynamical feasibility is violated. An anisotropic curve fitting algorithm is introduced to adjust higher-order derivatives of the trajectory while maintaining the original shape. Benchmark comparisons and real-world experiments verify its robustness and high-performance. The source code is released as ROS packages.
BibTeX
@article{zhou2021ego,
  author = {Xin Zhou and Zhepei Wang and Chao Xu and Fei Gao},
  title = {{EGO-Planner: An ESDF-free Gradient-based Local Planner for Quadrotors}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2021},
  url = {https://openreview.net/forum?id=KvZ3vLdvVd},
}
Figure