Consider the set of all states that can be reached up to some fixed time limit. Let the time-limited reachable set be the subset of that is reached up to and including time . Formally, this is
Imagine an animation of that starts at and gradually increases . The boundary of can be imagined as a propagating wavefront that begins at . It eventually reaches the boundary of (assuming it has a boundary; it does not if ). The boundary of can actually be interpreted as a level set of the optimal cost-to-come from for a cost functional that measures the elapsed time. The boundary is also a kind of forward projection, as considered for discrete spaces in Section 10.1.2. In that context, possible future states due to nature were specified in the forward projection. In the current setting, possible future states are determined by the unspecified actions of the robot. Rather than looking stages ahead, the time-limited reachable set looks for duration into the future. In the present context there is essentially a continuum of stages.
Recall that the Dubins car can only drive forward. From an arbitrary configuration, the time-limited reachable set appears as shown in Figure 14.4a. The time limit is small enough so that the car cannot rotate by more than . Note that Figure 14.4a shows a 2D projection of the reachable set that gives translation only. The true reachable set is a 3D region in . If , then the car will be able to drive in a circle. For any , consider the limiting case as approaches infinity, which results in . Imagine a car driving without reverse on an infinitely large, flat surface. It is possible to reach any desired configuration by driving along a circle, driving straight for a while, and then driving along a circle again. Therefore, for any . The lack of a reverse gear means that some extra maneuvering space may be needed to reach some configurations.
Now consider the Reeds-Shepp car, which is allowed to travel in
reverse. Any time-limited reachable set for this car must include all
points from the corresponding reachable set for the Dubins car
because new actions have been added to but none have been
removed. It is tempting to assert that the time-limited reachable set
appears as in Figure 14.4b; however, this is wrong.
In an arbitrarily small amount of time (or space) a car with reverse
can be wiggled sideways. This is achieved in practice by familiar
parallel-parking maneuvers. It turns out in this
always contains an open set around , which
means that it grows in all directions (see Section
15.3.2). The property is formally referred to as
small-time controllability and is covered in Section 15.4.
Steven M LaValle 2012-04-20