/Pareto-Optimal Search over Configuration Space Beliefs for Anytime Motion Planning

Pareto-Optimal Search over Configuration Space Beliefs for Anytime Motion Planning

Shushman Choudhury, Christopher Dellin and Siddhartha Srinivasa
Conference Paper, IEEE/RSJ International Conference on Intelligent Robots and Systems, October, 2016

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


We present POMP (Pareto Optimal Motion Planner), an anytime algorithm for geometric path planning on roadmaps. For robots with several degrees of freedom, collision checks are computationally expensive and often dominate planning time. Our goal is to minimize the number of collision checks for obtaining the first feasible path and successively shorter feasible paths. We assume that the roadmaps we search over are embedded in a continuous ambient space, where nearby points tend to share the same collision state. This enables us to formulate a probabilistic model that computes the probability of unevaluated configurations being collision-free. We update the model over time as more checks are performed. This model lets us define a weighting function for roadmap edges that is related to the probability of the edge being in collision. Our approach is to trade off between these two weights, gradually prioritizing edge length over collision likelihood. We also show that this tradeoff is approximately equivalent to minimizing the expected path length, with a penalty of being in collision. Our experiments demonstrate that POMP performs comparably with RRTConnect and LazyPRM for the first feasible path, and BIT* for anytime performance, both in terms of collision checks and total planning time.

BibTeX Reference
author = {Shushman Choudhury and Christopher Dellin and Siddhartha Srinivasa},
title = {Pareto-Optimal Search over Configuration Space Beliefs for Anytime Motion Planning},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2016},
month = {October},