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 χ ε X that is an ε-approximate solution in the following sense: d(χ)≤(1+ε)d(χ*) where χ* Ε 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 ε-approximate solutions satisfying the bound d(χ) ≤ d(χR *) + εR where R>0 is a new input parameter. Here χ* 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 ε-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) d 1-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.