Stochastic Reachability Based Motion Planning for Multiple Moving Obstacle Avoidance

One of the many challenges in designing autonomy for operation in uncertain and 
dynamic environments is the planning of collision-free paths. Roadmap-based motion 
planning is a popular technique for identifying collision-free paths, since it 
approximates the often infeasible space of all possible motions with a networked 
structure of valid configurations. We use stochastic reachable sets to identify 
regions of low collision probability, and to create roadmaps which incorporate 
likelihood of collision. We complete a small number of stochastic reachability 
calculations with individual obstacles a priori. This information is then 
associated with the weight, or preference for traversal, given to a transition in
the roadmap structure. Our method is novel, and scales well with the number of 
obstacles, maintaining a relatively high probability of reaching the goal in a 
finite time horizon without collision, as compared to other methods. We demonstrate 
our method on systems with up to 50 dynamic obstacles.