Search
Close this search box.

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.

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
    The International Journal of Robotics Research, 35(5):501–513, 2016 [link][bibtex]
    In Algorithmic Foundations of Robotics XI, Volume 107 of STAR, pages 591–607, 2015 [link][bibtex]
    arXiv:1305.2889v3 [link][bibtex]

Contacts

Kiril Solovey
Dan Halperin
Oren Salzman 
@article{ssh-fnehd-16,
  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      = {The International Journal of Robotics Research},
  year         = {2016},
  volume       = {35},
  number       = {5},
  pages        = {501--513},
  doi          = {10.1177/0278364915615688}
}

@article{ssh-fnehd-13,
  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      = {CoRR},
  volume       = {abs/1305.2889},
  year         = {2013},
  url          = {http://arxiv.org/abs/1305.2889},
  eprinttype   = {arXiv},
  eprint       = {1305.2889},
  timestamp    = {Mon, 13 Aug 2018 16:47:28 +0200},
  biburl       = {https://dblp.org/rec/journals/corr/abs-1305-2889.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@incollection{ssh-fnehd-15,

  author = {Kiril Solovey and Oren Salzman and Dan Halperin},

  editor = {H. Levent Akin and Nancy M. Amato and Volkan Isler and A. Frank van der Stappen},

  title = {Finding a Needle in an Exponential Haystack: Discrete {RRT} for Exploration of Implicit Roadmaps in Multi-robot Motion Planning},

  bookTitle = {Algorithmic Foundations of Robotics XI},

  year = {2015},

  publisher = {Springer},

  pages = {591--607},

  doi = {10.1007/978-3-319-16595-0_34},

  series = {Springer Tracts in Advanced Robotics ({STAR})},

  volume = {107}

}

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content