Chance-Constrained Optimal Path Planning With Obstacles

By Lars Blackmore, Masahiro Ono, Brian Charles Williams. IEEE Transactions on robotics, 2011

440 citations recorded by the source corpus.

Autonomous vehicles need to plan trajectories to a specified goal that avoid obstacles. For robust execution, we must take into account uncertainty, which arises due to uncertain localization, modeling errors, and disturbances. Prior work handled the case of set-bounded uncertainty. We present here a chance-constrained approach, which uses instead a probabilistic representation of uncertainty. The new approach plans the future probabilistic distribution of the vehicle state so that the probability of failure is below a specified threshold. Failure occurs when the vehicle collides with an obstacle or leaves an operator-specified region. The key idea behind the approach is to use bounds on the probability of collision to show that, for linear-Gaussian systems, we can approximate the nonconvex chance-constrained optimization problem as a disjunctive convex program. This can be solved to global optimality using branch-and-bound techniques. In order to improve computation time, we introduce a customized solution method that returns almost-optimal solutions along with a hard bound on the level of suboptimality. We present an empirical validation with an aircraft obstacle avoidance example.

Subfields: Automotive Engineering, Computer Vision and Pattern Recognition, Control and Systems Engineering

View Paper: https://www.semanticscholar.org/paper/d706b2ebb3531cf55e62a481504abfe0ae30f6fa

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

Citations in the corpus

Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey (2014, background): “215 If disturbance is Gaussian rather than set bounded, the MPC problem may be reformulated stochastically so the overall risk of collision is bounded to an arbitrary level, see, e.g., [30, 69].”
Safe Control under Uncertainty (2015, methodology): “More recently, researchers have proposed modeling the environment in a chance constrained framework, and there are some promising results in the area of urban autonomous driving [24, 39, 40, 6, 8].”
How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics (2017, background): “ constraint speciﬁes an upper bound on the probability of incurring a cost higher than a given threshold. Chance constraints have been widely studied in robotics for motion planning under uncertainty [6, 10, 23]. While chance constraints are suitable for capturing risk corresponding to boolean event”
Stochastic Model Predictive Control: An Overview and Perspectives for Future Research (2016, neutral): “Robot and vehicle path planning [89], [144], [145] [93] [64]”
Safe Control under Uncertainty with Probabilistic Signal Temporal Logic (2016, methodology): “In all of our examples discussed below, the optimization at every step is completed in less than 2 seconds on a 2.3 GHz Intel Core i7 processor with 16 GB RAM.”
Batch Policy Learning under Constraints (2019, background): “Other examples from the literature that belong to this safety perspective include planning under chance constraints (Ono et al., 2015; Blackmore et al., 2011).”
Optimization-Based Collision Avoidance (2017, methodology): “Optimization-based trajectory planning algorithms such as Model Predictive Control (MPC) have received signiﬁcant attention recently, ranging from (unmanned) aircraft to robots to autonomous cars [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12].”