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

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

doi:10.1007/978-3-319-16595-0_1

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

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

Algorithms, Geometry and Applications

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

18 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 + m²) 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 language	English
Title of host publication	Algorithmic Foundations of Robotics XI
Subtitle of host publication	ed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics
Editors	H. Levent Atkin, N.M. Amato, V. Isler, A.F. van der Stappen
Place of Publication	Dordrecht
Publisher	Springer
Pages	1-17
Number of pages	17
ISBN (Electronic)	978-3-319-16595-0
ISBN (Print)	978-3-319-16594-3
DOIs	https://doi.org/10.1007/978-3-319-16595-0_1
Publication status	Published - 2015
Event	11th 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 2014 → 5 Aug 2014 http://robot.cmpe.boun.edu.tr/wafr2014/

Publication series

Name	Springer Tracts in Advanced Robotics
Volume	107
ISSN (Print)	1610-7438
ISSN (Electronic)	1610-742X

Conference

Conference	11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey
Abbreviated title	WAFR 2014
Country/Territory	Turkey
City	Istanbul
Period	3/08/14 → 5/08/14
Internet address	http://robot.cmpe.boun.edu.tr/wafr2014/

Access to Document

10.1007/978-3-319-16595-0_1

Cite this

Adler, A., de Berg, M. T., Halperin, D., & Solovey, K. (2015). Efficient multi-robot motion planning for unlabeled discs in simple polygons. In H. Levent Atkin, N. M. Amato, V. Isler, & A. F. van der Stappen (Eds.), Algorithmic Foundations of Robotics XI: ed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics (pp. 1-17). (Springer Tracts in Advanced Robotics; Vol. 107). Springer. https://doi.org/10.1007/978-3-319-16595-0_1

Adler, A. ; de Berg, M.T. ; Halperin, D. et al. / Efficient multi-robot motion planning for unlabeled discs in simple polygons. Algorithmic Foundations of Robotics XI: ed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics. editor / H. Levent Atkin ; N.M. Amato ; V. Isler ; A.F. van der Stappen. Dordrecht : Springer, 2015. pp. 1-17 (Springer Tracts in Advanced Robotics).

@inproceedings{c7963394451345f4ad2c9c66ab8beb5e,

title = "Efficient multi-robot motion planning for unlabeled discs in simple polygons",

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.",

author = "A. Adler and {de Berg}, M.T. and D. Halperin and K. Solovey",

year = "2015",

doi = "10.1007/978-3-319-16595-0_1",

language = "English",

isbn = "978-3-319-16594-3",

series = "Springer Tracts in Advanced Robotics",

publisher = "Springer",

pages = "1--17",

editor = "{Levent Atkin}, H. and N.M. Amato and V. Isler and {van der Stappen}, A.F.",

booktitle = "Algorithmic Foundations of Robotics XI",

address = "Germany",

note = "11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey, WAFR 2014 ; Conference date: 03-08-2014 Through 05-08-2014",

url = "http://robot.cmpe.boun.edu.tr/wafr2014/",

}

Adler, A, de Berg, MT, Halperin, D & Solovey, K 2015, Efficient multi-robot motion planning for unlabeled discs in simple polygons. in H Levent Atkin, NM Amato, V Isler & AF van der Stappen (eds), Algorithmic Foundations of Robotics XI: ed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics. Springer Tracts in Advanced Robotics, vol. 107, Springer, Dordrecht, pp. 1-17, 11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey, Istanbul, Turkey, 3/08/14. https://doi.org/10.1007/978-3-319-16595-0_1

Efficient multi-robot motion planning for unlabeled discs in simple polygons. / Adler, A.; de Berg, M.T.; Halperin, D. et al.
Algorithmic Foundations of Robotics XI: ed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics. ed. / H. Levent Atkin; N.M. Amato; V. Isler; A.F. van der Stappen. Dordrecht: Springer, 2015. p. 1-17 (Springer Tracts in Advanced Robotics; Vol. 107).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Adler, A.

AU - de Berg, M.T.

AU - Halperin, D.

AU - Solovey, K.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84946051757&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-16595-0_1

DO - 10.1007/978-3-319-16595-0_1

M3 - Conference contribution

AN - SCOPUS:84946051757

SN - 978-3-319-16594-3

T3 - Springer Tracts in Advanced Robotics

SP - 1

EP - 17

BT - Algorithmic Foundations of Robotics XI

A2 - Levent Atkin, H.

A2 - Amato, N.M.

A2 - Isler, V.

A2 - van der Stappen, A.F.

PB - Springer

CY - Dordrecht

T2 - 11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey

Y2 - 3 August 2014 through 5 August 2014

ER -

Adler A, de Berg MT, Halperin D, Solovey K. Efficient multi-robot motion planning for unlabeled discs in simple polygons. In Levent Atkin H, Amato NM, Isler V, van der Stappen AF, editors, Algorithmic Foundations of Robotics XI: ed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics. Dordrecht: Springer. 2015. p. 1-17. (Springer Tracts in Advanced Robotics). doi: 10.1007/978-3-319-16595-0_1

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this