Backward search with backprojections

A backward search can be conducted by incrementally growing a plan outward from ${X_{G}}$ by using backprojections. A complete algorithm for computing feasible plans under nondeterministic uncertainty is outlined in Figure 10.6. Let $S$ denote the set of states for which the plan has been computed. Initially, $S = {X_{G}}$ and, if possible, $S$ may grow until $S = X$. The plan definition starts with $\pi (x) = u_T$ for each $x \in {X_{G}}$ and is incrementally extended to new states during execution.

Figure 10.6: A general algorithm for computing a feasible plan under nondeterministic uncertainty.

Figure 10.7: A state $x$ can be added to $S$ if there exists an action $u \in U(x)$ such that the one-stage forward projection is contained in $S$.

Step 2 takes every state $x$ that is not already in $S$ and checks whether it should be added. This requires determining whether some action, $u$, can be applied from $x$, with the next state guaranteed to lie in $S$, as shown in Figure 10.7. If so, then $\pi (x) = u$ is assigned and $S$ is extended to include $x$. If no such progress can be made, then the algorithm must terminate. Otherwise, every state is checked again by returning to Step 2. This is necessary because $S$ has grown, and in the next iteration new states may lie in its strong backprojection.

For efficiency reasons, the $X \setminus S$ set in Step 2 may be safely replaced with the smaller set, $\operatorname{WB}(S) \setminus S$, because it is impossible for other states in $X$ to be affected. Depending on the problem, this condition may provide a quick way to prune many hopeless states from consideration. As an example, consider a grid-like environment in which a maximum of two steps in any direction is possible at a given time. A simple distance test can be implemented to eliminate many states from possible inclusion into $S$ in Step 2.

As long as the consideration of states to include in $S$ is systematic, as considered in Section 2.2, numerous variations of the algorithm in Figure 10.6 are possible. One possibility is to keep track of the cost-to-go and grow $S$ based on incrementally inserting minimal-cost states. This leads to a nondeterministic version of Dijkstra's algorithm, which is covered next.