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 notation refers to the

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

The difference between (10.20) and (10.21) is either

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 :*

which can also be expressed as

Similarly, the

Note that cannot be formed by the union of over all . Another observation is that for each , we have .

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

and the

Note that .

Now consider backprojections from the goal, , under the action . The weak backprojection is

(10.27) |

The strong backprojection is . From any of the other states in , nature could cause the goal to be missed. Note that cannot be constructed by taking the union of over every .

Finally, consider backprojections that do not depend on an action.
These are
and
. In
the latter case, all states in lie in
because
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