Pseudo Approximation Algorithms with Applications to Optimal Motion Planning

We introduce a technique for computing approximatesolutions to optimization problems. If $X$ is the setof feasible solutions, the standard goalof approximation algorithms is to compute $xin X$ that is an$varepsilon$-approximate solution in the following sense:$$d(x) leq (1+varepsilon), d(x^*),$$where $x^* in X$ is an optimal solution,$dcolon Xrightarrow {Bbb R}_{geq 0}$ isthe optimization function to be minimized, and$varepsilon>0$ is an input parameter.Our approach is first to devise algorithms thatcompute pseudo $varepsilon$-approximate solutionssatisfying the bound$$d(x) leq d(x_R^*) + varepsilon 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$ providesa stratification of $X$ in the sense that (1) $X_R subseteq X_{R}$ for $R < R$ and (2) $X_R = X$ for $R$ sufficiently large.We first describe a highly efficient schemefor converting a pseudo $varepsilon$-approximationalgorithm into a true $varepsilon$-approximation algorithm.This scheme is useful becausepseudo approximation algorithms seem to beeasier to construct than $varepsilon$-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), namelythe shortest path for a point robot amidst polyhedral obstacles in three dimensions, and(B) $d_1$-optimal motion for a rod moving amidstplanar obstacles (1ORM).Previously, no polynomial time $varepsilon$-approximation algorithmfor (B) was known. For (A), our new solutionis simpler than previous solutions and hasan exponentially smaller complexity in terms of the input precision.