TY - GEN
T1 - Multi-robot motion planning of k-colored discs is PSPACE-hard
AU - Brocken, Thomas
AU - van der Heijden, G. Wessel
AU - Kostitsyna, Irina
AU - Lo-Wong, Lloyd E.
AU - Surtel, Remco J.A.
PY - 2020/9/1
Y1 - 2020/9/1
N2 - 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.
AB - 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.
KW - Algorithmic complexity
KW - Disc-robot motion planning
KW - PSPACE-hard
UR - http://www.scopus.com/inward/record.url?scp=85091416290&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FUN.2021.15
DO - 10.4230/LIPIcs.FUN.2021.15
M3 - Conference contribution
AN - SCOPUS:85091416290
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 10th International Conference on Fun with Algorithms, FUN 2021
A2 - Farach-Colton, Martin
A2 - Prencipe, Giuseppe
A2 - Uehara, Ryuhei
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 10th International Conference on Fun with Algorithms, FUN 2021
Y2 - 30 May 2021 through 1 June 2021
ER -