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

$\displaystyle B(x_f,{\cal U}) = \{ x_0 \in X \;\vert\; \exists {\tilde{u}}\in {\cal U}$ and $\displaystyle \exists t \in [0,\infty)$    such that $\displaystyle 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

$\displaystyle B(x_f,{\cal U},t) = \{ x_0 \in X \;\vert\; \exists {\tilde{u}}\in {\cal U}$ and $\displaystyle \exists t' \in [0,t]$    such that $\displaystyle 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.

Steven M LaValle 2012-04-20