Motion planning in the presence of movable obstacles

ABSTRACT

Motion planning algorithms have generally dealt with motion in a static environment, or more recently, with motion in an environment that changes in a known manner. We consider the problem of finding collision-free motions in a changeable environment. That is, we wish to find a motion for an object where the object is permitted to move some of the obstacles. In such an environment the final positions of the movable obstacles may or may not be part of the goal. In the case where the final positions of the obstacles are unspecified, the motion planning problem is shown to be NP-hard. An algorithm that runs in &Ogr;(n2logn) time after &Ogr;(n3log2n) preprocessing time is presented when the object to be moved is polygonal and there is only one movable polygonal obstacle in a polygonal environment of complexity &Ogr;(n). In the case where the final positions of the obstacles are specified the general problem is shown to be PSPACE-hard and an algorithm is given when there is one movable obstacle with the same preprocessing time as the previous algorithm but with &Ogr;(n2) query time.

REFERENCES

• 1: Varol Akman, Unobstructed shortest paths in polyhedral environments, Springer-Verlag New York, Inc., New York, NY, 1986
• 2: Aronov, B., Fortune, S., and Wilfong, G. Minimum Speed Motions. 1987.
• 3: Canny, J. A New Algebraic Method for Robot Motion Planning and Real Geometry. In Proc. 28th IEEE FOCS, 1987, pp. 39-48.
• 4: Steven Fortune , Gordon Wilfong, Planning constrained motion, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.445-459, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62256]
• 5: Fortune, S., Wilfong, G., and Yap, C. Coordinated Motion of Two Robot Arms. In Proc. IEEE Int. Conf. Robotics and Automation, 1986, pp. 1216-1223..
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Hopcroft, J., Schwartz, J., and Sharir, M. On the Complexity of Motion Planning for Multiple independent Objects; PSPACE Hardness of the "warehouseman's problem". Int. J. Robotics Research 3, 4 (1984), 76-88.
• 8: K Kant , S W Zucker, Toward efficient trajectory planning: the path-velocity decomposition, International Journal of Robotics Research, v.5 n.3, p.72-89, Fall 1986 [doi>10.1177/027836498600500304]
• 9: K. Kedem , M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles, Proceedings of the first annual symposium on Computational geometry, p.75-80, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323244]
• 10: Kirkpatrick, D. Optimal Search in Planar Subdivisions. SIAM J. Comput. 12, 1 (1983), 28-35.
• 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: Lumelsky, V. and Stepanov, A. Path- Planning Strategies for a Point Mobile Automaton Moving Amidst Unknown Obstacles of Arbitrary Shape. Algorithmica 2, 4 (1987), 403-430.
• 13: O'Dunlaing, C. Motion Planning With Inertial Constraints. Algorithmica 2, 4 (1987), 431-475.
• 14: O'Dunlaing, C. and Yap, C. A "Retraction" Method for Planning the Motion of a Disc. J. of Algorithms 6 (1985), 104-111.
• 15: Reif, J. and Sharir, M. Motion Planning in the Presence of Moving Obstacles. In Proc. 25th IEEE FOCS, 1985, pp. 144- 154.
• 16: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 17: Schwartz, J. and Sharir, M. On the Piano Movers' Problem: II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds. Adv. Appl. Math. 4 (1983), 298-351.
• 18: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 19: Yap, C. Algorithmic Motion Planning. In Advances in Robotics, Volume 1: Algorithmic and Geometric Aspects, J. Schwartz and C. Yap, Eds. Lawrence Erlbaurn Assoc, Hillsdale NJ, 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  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
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Moments
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Geometric
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory