11.2.3 Probabilistic Information Spaces

This section defines the I-map ${{\kappa}_{prob}}$ from Figure 11.3, which converts each history I-state into a probability distribution over $X$. A Markov, probabilistic model is assumed in the sense that the actions of nature only depend on the current state and action, as opposed to state or action histories. The set union and intersection of (11.30) and (11.31) are replaced in this section by marginalization and Bayes' rule, respectively. In a sense, these are the probabilistic equivalents of union and intersection. It will be very helpful to compare the expressions from this section to those of Section 11.2.2.

Rather than write ${{\kappa}_{prob}}({\eta})$, standard probability notation will be applied to obtain $P(x\vert{\eta})$. Most expressions in this section of the form $P(x_k\vert\cdot)$ have an analogous expression in Section 11.2.2 of the form $X_k(\cdot)$. It is helpful to recognize the similarities.

The first step is to construct probabilistic versions of $H$ and $F$. These are $P(x_k\vert y_k)$ and $P(x_{k+1}\vert x_k,u_k)$, respectively. The latter term was given in Section 10.1.1. To obtain $P(x_k\vert y_k)$, recall from Section 11.1.1 that $P(y_k\vert x_k)$ is easily derived from $P(\psi_k\vert x_k)$. To obtain $P(x_k\vert y_k)$, Bayes' rule is applied:

$$P(x_k\vert y_k) = {P(y_k\vert x_k) P(x_k) \over P(y_k)} = {P(y_k\... ...k) P(x_k) \over \displaystyle\strut \sum_{x_k \in X} P(y_k\vert x_k) P(x_k) } .$$ (11.35)

In the last step, $P(y_k)$ was rewritten using marginalization, (9.8). In this case $x_k$ appears as the sum index; therefore, the denominator is only a function of $y_k$, as required. Bayes' rule requires knowing the prior, $P(x_k)$. In the coming expressions, this will be replaced by a probabilistic I-state.

Now consider defining probabilistic I-states. Each is a probability distribution over $X$ and is written as $P(x_k\vert{\eta}_k)$. The initial condition produces $P(x_1)$. As for the nondeterministic case, probabilistic I-states can be computed inductively. For the base case, the only new piece of information is $y_1$. Thus, the probabilistic I-state, $P(x_1\vert{\eta}_1)$, is $P(x_1\vert y_1)$. This is computed by letting $k=1$ in (11.35) to yield

$$P(x_1\vert{\eta}_1) = P(x_1\vert y_1) = {P(y_1\vert x_1) P(x_1) \over \displaystyle\strut \sum_{x_1 \in X} P(y_1\vert x_1) P(x_1) } .$$ (11.36)

Now consider the inductive step by assuming that $P(x_k\vert{\eta}_k)$ is given. The task is to determine $P(x_{k+1} \vert {\eta}_{k+1})$, which is equivalent to $P(x_{k+1} \vert {\eta}_k,u_k,y_{k+1})$. As in Section 11.2.2, this will proceed in two parts by first considering the effect of $u_k$, followed by $y_{k+1}$. The first step is to determine $P(x_{k+1}\vert{\eta}_k,u_k)$ from $P(x_k\vert{\eta}_k)$. First, note that

$$P(x_{k+1} \vert {\eta}_k,x_k, u_k) = P(x_{k+1} \vert x_k, u_k)$$ (11.37)

because ${\eta}_k$ contains no additional information regarding the prediction of $x_{k+1}$ once $x_k$ is given. Marginalization, (9.8), can be used to eliminate $x_k$ from $P(x_{k+1}\vert x_k,u_k)$. This must be eliminated because it is not given. Putting these steps together yields

$$\begin{split}P(x_{k+1}\vert{\eta}_k,u_k) & = \sum_{x_k \in X}... ...in X} P(x_{k+1}\vert x_k,u_k) P(x_k\vert{\eta}_k) , \end{split}$$ (11.38)

which expresses $P(x_{k+1}\vert{\eta}_k,u_k)$ in terms of given quantities. Equation (11.38) can be considered as the probabilistic counterpart of (11.30).

The next step is to take into account the observation $y_{k+1}$. This is accomplished by making a version of (11.35) that is conditioned on the information accumulated so far: ${\eta}_k$ and $u_k$. Also, $k$ is replaced with $k+1$. The result is

$$P(x_{k+1}\vert y_{k+1},{\eta}_k,u_k) = {P(y_{k+1}\vert x_{k+1},{\... ...+1} \in X} P(y_{k+1}\vert x_{k+1},{\eta}_k,u_k) P(x_{k+1}\vert{\eta}_k,u_k) } .$$ (11.39)

This can be considered as the probabilistic counterpart of (11.31). The left side of (11.39) is equivalent to $P(x_{k+1} \vert {\eta}_{k+1})$, which is the probabilistic I-state for stage $k+1$, as desired. There are two different kinds of terms on the right. The expression for $P(x_{k+1}\vert{\eta}_k,u_k)$ is given in (11.38). Therefore, the only remaining term to calculate is $P(y_{k+1}\vert x_{k+1},{\eta}_k,u_k)$. Note that

$$P(y_{k+1}\vert x_{k+1},{\eta}_k,u_k) = P(y_{k+1}\vert x_{k+1})$$ (11.40)

because the sensor mapping depends only on the state (and the probability model for the nature sensing action, which also depends only on the state). Since $P(y_{k+1}\vert x_{k+1})$ is specified as part of the sensor model, we have now determined how to obtain $P(x_{k+1} \vert {\eta}_{k+1})$ from $P(x_k\vert{\eta}_k)$, $u_k$, and $y_{k+1}$. Thus, ${\cal I}_{prob}$ is another I-space that can be treated as just another state space.

The probabilistic I-space ${\cal I}_{prob}$ (shown in Figure 11.3) is the set of all probability distributions over $X$. The update expressions, (11.38) and (11.39), establish that the I-map ${{\kappa}_{prob}}$ is sufficient, which means that the planning problem can be expressed entirely in terms of ${\cal I}_{prob}$, instead of maintaining histories. A goal region can be specified as constraints on the probabilities. For example, from some particular $x \in X$, the goal might be to reach any probabilistic I-state for which $P(x_k \vert {\eta}_k) > 1/2$.

Figure 11.6: The probabilistic I-space for the three-state example is a 2-simplex embedded in ${\mathbb{R}}^3$. This simplex can be projected into ${\mathbb{R}}^2$ to yield the depicted triangular region in ${\mathbb{R}}^2$.

Example 11..14 (Three-State Example Revisited)   Now return to Example 11.13, but this time use probabilistic models. For a probabilistic I-state, let $p_i$ denote the probability that the current state is $i \in X$. Any probabilistic I-state can be expressed as $(p_0,p_1,p_2) \in {\mathbb{R}}^3$. This implies that the I-space can be nicely embedded in ${\mathbb{R}}^3$. By the axioms of probability (given in Section 9.1.2), $p_0+p_1+p_2 = 1$, which can be interpreted as a plane equation in ${\mathbb{R}}^3$ that restricts ${\cal I}_{prob}$ to a 2D set. Also following the axioms of probability, for each $i \in \{0,1,2\}$, $0 \leq p_i \leq 1$. This means that ${\cal I}_{prob}$ is restricted to a triangular region in ${\mathbb{R}}^3$. The vertices of this triangular region are $(0,0,1)$, $(0,1,0)$, and $(1,0,0)$; these correspond to the three different ways to have perfect state information. In a sense, the distance away from these points corresponds to the amount of uncertainty in the state. The uniform probability distribution $(1/3,1/3,1/3)$ is equidistant from the three vertices. A projection of the triangular region into ${\mathbb{R}}^2$ is shown in Figure 11.6. The interpretation in this case is that $p_0$ and $p_1$ specify a point in ${\mathbb{R}}^2$, and $p_2$ is automatically determined from $p_2 = 1 - p_0 - p_1$.

The triangular region in ${\mathbb{R}}^3$ is an uncountably infinite set, even though the history I-space is countably infinite for a fixed initial condition. This may seem strange, but there is no mistake because for a fixed initial condition, it is generally impossible to reach all of the points in ${\cal I}_{prob}$. If the initial condition can be any point in ${\cal I}_{prob}$, then all of the probabilistic I-space is covered because ${{\cal I}_0}= {\cal I}_{prob}$, in which ${{\cal I}_0}$ is the initial condition space.. $\blacksquare$