Solving the passive localization problem

The passive problem requires only that the nondeterministic I-states are computed correctly as the robot moves. A couple of examples of this are given.

Example 12..1 (An Easy Localization Problem)   Consider the example given in Figure 12.2a. Suppose that the robot is initially placed in position $1$ facing east. The initial condition is ${\eta_0}= X$, which can be represented as

$${\eta_0}= 1^{\psfig{figure=figs/locplus15.eps,width=3mm}}\cup 2^{... .../locplus15.eps,width=3mm}}\cup 5^{\psfig{figure=figs/locplus15.eps,width=3mm}},$$ (12.14)

the collection of all $20$ states in $X$. Suppose that the action sequence $({\rm F},{\rm L},{\rm F},{\rm L})$ is applied. In each case, a motion occurs, which results in the observation history $(y_2,y_3,y_4,y_5) = (1,1,1,1)$.

After the first action, $u_1 = {\rm F}$, the history I-state is ${\eta}_2 = (X,{\rm F},1)$. The nondeterministic I-state is

$$X_2({\eta}_2) = 1^{\psfig{figure=figs/locplus4.eps,width=3mm}}\cu... ...gs/locplus3.eps,width=3mm}}\cup 5^{\psfig{figure=figs/locplus4.eps,width=3mm}},$$ (12.15)

which means that any position is still possible, but the successful forward motion removed some orientations from consideration. For example, $1^{\psfig{figure=figs/locplus2.eps,width=3mm}}$ is not possible because the previous state would have to be directly south of $1$, which is an obstacle.

After the second action, $u_2 = {\rm L}$,

$$X_3({\eta}_3) = 3^{\psfig{figure=figs/locplus2.eps,width=3mm}}\cup 5^{\psfig{figure=figs/locplus4.eps,width=3mm}},$$ (12.16)

which yields only two possible current states. This can be easily seen in Figure 12.2a by observing that there are only two states from which a forward motion can be followed by a left motion. The initial state must have been either $1^{\psfig{figure=figs/locplus1.eps,width=3mm}}$ or $3^{\psfig{figure=figs/locplus2.eps,width=3mm}}$.

After $u_3 = {\rm F}$ is applied, the only possibility remaining is that $x_3$ must have been $3^{\psfig{figure=figs/locplus2.eps,width=3mm}}$. This yields

$$X_4({\eta}_4) = 4^{\psfig{figure=figs/locplus2.eps,width=3mm}},$$ (12.17)

which exactly localizes the robot: It is at position $4$ facing north. After the final action $u_4 = {\rm L}$ is applied it is clear that

$$X_5({\eta}_5) = 5^{\psfig{figure=figs/locplus4.eps,width=3mm}},$$ (12.18)

which means that in the final state, $x_5$, the robot is at position $1$ facing west. Once the exact robot state is known, no new uncertainty will accumulate because the effects of all actions are predictable. Although it was not shown, it is also possible to prune the possible states by the execution of actions that do not produce motions. $\blacksquare$

Example 12..2 (A Problem that Involves Symmetries)   Now extend the map from Figure 12.2a so that it forms a loop as shown in Figure 12.2b. In this case, it is impossible to determine the precise location of the robot. For simplicity, consider only actions that produce motion (convince yourself that allowing the other actions cannot fix the problem).

Suppose that the robot is initially in position $1$ facing east. If the action sequence $({\rm F},{\rm L},{\rm F},{\rm L},\ldots)$ is executed, the robot will travel around in cycles. The problem is that it is also possible to apply the same action sequence from position $3$ facing north. Every action successfully moves the robot, which means that, to the robot, the information appears identical. The other two cases in which this sequence can be applied to travel in cycles are 1) from $5$ heading west, and 2) from $7$ heading south. A similar situation occurs from $2$ facing east, if the sequence $({\rm L},{\rm F},{\rm L},{\rm F},\ldots)$ is applied. Can you find the other three starting states from which this sequence moves the robot at every stage? Similar symmetries exist when traveling in clockwise circles and making right turns instead of left turns.

The state space for this problem contains $32$ states, obtained from four directions at each position. After executing some motions, the nondeterministic I-state can be reduced down to a symmetry class of no more than four possible states. How can this be proved? One way is to use the algorithm that is described next. $\blacksquare$