We present a sampling-based framework for multi-robot motion planning which incorporates an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs.
Our pathfinding algorithm, discrete-RRT (dRRT), is an adaption of the celebrated RRT algorithm, for the discrete case of a graph. By rapidly exploring the high-dimensional configuration space represented by the implicit roadmap, dRRT is able to reach subproblems where minimal coordination between the robots is required. Integrating the implicit representation of the roadmap, the dRRT algorithm, and techniques that are tailored for such subproblems on the implicit roadmap allows us to solve multi-robot problems while exploring only a small portion of the configuration space.
We demonstrate our approach experimentally on scenarios of up to 60 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.
