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
Carnegie Mellon University, Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 591-607, April, 2015

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

BibTeX Reference
@conference{Solovey-2015-5939,
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 = {Workshop on the Algorithmic Foundations of Robotics (WAFR)},
school = {Robotics Institute , Carnegie Mellon University},
month = {April},
year = {2015},
pages = {591-607},
address = {Pittsburgh, PA},
}
2017-09-13T10:38:44+00:00