Efficient motion planning for an L-shaped object

ABSTRACT

We present an algorithm that solves the following motion-planning problem. Given an L-shaped body L and a 2-dimensional region with n point obstacles, decide whether there is a continuous motion connecting two given positions and orientations of L during which L avoids collision with the obstacles. The algorithm requires &Ogr;(n2 log2 n) time and &Ogr;(n2) storage. The algorithm is a variant of the cell-decomposition technique of the configuration space ([SS, LS]) but it employs a new and efficient technique for obtaining a compact representation of the free space, which results in a saving of an order of magnitude. The approach used in our algorithm seems applicable to motion-planning of certain robotic arms whose spaces of free placements have a structure similar to that of the L-shaped body.

REFERENCES

• ABF: F. Avnaim, J. D. Boissonnat and B. Faverjon, A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles, Preprint, 1988.
• AS: B. Aronov , M. Sharir, Triangles in space or building (and analyzing) castles in the Air, Proceedings of the fourth annual symposium on Computational geometry, p.381-391, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73432]
• AO: B. Aronov and C. b'D&rlaing, Analysis of the motionplanning problem for a simple two-link planar arm, Technical Report 314, Courant Institute of Mathematical Sciences 1987.
• Ca: J. Canny, The complexity of robot motion planning, Ph.D. dissertation, Computer Science Department, M.I.T., May 1987.
• GSS: L. J. Guibas , M. Sharir , S. Sifrony, On the general motion planning problem with two degrees of freedom, Proceedings of the fourth annual symposium on Computational geometry, p.289-298, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73423]
• KeO: Yan Ke , Joseph O'Rourke, Lower bounds on moving a ladder in two and three dimensions, Discrete & Computational Geometry, v.3 n.3, p.197-217, Jan., 1988 [doi>10.1007/BF02187908]
• KrO: M. J. Kreveld and M. H. Overmars, Concatenable Segment Trees, Technical Report RUU-CS-88-36, Computer Science Department, University of Utrecht, 1988.
• KSl: 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]
• KS2: K. Kedem , M. Sharir, Planning algorithm for a convex polygonal object in two-dimensional polygonal space, Discrete & Computational Geometry, v.5 n.1, p.43-75, Jan. 1990 [doi>10.1007/BF02187779]
• LS: Daniel Leven , Micha Sharir, An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers, Journal of Algorithms, v.8 n.2, p.192-215, June 1987 [doi>10.1016/0196-6774(87)90038-1]
• LW: 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]
• Me: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• Oy: C. 6'DGnlaing and C. K. Yap, A retraction method for planning the motion of a disc, Journal of Algorithms 6 (1985), pp. 104-111.
• Ov: M. H. Overmars, Geometric data structures for computer graphics: an overview, Thcowtical Foundations of Computer Graphica and CAD, Edited by R. A. Earnshaw, Springer- Verlag, Berlin Heidelberg, 1988, pp. 167-184.
• SiS: S. Sifrony and M. Shark, An efficient motion planning algorithm for a rod moving in two-dimensional polygonal space, Algorithmica 2 (1987), pp. 367-402.
• SS: 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, Communications on Pure and Applied Mathematics 36 (1983), pp. 345-398.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory