LIPIcs.FUN.2021.15.pdf
- Filesize: 0.93 MB
- 16 pages
Document
Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard
Authors
-
Part of:
Volume:
10th International Conference on Fun with Algorithms (FUN 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-09-16
Cite As Get BibTex
Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, and Remco J. A. Surtel. Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FUN.2021.15
Abstract
In the problem of multi-robot motion planning, a group of robots, placed in a polygonal domain with obstacles, must be moved from their starting positions to a set of target positions. We consider the specific case of unlabeled disc robots of two different sizes. That is, within one class of robots, where a class is given by the robots' size, any robot can be moved to any of the corresponding target positions. We prove that the decision problem of whether there exists a schedule moving the robots to the target positions is PSPACE-hard.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Disc-robot motion planning
- algorithmic complexity
- PSPACE-hard
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Aviv Adler, Mark de Berg, Dan Halperin, and Kiril Solovey. Efficient multi-robot motion planning for unlabeled discs in simple polygons. IEEE Transactions on Automation Science and Engineering, 12(4):1309-1317, 2015. URL: https://doi.org/10.1109/TASE.2015.2470096.
- Tiziana Calamoneri and Rossella Petreschi. An efficient orthogonal grid drawing algorithm for cubic graphs. In International Computing and Combinatorics Conference (COCOON), LNCS, volume 959, pages 31-40. 1995. URL: https://doi.org/10.1007/BFb0030817.
- Gary W. Flake and Eric B. Baum. Rush Hour is PSPACE-complete, or "Why you should generously tip parking lot attendants". Theoretical Computer Science, 270(1-2):895-911, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00173-6.
-
Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, 2005.
-
John E. Hopcroft, Jacob T. Schwartz, and Micha Sharir. On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the "Warehouseman’s Problem". The International Journal of Robotics Research, 3(4):76-88, 1984.
- Kiril Solovey and Dan Halperin. k-Color multi-robot motion planning. The International Journal of Robotics Research, 33(1):82-97, 2014. URL: https://doi.org/10.1177/0278364913506268.
-
Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. The International Journal of Robotics Research, 35(14):1750-1759, 2016.
- Kiril Solovey, Jingjin Yu, Or Zamir, and Dan Halperin. Motion planning for unlabeled discs with optimality guarantees. In Robotics: Science and Systems XI. Robotics: Science and Systems Foundation, 2015. URL: https://doi.org/10.15607/RSS.2015.XI.011.
-
Paul Spirakis and Chee K. Yap. Strong NP-hardness of moving many discs. Information Processing Letters, 19(1):55-59, 1984.
- John Tromp and Rudi Cilibrasi. Limits of rush hour logic complexity. Manuscript, 2005. URL: http://arxiv.org/abs/cs/0502068.