On the complexity of reachability and motion planning questions (extended abstract)

ABSTRACT

In this paper we consider from a theoretical viewpoint the complexity of some reachability and motion planning questions. Specifically, we are interested in determining which generalizations of the basic mover's problem result in computationally intractable problems. It has been shown that for any set of motion-planning problems with bounded degree of freedom, there is a polynomial-time algorithm to solve the motion-planning problem (although the degree of the polynomial may be large), but the two most basic generalizations to the problem, multiple movable obstacles and conformable objects, result in much harder problems. It has been shown that the warehouseman's problem is P-space hard: in this paper we show that the reachability problem for one of the simplest types of conformable objects, a two-dimensional linear (“robot arm”) linkage, is P-space complete. In addition, we demonstrate some motion-planning problems that take exponential time.

REFERENCES

• 1: 1. Howden, W. E., "The Sofa Problem," Comput J. 11 pp. 299- 301 (1968).
• 2: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 3: 3. Reif, J. H., "Complexity of the Mover's Problem and Generalizations (Extended Abstract)." Proc. 20th IEEE FOCS. pp. 421- 427 (1979).
• 4: 4. Brooks, R. A., "Planning collision-free motion for pick-and place operations." The International Journal of Research 2(4) (1983).
• 5: 5. Schwartz, J. T. and M. Sharir. "On the 'Piano Movers' Problem - II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds," Advances in Applied Math. 4 pp. 298-351 (1983).
• 6: 6. Hopcroft, J. E., J. T. Schwartz. and M. Sharir. "On the complexity of motion planning for multiple independent objects: Pspace hardness of the "Warehouseman's problem"," Preprint (1983).
• 7: 7. Hopcroft, J. E., D. A. Joseph. and S. H. Whitesides. "On the movement of robot arms in 2-dimensional bounded regions." Siam J. Comput. 14(2)(May, 1985).
• 8: John Hopcroft , Deborah Joseph , Sue Whitesides, Movement problems for 2-dimensional linkages, SIAM Journal on Computing, v.13 n.3, p.610-629, August 1984 [doi>10.1137/0213038]
• 9: 9. Karp. R. M., "Reducibility among combinatorial problems." pp. 85-103 in Complexity of Computer Computations. ed. R. Miller, J. Thatcher. Plenum Press. New York (1972).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Motion

General Terms:
Design, Measurement, Performance, Theory