Multiple, independent double integrators

Now consider generalizing to a vector of $n$ double integrators. In this case, ${\cal C}= {\mathbb{R}}^n$ and each $q \in {\cal C}$ is an $n$-dimensional vector. There are $n$ action variables and $n$ double integrators of the form ${\ddot q}_i = u_i$. The action space for each variable is $U_i = [-1,1]$ (once again, any acceleration bound can be used). The phase space $X$ is ${\mathbb{R}}^{2n}$, and each point is $x = (q_1,\ldots,q_n,{\dot q}_1,\ldots,{\dot q}_n)$. The $i$th double integrator produces two scalar equations of the phase transition equation: ${\dot x}_i = x_{n+i}$ and ${\dot x}_{n+i} = u_i$.

Even though there are $n$ double integrators, they are decoupled in the state transition equation. The phase of one integrator does not depend on the phase of another. Therefore, the ideas expressed so far can be extended in a straightforward way to obtain a lattice over ${\mathbb{R}}^{2n}$. Each action is an $n$-dimensional vector $u$. Each $U_i$ is discretized to yield values $-1$, 0, and $1$. There are $3^n$ edges emanating from any lattice point for which ${\dot q}_i \not = 0$ for all $i$. For any double integrator for which ${\dot q}_i = 0$, there are only two choices because $u_i = 0$ produces no motion. The projection of the reachability graph down to $(x_i,x_{n+i})$ for any $i$ from $1$ to $n$ looks exactly like Figure 14.13 and characterizes the behavior of the $i$th integrator.

The standard search algorithms can be applied to the lattice over ${\mathbb{R}}^{2n}$. Breadth-first search once again yields solutions that are approximately time-optimal. Resolution completeness can be obtained again by bounding $X$ and allowing $\Delta t$ to converge to zero. Now that there are more dimensions, a complicated obstacle region ${X_{obs}}$ can be removed from $X$. The traversal of each edge then requires collision detection along each edge of the graph. Note that the state trajectories are linear or parabolic arcs. Numerical integration is not needed because (14.22) already gives the closed-form expression for the state trajectory.