# 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 language English (US) 170-178 9 https://doi.org/10.1145/513400.513422 Published - 2002 Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, SpainDuration: Jun 5 2002 → Jun 7 2002

### Other

Other Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) Spain Barcelona 6/5/02 → 6/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.