15.3.2 Reeds-Shepp Curves

Now consider the shortest paths of the Reeds-Shepp car. The only difference in comparison to the Dubins car is that travel in the reverse direction is now allowed. The same criterion (15.42) is optimized, which is the distance traveled by the center of the rear axle. The shortest path is equivalent to the path that takes minimum time, as for the Dubins car. The simplified system in (15.43) can be enhanced to obtain

in which and . The first action variable, , selects the gear, which is forward () or reverse (). Once again, assume for simplicity that . The results stated here apply to any .

It was shown in [814] that there are no more than 48 different words that describe the shortest paths for the Reeds-Shepp car. The base word notation from Section 15.3.1 can be extended to nicely express the shortest paths. A new symbol, ``'', is used in the words to indicate that the ``gear'' is shifted from forward to reverse or reverse to forward. Reeds and Shepp showed that the shortest path for their car can always be expressed with one of the following base words:

As many as five primitives could be needed to execute the shortest path. A subscript of is given in some cases because the curve must be followed for precisely radians. For some others, is given as a subscript to indicate that it must match the parameter of another primitive. The form given in (15.49) is analogous to (15.46) for the Dubins car. The parameter ranges can also be specified, to yield a form analogous to (15.47). The result is shown in Figure 15.7. Example curves for two cases are shown in Figure 15.9.

Now the base words will be made more precise by specifying the
particular motion primitive. Imagine constructing a list of words
analogous to (15.44) for the Dubins car. There are six
primitives as shown in Figure 15.8. The symbols ,
, and are used again. To indicate the forward or reverse gear,
and superscripts will be used as shown in Figure
15.8.^{15.6}

Figure 15.10 shows 48 different words, which result from
uncompressing the base words expressed using , , and ``''
in (15.49). Each shortest path is a word with length at most
five. There are substantially more words than for the Dubins car.
Each base word in (15.49) expands into four or eight words
using the motion primitives. To uncompress each base word, the rule
that and cannot be applied consecutively is maintained. This
yields four possibilities for the first six compressed words. The
remaining three involve an intermediate primitive, which allows
eight possible sequences of s and s for each one. Two of the
48 words were eliminated in [923]. Each of the remaining 46
words can actually occur for a shortest path and are called the
*Reeds-Shepp curves*.

For use as an LPM, the problem appears
once again of determining the particular word and parameters for a
given and . This was not difficult for Dubins
curves, but now there are 46 possibilities. The naive approach of
testing every word and choosing the shortest one may be too costly.
The precise cell boundaries in over which each word applies are
given in [903]. The cell boundaries are unfortunately quite
complicated, which makes the point location algorithm difficult to
implement. A simple way to prune away many words from consideration
is to use intervals of validity for . For some values of
, certain compressed words are impossible as shortest paths.
A convenient table of words that become active over ranges of
is given in [903]. Once again, the length of the shortest
path can serve as a distance function in sampling-based planning
algorithms. The resulting *Reeds-Shepp metric* is continuous
because the Reeds-Shepp car is STLC, which will be established in Section 15.4.

Steven M LaValle 2012-04-20