14.2.1.2 Time-limited reachable set

Consider the set of all states that can be reached up to some fixed time limit.Let the time-limited reachable set $R(x_0,{\cal U},t)$ be the subset of $R(x_0,{\cal U})$ that is reached up to and including time $t$. Formally, this is

$$R(x_0,{\cal U},t) = \{ x_1 \in X \;\vert\; \exists {\tilde{u}}\in {\cal U} \exists t' \in [0,t] x(t') = x_1 \} .$$ (14.5)

For the last case in Example 14.2, the time-limited reachable sets are closed discs of radius $t$ centered at $(x_0,y_0)$. A version of (14.5) that takes the obstacle region into account can be defined as $R(x_0,{{\cal U}_{free}},t)$.

Imagine an animation of $R(x_0,{\cal U},t)$ that starts at $t=0$ and gradually increases $t$. The boundary of $R(x_0,{\cal U},t)$ can be imagined as a propagating wavefront that begins at $x_0$. It eventually reaches the boundary of $R(x_0,{\cal U})$ (assuming it has a boundary; it does not if $R(x_0,{\cal U}) = X$). The boundary of $R(x_0,{\cal U},t)$ can actually be interpreted as a level set of the optimal cost-to-come from $x_0$ 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 $k$ stages ahead, the time-limited reachable set looks for duration $t$ into the future. In the present context there is essentially a continuum of stages.

Example 14..3 (Reachable Sets for Simple Cars)   Nice illustrations of reachable sets can be obtained from the simple car models from Section 13.1.2. Suppose that $X = {\cal C}= {\mathbb{R}}^2 \times {\mathbb{S}}^1$ and ${X_{obs}}= \emptyset$.

Figure 14.4: (a) The time-limited reachable set for the Dubins car facing to the right; (b) this is not the time-limited reachable set for the Reeds-Shepp car!

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 $t$ is small enough so that the car cannot rotate by more than $\pi/2$. 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 ${\cal C}$. If $t > 2 \pi$, then the car will be able to drive in a circle. For any $q$, consider the limiting case as $t$ approaches infinity, which results in $R(q,{\cal U})$. 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, $R(q,{\cal U}) = {\cal C}$ for any $q \in {\cal C}$. 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 $U$ 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 case that $R(q,{\cal U},t)$ always contains an open set around $q$, 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. $\blacksquare$