Blog
About

  • Record: found
  • Abstract: found
  • Article: found
Is Open Access

PSPACE-hardness of unlabeled motion planning and variants

Preprint

Read this article at

Bookmark
      There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

      Abstract

      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.

      Related collections

      Most cited references 13

      • Record: found
      • Abstract: not found
      • Article: not found

      On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- Hardness of the "Warehouseman's Problem"

        Bookmark
        • Record: found
        • Abstract: not found
        • Article: not found

        PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

          Bookmark
          • Record: found
          • Abstract: not found
          • Article: not found

          On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers

            Bookmark

            Author and article information

            Journal
            1408.2260

            Theoretical computer science, Robotics

            Comments

            Comment on this article