CSE 321: Discrete Structures
February 23, 2001
Due: Wednesday, February 28
Reading Assignment: Rosen, Sections 6.1 - 6.5
- Bayes' rule: Rosen, page 305, problems 40 and 42. Take
a close look at problem 41.
- 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
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
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
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:
|P(L = l | o)
All we need to know are the values for
and P(L =
l). P(L = l is given by the distribution before the robot
made the observation (given in Equation (1)).
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
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 lDL 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 lDR,lWL and lWR. For
example, lWR are positions 0, 1 and 3. Now we can summarize the
robot's ability to detect doors and walls as follows:
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 = lWL),
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.
- 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.
- 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 = li). This
probability distribution combines the fact that the robot has
detected a door to its left and a wall to its right.
- Compute the mean and the variance of the two previous
distributions over possible robot positions.
- Rosen, Section 6.1, problem 4.
- Rosen, Section 6.1, problem 20.
- 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
- 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?