Approximation algorithms for shortest path motion planning

ABSTRACT

This paper gives approximation algorithms of solving the following motion planning problem: Given a set of polyhedral obstacles and points s and t, find a shortest path from s to t that avoids the obstacles. The paths found by the algorithms are piecewise linear, and the length of a path is the sum of the lengths of the line segments making up the path. Approximation algorithms will be given for versions of this problem in the plane and in three-dimensional space. The algorithms return an &egr;-short path, that is, a path with length within (1 + &egr;) of shortest. Let n be the total number of faces of the polyhedral obstacles, and &egr; a given value satisfying &Ogr; < &egr; ≤ &pgr;. The algorithm for the planar case requires &Ogr;(n log n)/&egr; time to build a data structure of size &Ogr;(n/&egr;). Given points s and t, and &egr;-short path from s to t can be found with the use of the data structure in time &Ogr;(n/&egr; + n log n). The data structure is associated with a new variety of Voronoi diagram. Given obstacles S ⊂ &Egr;3 and points s, t &egr; E3, an &egr;-short path between s and t can be found in &Ogr;(n2&lgr;(n) log(n/&egr;)/&egr;4 + n2 lognp log(n logp)) time, where p is the ratio of the length of the longest obstacle edge to the distance between s to t. The function &lgr;(n) = &agr;(n)&Ogr;(&agr;(n)&Ogr;(1)), where the &agr;(n) is a form of inverse of Ackermann's function. For log(1/&egr;) and log p that are &Ogr;(log n), this bound is &Ogr;(log n2(n)&lgr;(n)/&egr;4).

REFERENCES

• AAG*85: Takao Asano, Tetsuo Asano, L. Guibas, J~ Hershberger, and H. Imai. Visibilitypolygon search and Euclidean shortest paths. In Proc. 26th IEEE FOC$, pages 1.55-164, } 985.
• Che86: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• Egg58: H.G. Eggleston. Convexity. Cambridge University Press, Cambridge, 1958.
• FT84: M. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization problems. Ill Proc. 25th IEEE FOCS, pages 338-346, 1984.
• Mou84: D. Mount. On finding shortest paths on convex polyhedra. Technical Report, Department of Computer Science, Univ. of Maryland, 1984.
• Pap85: C.H. Papadimitriou. An algorithm for shortest-path motion in three dimensions. Information Processing Letters, 20:259- 263, 1985.
• RS85: J. Rcif and J. A. Storcr. Shortest paths in Euclidean space with polyhedral obstacles. Technical Report CS-85-121, Departincnt of Computer Science, Brandeis Univ., 1985.
• SB86: A Sharir , A Baltsan, On shortest paths amidst convex polyhedra, Proceedings of the second annual symposium on Computational geometry, p.193-206, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10537]
• SCK*86: M. Sharir, R. Cole, K. Kedem, D. Leven, R. Pollack, and S. S ifrony. Geometric applications of Davenport-Schinzel sequences. In Proc. 27th IEEE FOCS, pages 77-86, } 986.
• SS84: Micha Sharir( , Amir Schorr, On shortest paths in polyhedral spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.144-153, December 1984 [doi>10.1145/800057.808676]
• Yao82: A.C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, } 1:721-736, 1982.
• Yap85: C.K. Yap. Algorithmic motion planning. In j. T. Schwartz and C. K. Yap, editors, Advance in Robotics, Volume I, Lawrence Erlbaum Associates, 1985.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory, Verification