Backward search

Backward versions of any of the forward search algorithms of Section 2.2.2 can be made. For example, a backward version of Dijkstra's algorithm can be made by starting from ${x_{G}}$. To create backward search algorithms, suppose that there is a single goal state, ${x_{G}}$. For many planning problems, it might be the case that the branching factor is large when starting from ${x_{I}}$. In this case, it might be more efficient to start the search at a goal state and work backward until the initial state is encountered. A general template for this approach is given in Figure 2.6. For forward search, recall that an action $u \in U(x)$ is applied from $x \in X$ to obtain a new state, $x' = f(x,u)$. For backward search, a frequent computation will be to determine for some $x'$, the preceding state $x \in X$, and action $u \in U(x)$ such that $x' = f(x,u)$. The template in Figure 2.6 can be extended to handle a goal region, ${X_{G}}$, by inserting all ${x_{G}}\in {X_{G}}$ into $Q$ in line 1 and marking them as visited.

For most problems, it may be preferable to precompute a representation of the state transition function, $f$, that is ``backward'' to be consistent with the search algorithm. Some convenient notation will now be constructed for the backward version of $f$. Let ${U^{-1}}= \{(x,u) \in X \times U \;\vert\; x \in X, u \in U(x)\}$, which represents the set of all state-action pairs and can also be considered as the domain of $f$. Imagine from a given state $x' \in X$, the set of all $(x,u) \in {U^{-1}}$ that map to $x'$ using $f$. This can be considered as a backward action space, defined formally for any $x' \in X$ as

$${U^{-1}}(x') = \{ (x,u) \in {U^{-1}}\;\vert\; x' = f(x,u) \} .$$ (2.3)

For convenience, let $u^{-1}$ denote a state-action pair $(x,u)$ that belongs to some ${U^{-1}}(x')$. From any $u^{-1}\in {U^{-1}}(x')$, there is a unique $x \in X$. Thus, let ${f^{-1}}$ denote a backward state transition function that yields $x$ from $x'$ and $u^{-1}\in {U^{-1}}(x')$. This defines a backward state transition equation, $x = {f^{-1}}(x',u^{-1})$, which looks very similar to the forward version, $x' = f(x,u)$.

The interpretation of ${f^{-1}}$ is easy to capture in terms of the state transition graph: reverse the direction of every edge. This makes finding a plan in the reversed graph using backward search equivalent to finding one in the original graph using forward search. The backward state transition function is the variant of $f$ that is obtained after reversing all of the edges. Each $u^{-1}$ is a reversed edge. Since there is a perfect symmetry with respect to the forward search of Section 2.2.1, any of the search algorithm variants from Section 2.2.2 can be adapted to the template in Figure 2.6, provided that ${f^{-1}}$ has been defined.

Figure 2.6: A general template for backward search.