Backprojections

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 $x \in X$ be given. Under a fixed action $u$, what previous states, $x^\prime \in X$, could possibly lead to $x$? This depends only on the possible choices of nature and is expressed as

$$\operatorname{WB}(x,u) = \{x^\prime \in X \;\vert\; \exists \theta \in \Theta(x^\prime,u) x = f(x^\prime,u,\theta)\}.$$ (10.20)

The notation $\operatorname{WB}(x,u)$ refers to the weak backprojection of $x$ under $u$, and gives the set of all states from which $x$ may possibly be reached in one stage.

The backprojection is called ``weak'' because it does not guarantee that $x$ is reached, which is a stronger condition. By guaranteeing that $x$ is reached, a strong backprojection of $x$ under $u$ is defined as

$$\operatorname{SB}(x,u) = \{x^\prime \in X \;\vert\; \forall \theta \in \Theta(x^\prime,u), \; x = f(x^\prime,u,\theta)\}.$$ (10.21)

The difference between (10.20) and (10.21) is either there exists an action of nature that enables $x$ to be reached, or $x$ is reached for all actions of nature. Note that $\operatorname{SB}(x,u) \subseteq \operatorname{WB}(x,u)$. In many cases, $\operatorname{SB}(x,u) = \emptyset$, and $\operatorname{WB}(x,u)$ is rarely empty. The backprojection that was introduced in (8.66) of Section 8.5.2 did not involve uncertainty; hence, the distinction between weak and strong backprojections did not arise.

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, $x$, consider a set $S \subseteq X$ of states. What are the states from which an element of $S$ could possibly be reached in one stage under the application of $u$? This is the weak backprojection of $S$ under $u$:

$$\operatorname{WB}(S,u) = \{x^\prime \in X \;\vert\; \exists \theta \in \Theta(x^\prime,u) f(x^\prime,u,\theta) \in S\},$$ (10.22)

which can also be expressed as

$$\operatorname{WB}(S,u) = \bigcup_{x \in S} \operatorname{WB}(x,u) .$$ (10.23)

Similarly, the strong backprojection of $S$ under $u$ is defined as

$$\operatorname{SB}(S,u) = \{x^\prime \in X \;\vert\; \forall \theta \in \Theta(x^\prime,u), \; f(x^\prime,u,\theta) \in S \} .$$ (10.24)

Note that $\operatorname{SB}(S,u)$ cannot be formed by the union of $SB(x,u)$ over all $x \in S$. Another observation is that for each $x_k \in \operatorname{SB}(S,u_k)$, we have $X_{k+1}(x_k,u_k) \subseteq S$.

Now the dependency on $u$ will be removed. This yields a backprojection of a set $S$. These are states from which there exists an action that possibly reaches $S$. The weak backprojection of $S$ is

$$\operatorname{WB}(S) = \{x^\prime \in X \;\vert\; \exists u \in U(x) x \in \operatorname{WB}(S,u) \},$$ (10.25)

and the strong backprojection of $S$ is

$$\operatorname{SB}(S) = \{x^\prime \in X \;\vert\; \exists u \in U(x) x \in \operatorname{SB}(S,u) \} .$$ (10.26)

Note that $\operatorname{SB}(S) \subseteq \operatorname{WB}(S)$.

Example 10..5 (Backprojections)   Once again, consider the model from the first part of Example 10.1. The backprojection $\operatorname{WB}(0,2)$ represents the set of all states from which $u=2$ can be applied and $x = 0$ is possibly reached; the result is $\operatorname{WB}(0,2) = \{-3,-2,-1\}$. The state 0 cannot be reached with certainty from any state in $\operatorname{WB}(0,2)$. Therefore, $\operatorname{SB}(0,2) = \emptyset$.

Now consider backprojections from the goal, ${X_{G}}= \{-1,0,1\}$, under the action $u=2$. The weak backprojection is

$$\operatorname{WB}({X_{G}},2) = \operatorname{WB}(-1,2) \cup \operatorname{WB}(0,2) \cup \operatorname{WB}(1,2) = \{-4,-3,-2,-1,0\} .$$ (10.27)

The strong backprojection is $\operatorname{SB}({X_{G}},2) = \{-2\}$. From any of the other states in $\operatorname{WB}({X_{G}},2)$, nature could cause the goal to be missed. Note that $\operatorname{SB}({X_{G}},2)$ cannot be constructed by taking the union of $\operatorname{SB}(x,2)$ over every $x \in {X_{G}}$.

Finally, consider backprojections that do not depend on an action. These are $\operatorname{WB}({X_{G}}) = \{-4,-3,\ldots,4\}$ and $\operatorname{SB}({X_{G}}) = {X_{G}}$. In the latter case, all states in ${X_{G}}$ lie in $\operatorname{SB}({X_{G}})$ because $u_T$ can be applied. Without allowing $u_T$, we would obtain $\operatorname{SB}({X_{G}}) = \{-2,2\}$. $\blacksquare$

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 $S$ will be reached with at least probability $p$.