14.2.2.1 Reachability graph

After time discretization has been performed, the reachable set can be adapted to ${\cal U}_d$ to obtain $R(x_0,{\cal U}_d)$. An interesting question is: What is the effect of sampling on the reachable set? In other words, how do $R(x_0,{\cal U})$ and $R(x_0,{\cal U}_d)$ differ? This can be addressed by defining a reachability graph, which will be revealed incrementally by a planning algorithm.

Let $T_r(x_0,{\cal U}_d)$ denote a reachability tree, which encodes the set of all trajectories from $x_0$ that can be obtained by applying trajectories in ${\cal U}_d$. Each vertex of $T_r(x_0,{\cal U}_d)$ is a reachable state, $x \in R(x_0,{\cal U}_d)$. Each edge of $T_r(x_0,{\cal U}_d)$ is directed; its source represents a starting state, and its destination represents the state obtained by applying a constant action $u \in U_d$ over time $\Delta t$. Each edge $e$ represents an action trajectory segment, $e : [0,\Delta t] \rightarrow U$. This can be transformed into a state trajectory, ${\tilde{x}}_e$, via integration using (14.1), from 0 to $\Delta t$ of $f(x,u)$ from the source state of $e$.

Thus, in terms of ${\tilde{x}}_e$, $T_r$ can be considered as a topological graph in $X$ ($T_r$ will be used as an abbreviation of $T_r(x_0,{\cal U}_d)$). The swath $S(T_r)$ of $T_r$ is

$$S(T_r) = \bigcup_{e \in E} \bigcup_{t \in [0,\Delta t]} x_e(t) ,$$ (14.8)

in which $x_e(t)$ denotes the state obtained at time $t$ from edge $e$. (Recall topological graphs from Example 4.6 and the swath from Section 5.5.1.)

Figure 14.6: A reachability tree for the Dubins car with three actions. The $k$th stage produces $3^k$ new vertices.

Example 14..4 (Reachability Tree for the Dubins Car)   Several stages of the reachability tree for the Dubins car are shown in Figure 14.6. Suppose that there are three actions (straight, right-turn, left-turn), and $\Delta t$ is chosen so that if the right-turn or left-turn action is applied, the car travels enough to rotate by $\pi/2$. After the second stage, there are nine leaves in the tree, as shown in Figure 14.6a. Each stage produces $3^k$ new leaves. In Figure 14.6b, $81$ new leaves are added in stage $k = 4$, which yields a total of $81+27+9+3+1$ vertices. In many cases, the same state is reachable by different action sequences. The swath after the first four stages is the set of all points visited so far. This is a subset of ${\cal C}$ that is the union of all vertices and all points traced out by ${\tilde{x}}_e$ for each $e \in E$. $\blacksquare$

From Example 14.4 it can be seen that it is sometimes possible to arrive at the same state using two or more alternative action trajectories. Since each action trajectory can be expressed as an action sequence, the familiar issue arises from classical AI search of detecting whether the same state has been reached from different action sequences. For some systems, the reachability problem can be dramatically simplified by exploiting this information. If the same state is reached from multiple action sequences, then only one vertex needs to be represented.

This yields a directed reachability graph ${\cal G}_r(x_0,{\cal U}_d)$, which is obtained from $T_r(x_0,{\cal U}_d)$ by merging its duplicate states. If every action sequence arrives at a unique state, then the reachability graph reduces to the reachability tree. However, if multiple action sequences arrive at the same state, this is represented as a single vertex ${\cal G}_r$. From this point onward, the reachability graph will be primarily used. As for a reachability tree, a reachability graph can be interpreted as a topological graph in $X$, and its swath $S({\cal G}_r)$ is defined by adapting (14.8).

The simplest case of arriving at the same state was observed in Example 2.1. The discrete grid in the plane can be modeled using the terminology of Chapter 13 as a system of the form ${\dot x}= u_1$ and ${\dot y}= u_2$ for a state space $X = {\mathbb{R}}^2$. The discretized set $U_d$ of actions is $\{(1,0)$, $(0,1)$, $(-1,0)$, $(0,-1)\}$. Let $\Delta t = 1$. In this case, the reachability graph becomes the familiar 2D grid. If $(0,0)$ is the initial state, then the grid vertices consist of all states in which both coordinates are integers.

Through careless discretization of an arbitrary system, such a nice grid usually does not arise. However, in many cases a discretization can be carefully chosen so that the states become trapped on a grid or lattice. This has some advantages in sampling-based planning. Section 14.4.1 covers a method that exploits such structure for the system ${\ddot q} = u$. It can even be extended to more general systems, provided that the system can be expressed as ${\ddot q}= g(q,{\dot q},u)$ and it is not underactuated. It was shown recently that by a clever choice of discretization, a very large class of nonholonomic systems^14.4 can also be forced onto a lattice [762]. This is usually difficult to achieve, and under most discretizations the vertices of the reachability graph are dense in the reachable set.

It is also possible to define backward versions of the reachability tree and reachability graph, in the same way that backward reachable sets were obtained. These indicate initial states and action sequences that will reach a given goal state and are no more difficult to define or compute than their forward counterparts. They might appear more difficult, but keep in mind that the initial states are not fixed; thus, no BVP appears. The initial states can be obtained by reverse-time integration of the state transition equation; see Section 14.3.2.