Pseudo approximation algorithms, with applications to optimal motion planning

Tetsuo Asano, David Kirkpatrick, Chee Yap

Research output: Contribution to conferencePaperpeer-review

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 to first 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 xR* denotes an optimal solution in the space XR 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 ε-approximation algorithm into a true ε-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than ε-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) d1-optimal motion for a rod moving amidst polygonal obstacles in 2D. Previously, no true ε-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.

Original languageEnglish (US)
Pages170-178
Number of pages9
DOIs
StatePublished - 2002
EventProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain
Duration: Jun 5 2002Jun 7 2002

Other

OtherProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02)
CountrySpain
CityBarcelona
Period6/5/026/7/02

Keywords

  • Approximation algorithms
  • Binary search
  • Euclidean shortest path
  • NP-hard problem
  • Optimal motion planning
  • Pseudo approximation
  • Robot motion planning
  • d-optimal motion

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational 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