154
views
0
recommends
+1 Recommend
0 collections
    4
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      PSPACE-hardness of unlabeled motion planning and variants

      Preprint

      Read this article at

          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 references13

          • 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
                Theoretical computer science, Robotics

                Comments

                Comment on this article