A backward search can be conducted by incrementally growing a plan outward from by using backprojections. A complete algorithm for computing feasible plans under nondeterministic uncertainty is outlined in Figure 10.6. Let denote the set of states for which the plan has been computed. Initially, and, if possible, may grow until . The plan definition starts with for each and is incrementally extended to new states during execution.
Step 2 takes every state that is not already in and checks whether it should be added. This requires determining whether some action, , can be applied from , with the next state guaranteed to lie in , as shown in Figure 10.7. If so, then is assigned and is extended to include . 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 has grown, and in the next iteration new states may lie in its strong backprojection.
For efficiency reasons, the set in Step 2 may be safely replaced with the smaller set, , because it is impossible for other states in 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 in Step 2.
As long as the consideration of states to include in 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 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