Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard

Brocken, Thomas; van der Heijden, G. Wessel; Kostitsyna, Irina; Lo-Wong, Lloyd E.; Surtel, Remco J. A.

doi:10.4230/LIPIcs.FUN.2021.15

File

LIPIcs.FUN.2021.15.pdf

Filesize: 0.93 MB
16 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FUN.2021.15
URN: urn:nbn:de:0030-drops-127769

Author Details

Thomas Brocken

TU Eindhoven, The Netherlands

G. Wessel van der Heijden

TU Eindhoven, The Netherlands

Irina Kostitsyna

TU Eindhoven, The Netherlands

Lloyd E. Lo-Wong

TU Eindhoven, The Netherlands

Remco J. A. Surtel

TU Eindhoven, The Netherlands

Cite AsGet 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)

0

PDF Downloads

0

Metadata Views

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.