Source-linked AI summary
FASTER: Fast and Safe Trajectory Planner for Flights in Unknown Environments
Jesus Tordesillas, Brett T. Lopez, Jonathan P. How
TL;DR
High-speed planning in unknown environments must react quickly while preserving safety, but common obstacle-handling and stopping strategies yield slow, conservative trajectories. FASTER jointly plans in free-known and unknown space, keeps a safe free-known backup, and uses flexible MIQP allocation with an efficient replanning heuristic; experiments demonstrated agile flights up to 3.6 m/s.
Problem
High-speed trajectory planning in unknown environments requires fast reactions and safety, while tractability-driven obstacle handling and final-stop strategies can produce slow, conservative trajectories.
Method
FASTER plans in F ∪ U while maintaining a feasible safe trajectory in F, and uses MIQP interval allocation with a previous-step-based time heuristic and cost-to-go selection.
Results
3.6 m/s: FASTER achieved agile flights in unknown cluttered environments in simulation and hardware experiments.
Takeaways & Limitations
FASTER provides a planning framework that combines higher nominal speed with safety through a continuously available free-known backup trajectory.
Abstract
from arXiv · showhide
High-speed trajectory planning through unknown environments requires algorithmic techniques that enable fast reaction times while maintaining safety as new information about the operating environment is obtained. The requirement of computational tractability typically leads to optimization problems that do not include the obstacle constraints (collision checks are done on the solutions) or use a convex decomposition of the free space and then impose an ad-hoc time allocation scheme for each interval of the trajectory. Moreover, safety guarantees are usually obtained by having a local planner that plans a trajectory with a final "stop" condition in the free-known space. However, these two decisions typically lead to slow and conservative trajectories. We propose FASTER (Fast and Safe Trajectory Planner) to overcome these issues. FASTER obtains high-speed trajectories by enabling the local planner to optimize in both the free-known and unknown spaces. Safety guarantees are ensured by always having a feasible, safe back-up trajectory in the free-known space at the start of each replanning step. Furthermore, we present a Mixed Integer Quadratic Program formulation in which the solver can choose the trajectory interval allocation, and where a time allocation heuristic is computed efficiently using the result of the previous replanning iteration. This proposed algorithm is tested extensively both in simulation and in real hardware, showing agile flights in unknown cluttered environments with velocities up to 3.6 m/s.
I. INTRODUCTION
FASTER targets faster, less conservative flight planning by optimizing in free-known and unknown space while maintaining a safe free-known backup trajectory. Its contributions include flexible interval and time allocation, a cost-to-go heuristic, and simulation and hardware validation.
- Motivation: Existing safety strategies construct trajectories entirely in F with a final stop condition, but these approaches can produce slow trajectories when F is small.
- Contributions: FASTER allows the local planner to optimize in F ∪ U while maintaining a safe trajectory in F.The safe trajectory is available at the beginning of every replanning step.
- Contributions: FASTER reduces conservatism in the MIQP formulation for trajectory interval and time allocation compared with prior work.
- Contributions: A cost-to-go heuristic computed cheaply from the previous replanning step helps the local planner choose which direction to optimize toward.
- Evaluation: 3.6 m/s: simulation and hardware experiments demonstrated agile flights in completely unknown cluttered environments.
II. RELATED WORK
UAV local planners differ in their operating space and optimization formulation. Existing approaches trade computational efficiency or safety for maneuverability and speed, while convex decomposition introduces interval and time allocation constraints.
- Planning space: Some local planners use only recent perception data, requiring trajectories to remain within the sensor field of view.
- Planning space: Other planners use historical maps but restrict trajectories to free-known space, typically relying on a final stop condition for safety.
- Optimization formulation: Obstacle-free optimization is computationally efficient and supports multiple sampled candidates, but discretization limits sophisticated maneuvers and can slow flights in clutter.
- Optimization formulation: Convex decomposition directly imposes obstacle constraints, but commonly fixes one trajectory segment per polyhedron and creates interval and time allocation problems.
A. Planning
FASTER combines a JPS-guided hierarchical planner with MIQP-based cubic trajectories, optimizing through free-known and unknown space while maintaining a safe free-known backup. Its formulation lets the optimizer select corridor intervals and uses previous replanning results to adapt time allocation efficiently.
- Architecture: FASTER uses a long-horizon JPS global planner to guide a short-horizon local planner toward the goal.JPS finds shortest piecewise-linear paths in a 3D uniformly weighted voxel grid while remaining complete and optimal.
- Trajectory types: The Whole Trajectory is optimized in F ∪ U, whereas the Safe Trajectory is constrained entirely to free-known space F and includes a final stop condition.The Safe Trajectory provides the fallback segment used to preserve safety when planning through unknown space.
- Trajectory types: The Committed Trajectory concatenates the Whole Trajectory segment A → R with the Safe Trajectory and is executed if later replanning steps find no feasible solution.This committed path is guaranteed to remain inside F and serves as the executable backup.
- Trajectory model: Cubic trajectories arise from triple-integrator dynamics with constant jerk on each interval, producing third-degree polynomial position splines.The state and input represent position, velocity, acceleration, and jerk; each interval uses a cubic polynomial x_n(τ).
- MIQP formulation: Binary corridor variables allow each interval to select at least one overlapping polyhedron, while control-point containment keeps the cubic Bézier trajectory inside the chosen corridor.The optimizer is free to choose which polyhedron contains each interval rather than assigning one fixed polyhedron per segment.
- Time allocation: The common interval duration dt is computed from velocity, acceleration, and jerk limits, then scaled by a factor searched around the factor that worked in the previous replanning step.When f = 1, the heuristic gives a lower bound on the minimum feasible interval time; the solver tests increasing factors until convergence.
- Direction selection: The planner chooses between a newly computed JPS path and an obstacle-adjusted previous path by comparing heuristic cost-to-go values in each direction.The selected direction minimizes the estimated time to continue from the relevant sphere intersection to the projected goal.
B. Mapping
The mapping system uses a sliding occupancy map centered on the UAV, updating as it flies. Known occupied and unknown regions are inflated by the UAV radius to support safety.
- The sliding map moves with the UAV during flight.Depth data is fused into the occupancy grid using 3D Bresenham ray-tracing.
- The forest simulation environment measures 50 × 50 m.
- Timing analysis compares MIQP and convex-decomposition costs for Whole and Safe Trajectories as Pmax varies.The shaded region represents the 1-σ standard-deviation interval.
A. Simulation
Simulation studies evaluate FASTER in random forest and bugtrap environments against multiple planning methods, measuring distance, completion time, and computational timing. FASTER improves flight distance and time while maintaining tractable runtimes.
- FASTER is evaluated in 10 random forest environments against seven alternative planning approaches.The comparisons include RRT*, NBVP, Safe Local Exploration, and Multi-Fidelity methods.
- 8−51% improvement in distance is achieved across the forest comparisons.The reported dynamic limits are vmax = 5 m/s, amax = 5 m/s2, and jmax = 8 m/s3.
- 52% improvement in completion time is achieved over the previous algorithm in the forest simulation.Completion-time values are compared with the authors’ earlier method.
- 63% improvement in total flight time is achieved in the bugtrap environment despite similar total distance.The bugtrap comparison uses vmax = 10 m/s, amax = 10 m/s2, and jmax = 40 m/s3.
B. Hardware
Hardware experiments use onboard perception, mapping, and planning components to test FASTER in cluttered obstacle courses. The UAV performs agile maneuvers at speeds reaching 3.6 m/s while the planner maintains low runtime.
- Perception runs on a RealSense camera, while mapping and planning run on an Intel NUC and control runs on a Qualcomm Snapdragon Flight.State estimation fuses propagated IMU measurements with external motion capture using a Kalman filter.
- 2.1 m/s maximum speed is achieved in the first two obstacle-course experiments.The UAV avoids table obstacles, passes through a narrow gap, and flies below a triangular obstacle.
- 3.6 m/s maximum speed is achieved while navigating poles of different heights and passing below a cardboard-box structure.
- Below 32 ms is the 75th-percentile runtime for both Whole and Safe Trajectory MIQPs when Pmax = 2.This runtime result is reported for both forest simulation and onboard hardware experiments.
V. CONCLUSIONS
FASTER is presented as a fast and safe planner for agile flight in unknown environments, combining higher nominal speed with safety and successful simulation and hardware testing.
- FASTER is presented as a fast and safe planner for agile flights in unknown environments.
- The reported timing breakdown uses Pmax = 2, N = 10 for the Whole Trajectory, and N = 7 for the Safe Trajectory.
- Planning in both U and F supports higher nominal speed while maintaining a Safe Trajectory in F at each replanning step.The Safe Trajectory is planned in F before every replanning step.
- FASTER was tested in simulation and on real hardware, achieving velocities up to 3.6 m/s.