## 12.2.1 Discrete Localization

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, (12.11)

which represent forward,'' backward,'' right motion,'' and left motion,'' respectively. These motions occur with respect to the current orientation of the robot, which may be unknown. See Figure 12.2b. For the action, the robot moves forward one grid element and maintains its orientation. For the action, the robot changes its orientation by degrees and then moves forward one grid element. For the R action, the robot turns right by degrees and then moves forward one grid element. The L action behaves similarly. If it is not possible to move because of an obstacle, it is assumed that the robot changes its orientation (in the case of B, R, or L) but does not change its position. This is depicted in Figure 12.3a.

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 (12.12)

One special adjustment was made in comparison to (11.14). There is no observation because the sensor mapping requires a previous state to report a value. Thus, the observation history starts with . An example history I-state for stage is (12.13)

in which , , and .

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.

Subsections
Steven M LaValle 2012-04-20