Probabilistic forward projections

The probabilistic forward projection can be considered as a Markov process because the ``decision'' part is removed once the actions are given. Suppose that $ x_k$ is given and $ u_k$ is applied. What is the probability distribution over $ x_{k+1}$? This was already specified in (10.6) and is the one-stage forward projection. Now consider the two-stage probabilistic forward projection, $ P(x_{k+2}\vert x_k,u_k,u_{k+1})$. This can be computed by marginalization as

$\displaystyle P(x_{k+2}\vert x_k,u_k,u_{k+1}) = \sum_{x_{k+1} \in X} P(x_{k+2}\vert x_{k+1},u_{k+1}) P(x_{k+1}\vert x_k,u_k) .$ (10.13)

Computing further forward projections requires nested summations, which marginalize all of the intermediate states. For example, the three-stage forward projection is

\begin{displaymath}\begin{split}P(x_{k+3}\vert x_k,u_k,& u_{k+1},u_{k+2}) =  &...
...+2}\vert x_{k+1},u_{k+1}) P(x_{k+1}\vert x_k,u_k) . \end{split}\end{displaymath} (10.14)

A convenient expression of the probabilistic forward projections can be obtained by borrowing nice algebraic properties from linear algebra. For each action $ u \in U$, let its state transition matrix $ M_u$ be an $ n \times n$ matrix, for $ n
= \vert X\vert$, of probabilities. The matrix is defined as

$\displaystyle M_u = \begin{pmatrix}m_{1,1} & m_{1,2} & \cdots & m_{1,n}  m_{2...
...s & \vdots & & \vdots  m_{n,1} & m_{n,2} & \cdots & m_{n,n}  \end{pmatrix},$ (10.15)

in which

$\displaystyle m_{i,j} = P(x_{k+1} = i \; \vert \; x_k = j, \;u) .$ (10.16)

For each $ j$, the $ j$th column of $ M_u$ must sum to one and can be interpreted as the probability distribution over $ X$ that is obtained if $ u_k$ is applied from state $ x_k = j$.

Let $ v$ denote an $ n$-dimensional column vector that represents any probability distribution over $ X$. The product $ M_u v$ yields a column vector that represents the probability distribution over $ X$ that is obtained after starting with $ v$ and applying $ u$. The matrix multiplication performs $ n$ inner products, each of which is a marginalization as shown in (10.13). The forward projection at any stage, $ k$, can now be expressed using a product of $ k-1$ state transition matrices. Suppose that $ {\tilde{u}}_{k-1}$ is fixed. Let $ v = [0 \; 0 \; \cdots 0 \; 1 \; 0 \; \cdots \; 0]$, which indicates that $ x_1$ is known (with probability one). The forward projection can be computed as

$\displaystyle v^\prime = M_{u_{k-1}} M_{u_{k-2}} \cdots M_{u_2} M_{u_1} v .$ (10.17)

The $ i$th element of $ v^\prime$ is $ P(x_k = i \;\vert\; x_1,
{\tilde{u}}_{k-1})$.

Example 10..4 (Probabilistic Forward Projections)   Once again, use the first model from Example 10.1; however, now assign probability $ 1/3$ to each nature action. Assume that, initially, $ x_1 =
0$, and $ u=2$ is applied in every stage. The one-stage forward projection yields probabilities

$\displaystyle [1/3 \;\; 1/3 \;\; 1/3]$ (10.18)

over the sequence of states $ (1,2,3)$. The two-stage forward projection yields

$\displaystyle [1/9 \;\; 2/9 \;\; 3/9 \;\; 2/9 \;\; 1/9]$ (10.19)

over $ (2,3,4,5,6)$. $ \blacksquare$

Steven M LaValle 2020-08-14