TL;DR
COAST (Corridor-Optimized Aerially-Safe Trajectories) is a new B-Spline trajectory planner that achieves sub-5ms computation times while providing hard safety guarantees through Safe Flight Corridors (SFCs). By leveraging MINVO transforms and the inherent properties of clamped B-Splines, it enables aggressive, dynamically feasible flight in cluttered environments without the typical trade-off between speed and safety.
What Problem Does This Paper Address?
In the world of autonomous drone flight, trajectory planners face a frustrating "speed vs. safety" dilemma.
On one hand, penalty-based methods are computationally fast but rely on "soft constraints"—essentially just telling the drone that hitting a wall is "very expensive." This lacks formal safety guarantees. On the other hand, Safe Flight Corridor (SFC) methods provide "hard constraints" by defining volumes of space mathematically proven to be obstacle-free. However, traditional SFC planners are often too slow for real-time, high-speed flight because optimizing a smooth curve within these complex volumes is computationally taxing.
COAST aims to bridge this gap, providing a planner that is both mathematically "safe" (guaranteed collision-free) and fast enough for real-time deployment on hardware with limited onboard compute.
Methods
COAST divides the trajectory planning problem into a two-stage pipeline:
- Front-End (Pathfinding & SFC Generation): It uses an A* algorithm to find an initial path through a voxelized map. A greedy pruning algorithm then simplifies this path into a chain of rectangular prisms—the Safe Flight Corridors. These prisms are dynamically resized based on local obstacles to maximize the available flight volume.
- Back-End (Optimization): This is where the magic happens. The planner formulates a Quadratic Programming (QP) problem to optimize the B-Spline control points.
Key technical innovations include:
- Vector Representation for Snap Minimization: The authors developed a way to represent B-Spline derivatives (velocity, acceleration, jerk, and snap) as sparse matrix operations. This allows the "snap" (the 4th derivative of position, crucial for quadrotor smoothness) to be minimized using a pre-computable cost function.
- Clamped B-Splines: Unlike "natural" splines, clamped B-splines pin the trajectory endpoints exactly to the control points, which simplifies staying within the SFC boundaries at the start and end of a segment.
- MINVO Transforms: Standard B-Spline properties provide a "convex hull" for safety, but these bounds are often too conservative (too large), leading to sluggish flight. COAST uses Minimum Volume (MINVO) transforms to create much tighter bounds around the trajectory, allowing the drone to fly more aggressively while still staying within physical limits.
Datasets
The authors evaluated COAST using high-fidelity simulations:
- Randomized Forest Environments: Static environments populated with cylindrical obstacles at 5% and 10% density levels in a 100 x 40m field.
- ROSflight & ROScopter: The planner was integrated with the open-source ROSflight framework to verify dynamic feasibility in a closed-loop control setting, simulating real quadrotor physics.
Key Insights and Ideas
- Exploiting Sparsity: Because B-Splines have "local support" (changing one control point only affects a small part of the curve), the resulting optimization matrices are extremely sparse. The authors used the OSQP solver, which is specifically designed to exploit this sparsity for massive speedups.
- Tightening the Bounds: The use of MINVO transforms is a standout idea. By creating a tighter convex hull than standard B-Spline basis functions, the planner can push the vehicle closer to its actual physical limits (velocity and acceleration) without risking a violation.
- Geometric Containment: By ensuring that the control points of the spline stay within the intersection of sequential SFC prisms, the authors mathematically guarantee that the entire continuous curve stays inside the safe volume.
Key Results
The performance metrics for COAST are impressive, particularly regarding its suitability for real-time use:
- Computation Speed: The mean end-to-end replanning time was under 5 ms (specifically 2.46 ms at 5% density and 4.25 ms at 10% density). The core optimization (OSQP) had a median solve time of just 0.32 ms.
- Safety: In closed-loop testing, the system achieved zero violations of per-axis velocity and acceleration limits.
- Robustness: In a Monte Carlo analysis of over 100,000 solves, 91% of trajectories were recovered on the first attempt. Collisions occurred in only 0.3% of trials (mostly due to the planner "stalling" or failing to find a path rather than a safety violation).
Limitations and Future Work
While COAST is fast and safe, the authors noted a few areas for improvement:
- Flight Stalling: In very dense environments, the local planner can occasionally get "stuck" or stall. Future work will look at advanced local and global horizon algorithms to mitigate this.
- Uniform Knot Spacing: The current use of uniform knots can lead to conservative velocity profiles. The authors plan to integrate non-uniform knot sequences to allow for even higher flight velocities.
- Platform Expansion: While tested on quadrotors, the authors aim to extend this kinodynamically feasible architecture to fixed-wing platforms and validate it through rigorous outdoor hardware experiments.
Summary updated