Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning
This work addresses the problem of efficient motion planning for multi-robot systems, offering a significant performance improvement over prior methods.
The paper tackles multi-robot motion planning by introducing a sampling-based framework that combines an implicit roadmap representation with a novel pathfinding algorithm called discrete-RRT (dRRT), resulting in a speedup of at least ten times faster than existing algorithms in scenarios with up to 60 degrees of freedom.
We present a sampling-based framework for multi-robot motion planning which combines an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of a tensor product of roadmaps for the individual robots. 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.