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

$$\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].