14.2.1.3 Backward reachable sets

The reachability definitions have a nice symmetry with respect to time. Rather than describing all points reachable from some $x \in X$, it is just as easy to describe all points from which some $x \in X$ can be reached. This is similar to the alternative between forward and backward projections in Section 10.1.2.

Let the backward reachable set be defined as

$$B(x_f,{\cal U}) = \{ x_0 \in X \;\vert\; \exists {\tilde{u}}\in {\cal U} \exists t \in [0,\infty) x(t) = x_f \} ,$$ (14.6)

in which $x(t)$ is given by (14.1) and requires that $x(0) = x_0$. Note the intentional similarity to (14.4). The time-limited backward reachable set is defined as

$$B(x_f,{\cal U},t) = \{ x_0 \in X \;\vert\; \exists {\tilde{u}}\in {\cal U} \exists t' \in [0,t] x(t') = x_f \} ,$$ (14.7)

which once again requires that $x(0) = x_0$ in (14.1). Completeness can even be defined in terms of backward reachable sets by defining a backward-time counterpart to ${\cal U}$.

At this point, there appear to be close parallels between forward, backward, and bidirectional searches from Chapter 2. The same possibilities exist in sampling-based planning under differential constraints. The forward and backward reachable sets indicate the possible states that can be reached under such schemes. The algorithms explore subsets of these reachable sets.