Chance-Constrained Optimal Path Planning With Obstacles

Blackmore, Lars; Ono, Masahiro; Williams, Brian C. · 2011 · OpenAlex-citations

DOI: 10.1109/tro.2011.2161160

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of optimal path planning for autonomous vehicles, such as Unmanned Aerial Vehicles (UAVs), in environments with obstacles and uncertainty. Traditional approaches often assume perfect state knowledge or use set-bounded uncertainty models, which can be overly conservative or fail to account for stochastic disturbances like wind and localization errors. The authors propose a chance-constrained approach that explicitly models uncertainty probabilistically, ensuring the probability of collision or leaving a safe region remains below a user-specified threshold. This method allows operators to trade off conservatism against performance, offering a more meaningful representation of risk compared to deterministic or set-bounded methods. The study assumes linear, discrete-time system dynamics with Gaussian uncertainty in the initial state, process noise, and model errors. The core technical contribution is a novel bounding technique that approximates the non-convex chance-constrained optimization problem as a Disjunctive Convex Program. By deriving analytic bounds on the probability of collision, the authors decompose the complex multi-variable Gaussian integrals into tractable univariate constraints. This transformation enables the use of branch-and-bound algorithms to solve the problem to global optimality. To address computational demands for onboard applications, the authors introduce a customized solution method using disjunctive linear bounds that provides almost-optimal solutions with hard bounds on suboptimality, significantly reducing computation time compared to solving the full program or using computationally intensive particle-based sampling methods. The paper validates the approach through simulation, specifically using an aircraft obstacle avoidance example. The results demonstrate that the proposed method introduces very little conservatism compared to the true chance-constrained problem, unlike prior set-conversion techniques which were shown to be conservative by orders of magnitude. The customized solution algorithm effectively reduces solution time while maintaining tight bounds on suboptimality in almost all cases. The empirical comparison with particle-based approaches highlights the superior computational efficiency of the proposed bounding method, which guarantees constraint satisfaction rather than approximating it. The significance of this work lies in its ability to handle non-convex feasible regions (obstacles) under probabilistic uncertainty without resorting to excessive conservatism. By providing a tractable, globally optimal solution framework for chance-constrained path planning, the paper advances the field of autonomous vehicle control. It offers a practical tool for designing robust trajectories that balance safety and performance, enabling reliable operation in uncertain environments where precise collision avoidance is critical.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• situational awareness