Carnegie Mellon University
The
Pareto-Optimal Search over Configuration Space Beliefs for Anytime Motion Planning

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


Download
  • Adobe portable document format (pdf) (4MB)
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.

Abstract
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.

Keywords
Motion Planning

Notes
Sponsor: National Science Foundation IIS (1409003), Toyota Motor Engineering and Manufacturing (TEMA) and the Office of Naval Research
Associated Center(s) / Consortia: Quality of Life Technology Center, National Robotics Engineering Center, Center for the Foundations of Robotics, and Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Rapid Manufacturing Lab and Personal Robotics
Associated Project(s): Motion Planner

Text Reference
Shushman Choudhury, Christopher Dellin, and Siddhartha Srinivasa, "Pareto-Optimal Search over Configuration Space Beliefs for Anytime Motion Planning," IEEE/RSJ International Conference on Intelligent Robots and Systems, October, 2016.

BibTeX Reference
@inproceedings{Choudhury_2016_8189,
   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",
   month = "October",
   year = "2016",
}