Many interesting lessons about realistic localization problems can be learned by first studying a discrete version of localization. Problems that may or may not be solvable can be embedded in more complicated problems, which may even involve continuous state spaces. The discrete case is often easier to understand, which motivates its presentation here. To simplify the presentation, only the nondeterministic I-space will be considered; see Section 12.2.3 for the probabilistic case.
Suppose that a robot moves on a 2D grid, which was introduced in Example 2.1. It has a map of the grid but does not know its initial location or orientation within the grid. An example is shown in Figure 12.2a.
To formulate the problem, it is helpful to include in the state both the position of the robot and its orientation. Suppose that the robot may be oriented in one of four directions, which are labeled N, E, W, and S, for ``north,'' ``east,'' ``west,'' and ``south,'' respectively. Although the robot is treated as a point, its orientation is important because it does not have a compass. If it chooses to move in a particular direction, such as straight ahead, it does not necessarily know which direction it will be heading with respect to the four directions.
Thus, a state, , is written as , in which is a position and is one of the four directions. A set of states at the same position will be denoted with special superscripts that point in the possible directions. For example, indicates the set of states for which and the direction may be north (N) or east (E), because the superscript points in the north and east directions.
The robot is given four actions,
The robot has one simple sensor that can only detect whether it was able to move in the direction that was attempted. The sensor space is , and the sensor mapping is . This yields if and place the robot at different positions, and otherwise. Thus, the sensor indicates whether the robot has moved after the application of an action.
Nondeterministic uncertainty will be used, and the initial I-state is always assumed to be (this can easily be extended to allow starting with any nonempty subset of ). A history I-state at stake in its general form appears as
The passive localization problem starts with a given map, such as the one shown in Figure 12.2a, and a history I-state, , and computes the nondeterministic I-state . The active localization problem is to compute some and sequence of actions, , such that the nondeterministic I-state is as small as possible. In the best case, might become a singleton set, which means that the robot knows its position and orientation on the map. However, due to symmetries, which will be presented shortly in an example, it might not be possible.