15.3 Optimal Paths for Some Wheeled Vehicles

For some of the wheeled vehicle models of Section 13.1.2, the shortest path between any pair of configurations was completely characterized. In this section, $X = {\cal C}= {\mathbb{R}}^2 \times {\mathbb{S}}^1$, which corresponds to the C-space for a rigid body in the plane. For each model, the path length in ${\cal C}$ must be carefully defined to retain some physical significance in the world ${\cal W}= {\mathbb{R}}^2$ in which the vehicle travels. For example, in the case of the simple car, the distance in ${\cal W}$ traveled by the center of the rear axle will be optimized. If the coordinate frame is assigned appropriately, this corresponds to optimizing the path length in the ${\mathbb{R}}^2$ subspace of ${\cal C}$ while ignoring orientation. Keep in mind that the solutions given in this section depend heavily on the particular cost functional that is optimized.

Sections 15.3.1-15.3.3 cover the shortest paths for the Dubins car, the Reeds-Shepp car, and a differential-drive model, respectively. In each case, the paths can be elegantly described as combinations of a few motion primitives. Due to symmetries, it is sufficient to describe the optimal paths from a fixed initial configuration ${q_{I}}= (0,0,0)$ to any goal configuration ${q_{G}}\in {\cal C}$. If the optimal path is desired from a different ${q_{I}}\in {\cal C}$, then it can be recovered from rigid-body transformations applied to ${q_{I}}$ and ${q_{G}}$ (the whole path can easily be translated and rotated without effecting its optimality, provided that ${q_{G}}$ does not move relative to ${q_{I}}$). Alternatively, it may be convenient to fix ${q_{G}}$ and consider optimal paths from all possible ${q_{I}}$.

Once ${q_{I}}$ (or ${q_{G}}$) is fixed, ${\cal C}$ can be partitioned into cells that correspond to sets of placements for ${q_{G}}$ (or ${q_{I}}$). Inside of each cell, the optimal curve is described by a fixed sequence of parameterized motion primitives. For example, one cell for the Dubins car indicates ``turn left,'' ``go straight,'' and then ``turn right.'' The curves are ideally suited for use as an LPM in a sampling-based planning algorithm.

This section mainly focuses on presenting the solutions. Establishing their correctness is quite involved and is based in part on Pontryagin's minimum principle from Section 15.2.3. Other important components are Filipov's existence theorem (see [903]) and Boltyanskii's sufficient condition for optimality (which also justifies dynamic programming) [130]. Substantially more details and justifications of the curves presented in Sections 15.3.1 and 15.3.2 appear in [903,904,923]. The corresponding details for the curves of Section 15.3.3 appear in [64].