Dynamic Replanning with Posterior Sampling

Abstract

When navigating to a goal in an uncertain environment, a robot must simultaneously navigate the exploration-exploitation tradeoff: should it aim to gain information and reduce uncertainty, or should it simply brave the unknown? We formalize this as the Bayesian dynamic motion planning problem, and we analyze how several strategies from the literature balance these concerns via determinization and planning. Within the framework of determinization in the face of uncertainty, we shift the burden of exploration to determinization rather than planning. Dynamic Replanning with Posterior Sampling (DRPS) is very efficient: each iteration consists of a single posterior update and a shortest path query. Relative to comparative baselines across seven datasets of 2D planning problems, DRPS has a higher percentage of success, traverses lower or comparable total distances, and accelerates total planning time by 4–7×. Across a dataset of larger 7D Baxter manipulator planning problems, DRPS reduces total distance by 40% and total planning time by 18×.