Resolution issues

One of the main complications in using state discretization is that there are three spaces over which sampling occurs: time, the action space, and the state space. Assume the discrete-time model is used. If obtaining optimal solutions is important, then very small cells should be used (e.g., 50 to 100 per axis). This limits its application to state spaces of a few dimensions. The time interval $\Delta t$ should also be made small, but if it is too small relative to the cell size, then it may be impossible to leave a cell. If only feasibility is the only requirement, then larger cells may be used, and $\Delta t$ must be appropriately increased. A course quantization of $U$ may cause solutions to be missed, particularly if $\Delta t$ is large. As $\Delta t$ decreases, the number of samples in $U_d$ becomes less important.

To obtain resolution completeness, the sampling should be improved each time the search fails. Each time that the search is started, the sampling dispersion for at least one of the three spaces should be decreased. The possibilities are 1) the time interval $\Delta t$ may be reduced, 2) more actions may be added to $U_d$, or 3) more points may be added to $P$ to reduce the cell size. If the dispersion approaches zero for all three spaces, and if ${X_{G}}$ contains an open subset of ${X_{free}}$, then resolution completeness is obtained. If ${X_{G}}$ is only a point, then solutions that come within some $\epsilon > 0$ must be tolerated.

Figure 14.18: (a) The Dubins car is able to turn around if it turns left as sharply as possible. (b) Unfortunately, the required vertex is pruned because one cell along the required trajectory already contains a vertex. This illustrates how missing a possible action can cause serious problems many stages later.

Recall that resolution completeness assumes that $f$ has bounded derivatives or at least satisfies a Lipschitz condition (14.11). The actual rate of convergence is mainly affected by three factors: 1) the rate at which $f$ varies with respect to changes in $u$ and $x$ (characterized by Lipschitz constants), 2) the required traversal of narrow regions in ${X_{free}}$, and 3) the controllability of the system. The last condition will be studied further for nonholonomic systems in Section 15.4. For a concrete example, consider making a U-turn with a Dubins car that has a very large turning radius, as shown in Figure 14.18. A precise turn may be required to turn around, and this may depend on an action that was chosen many stages earlier. The Dubins car model does not allow zig-zagging (e.g., parallel parking) maneuvers to make local corrections to the configuration.