Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning - Robotics Institute Carnegie Mellon University

Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning

Kiril Solovey, Oren Salzman, and Dan Halperin
Journal Article, International Journal of Robotics Research: Special Issue on WAFR '14, Vol. 35, No. 5, pp. 501 - 513, April, 2016

Abstract

We present a sampling-based framework for multi-robot motion planning. which combines an implicit representation of roadmaps for multi-robot motion planning 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 the tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios that involve as many as 60 degrees of freedom and on scenarios that require tight coordination between robots. On most of these scenarios our algorithm is faster by a factor of at least 10 when compared to existing algorithms that we are aware of.

Notes
http://journals.sagepub.com/doi/10.1177/0278364915615688

BibTeX

@article{Solovey-2016-5297,
author = {Kiril Solovey and Oren Salzman and Dan Halperin},
title = {Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning},
journal = {International Journal of Robotics Research: Special Issue on WAFR '14},
year = {2016},
month = {April},
volume = {35},
number = {5},
pages = {501 - 513},
}