Sometimes it is helpful to define the set of possible previous states from which one or more current states could be obtained. For example, they will become useful in defining graph-based planning algorithms in Section 10.2.3. This involves maintaining a backprojection, which is a counterpart to the forward projection that runs in the opposite direction. Backprojections were considered in Section 8.5.2 to keep track of the active states in a Dijkstra-like algorithm over continuous state spaces. In the current setting, backprojections need to address uncertainty.
Consider the case of nondeterministic uncertainty. Let a state be given. Under a fixed action , what previous states, , could possibly lead to ? This depends only on the possible choices of nature and is expressed as
The backprojection is called ``weak'' because it does not guarantee that is reached, which is a stronger condition. By guaranteeing that is reached, a strong backprojection of under is defined as
Two useful generalizations will now be made: 1) A backprojection can be defined from a set of states; 2) the action does not need to be fixed. Instead of a fixed state, , consider a set of states. What are the states from which an element of could possibly be reached in one stage under the application of ? This is the weak backprojection of under :
Now the dependency on will be removed. This yields a backprojection of a set . These are states from which there exists an action that possibly reaches . The weak backprojection of is
Now consider backprojections from the goal, , under the action . The weak backprojection is
Finally, consider backprojections that do not depend on an action.
the latter case, all states in lie in
can be applied. Without allowing , we would obtain
Other kinds of backprojections are possible, but we will not define them. One possibility is to make backprojections over multiple stages, as was done for forward projections. Another possibility is to define them for the probabilistic case. This is considerably more complicated. An example of a probabilistic backprojection is to find the set of all states from which a state in will be reached with at least probability .
Steven M LaValle 2012-04-20