Grid Filter Lab

Fall 2008

Purpose:

The purpose of this lab is as follows: This will be accomplished in an environment similar to the Capture the Flag environment used for the class project.

What you should learn:

When you complete this lab, you should be well-informed in the following two areas: For each of these areas, you should be able to talk and write intelligently about the following:

Description:

Many robots in the world use some combination of sonars and lasers to sense distances to objects.  Although these sensors are useful for providing information about when a robot is too close to an obstacle, it's only been within the last decade that algorithms have existed for taking these sensor readings and turning them into accurate maps of obstacles in the world.  Naturally, the laser readings are more accurate than the sonar readings.

The key breakthrough in using laser range finders to build maps of the environment was the application of Bayes rule to the problem of mapping observations from the laser into estimates of the states of obstacles in the environment.  More specifically, people applied Bayes rule in a sequential choice problem using the extension known as the Bayes filter.  The Bayes filter, in its general form, does not provide enough details to actually build a map of the environment from sensor readings.  In addition to the general filter, robots needed some way to efficiently represent obstacles.  They also needed some way to model the observation process --- something that was accurate enough to allow maps to be built, but simple enough to be computable in realistic time.

In this lab, you'll use a Bayes filter to estimate the locations of obstacles in the environment.  You'll represent obstacles using an occupancy grid and you'll use a very simple sensor model.  (In fact, the observations that you'll make don't match any realistic sensor.  The sensor created in the BZFlag environment is designed so that you can use a very simple sensor model.)  The occupancy grid discretizes the world into a grid of cells.  Let S denote the set of all such cells in the environment.  For each cell, we can conclude that the cell is either occupied or not occupied by an obstacle.  Thus, if we let i and j represent the x index and y index of the cells, then the set of relevant states in the world consists of an "occupied" or "unoccupied" label for each cell.  Thus, S={si,j: si,j = "occupied" or si,j = "unoccupied"}.

As the robot moves around the environment, it has a sensor that can take noisy sensor readings of the cells around it.  For the purposes of this lab, we set this sensor to be a square that is centered on the robot.  The square is known as the sensor footprint of the robot, meaning the set of states surrounding the robot that are sensed.  Outside of this square, no information is obtained about obstacles in the world.  Within this square, information is returned about obstacles in the world, but this information is noisy.  Sometimes the sensor says that a cell is occupied when it is not, and sometimes the sensor says that a cell is unoccupied when it is.  We call these two errors a false alarm and a missed detection, respectively.

The size of the sensor is eight times the length of the robot (actually, the size of the sensor has been changed from 80x80 to 160x160).  (Since we are using tank robots, the size of the sensor is eight times the length of the longest axis of the robot.)  Let L denote the length of the robot, meaning that the sensor square is 8L by 8L in size.  This means that the sensor can see things four robot lengths in front (as measured from the center of the robot), four robot lengths to each side, and four robot lengths behind us.  Interestingly, this sensor can see all cells within this grid; there is no occlusion (like their normally would be with a range sensor, since range sensors typically cannot see through things).

Rounding up L to the nearest integer, we can discretize the sensor square into a 8L  by 8L grid of unit area cells.  The sensor will return one of two readings for each cell within the sensor footprint: a hit or a miss.  Since the sensor cannot see outside of the sensor square, we do not get to observe obstacles throughout the entire environment; there are many cells for which we do not get observations.  Thus, the set of observations is O={hit, miss, no_data} for each cell in the world.

Your job is to translate these observations into estimates of the four corners of all obstacles in the world by applying the Bayes filter.  Since we are assuming that obstacles are placed and sized so that their corners align on integer values, and since we are discretizing the world into cells of unit area, you can apply a form of the Bayes filter known as the Grid Filter.  The term "grid" simply means that we represent states of the world in a grid of x and y values.  For each cell in the grid, you should estimate the probability that it is occupied.  (You automatically get the probability that it is not occupied, since p(s=occupied) = 1-p(s=not occupied).)  You'll update this estimate as you get more observations.  This means that you should apply Bayes rule to translate observations into estimates of the true state.  The pseudo-code for this lab looks something like the following:

for each state si,j of the world
observe oi,j from the set {hit, miss, no_data}
update p(si,j=occupied |oi,j ) = p(oi,j |si,j =occupied) p(si,j=occupied)
move the robot and repeat
When you are confident in your probabilities, set a threshold.  If the probability of it being occupied is high enough, conclude that the cell is occupied.  Then, do a search of all occupied cells to determine where the corner of the obstacle is.  Print out the locations of all four corners of all obstacles in the world.

There are four things that you will need to focus on to get this pseudo-code to work in practice.  First, you will need to create a likelihood.  Nominally, the probability of a false alarm is 0.6, meaning that 60% of the time the sensor will think that an unoccupied cell is occupied.  Also, the probability of a correct detection is 0.95, meaning that 95% of the time the sensor will correctly sense when a cell is occupied.  These numbers translate directly into simple estimates of a likelihood function.

Second, you can improve the efficiency of your algorithm by noting that obstacles are made up of several occupied cells.  If you are clever, you can observe that the probability of a cell being occupied is pretty low if none of the cells around it are occupied, and it's pretty high if all of the cells around it are occupied.  Although you don't need to do this to get the lab to work, it may make your algorithm converge more quickly.  However, it may also take more time to implement since you will need to look at cells around a particular cell to update its posterior probability.

Third, you will have to start with a prior probability that makes sense to you.  I started with a high prior probability of a cell being occupied since the likelihood that I used did a better job concluding that a cell was not occupied than that a cell was occupied.  You should experiment with a few things to see what works for you.

Fourth, you should be smart in how you have your robots move in the environment so that you build up your map as quickly as possible.  The MATLAB code that implements the Grid Filter has the robot move in pseudo-random directions.  This isn't very smart and you should be able to do much better.

What you will need:

If you built BZFlag on your own Linux machine then re-download the following files, place them in your bzflag/src/bzrobots/ directory, and run "make" in that directory: For instructions on how to get the occupational grid from BZRobots, visit the wiki at http://cs470.pbwiki.com/Occupancy+Grid

What you should turn in:

When you are done, you pass the lab off to the TA in person.  The TA will check to see that you correctly locate obstacles in two or three different worlds.  The TA will also have you show where you implemented the Grid Filter; you'll be asked to explain how you implemented the likelihoods.  After passing the lab off with the TA, you should send a lab write-up to cs470ta@cs.byu.edu.    The lab write-up should include:
  1. the amount of time you and your partner each spent on the lab,
  2. a summary of what you learned,
  3. a discussion of the types of likelihoods you tried in the lab,
  4. a discussion of what happens when the sensor has different parameters (ex. it has a bigger range, it returns noisier estimates, it only detects moving objects, etc),
  5. a discussion of how you would apply the grid filter in the capture the flag tournament, especially given the fact that you might get tagged if you spend too much time wandering around the opponent's territory without having a good map.
This write-up can be either an email attachment or just regular ol' text in the body of your email.  Do, however, check for spelling, grammar, and readability.

Lab 3 Passoff Sheet Posted:

You can download it here.