Tight Collision Probability for UAV Motion Planning in Uncertain Environment

Tianyu Liu, Fu Zhang, Fei Gao, Jia Pan

TL;DR

This paper introduces a novel motion planning framework for UAVs that calculates a "tight" upper bound for collision probability in environments with both dynamic obstacles and wind disturbances. By combining an exact mathematical solution for risk estimation with an iterative optimization algorithm, the authors enable drones to fly more efficiently—avoiding the overly cautious "frozen robot" behavior of previous methods—without sacrificing safety.

What Problem Does This Paper Address?

Navigating a drone through a crowded factory or a windy outdoor space is a nightmare for traditional motion planners. There are three main sources of "messiness":

  1. Dynamic Obstacles: People or other robots moving in unpredictable ways.
  2. External Disturbances: Wind gusts that push the drone off its intended path.
  3. Intrinsic Uncertainty: Small errors in the drone's own sensors and internal models.

Existing solutions usually fall into two camps: "chance-constrained" (probabilistic) or "set-bounded" (worst-case scenario). The problem is that current probabilistic methods often use loose approximations of risk. To be "safe," these drones end up being extremely conservative, taking long, inefficient detours or stopping entirely because they overestimate the chance of a crash. This paper aims to find the "Goldilocks" zone: a risk estimate that is mathematically rigorous (tight) so the drone can be assertive yet safe.

Methods

The authors propose a reliable motion planning framework that treats the robot and obstacles as ellipsoids. Their approach hinges on three key technical pillars:

  • The Tight Probability Bound: They model the collision region as the Minkowski sum of the robot and obstacle ellipsoids. To calculate the probability of the drone entering this region, they derive an exact solution using series expansions of quadratic forms in Gaussian variables.
  • Dual-Speed Estimation:
    • Approximated Solution: For fast, "good enough" checks during the initial path-searching phase, they use Gauss-Hermite quadrature (a numerical integration technique).
  • Exact Solution: They use the computationally heavier series expansion during the final trajectory optimization to ensure the safety certificate is as precise as possible.
  • Iterative Trajectory Optimization: Since the exact probability function is non-convex and hard to optimize directly, they use an iterative algorithm. It starts with a simplified, linearized version of the risk and progressively "tightens" the trajectory until it hits the user-defined safety threshold.
  • Forward Reachable Sets (FRS): To handle wind, they calculate an FRS—essentially a "bubble" that accounts for where the drone could be pushed by external forces—and integrate this into the collision check.

Datasets

The paper evaluates the method using custom-designed simulation environments and real-world experiments rather than static datasets:

  • Simulation Scenarios:
    • Crowd Navigation (CN): A 20m x 10m space with 20 humans moving via a "social force" model.
  • Factory Patrolling (FP): A 20m x 12m space with 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 Ideas

  • Linearization is Too Cautious: The authors demonstrate that standard linearized collision constraints (used in many SOTA planners) significantly overestimate risk. For a 0.3-level risk set, the linearized version might estimate the risk at 0.22 when the true risk is much lower.
  • The "Tightness" Advantage: By using a tighter bound, the drone can navigate through narrower gaps between moving people that other planners would deem "too risky."
  • Heuristic Interpolation: In their optimization loop, they found that the linearized probability and the exact probability are positively correlated. They use this to "guess" the next best step via proportional interpolation, which speeds up the convergence of their algorithm.

Key Results

  • Higher Success Rates: In the "Factory Patrolling" simulation, the proposed method achieved a 99% success rate, compared to 92% and 85% for competing state-of-the-art methods.
  • Efficiency: The drone completed missions faster. In the "Crowd Navigation" test, the mission time was 22.5 seconds, whereas competitors took 26-27 seconds because they were being too cautious.
  • Real-Time Performance: Despite the complex math, the entire pipeline (including FRS calculation and trajectory optimization) runs in roughly 50ms on an NVIDIA Orin NX onboard computer, making it viable for real-world flight.

Limitations and Future Work

  • Perfect Sensing Assumption: The current framework assumes the drone knows the exact position and velocity of obstacles (likely via a motion capture system or high-end sensors). In the real world, "visibility" is often limited.
  • Future Direction: The authors plan to integrate visibility planning to account for sensor occlusions and reduce localization uncertainty.
  • Geometric Simplification: While ellipsoids are efficient, they don't perfectly capture the shape of every object. Extending this to more complex, non-convex shapes while maintaining "tightness" remains a challenge.

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},
}

Loading related content...

Figure