A probabilistic approach to optimal robust path planning with obstacles

Autonomous vehicles need to plan trajectories to a specified goal that avoid obstacles. Previous approaches that used a constrained optimization approach to solve for finite sequences of optimal control inputs have been highly effective. For robust execution, it is essential to take into account the inherent uncertainty in the problem, which arises due to uncertain localization, modeling errors, and disturbances. Prior work has handled the case of deterministically bounded uncertainty. We present here an alternative approach that uses a probabilistic representation of uncertainty, and plans the future probabilistic distribution of the vehicle state so that the probability of collision with obstacles is below a specified threshold. This approach has two main advantages; first, uncertainty is often modeled more naturally using a probabilistic representation (for example in the case of uncertain localization); second, by specifying the probability of successful execution, the desired level of conservatism in the plan can be specified in a meaningful manner. The key idea behind the approach is that the probabilistic obstacle avoidance problem can be expressed as a disjunctive linear program using linear chance constraints. The resulting disjunctive linear program has the same complexity as that corresponding to the deterministic path planning problem with no representation of uncertainty. Hence the resulting problem can be solved using existing, efficient techniques, such that planning with uncertainty requires minimal additional computation. Finally, we present an empirical validation of the new method with a number of aircraft obstacle avoidance scenarios