Alternative lattices for the double integrator

Many alternative lattices can be constructed over $X$. Different discretizations of $U$ and time can be used. Great flexibility is allowed if feasibility is the only concern, as opposed to optimality. Since ${\cal C}= {\mathbb{R}}$, it is difficult to define an obstacle avoidance problem; however, the concepts will be soon generalized to higher dimensions. In this case, finding a feasible trajectory that connects from some initial state to a goal state may be the main concern. Note, however, that if ${x_{I}}$ and ${x_{G}}$ are states with zero velocity, then the state could hover around close to the $q$-axis, and the speeds will be so slow that momentum is insignificant. This provides some incentive for at least reducing the travel time as much as possible, even if the final result is not optimal. Alternatively, the initial and goal states may not have zero velocity, in which case, any feasible solution may be desired. For example, suppose the goal is to topple a sports utility vehicle (SUV) as part of safety analysis.

To get a feeling for how to construct lattices, recall again the analogy to conveyor belts. A lattice can be designed by placing horizontal rows of sample points at various values of ${\dot q}$. These could, for example, be evenly spaced in the ${\dot q}$ direction as in Figure 14.13. Imagine the state lies on a conveyor belt. If desired, a move can be made to any other conveyor belt, say at ${\dot q}'$, by applying a nonzero action for some specific amount of time. If ${\dot q}' > {\dot q}$, then $u > 0$; otherwise, $u < 0$. If the action is constant, then after time $\vert{\dot q}- {\dot q}'\vert/u$ has passed, the state will arrive at ${\dot q}'$. Upon arrival, the position $q$ on the conveyor belt might not coincide with a sample point. This is no problem because the action $u = 0$ can be applied until the state drifts to the next sample point. An alternative is to choose an action from $U$ that drives directly to a lattice point within its forward, time-limited reachable set. Recall Figure 14.14; the cone can be placed on a lattice point to locate other lattice points that can be reached by application of a constant action in $U$ over some time interval.

Recall from Figure 14.13 that longer distances are traveled over time $\Delta t$ as $\vert{\dot q}\vert$ increases. This may be undesirable behavior in practice because the resolution is essentially much poorer at higher speeds. This can be compensated for by placing the conveyor belts closer together as $\vert{\dot q}\vert$ increases. As the speed increases, a shorter time interval is needed to change belts, and the distance traveled can be held roughly the same for all levels. This corresponds to the intuition that faster response times are needed at higher speeds.

A multi-resolution version can also be made [816]. The simple problem considered so far can actually be solved combinatorially, without any approximation error [747]; however, the lattice-based approach was covered because it can be extended to much harder problems, as will be explained next.