Abstract
Operating unmanned aerial vehicles (UAVs) in complex environments with dynamic obstacles and external disturbances poses significant challenges due to inherent uncertainties. Inaccurate robot localization and modeling errors further complicate safe navigation. While existing research often addresses static environments or treats disturbances in isolation, this paper proposes a reliable motion planning framework that integrates various uncertainties into a probabilistic chance constraint. By calculating the collision probability between a Gaussian-distributed forward reachable set and obstacle states, we provide a robust safety certificate. To minimize the conservatism typical of such methods, we introduce a tight upper bound for collision probability, evaluated through both exact and approximate solutions. Our approach is validated in simulation and real-world experiments, demonstrating superior efficiency and reliability in uncertain environments.
Introduction
Navigating a drone through a crowded factory or a gusty outdoor space is a significant challenge for traditional motion planners. In these scenarios, three primary sources of uncertainty converge: dynamic obstacles (e.g., moving people), external disturbances (e.g., wind gusts), and intrinsic uncertainty (e.g., sensor noise and modeling errors).
Existing solutions generally fall into two categories: chance-constrained (probabilistic) or set-bounded (worst-case). However, current probabilistic methods often rely on loose approximations of risk. To ensure safety, these planners become overly conservative, leading to inefficient detours or the "frozen robot" problem, where the UAV stops entirely because it overestimates the likelihood of a collision. This research aims to find a "Goldilocks" zone: a risk estimate that is mathematically rigorous and "tight," allowing the drone to be assertive yet safe.
Methodology
The proposed framework treats both the robot and obstacles as ellipsoids and hinges on three technical pillars to ensure precise risk estimation.
1. The Tight Probability Bound
The collision region is modeled as the Minkowski sum of the robot and obstacle ellipsoids. To calculate the probability of the drone entering this region, the authors derive an exact solution using series expansions of quadratic forms in Gaussian variables. This provides a much more accurate risk assessment than standard linearization techniques.
2. Dual-Speed Estimation
To balance computational efficiency with mathematical rigor, the framework employs two methods of risk calculation:
- Approximated Solution: During the initial path-searching phase, the system uses Gauss-Hermite quadrature—a numerical integration technique—for fast, "good enough" safety checks.
- Exact Solution: During the final trajectory optimization phase, the computationally intensive series expansion is used to ensure the safety certificate is as precise as possible.
3. Iterative Trajectory Optimization
Because the exact probability function is non-convex and difficult to optimize directly, the framework utilizes an iterative algorithm. It begins with a simplified, linearized version of the risk and progressively "tightens" the trajectory through proportional interpolation until it meets the user-defined safety threshold. Additionally, the framework incorporates Forward Reachable Sets (FRS) to account for where wind disturbances might push the drone, integrating this "reachability bubble" into the collision check.
Experimental Validation
The method was evaluated through custom simulation environments and real-world flight tests:
- Crowd Navigation (CN): A 20m x 10m space featuring 20 humans moving according to a "social force" model.
- Factory Patrolling (FP): A 20m x 12m space containing static obstacles and 12 randomly walking humans.
- Real-World Experiment: A quadrotor hovering in a windy environment generated by a large fan while actively avoiding a human walking toward it.
Key Insights and Results
Overcoming Conservatism
The research demonstrates that standard linearized collision constraints significantly overestimate risk. For instance, a linearized model might estimate risk at 0.22 for a 0.3-level risk set, even when the true risk is much lower. By using a tighter bound, the UAV can navigate through narrower gaps between moving obstacles that other planners would deem too risky.
Performance Metrics
- Success Rate: In the Factory Patrolling simulation, the proposed method achieved a 99% success rate, significantly outperforming competing state-of-the-art methods (92% and 85%).
- Efficiency: The drone completed missions faster. In the Crowd Navigation test, the mission time was 22.5 seconds, compared to 26–27 seconds for competitors.
- Real-Time Viability: Despite the mathematical complexity, the entire pipeline—including FRS calculation and trajectory optimization—runs in approximately 50ms on an NVIDIA Orin NX onboard computer.
Conclusion and Future Work
This framework provides a reliable and efficient solution for UAV motion planning by reducing the gap between estimated and actual collision probabilities. While the current model assumes perfect sensing of obstacle positions and velocities, future work will focus on integrating visibility planning to account for sensor occlusions. Additionally, the authors aim to extend the geometric modeling beyond ellipsoids to more complex, non-convex shapes while maintaining the tightness of the probability bounds.
Summary updated