Pseudo approximation algorithms, with applications to optimal motion planning

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 x_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) X_R ⊆ X_R′, for R < R′ and (2) X_R = 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₁-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.