Discrete problems

First consider adding probabilities to the discrete grid problem of Section 12.2.1. A state is once again expressed as $x = (p,d)$. The initial condition is a probability distribution, $P(x_1)$, over $X$. One reasonable choice is to make $P(x_1)$ a uniform probability distribution, which makes each direction and position equally likely. The robot is once again given four actions, but now assume that nature interferes with state transitions. For example, if $u_k = F$, then perhaps with high probability the robot moves forward, but with low probability it may move right, left, or possibly not move at all, even if it is not blocked.

The sensor mapping from Section 12.2.1 indicated whether the robot moved. In the current setting, nature can interfere with this measurement. With low probability, it may incorrectly indicate that the robot moved, when in fact it remained stationary. Conversely, it may also indicate that the robot remained still, when in fact it moved. Since the sensor depends on the previous two states, the mapping is expressed as

$$y_k = h(x_k,x_{k-1},\psi_k) .$$ (12.19)

With a given probability model, $P(\psi_k)$, this can be expressed as $P(y_k\vert x_k,x_{k-1})$.

To solve the passive localization problem, the expressions from Section 11.2.3 for computing the derived I-states are applied. If the sensor mapping used only the current state, then (11.36), (11.38), and (11.39) would apply without modification. However, since $h$ depends on both $x_k$ and $x_{k-1}$, some modifications are needed. Recall that the observations start with $y_2$ for this sensor. Therefore, $P(x_1\vert{\eta}_1) = P(x_1 \vert y_1) = P(x_1)$, instead of applying (11.36).

After each stage, $P(x_{k+1} \vert {\eta}_{k+1})$ is computed from $P(x_k\vert{\eta}_k)$ by first applying (11.38) to take into account the action $u_k$. Equation (11.39) takes into account the sensor observation, $y_{k+1}$, but $P(y_{k+1}\vert x_{k+1},{\eta}_k,u_k)$ is not given because the sensor mapping also depends on $x_{k-1}$. It reduces using marginalization as

$$P(y_k \vert {\eta}_{k-1},u_{k-1},x_k) = \sum_{x_{k-1} \in X} P(y_... ...t {\eta}_{k-1},u_{k-1},x_{k-1},x_k) P(x_{k-1} \vert {\eta}_{k-1},u_{k-1},x_k) .$$ (12.20)

The first factor in the sum can be reduced to the sensor model,

$$P(y_k \vert {\eta}_{k-1},u_{k-1},x_{k-1},x_k) = P(y_k \vert x_{k-1},x_k),$$ (12.21)

because the observations depend only on $x_{k-1}$, $x_k$, and the nature sensing action, $\psi_k$. The second term in (12.20) can be computed using Bayes' rule as

$$P(x_{k-1} \vert {\eta}_{k-1},u_{k-1},x_k) = {P(x_k \vert {\eta}_{... ..._k \vert {\eta}_{k-1},u_{k-1},x_{k-1}) P(x_{k-1} \vert {\eta}_{k-1},u_{k-1}) },$$ (12.22)

in which $P(x_k \vert {\eta}_{k-1},u_{k-1},x_{k-1})$ simplifies to $P(x_k \vert u_{k-1},x_{k-1})$. This is directly obtained from the state transition probability, which is expressed as $P(x_{k+1}\vert x_k,u_k)$ by shifting the stage index forward. The term $P(x_{k-1} \vert {\eta}_{k-1},u_{k-1})$ is given by (11.38). The completes the computation of the probabilistic I-states, which solves the passive localization problem.

Solving the active localization problem is substantially harder because a search occurs on ${\cal I}_{prob}$. The same choices exist as for the discrete localization problem. Computing an information-feedback plan over the whole I-space ${\cal I}_{prob}$ is theoretically possible but impractical for most environments. The search-based idea that was applied to incrementally grow a directed graph in Section 12.2.1 could also be applied here. The success of the method depends on clever search heuristics developed for this particular problem.