Approximate Branch and Bound for Fast, Risk-Bound Stochastic Path Planning

Abstract

Path planning under uncertainty is a difficult and often intractable problem. Autonomous agents must model and reason about complex stochastic processes to quickly derive high quality plans. Most approaches separate the model of uncertainty from the planning; a model is selected and then a controller derived. This work proposes an approach for fast path planning under uncertainty that scales the model of uncertainty such that good policies receive the most effort. To do this, we use an innovative form of the problem's chance constraint to formulate a convex, stochastic path planning problem from the non-convex problem. Next, a bound on the path's expected cost is developed that allows a trade-off between speed of computation and accuracy. The bound is trivially parallelized on a GPU. Finally, a modified branch and bound algorithm is introduced that scales computational effort for more promising solutions. The method is benchmarked against existing approaches including those using Boole's inequality, a MILP approach, and a parallelized sampling-based approach. It outperforms other approaches based on speed and the ability to meet the chance constraint while not being overly conservative.