Pseudo approximation algorithms, with applications to optimal motion planning

ABSTRACT

(MATH) We introduce a technique for computing approximate solutions to optimization problems. If X is the set of feasible solutions, the standard goal of approximation algorithms is to compute &khgr; &egr; X that is an &egr;-approximate solution in the following sense: d(&khgr;)&xie;(1+&egr;)d(&khgr;^*) where &khgr;^* &Egr; X is an optimal solution, d : X → 0 is the optimization function to be minimized, and $\vareps>0 is an input parameter. Our approach is to first devise algorithms that compute pseudo &egr;-approximate solutions satisfying the bound d(&khgr;) &xie; d(&khgr;R ^*) + &egr;R where R>0 is a new input parameter. Here &khgr;^* R denotes an optimal solution in the space X R of R-constrained feasible solutions. The parameterization provides a stratification of X in the sense that (1) XR ⊆ XR' , for R < R' and (2) XR = X for R sufficiently large.We first describe a highly efficient scheme for converting a pseudo &egr;-approximation algorithm into a true &egr;-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than &egr;-approximation algorithms.We then apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in 3D, and (B) d 1-optimal motion for a rod moving amidst polygonal obstacles in 2D. Previously, no true &egr;-approximation algorithm for (B) was known. For (A), our new solution is not only simpler than two previous solutions but also has a lower complexity (in the algebraic model) measured in terms of the input precision. Note that (A) and (B) are the simplest NP-hard motion planning problems in 3-D and 2-D respectively.

REFERENCES

• 1: Tetsuo Asano , David Kirkpatrick , Chee K. Yap, d1-optimal motion for a rod (extended abstract), Proceedings of the twelfth annual symposium on Computational geometry, p.252-263, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237394]
• 2: A. S. Besicovitch. On Kakeya's problem and a similar one. Mathematische Zeitschrift, 27:312--320, 1928.
• 3: J. Canny and J. H. Reif. New lower bound techniques for robot motion planning problems. IEEE Foundations of Computer Science, 28:49--60, 1987.
• 4: Joonsoo Choi , Jürgen Sellen , Chee-Keng Yap, Approximate Euclidean shortest path in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.41-48, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177501]
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: Dan Halperin , Lydia Kavraki , Jean-Claude Latombe, Robotics, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 7: C. Icking, G. Rote, E. Welzl, and C. Yap. Shortest paths for line segments. Algorithmica, 10:182--200, 1993.
• 8: 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]
• 9: J. O'Rourke. Finding a shortest ladder path: a special case. IMA Preprint Series 353, Institute for Mathematics and its Applications, University of Minnesota, 1987.
• 10: C. H. Papadimitriou. An algorithm for shortest-path motion in three dimensions. Inform. Process. Lett., 20:259--263, 1985.
• 11: C. H. Papadimitriou and E. B. Silverberg. Optimal piecewise linear motion of an object among obstacles. Algorithmica, 2:523--539, 1987.
• 12: J. T. Schwartz and M. Sharir. On the piano movers' problem: I. the case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Communications on Pure and Applied Mathematics, 36:345--398, 1983.
• 13: Jürgen Sellen , Joonsoo Choi , Chee-Keng Yap, Precision-Sensitive Euclidean Shortest Path in 3-Space, SIAM Journal on Computing, v.29 n.5, p.1577-1595, March 2000 [doi>10.1137/S0097539798340205]
• 14: M. Sharir. A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder. NYU Robotics Report 188, Courant Institute, New York University, 1989.
• 15: M. Sharir, C. O'D'únlaing, and C. Yap. Generalized Voronoi diagrams for moving a ladder I: topological analysis. Communications in Pure and Applied Math., XXXIX:423--483, 1986.
• 16: M. Sharir, C. O'D'únlaing, and C. Yap. Generalized Voronoi diagrams for moving a ladder II: efficient computation of the diagram. Algorithmica, 2:27--59, 1987.
• 17: S. M. Ulam. Problems of Modern Mathematics. Science Editions, New York, 1964. Originally published as: A Collection of Mathematical Problems, Interscience Publishers, New York, 1960.
• 18: C. K. Yap. Algorithmic motion planning. In J. T. Schwartz and C. K. Yap, editors, Advances in Robotics, Vol. 1: Algorithmic and geometric issues, chapter~3. Lawrence Erlbaum Associates, 1987.

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

General Terms:
Algorithms, Theory

Keywords:
NP-hard problem, d 1-optimal motion, Euclidean shortest path, approximation algorithms, binary search, optimal motion planning, pseudo approximation, robot motion planning