Pseudo Approximation Algorithms with Applications to Optimal Motion Planning

Tetsuo Asano, David Kirkpatrick, Chee Yap

Research output: Contribution to journalArticle

Abstract

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 x ε X that is an ε-approximate solution in the following sense: d(x) ≤ (1 + ε) d(x*), where x* ∈ X is an optimal solution, d: X → ℝ≥0 is the optimization function to be minimized, and ε > 0 is an input parameter. Our approach is first to devise algorithms that compute pseudo ε-approximate solutions satisfying the bound d(x) ≤ d(x*R) + εR, where R > 0 is a new input parameter. Here x*R denotes an optimal solution in the space X R of R-constrained feasible solutions. The parameter R provides a stratification of X in the sense that (1) XR ⊆ X R′ for R < R′ and (2) XR = X for R sufficiently large. We first describe a highly efficient scheme for converting a pseudo ε-approximation algorithm into a true ε-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than ε-approximation algorithms. Another benefit is that our algorithm is automatically precision-sensitive. We 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 three dimensions, and (B) d1-optimal motion for a rod moving amidst planar obstacles (1ORM). Previously, no polynomial time ε-approximation algorithm for (B) was known. For (A), our new solution is simpler than previous solutions and has an exponentially smaller complexity in terms of the input precision.

Original languageEnglish (US)
Pages (from-to)139-171
Number of pages33
JournalDiscrete and Computational Geometry
Volume31
Issue number1
DOIs
StatePublished - Jan 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Pseudo Approximation Algorithms with Applications to Optimal Motion Planning'. Together they form a unique fingerprint.

  • Cite this