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

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

11 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
TitelAlgorithmic Foundations of Robotics XI
Subtiteled Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics
RedacteurenH. Levent Atkin, N.M. Amato, V. Isler, A.F. van der Stappen
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's1-17
Aantal pagina's17
ISBN van elektronische versie978-3-319-16595-0
ISBN van geprinte versie978-3-319-16594-3
DOI's
StatusGepubliceerd - 2015
Evenement11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey - Boğaziçi University, Istanbul, Turkije
Duur: 3 aug 20145 aug 2014
http://robot.cmpe.boun.edu.tr/wafr2014/

Publicatie series

NaamSpringer Tracts in Advanced Robotics
Volume107
ISSN van geprinte versie1610-7438
ISSN van elektronische versie1610-742X

Congres

Congres11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey
Verkorte titelWAFR 2014
LandTurkije
StadIstanbul
Periode3/08/145/08/14
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Efficient multi-robot motion planning for unlabeled discs in simple polygons'. Samen vormen ze een unieke vingerafdruk.

Citeer dit