Close this search box.

Scalable Asymptotically-Optimal Multi-Robot Motion Planning


Scalable Asymptotically-Optimal Multi-Robot Motion Planning
Simultaneous planning for multiple high-dimensional systems is a difficult, motivating challenge for this work

Finding asymptotically-optimal paths in multi-robot motion planning problems could be achieved, in principle, using sampling-based planners in the composite configuration space of all of the robots in the space. The dimensionality of this space increases with the number of robots, rendering this approach impractical. This work focuses on a scalable sampling-based planner for coupled multi-robot problems that provides asymptotic optimality. It extends the dRRT approach, which proposed building roadmaps for each robot and searching an implicit roadmap in the composite configuration space. This work presents a new method, dRRT* , and develops theory for scalable convergence to optimal paths in multi-robot problems. Simulated experiments indicate dRRT* converges to high-quality paths while scaling to higher numbers of robots where the naive approach fails. Furthermore, dRRT* is applicable to high-dimensional problems, such as planning for robot

Links & Awards

  • Andrew Dobson, Kiril Solovey, Rahul Shome, Dan Halperin, and Kostas E. Bekris
    Scalable Asymptotically-Optimal Multi-Robot Motion Planning
    In International Symposiun on MULTI-ROBOT and MULTI-AGENT SYSTEMS (MRS), 2017 [link][bibtex]
    Arxiv [link][bibtex]
  • Award


Dan Halperin
Kiril Solovey
Andrew Dobson
Rahul Shome
Kostas E. Bekris

Yair Oz - Webcreator


Skip to content