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.
\item Initialize $S = ...
...more progress can be made. Otherwise, go
to Step 2.

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.

Steven M LaValle 2012-04-20