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

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
The International Journal of Robotics Research (IJRR), Vol. 35, No. 5, pp. 501-513, January, 2016

Download Publication (PDF)

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 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.

BibTeX Reference
@article{Solovey-2016-5297,
title = {Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning},
author = {Kiril Solovey and Oren Salzman and Dan Halperin},
booktitle = {The International Journal of Robotics Research (IJRR)},
notes = {http://journals.sagepub.com/doi/10.1177/0278364915615688},
month = {January},
year = {2016},
volume = {35},
number = {5},
pages = {501-513},
}
2017-09-13T10:38:31+00:00