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

Abstract

Coordinated motion planning for a large number af three-di mensional objects in the presence of obstacles is a computa tional problem whose complexity is important to calibrate. In this paper we show that even the restricted two-dimensional problem for arbitrarily many rectangles in a rectangular region is PSPACE-hard. This result should be viewed as a guide to the difficulty, of the general problem and should lead researchers to consider more tractable restricted classes of motion problems of practical interest.

Get full access to this article

View all access options for this article.

References

Garey, M.R. , and Johnson, D.S. 1979, Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman.

Hopcroft, J. , Joseph, D. , and Whitesides, S. 1982. Movement problems for 2-dimensional linkages. Tech. Rept. 82-575. Ithaca, N.Y.: Cornell University Computer Science Department. To be reprinted in SIAM J. Computing

Hopcroft, J. , and Ullman, J. 1979. Introduction to automata theory, languages, and computations . Reading, Mass.: Addison-Weslev .

Hopcroft, J. and Wilfong, G. 1984. Reducing multiple object motion planning to graph searching. Tech. Rept. 84-616. Ithaca, N.Y.: Cornell University Computer Science Department.

Reif, J. 1979. Complexity of the movers' problem and generalizations. Proc. 20th IEEE Conf on Foundations of Comp. Sci. Long Beach, Calif.: IEEE Computer Society, pp. 421-427.

Schwartz, J.T. , and Sharir, M. 1983a. On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., vol. 4, pp. 298 -351.

Schwartz, J.T. , and Sharir, M. 1983b. On the piano movers' problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers. Int. J. Robotics Res. 2(3):46-75.

Sharir, M. , and Schorr, A. 1984. On shortest paths in polyhedral spaces. Proc. 16th ACM Symp. Theory of Computing. New York: Association for Computing Machinery, pp. 144-153.