Homework 4: histogram filter

Due 4/22/2012 (Monday).

This homework assignment is to use a histogram filter to partially localize the robot.

The figure illustrates the environment. There are 22 possible states in which the robot might be represented by the open squares. The shaded areas are obstacles.

The position of the robot is not observed. However, on each time step, the robot observes the color of the cell in which it is located. (Each cell is either yellow or pink, as indicated in the diagram.)

Although the robot is not aware of it (at first), it takes the path indicated by the eight sequential numbers in the figure. (On the first time step, the robot is in the location labelled "1"; on the second time step, it is at "2", and so on.) After eight time steps, estimation terminates.

Prior to the observation at time 1, the belief state is a uniform distribution over the 22 states. The process model is as follows: on each time step, there is a 0.1 chance that the robot fails to move to the next state and instead remains in the current state. The observation model is as follows: there is a 0.2 chance of observing the color of a cell incorrectly.

The histogram filter should execute for eight time steps.

The programming should be done in MATLAB or Octave. Students may get access to MATLAB here. Alternatively, students may code in Python (using Numpy). If the student would rather code in a different language, please see Dr Platt.

Please submit the following:

1. a PDF file containing 9 plots of the belief state distribution over the state space. The first plot shold show the prior distribution and the other eight plots should show the distribution after executing the histogram filter update on that time step. You may display this probability distribution as a numerical array or as a plot where the probability of cells is denoted by gray level.

Also, submit the following: 1) A text file showing output from a sample run of your code. 2) A directory containing all source code for your project. 3) A short readme file enumerating the important files in your submission.

Notes and updates:

None yet...