Approximation algorithm framework

The lattices developed in this section were introduced in [290] for analyzing the kinodynamic planning problem in the rigorous approximation algorithm framework for NP-hard problems [765]. Suppose that there are two or three independent double integrators. The analysis shows that the computed solutions are approximately optimal in the following sense. Let $ c_0$ and $ c_1$ be two positive constants that define a function

$\displaystyle \delta(c_0,c_1)({\dot q}) = c_0 + c_1 \Vert{\dot q}\Vert .$ (14.25)

Let $ t_F$ denote the time at which the termination action is applied. A state trajectory is called $ \delta(c_0,c_1)$-safe if for all $ t \in [0,t_F]$, the ball of radius $ \delta(c_0,c_1)({\dot q})$ that is centered at $ q(t)$ does not cause collisions with obstacles in $ {\cal W}$. Note that the ball radius grows linearly as the speed increases. The robot can be imagined as a disk with a radius determined by speed. Let $ {x_{I}}$, $ {x_{G}}$, $ c_0$, and $ c_1$ be given (only a point goal region is allowed). Suppose that for a given problem, there exists a $ \delta(c_0,c_1)$-safe state trajectory (resulting from integrating any $ {\tilde{u}}\in {\cal U}$) that terminates in $ {x_{G}}$ after time $ t_{opt}$. It was shown that by choosing the appropriate $ \Delta t$ (given by a formula in [290]), applying breadth-first search to the reachability lattice will find a $ (1-\epsilon)\delta(c_0,c_1)$-safe trajectory that takes time at most $ (1+\epsilon) t_{opt}$, and approximately connects $ {x_{I}}$ to $ {x_{G}}$ (which means that the closeness in $ X$ depends on $ \epsilon$). Furthermore, the running time of the algorithm is polynomial in $ 1/\epsilon$ and the number of primitives used to define polygonal obstacles.14.5 One of the key steps in the analysis is to show that any state trajectory can be closely tracked using only actions from $ U_d$ and keeping them constant over $ \Delta t$. One important aspect is that it does not necessarily imply that the computed solution is close to the true optimum, as it travels through $ X$ (only the execution times are close). Thus, the algorithm may give a solution from a different homotopy class from the one that contains the true optimal trajectory. The analysis was extended to the general case of open-chain robot arms in [288,441].

Steven M LaValle 2012-04-20