Abstract
In this paper, we propose a robust and efficient quadrotor motion planning system for fast flight in 3-D complex environments. We adopt a kinodynamic path searching method to find a safe, kinodynamic feasible and minimum-time initial trajectory in the discretized control space. We improve the smoothness and clearance of the trajectory by a B-spline optimization, which incorporates gradient information from a Euclidean distance field (EDF) and dynamic constraints efficiently utilizing the convex hull property of B-spline. Finally, by representing the final trajectory as a non-uniform B-spline, an iterative time adjustment method is adopted to guarantee dynamically feasible and non-conservative trajectories. We validate our proposed method in various complex simulational environments. The competence of the method is also validated in challenging real-world tasks. We release our code as an open-source package.
Introduction
Autonomous quadrotor flight in unknown, complex environments requires a delicate balance between safety, dynamic feasibility, and computational efficiency. Existing motion planning methods often struggle to meet all three simultaneously. Hard-constrained methods, while safe, are typically computationally expensive and produce conservative, slow trajectories. Conversely, soft-constrained methods using gradient-based optimization are faster but often fail in dense environments due to local minima or an inability to strictly guarantee that the drone stays within its physical motor limits.
Researchers from HKUST have developed a three-stage motion planning system designed to bridge this gap, enabling quadrotors to fly aggressively through cluttered environments. The system generates safe, smooth, and high-speed trajectories in just a few milliseconds, significantly outperforming previous state-of-the-art methods.
Methodology
The proposed system follows a "bottom-up" systematic approach consisting of three main components:
1. Kinodynamic Path Searching
The "front-end" utilizes a hybrid-state A* search. Instead of searching for simple geometric lines, it explores "motion primitives"—short bursts of control inputs that obey the laws of physics. This ensures the initial path is not only safe but also physically achievable by the quadrotor's motors.
2. B-spline Trajectory Optimization
To refine the often jagged initial path, the system employs B-spline optimization. A key innovation here is leveraging the convex hull property of B-splines: if the control points of a B-spline are within a safe zone or within velocity limits, the entire continuous curve is guaranteed to be as well. This allows the optimizer to handle complex constraints using simple, distance-based gradients from a Euclidean Distance Field (EDF).
3. Iterative Time Adjustment
If the optimized path requires speeds exceeding the drone's limits, the system uses an iterative time-adjustment technique. By representing the trajectory as a non-uniform B-spline, it "stretches" the time allocated to specific segments (knot spans) until the velocity and acceleration profiles are within feasible limits, without needing to restart the entire optimization process.
Key Results and Discussion
The method was rigorously evaluated in both simulated random forests and real-world experiments using a quadrotor equipped with a Velodyne VLP-16 LiDAR.
- Computational Efficiency: The B-spline optimization converges in approximately 1ms, a 10x improvement over previous gradient-based methods (~10ms). Total path searching time was reduced from ~60ms to ~5ms.
- Robustness: In dense simulations, the proposed path search achieved a 100% success rate, whereas previous methods dropped to 77% at similar resolutions.
- Real-world Agility: The system successfully navigated unknown indoor environments at speeds up to 2.5 m/s, demonstrating real-time reactivity to obstacles and changing goals.
Conclusion
This research presents a highly efficient framework for fast autonomous flight. By decoupling geometric shape from temporal speed and utilizing the unique properties of B-splines, the system achieves high-speed navigation with guaranteed safety. While currently limited by the onboard sensor's horizon, future work aims to scale this system for larger environments and multi-drone coordination.
Summary updated