14.4.2 Incorporating State Space Discretization

If the reachability graph is not a lattice, which is typically the case with underactuated and nonholonomic systems, then state space discretization can be used to force it to behave like a lattice. If there are no differential constraints, then paths can be easily forced to travel along a lattice, as in the methods of Section 7.7.1. Under differential constraints, the state cannot be forced, for example, to follow a staircase path. Instead of sampling $X$ and forcing trajectories to visit specific points, $X$ can be partitioned into small cells, within which no more than one vertex is allowed in the search graph. This prevents a systematic search algorithm from running forever if the search graph has an infinite number of vertices in some bounded region. For example, with the Dubins car, if $u$ is fixed to an integer, an infinite number of vertices on a circle is obtained, as mentioned in Section 14.2.2. The ideas in this section are inspired mainly by the Barraquand-Latombe dynamic programming method [73], which has been mainly applied to the models in Section 13.1.2. In the current presentation, however, the approach is substantially generalized. Here, optimality is not even necessarily required (but can be imposed, if desired).