Tight Collision Probability for UAV Motion Planning in Uncertain Environment

Tianyu Liu, Fu Zhang, Fei Gao, Jia Pan

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

Abstract

Operating unmanned aerial vehicles (UAVs) in complex environments that feature dynamic obstacles and external disturbances poses significant challenges, primarily due to the inherent uncertainty in such scenarios. Additionally, inaccurate robot localization and modeling errors further exacerbate these challenges. Recent research on UAV motion planning in static environments has been unable to cope with the rapidly changing surroundings, resulting in trajectories that may not be feasible. Moreover, previous approaches that have addressed dynamic obstacles or external disturbances in isolation are insufficient to handle the complexities of such environments. This paper proposes a reliable motion planning framework for UAVs, integrating various uncertainties into a chance constraint that characterizes the uncertainty in a probabilistic manner. The chance constraint provides a probabilistic safety certificate by calculating the collision probability between the robot's Gaussian-distributed forward reachable set and states of obstacles. To reduce the conservatism of the planned trajectory, we propose a tight upper bound of the collision probability and evaluate it both exactly and approximately. The approximated solution is used to generate motion primitives as a reference trajectory, while the exact solution is leveraged to iteratively optimize the trajectory for better results. Our method is thoroughly tested in simulation and real-world experiments, verifying its reliability and effectiveness in uncertain environments.
BibTeX
@inproceedings{liu2023tight,
  author = {Tianyu Liu and Fu Zhang and Fei Gao and Jia Pan},
  title = {{Tight Collision Probability for UAV Motion Planning in Uncertain Environment}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=qE66XoWMno},
}
Figure