Efficient multi-robot motion planning for unlabeled discs in simple polygons

A. Adler, M.T. de Berg, D. Halperin, K. Solovey

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)

Abstract

We consider the following motion-planning problem: we are given m unit discs in a simple polygon with n vertices, each at their own start position, and we want to move the discs to a given set of m target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in O (n log n + mn + m2) time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multirobot motion planning problem for discs moving in a simple polygon, which is known to be strongly np-hard.

Original languageEnglish
Title of host publicationAlgorithmic Foundations of Robotics XI
Subtitle of host publicationed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics
EditorsH. Levent Atkin, N.M. Amato, V. Isler, A.F. van der Stappen
Place of PublicationDordrecht
PublisherSpringer
Pages1-17
Number of pages17
ISBN (Electronic)978-3-319-16595-0
ISBN (Print)978-3-319-16594-3
DOIs
Publication statusPublished - 2015
Event11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey - Boğaziçi University, Istanbul, Turkey
Duration: 3 Aug 20145 Aug 2014
http://robot.cmpe.boun.edu.tr/wafr2014/

Publication series

NameSpringer Tracts in Advanced Robotics
Volume107
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Conference

Conference11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey
Abbreviated titleWAFR 2014
CountryTurkey
CityIstanbul
Period3/08/145/08/14
Internet address

Fingerprint Dive into the research topics of 'Efficient multi-robot motion planning for unlabeled discs in simple polygons'. Together they form a unique fingerprint.

Cite this