Motion planning in the presence of moving obstacles

ABSTRACT

This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental importance to robotics, but their computational complexity has not previously been investigated. We provide evidence that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In particular, we prove the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP-hard even if B has no velocity modulus bound, where, in both cases, B has 6 degrees of freedom. To prove these results, we use a unique method of simulation of a Turing machine that uses time to encode configurations (whereas previous lower bound proofs in robotic motion planning used the system position to encode configurations and so required unbounded number of degrees of freedom). We also investigate a natural class of dynamic problems that we call asteroid avoidance problems: B, the object we wish to move, is a convex polyhedron that is free to move by translation with bounded velocity modulus, and the polyhedral obstacles have known translational trajectories but cannot rotate. This problem has many applications to robot, automobile, and aircraft collision avoidance. Our main positive results are polynomial time algorithms for the 2-D asteroid avoidance problem, where B is a moving polygon and we assume a constant number of obstacles, as well as single exponential time or polynomial space algorithms for the 3-D asteroid avoidance problem, where B is a convex polyhedron and there are arbitrarily many obstacles. Our techniques for solving these asteroid avoidance problems use “normal path” arguments, which are an intereting generalization of techniques previously used to solve static shortest path problems. We also give some additional positive results for various other dynamic movers problems, and in particular give polynomial time algorithms for the case in which B has no velocity bounds and the movements of obstacles are algebraic in space-time.

REFERENCES

• 1: Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
• 2: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 3: ~ANNY, J., AND REIF, J. 1987. New lower bound techniques for robot motion planning problems. ~In Proceedings of the 28th IEEE S vmposmm on Foundaaons of Computer Science. IEEE, New ~York, pp. 49-60.
• 4: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 5: ~COOKE, G. E., AND FINNEY, R. R. L. 1967. Homology of Cell Complexes. Mathematical Notes, ~Princeton University Press, Princeton, N.J.
• 6: 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]
• 7: ~HOPCROFT, J., JOSEPH, D., AND WHITESIDES, S. 1985. On the movement of robot arm in ~2-dimensional bounded regions. SIAM J. Comput. 14, 315-333.
• 8: ~HOPCROFF, J. E., SCHWARTZ, J. T., AND SHARIR, M. 1984b. On the complexity of motion ~planning for multiple independent objects; PSPACE-hardness of the "Warehouseman's Prob- ~lem.'' hzt..1. Rob. Res. 3, 4, 76-88.
• 9: Jacob T. Schwartz , Micha Sharir , John E. Hopcroft, Planning, geometry, and complexity of robot motion, Ablex Publishing Corp., Norwood, NJ, 1986
• 10: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 11: 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]
• 12: Colm ó'Dúnlaing , Micha Sharir , Chee K. Yap, Retraction: A new approach to motion-planning, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.207-220, December 1983 [doi>10.1145/800061.808750]
• 13: ~O'DONLAING, C., AND YAP, C. K. 1985. A "retraction" method for planning the motion of a disc. ~J. Algorithms 6, 104 111.
• 14: ~R~,rF, J., 1979. Complexity of the mover's problem and generalizations. In Proceedings of the 20th ~1EEE Symposmm on Foundattons o) Computer Science (Puerto Rico, Oct.). IEEE, New York, ~pp. 421 427. (Also in Plannbzg, Geometry, and ComplexiO' of Robot Motion, J. Hopcroft, J. ~Schwartz, M. Sharir, eds, Ablex Pub. Co., Norwood, N.J. 1987, pp. 267-2813
• 15: ~REIF, J. H., AND SHARm, M. 1985. Motion planning in the presence of moving obstacles. In ~Proceedings o{' the 26th IEEE ~vmpostum on Foundations of Compt~ter Sctence. IEEE, New York, ~pp. 144-154.
• 16: ~REIF, J. H., AND STORER, J. A. 1985. Shortest paths in Euclidean space with polyhedral ~obstacles. Tech. Rep. TR-05-85. Alken Computation Lab, Harvard Umversity, Cambridge, ~Mass, Apr. 1985.
• 17: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
• 18: ~SCHWARTZ, J. T., AND SHAreR, M. 1983a. On the "Piano Movers" problem. I. The case of a ~two-dimensional rigid polygonal body moving amidst polygonal barriers. Comm. Pure Appl ~Math. 36, 345 398.
• 19: ~SCHWARTZ, J. T., AND SHAreR, M. 1983b On the "Piano Movers" problem. 11. General ~techniques for computing topological properties of real algebraic manifolds. Adu. Appl. Math. ~4, 298-351.
• 20: ~SCHWARTZ, J. T., AND SIIARIR, M. 1983c. On the "Piano Movers" problem. III. Coordinating the ~motion of several indepcndcnt bo&es: The special case of circular bodms moving amidst ~polygonal barriers. Int. J. Rob. Res. 2, 3, 46 75.
• 21: ~SCHWARTZ, J. T., AND SIIARIR, M. 1984. On the "Pmno Movers" problem. V. The case of a rod ~mowng m 3-D space amidst polyhedral obstacles. Comm. Pure Appl. Math. 37, 817-846.
• 22: Micha Sharir, Algorithmic Motion Planning in Robotics, Computer, v.22 n.3, p.9-20, March 1989 [doi>10.1109/2.16221]
• 23: K. Sutner , W. Maass, Motion planning among time dependent obstacles, Acta Informatica, v.26 n.1-2, p.93-122, Oct. 1988 [doi>10.1007/BF02915447]

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
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory

Keywords:
Turing machines, computational geometry, cylindrical algebraic decomposition, decision procedures, motion planning, moving obstacles, theory of reals