##

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
and forcing trajectories to visit specific points, 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 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).

**Subsections**
Steven M LaValle
2012-04-20