Motion planning amidst fat obstacles (extended abstract)

ABSTRACT

We present an efficient and simple paradigm for motion planning amidst fat obstacles. The paradigm fits in the cell decomposition approach to motion planning and exploits workspace properties that follow from the fatness of the obstacles. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same (expectedly small) size. The approach applies to robots with any fixed number of degrees of freedom and turns out to be successful in many cases: it leads to nearly optimal O(nlogn) algorithms for motion planning in 2D, and for motion planning in 3D amidst obstacles of comparable size. In addition, we obtain algorithms for planning 3D motions among polyhedral obstacles, running in O(n2logn) time, and among arbitrary obstacles, running in time O(n3).

REFERENCES

• 1: H. ALT, R. FLEISCHER, M. KAUFMANN, K. MEHLHORN, S, N)~HER, S. SCHIRRA, AND C. UHRIG, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, Algorithmica 8 (1992), pp. 391-406.
• 2: Francis Avnaim , Jean-Daniel Boissonnat , Bernard Faverjon, A practical exact motion planning algorithm for polygonal object amidst polygonal obstacles, Proceedings of the Workshop on Geometry and Robotics, p.67-86, May 26-28, 1988
• 3: J.L. BENTLEY AND T.A. OTFMAN, Algorithms for reporting and counting geometric intersections, IEEE Transactions on Computers 28 (1979), pp. 643-647.
• 4: Marc de Berg , Leonidas J. Guibas , Dan Halperin, Vertical decompositions for triangles in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.1-10, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177427]
• 5: Jiří Matoušek , Nathaly Miller , Micha Sharir , Shmuel Sifrony , János Pach , Emo Welzl, Fat triangles determine linearly many holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.49-58, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185347]
• 6: Mark H. Overmars, Point location in fat subdivisions, Information Processing Letters, v.44 n.5, p.261-265, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90211-D]
• 7: J.T. SCHWARTZ AND M. SHARIR, On the piano movers' problem i. The case of a two-dimensional rigid polygonal body moving amidst polygonal boundaries, Comm. Pure Appl. Math. 36 (1983), pp. 345-398.
• 8: J.T. SCHWARTZ AND M. SHARIR, On the piano movers' problem II. General techniques for computing topological properties of real algebraic manifolds, Adv. in Applied Mathematics 4 (1983), pp. 298-351.
• 9: J.T. SCHWARTZ AND M. SHARIR, Efficient motion planning algorithms in environments of bounded local complexity, Report 164, Department of Computer Science, Courant Inst. Math. Sci., New York NY (1985).
• 10: S. SIFRONY AND M. SHARIR, A new efficient motion planning algorithm for a rod in two-dimensional polygonal space, Algorithmica 2 (i987), pp. 367-402.
• 11: A. Frank van der Stappen , Dan Halperin , Mark H. Overmars, The complexity of the free space for a robot moving amidst fat obstacles, Computational Geometry: Theory and Applications, v.3 n.6, p.353-373, Dec. 1993 [doi>10.1016/0925-7721(93)90007-S]
• 12: A.E VAN DER $TAPPEN, The complexity of the free space for motion planning amidst fat obstacles, Journal oflntelligent & Robotic Systems, in press.
• 13: A.F. VAN DER STAPPEN, D. HALPERIN, AND M.H. OVERMARS, Efficient algorithms for exact motion planning amidst fat obstacles, Proc. of the IEEE Int. Conf. on Robotics and Automation, Atlanta GA (1993), Vol. 1, pp. 29%304.
• 14: A.E VAN DER STAPPEN AND M.H. OVERMARS, Motion planning amidst fat obstacles, in preparation.

INDEX TERMS

Primary 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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification