Efficient multi-robot motion planning for unlabeled discs in simple polygons (Extended abstract)

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

81 Citaten (Scopus)
1 Downloads (Pure)

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(mn+m^2)$ 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 multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard.
Originele taal-2Engels
TitelProceedings of the30th European Workshop on Computational Geometry (EuroCG 2014), Ein-Gedi, Israel, March 3-5, 2014)
Pagina's1-4
StatusGepubliceerd - 2014
Evenement30th European Workshop on Computational Geometry (EuroCG 2014) - Dead Sea, Israël
Duur: 3 mrt 20145 mrt 2014
Congresnummer: 30
https://www.cs.bgu.ac.il/~eurocg14/

Workshop

Workshop30th European Workshop on Computational Geometry (EuroCG 2014)
Verkorte titelEuroCG 2014
LandIsraël
StadDead Sea
Periode3/03/145/03/14
Ander30th European Workshop on Computational Geometry
Internet adres

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

Citeer dit