An effective algorithmic framework for near optimal multi-robot path planning

Jingjin Yu, Daniela Rus

Research output: Chapter in Book/Report/Conference proceedingChapter

20 Scopus citations


We present a centralized algorithmic framework for solving multi-robot path planning problems in general, two-dimensional, continuous environments while minimizing globally the task completion time. The framework obtains high levels of effectiveness through the composition of an optimal discretization of the continuous environment and the subsequent fast, near-optimal resolution of the resulting discrete planning problem. This principled approach achieves orders of magnitudes better performance with respect to both speed and the supported robot density. For a wide variety of environments, our method is shown to compute globally near-optimal solutions for 50 robots in seconds with robots packed close to each other. In the extreme, the method can consistently solve problems with hundreds of robots that occupy over 30% of the free space.

Original languageEnglish (US)
Title of host publicationSpringer Proceedings in Advanced Robotics
PublisherSpringer Science and Business Media B.V.
Number of pages17
StatePublished - 2018

Publication series

NameSpringer Proceedings in Advanced Robotics
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Mechanical Engineering
  • Engineering (miscellaneous)
  • Artificial Intelligence
  • Computer Science Applications
  • Applied Mathematics


  • Continuous Environment
  • Discrete Plane
  • Multi-robot Path Planning
  • Robot Density
  • Task Completion Time


Dive into the research topics of 'An effective algorithmic framework for near optimal multi-robot path planning'. Together they form a unique fingerprint.

Cite this