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

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.