Motion planning for unlabeled discs with optimality guarantees

Kiril Solovey, Jingjin Yu, Or Zamir, Dan Halperin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations


We study the problem of path planning for unlabeled (indistinguishable) unit-disc robots in a planar environment cluttered with polygonal obstacles. We introduce an algorithm which minimizes the total path length, i.e., the sum of lengths of the individual paths. Our algorithm is guaranteed to find a solution if one exists, or report that none exists otherwise. It runs in time Õ(m4 + m2n2), where m is the number of robots and n is the total complexity of the workspace. Moreover, the total length of the returned solution is at most OPT+4m, where OPT is the optimal solution cost. To the best of our knowledge this is the first algorithm for the problem that has such guarantees. The algorithm has been implemented in an exact manner and we present experimental results that attest to its efficiency.

Original languageEnglish (US)
Title of host publicationRobotics
Subtitle of host publicationScience and Systems XI, RSS 2015
EditorsJonas Buchli, David Hsu, Lydia E. Kavraki
PublisherMIT Press Journals
ISBN (Electronic)9780992374716
StatePublished - 2015
Externally publishedYes
Event2015 Robotics: Science and Systems Conference, RSS 2015 - Rome, Italy
Duration: Jul 13 2015Jul 17 2015

Publication series

NameRobotics: Science and Systems


Other2015 Robotics: Science and Systems Conference, RSS 2015

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Control and Systems Engineering


Dive into the research topics of 'Motion planning for unlabeled discs with optimality guarantees'. Together they form a unique fingerprint.

Cite this