Title | ||
---|---|---|
Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-robot Motion Planning. |
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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-319-16595-0_34 | ALGORITHMIC FOUNDATIONS OF ROBOTICS XI |
Keywords | DocType | Volume |
Multi-robot motion planning,sampling-based motion planning | Journal | 107 |
Issue | ISSN | Citations |
5 | 1610-7438 | 7 |
PageRank | References | Authors |
0.59 | 17 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kiril Solovey | 1 | 71 | 10.30 |
Oren Salzman | 2 | 61 | 15.27 |
Dan Halperin | 3 | 1291 | 105.20 |