Source-linked AI summary
EGO-Planner: An ESDF-free Gradient-based Local Planner for Quadrotors
Xin Zhou, Zhepei Wang, Hongkai Ye, Chao Xu, Fei Gao
TL;DR
ESDF construction is a major computational bottleneck in gradient-based quadrotor planning, while trajectory optimization uses only a limited portion of the updated field. The paper proposes an ESDF-free planner that extracts obstacle information from trajectory collisions, adjusts time allocation for dynamic feasibility, and refines trajectories anisotropically; experiments report comparable performance with computation time reduced by over an order of magnitude.
Problem
ESDF construction can consume up to about 70% of local-planning processing time and computes values outside the trajectory's limited planning subspace.
Method
The planner evaluates obstacle gradients directly, stores information only for newly encountered obstacles, reallocates time when dynamics are infeasible, and uses anisotropic curve fitting for trajectory refinement.
Results
The proposed planner achieves comparable performance to state-of-the-art ESDF-based planners while reducing computation time by over an order of magnitude.
Takeaways & Limitations
ESDF-free gradient-based planning can provide robust, highly efficient quadrotor local planning with safe trajectories and comparable smoothness and aggressiveness.
Takeaways & Limitations
The planner is designed for static environments and handles slowly moving obstacles below 0.5m/s without modification.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Gradient-based quadrotor planners depend on ESDF information, but ESDF construction can dominate computation while updating regions irrelevant to the optimized trajectory. EGO removes this dependency by extracting obstacle gradients directly and adds trajectory refinement for dynamical feasibility.
- ESDF computation takes up to about 70% of total processing time in local planning, making it a bottleneck for resource-limited platforms.
- Existing ESDF construction methods spend computation on values that do not contribute to trajectory optimization because the trajectory covers only a limited updating range.
- The framework optimizes smoothness, collision avoidance, and dynamical feasibility, then reallocates time and refines the trajectory when dynamical limits are violated.
- Compared with state-of-the-art methods, EGO reports comparable smoothness and aggressiveness with computation time reduced by over an order of magnitude.
- EGO evaluates and projects obstacle-gradient information directly instead of querying a pre-built ESDF.
II. RELATED WORK
Prior quadrotor planners use gradient-based optimization and ESDFs to obtain obstacle-distance gradients, but ESDF construction is computationally burdensome and can provide insufficient information. EGO instead assigns obstacle-derived guidance only to colliding trajectory segments.
- A. Gradient-based Motion Planning: Gradient-based motion planning formulates UAV local trajectory generation as unconstrained nonlinear optimization using obstacle-gradient information.
- B. ESDF Construction: ESDF construction methods include incremental global updating and batch local calculation, but neither focuses computation solely on the trajectory.
- III. Collision Avoidance Force Estimation: EGO generates a collision-free guiding path for each detected colliding segment and assigns obstacle-surface anchor points with repulsive directions to its control points.
- III. Collision Avoidance Force Estimation: Obstacle information is stored only when a control point newly satisfies the positive-distance criterion for all valid obstacle pairs, reducing duplicate processing.
- B. ESDF Construction: ESDF-based planners can fall into local minima because insufficient or incorrect ESDF information prevents escape from obstacles, motivating collision-free initialization.
IV. GRADIENT-BASED TRAJECTORY OPTIMIZATION
EGO parameterizes trajectories with uniform B-splines and optimizes their control points using smoothness, collision, and dynamical-feasibility penalties. B-spline geometric properties allow trajectory-wide constraints to be handled through control-point conditions.
- A. Problem Formulation: The trajectory is represented by a uniform B-spline uniquely determined by its degree, 3D control points, and knot vector.
- A. Problem Formulation: Each B-spline span lies within the convex hull of successive control points, enabling geometric feasibility constraints through control-point bounds.
- A. Problem Formulation: The optimization variables are B-spline control points planned in a reduced space of differentially flat outputs.
- A. Problem Formulation: The objective combines smoothness, collision, and dynamical-feasibility penalties, weighted by λs, λc, and λd.
1) Smoothness penalty:
The smoothness penalty reduces higher-order trajectory derivatives while collision costs push control points away from obstacles. Collision gradients are computed directly from the control-point cost rather than interpolated from a precomputed ESDF.
- The smoothness formulation penalizes squared acceleration and jerk without time integration.
- Minimizing derivative control points is sufficient to reduce the corresponding derivatives along the entire B-spline trajectory.
- The resulting smoothness cost minimizes higher-order derivatives, making the whole trajectory smooth.
- Collision costs penalize control points within safety clearance sf and use a twice continuously differentiable function with a suppressed slope near obstacles.
- Each control point accumulates costs from its associated obstacle anchor-direction pairs, receiving greater deformation weight when it discovers more obstacles.
- The collision gradient is obtained by differentiating the accumulated collision cost with respect to control points instead of interpolating a traditional ESDF.
3) Feasibility penalty:
Feasibility is enforced by limiting higher-order derivatives dimension by dimension. Because of the B-spline convex hull property, constraining derivative control points constrains the full trajectory.
- Feasibility limits higher-order trajectory derivatives separately along each dimension x, y, and z.
- The B-spline convex hull property makes derivative-control-point constraints sufficient to constrain the entire trajectory.
- The feasibility penalty uses weights wv, wa, and wj for derivative terms and a twice continuously differentiable metric F(·).
- The piecewise metric parameters are selected for second-order continuity, derivative limits, interval splitting, and an elastic coefficient λ < 1−ϵ.
B. Numerical Optimization
The objective changes as new obstacles are discovered, so optimization must restart quickly; its near-quadratic structure motivates efficient quasi-Newton solvers. The section compares Barzilai-Borwein, truncated Newton, and L-BFGS methods, with line search enforcing convergence.
- Newly discovered obstacles adaptively alter objective J, requiring an optimization solver capable of fast restarts.
- The approximately quadratic objective motivates using Hessian information, while exact inverse-Hessian computation is too expensive for real-time applications.
- The comparison includes Barzilai-Borwein, truncated Newton, and L-BFGS quasi-Newton methods with different Hessian-approximation strategies.
- The Newton-style update uses step length αk and an iteratively updated approximate inverse Hessian Hk.
- The L-BFGS implementation uses two-loop recursion with linear time and space complexity, initializing its inverse Hessian using the Barzilai-Borwein step weight.
- A monotone line search satisfying the strong Wolfe condition is used to enforce convergence.
V. TIME RE-ALLOCATION AND TRAJECTORY REFINEMENT
The planner reallocates time when derivative limits are violated, then anisotropically fits a new curve to preserve the safe trajectory’s shape while improving feasibility.
- Time Re-allocation: Time re-allocation lengthens selected knot spans when velocity, acceleration, or jerk limits are exceeded.The required extension is derived from each derivative’s inverse dependence on the time span.
- Trajectory Refinement: A new uniform B-spline is generated with reallocated time while retaining the safe trajectory’s shape and control-point count.
- Trajectory Refinement: The refined objective combines smoothness, feasibility, and curve-fitting penalties, and is solved using L-BFGS.
- Trajectory Refinement: Anisotropic fitting assigns low penalties to axial displacement and high penalties to radial displacement, allowing smoothness adjustment while avoiding collision.The fitting penalty uses a spheroidal metric so equal spheroid-surface displacements receive equal penalties.
A. Implementation Details
The implementation uses a local-support B-spline planner with collision checking, obstacle-information updates, optimization, and feasibility refinement, evaluated through controlled solver comparisons.
- Implementation Details: The planner uses a cubic B-spline with about 25 control points over a roughly 7 m planning horizon.These empirical settings balance problem complexity and degrees of freedom.
- Implementation Details: Rebound Planning iteratively adds information for newly encountered obstacles, evaluates penalties and gradients, and performs one-step optimization until collision-free.
- Implementation Details: If the optimized trajectory is dynamically infeasible, the planner reallocates time and applies curve-fitting optimization before returning it.
- Implementation Details: The planner discretizes trajectory comparisons and checks a fixed-radius circular pipe around the final trajectory to enforce clearance.The optimizer stops when no collision is detected.
- Optimization Algorithms Comparison: Solver comparisons record success rate, computation time, and objective-function evaluations across 100 independent runs in random maps.
C. Trajectory Generation With & Without ESDF
EGO achieves comparable success to ESDF-based planning with collision-free initialization, while trading slightly higher trajectory energy for shorter optimization time and avoiding ESDF-maintenance cost.
- Trajectory Generation With & Without ESDF: EGO achieves a comparable success rate to ESDF-based methods with collision-free initialization.The comparison distinguishes EI, using collision-free initialization, from ENI, without it.
- Trajectory Generation With & Without ESDF: EGO produces slightly higher trajectory energy than EI but shorter optimization time.The paper attributes this trade-off to stronger trajectory deformation forces from EGO’s control-point representation.
- Trajectory Generation With & Without ESDF: Even with a reduced ESDF update volume, ESDF updating remains a majority of computation time for a 9 m trajectory.
- Multiple Planners Comparison: Compared with Fast-Planner and EWOK, EGO is evaluated across obstacle densities using repeated runs from identical starts and ends.Average performance statistics and ESDF computation time are reported in the planner comparison.
- Multiple Planners Comparison: EGO achieves shorter flight time and trajectory length but higher energy cost than Fast-Planner, while saving computation time by omitting ESDF updating.
E. Real-world Experiments
Real-world tests in cluttered indoor and outdoor environments demonstrate feasible aggressive flight under limited sensing, including narrow passages, abrupt goals, and unreliable forest maps.
- Real-world Experiments: In indoor waypoint flights, the drone traverses a narrow passage of less than one meter and reaches 3.56 m/s in clutter.
- Real-world Experiments: Abruptly assigned indoor goals under limited field of view require immediate feasible trajectories when goals or collision threats appear.
- Real-world Experiments: Outdoor forest flights remain feasible despite swinging vegetation and unreliable mapping, with the drone reaching speeds above 3 m/s.
- Real-world Experiments: The experiments support the planner’s robustness and efficiency across simulation benchmarks and real-world tests.
- Limitations: The planner is designed for static environments and handles slowly moving obstacles below 0.5 m/s without modification.