Personal tools
You are here: Home Projects drrt
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930
Log in


Forgot your password?
 

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 incorporates an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs. 

Our pathfinding algorithm, discrete-RRT (dRRT), is an adaption of the celebrated RRT algorithm, for the discrete case of a graph. By rapidly exploring the high-dimensional configuration space represented by the implicit roadmap, dRRT is able to reach subproblems where minimal coordination between the robots is required. Integrating the implicit representation of the roadmap, the dRRT algorithm, and techniques that are tailored for such subproblems on the implicit roadmap allows us to solve multi-robot problems while exploring only a small portion of the configuration space. 

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.

scenarios

3D scenarios that were used in experiments.

Links
  • Kiril Solovey*, Oren Salzman* and Dan Halperin (*equal contribution)
    Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-Robot Motion Planning
    In Workshop on the Algorithmic Foundations of Robotics (WAFR)2014 [link].

Contacts

Kiril Solovey home icon contact
Oren Salzman http://acg.cs.tau.ac.il/danhalperin contact
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Document Actions