Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

#### 6.5.2.1 Localization

Suppose a robot wants to determine its location based on its history of
actions and it sensor readings. This is the problem of **localization**.

Figure 6.15 shows a belief-network
representation of the localization problem. There is a variable
*Loc _{i}* for each time

*i*, which represents the robot's location at time

*i*. There is a variable

*Obs*for each time

_{i}*i*, which represents the robot's observation made at time

*i*. For each time

*i*, there is a variable

*Act*that represents the robot's action at time

_{i}*i*. In this section, assume that the robot's actions are observed (we consider the case in which the robot chooses its actions in Chapter 9).

This model assumes the following dynamics: At time *i*, the robot is at location
*Loc _{i}*, it observes

*Obs*, then it acts, it observes its action

_{i}*Act*, and time progresses to time

_{i}*i+1*, where it is at location

*Loc*. Its observation at time

_{i+1}*t*only depends on the state at time

*t*. The robot's location at time

*t+1*depends on its location at time

*t*and its action at time

*t*. Its location at time

*t+1*is conditionally independent of previous locations, previous observations, and previous actions, given its location at time

*t*and its action at time

*t*.

The localization problem is to determine the robot's location as a function of its observation history:

P(Loc_{t}| Obs_{0}, Act_{0}, Obs_{1}, Act_{1}, ..., Act_{t-1},Obs_{t}).

**Example 6.28:**Consider the domain depicted in Figure 6.16.

There is a circular corridor, with 16
locations numbered 0 to 15. The robot is at one of these
locations at each time. This is modeled with, for every time *i*,
a variable *Loc _{i}* with domain

*{0,1,...,15}*.

- There are doors at positions 2, 4, 7, and 11 and no doors at other locations.
- The robot has a sensor that can noisily sense whether or not it is in front of a
door. This is modeled with a variable
*Obs*for each time_{i}*i*, with domain*{door,nodoor}*. Assume the following conditional probabilities:*P(Obs=door | atDoor) = 0.8**P(Obs=door | notAtDoor) = 0.1*where

*atDoor*is true at states 2, 4, 7, and 11 and*notAtDoor*is true at the other states.Thus, the observation is partial in that many states give the same observation and it is noisy in the following way: In 20% of the cases in which the robot is at a door, the sensor falsely gives a negative reading. In 10% of the cases where the robot is not at a door, the sensor records that there is a door.

- The robot can, at each time, move left, move right, or stay still. Assume that the
*stay still*action is deterministic, but the dynamics of the moving actions are stochastic. Just because it carries out the*goRight*action does not mean that it actually goes one step to the right - it is possible that it stays still, goes two steps right, or even ends up at some arbitrary location (e.g., if someone picks up the robot and moves it). Assume the following dynamics, for each location*L*:*P(Loc*_{t+1}= L | Act_{t}=goRight ∧Loc_{t}=L) = 0.1*P(Loc*_{t+1}= L+1 | Act_{t}=goRight ∧Loc_{t}=L) = 0.8*P(Loc*_{t+1}= L+2 | Act_{t}=goRight ∧Loc_{t}=L) = 0.074*P(Loc*L'_{t+1}= L' | Act_{t}=goRight ∧Loc_{t}=L) = 0.002 for any other location*.*All location arithmetic is modulo 16. The action

*goLeft*works the same but to the left.

The robot starts at an unknown location and must determine its location.

It may seem as though the domain is too ambiguous, the sensors are too noisy, and the dynamics is too stochastic to do anything. However, it is possible to compute the probability of the robot's current location given its history of actions and observations.

Figure 6.17 gives the robot's probability distribution over its locations, assuming it starts with no knowledge of where it is and experiences the following observations: observe door, go right, observe no door, go right, and then observe door. Location 4 is the most likely current location, with posterior probability of 0.42. That is, in terms of the network of Figure 6.15:

P(Loc _{2}=4| Obs _{0}=door,Act_{0}=goRight,Obs_{1}=nodoor,Act _{1}=goRight,Obs_{2}=door)=0.42

Location 7 is the second most likely current location, with posterior probability of 0.141. Locations 0, 1, 3, 8, 12, and 15 are the least likely current locations, with posterior probability of 0.011.

You can see how well this works for other sequences of observations by using the applet at the book web site.

**Example 6.29:**Let us augment Example 6.28 with another sensor. Suppose that, in addition to a door sensor, there is also a light sensor. The light sensor and the door sensor are conditionally independent given the state. Suppose the light sensor is not very informative; it can only give yes-or-no information about whether it can detect any light, and that this is very noisy, and depends on the location.

This is modeled in Figure 6.18 using the following variables:

*Loc*is the robot's location at time_{t}*t*.*Act*is the robot's action at time_{t}*t*.*D*is the door sensor value at time_{t}*t*.*L*is the light sensor value at time_{t}*t*.

Conditioning on both *L _{i}* and

*D*lets it combine information from the light sensor and the door sensor. This is an instance of

_{i}**sensor fusion**. It is not necessary to define any new mechanisms for sensor fusion given the belief-network model; standard probabilistic inference combines the information from both sensors.