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.

(12.14) |

the collection of all states in . Suppose that the action sequence is applied. In each case, a motion occurs, which results in the observation history .

After the first action, , the history I-state is . The nondeterministic I-state is

(12.15) |

which means that any position is still possible, but the successful forward motion removed some orientations from consideration. For example, is not possible because the previous state would have to be directly south of , which is an obstacle.

After the second action, ,

(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 or .

After is applied, the only possibility remaining is that must have been . This yields

(12.17) |

which exactly localizes the robot: It is at position facing north. After the final action is applied it is clear that

(12.18) |

which means that in the final state, , the robot is at position 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.

Suppose that the robot is initially in position facing east. If the action sequence 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 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 heading west, and 2) from heading south. A similar situation occurs from facing east, if the sequence 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 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.

Steven M LaValle 2012-04-20