CSE 321: Discrete Structures
Assignment #6
February 23, 2001
Due: Wednesday, February 28

Reading Assignment: Rosen, Sections 6.1 - 6.5

Problems:

1.

Bayes' rule: Rosen, page 305, problems 40 and 42. Take a close look at problem 41.

2.

Mobile robot localization: Bayes' rule underlies all modern AI systems for probabilistic inference. One application of this rule is the update of a robot's position estimate based on new sensor information. To see, look at the example below.

The robot is placed in the hallway facing east and it does not know where it is (it only knows its orientation). The hallway is tessellated and the robot can be in any of the five squares (always facing east). Assume that the width of each square is 1 meter. Then the squares are numbered by their distance from the beginning of the hallway. Given the tessellation of the hallway, we can represent the position of the robot by a random variable L. This variable takes on values between 0 and 4, depending on the robot's current position. At each point in time, the robot's position estimate is represented by a probability distribution over all possible locations. In the beginning, the robot does not know where it is. This can be represented by the following distribution:

P(L = 0) = P(L = 1) = P(L = 2) = P(L = 3) = P(L = 4) = 1/5 (1)

The robot has a camera that can be pointed to the left or to the right. In order to determine where it is, the robot tries to detect doors by looking either to the left or to the right (note that the robot faces east). As you can see in the figure, there are four doors in the hallway. Now we want to update the robot's position estimate based on an observation, i.e. we want to compute the probability distribution of L given an observation. In general, we denote observations by o (where i ranges over the possible observations). The probability distribution after the observation can be represented by P(L = l | o) (l is a number between 0 and 4). However, it is not easy to compute this value directly. In mobile robot localization we use Bayes' rule to compute this value:

$$\frac{P(o \mid L = l) P(L = l)}{\sum_{i=1}^n P(o \mid L = l_i) P(L = l_i)}$$ P(L = l | o) = (2)

All we need to know are the values for $P(o \mid L = l)$ and P(L = l). P(L = l is given by the distribution before the robot made the observation (given in Equation (1)). The term $P(o \mid L = l)$ describes the probability of making an observation given the position of the robot. In our example, we have four possible observations: The robot can detect a door to its left, it can detect a door to its right, it can detect a wall to its left, or it can detect a wall to its right. We will denote these four observations by DL, DR, WL, and WR (i.e.these are the four possible values of o). To determine $P(o \mid L = l)$, the probability of making observation o at location l, we make the following assumption about the robot's ability to detect doors and walls. If the robot points the camera towards a door, then it successfully detects this door with probability 0.8. However, it sometimes confuses the door for a wall, i.e. with probability 0.2 it erroneously detects a wall, even though it looks at a door. Detecting walls is easier, therefore, the probability of detecting a wall if the robot is looking at a wall is 0.9. With probability 0.1 it thinks it detects a door even though it looks at a wall. There are four different types of positions in the hallway: Let l_DL denote any position in the hallway, at which there is a door to the left of the robot (these are positions 1 and 4 in our example). The other three types are given by l_DR,l_WL and l_WR. For example, l_WR are positions 0, 1 and 3. Now we can summarize the robot's ability to detect doors and walls as follows:

$$\begin{eqnarray*}P( DL \vert L = l_{DL}) & = & 0.8\\ P( DL \vert L = l_{WL}) &... ...ert L = l_{WR}) & = & 0.9\\ P( WR \vert L = l_{DR}) & = & 0.1 \end{eqnarray*}$$

For example, the probability that the robot detects a door to its left if it is at location 3, is determined by P( DL | L = l_WL), since there is actually a wall to the robot's left side at position 3. Now we can start to estimate the position of the robot.

(a)

Assume that the robot does not know where it is (P(L) is given by equation (1)). The robot detects a door to it's left, i.e. it makes the observation DL. What is the distribution of the robot's position estimate after this observation? Use a calculator (or write a computer program) and Bayes' rule.

(b)

Assume the robot has already updated its position estimate based on the first observation DL. Now the robot turns the camera and looks to the right. What is the robot's position estimate, if it detects a wall to the right? Use the distribution you computed in the previous step to represent P(L = l_i). This probability distribution combines the fact that the robot has detected a door to its left and a wall to its right.

(c)

Compute the mean and the variance of the two previous distributions over possible robot positions.

3.

Rosen, Section 6.1, problem 4.

4.

Rosen, Section 6.1, problem 20.

5.

Extra credit:

• Consider the robot localization example. The robot has already detected a door to its left and a wall to its right. Now it points the camera back to the left and, oops, it detects wall! Compute the new probability distribution and check whether the new values make sense.
• We might have assumed that the robot never fails when it detects a door or a wall. How could you represent such a sensor model using the conditional probabilities? What would the distributions look like after the observations DL, WR and WL?