On the hardness of unlabeled multi-robot motion planning
This provides foundational hardness results for robotics planning, addressing a gap in theoretical understanding for interchangeable robots.
The paper tackled the problem of unlabeled multi-robot motion planning for unit-square robots in polygonal obstacles, proving it is PSPACE-hard and extending this result to three variants and the labeled case.
In unlabeled multi-robot motion planning several interchangeable robots operate in a common workspace. The goal is to move the robots to a set of target positions such that each position will be occupied by some robot. In this paper, we study this problem for the specific case of unit-square robots moving amidst polygonal obstacles and show that it is PSPACE-hard. We also consider three additional variants of this problem and show that they are all PSPACE-hard as well. To the best of our knowledge, this is the first hardness proof for the unlabeled case. Furthermore, our proofs can be used to show that the labeled variant (where each robot is assigned with a specific target position), again, for unit-square robots, is PSPACE-hard as well, which sets another precedence, as previous hardness results require the robots to be of different shapes.