Search
Close this search box.

PSPACE-hardness of unlabeled motion planning and variants

An example of an AND gadget used for the construction of the proof.
An example of an AND gadget used for the construction of the proof. The green and purple squares represent interchangeable robots. Obstacles are illustrated by the gray areas. Additionally, we have a black bounding wall for the gadget, and a red-point obstacle. Robot A1 is considered to be outside the gadget, while robots A2, A3, are considered inside. Robot A1 can move inside the gadget (by moving a half-step down) if and only if A2 and A3 move outside

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

Links

  • Kiril Solovey and Dan Halperin
    PSPACE-hardness of unlabeled motion planning and variants
    In proceedings of Robotics: Science and Systems (RSS), 2014, best student paper [pdf][bibtex]

Contacts

Kiril Solovey
Dan Halperin
@article{article,
  author = {Kiril Solovey and Dan Halperin},
  year = {2014},
  title = {PSPACE-hardness of unlabeled motion planning and variants},
  booktitle = {Proceedings of Robotics: Science and Systems X}
}

Yair Oz - Webcreator

Contact

Skip to content