Carnegie Mellon University
The
A General Technique for Fast Comprehensive Multi-Root Planning on Graphs by Coloring Vertices and Deferring Edges

Christopher Dellin and Siddhartha Srinivasa
2015 IEEE International Conference on Robotics and Automation (ICRA), May, 2015.


Download
  • Adobe portable document format (pdf) (805KB)
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 formulate and study the comprehensive multi-root (CMR) planning problem, in which feasible paths are desired between multiple regions. We propose two primary contributions which allow us to extend state- of-the-art sampling-based planners. First, we propose the notion of vertex coloring as a compact representation of the CMR objective on graphs. Second, we propose a method for deferring edge evaluations which do not advance our objective, by way of a simple criterion over these vertex colorings. The resulting approach can be applied to any CMR-agnostic graph-based planner which evaluates a sequence of edges. We prove that the theoretical performance of the colored algorithm is always strictly better than (or equal to) that of the corresponding uncolored version. We then apply the approach to the Probabalistic RoadMap (PRM) algorithm; the resulting Colored Probabalistic RoadMap (cPRM) is illustrated on 2D and 7D CMR problems.

Notes
Associated Center(s) / Consortia: Quality of Life Technology Center, National Robotics Engineering Center, and Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Personal Robotics

Text Reference
Christopher Dellin and Siddhartha Srinivasa, "A General Technique for Fast Comprehensive Multi-Root Planning on Graphs by Coloring Vertices and Deferring Edges," 2015 IEEE International Conference on Robotics and Automation (ICRA), May, 2015.

BibTeX Reference
@inproceedings{Dellin_2015_7845,
   author = "Christopher Dellin and Siddhartha Srinivasa",
   title = "A General Technique for Fast Comprehensive Multi-Root Planning on Graphs by Coloring Vertices and Deferring Edges",
   booktitle = "2015 IEEE International Conference on Robotics and Automation (ICRA)",
   month = "May",
   year = "2015",
}