MP3 Lost in Space (Particle Filters)

Background Story

The robot BB-8 is kidnapped by Galactic Empire and have been thrown into a maze on the Death Star. Luckily, he is able to find a map of the maze from the Death Star Network. But he can not locate where he is. BB-8 carries four ultrasonic sensors pointing towards front, back, left and right, so he can measure the distance to walls on the four directions.

Your task is to implement a particle filter in 2 dimensional space and send it to BB-8 to help him localize his position and escape.

You may work in a group of two freedom fighters. Each group only needs to submit once on compass 2g.

Mission Preparation

  • Just like in the last MP, download the files from GitLab repo:
git clone
  • There should be two files in the repo: “maze.npy” contains the map sent back by BB-8; the other jupyter file is where you develop your code. Open the jupytr notebook and navigate to the downloaded file:
jupyter notebook

Recall that in lecture 9, we have discussed Monte Carlo Localization (MCL). Using this algorithm, we can approximate the posterior probability distribution of current location based on motion models and measurements updates. MCL is essentially an implementation of the particle filtering algorithm.

MCL is really an implementation of the Particle Filtering (PF) algorithm (also discussed in class). With a given map of the environment, the robot (or a self-driving car) can use particle filtering algorithm to localize its current position with noisy sensor measurements. The details about particle filtering can be found in lecture 9 notes.

Mission Briefing

To visualize the simulation, we used python turtle graphics package. The maze is displayed as a 500 pixel x 500 pixel image. The green turtle is the actual position of BB-8 (Ground truth). The yellow turtle is the estimated position (AKA the result) of MCL/PF. The blue triangles are the particles.

BB-8 ‘s position in 2D space has 2 parameters: x, y (in pixels, ranging from 0 to 500). Here (0,0) is at the bottom-left corner.

To simplify the environment, the maze is divided to 20×20 cells. There may or may not be walls on the boundaries of each cell. BB-8’s motion model is the following:

  • BB-8 is always facing upwards (North) and at each step
  • BB-8 can only be controlled to move from the center of one cell to the center of one of four neighboring cells or stays
  • BB-8 will stay if he hits a wall

The corresponding control commands (u_t) are: 0 halt, 1 down, 2 right, 3 up, 4 left.

The code has three classes: the maze class is used to draw maze and robot position; the default_2D_model class is used to model the behavior of BB-8; and the particleFilter class is where you need to implement the particle filter. You only need to modify the particleFilter class. You can call any function of the model class, but you shouldn’t need to call any function inside maze class.

Here are some important functions:
(1) readingMap(position): return the accurate sensor measurement if the robot is at that position;
(2) readingSensor: return the current sensor measurement of BB-8 with some noise added.
(3) simulateNextPosition(previousEstimate, currentControl=0): return the estimated robot position based on last estimation and control input. Some noise is added here, too.
(4) run(currentControl=0): BB-8 will move according to the control input, and the maze will plot the current location.
(5) readPosition(): This function should only be used for debugging.

Fill in all the “TODO” parts. Once you think your particle filter is completed, you need to hard code a sequence of control input to control the robot to move from bottom left corner to upper right corner. Then try again to move from upper left to bottom right. While moving, the estimated position should be very close to real position. And the particles should gradually converge to a cluster near the real position.

In outer space, there is no gravity. So your code should be able to solve the localization problem in 3D space too.

Mission Report

To help BB-8 understand how your code works, you need to write a report at least 2 pages long, including:
(1) Explanation of each part of particle filtering algorithm. Talk about the implementation and purpose;
(2) The advantages and disadvantages of particle filtering;
(3) Issues/obstacles in your code development and how you overcame them;
(4) Is your code still working in higher dimensional space (3D, 4D, arbitrary dimension) and why?

Mission Complete

After you have finished the code and the report, please submit a zip file with name “netid1_netid2_mp3” containing the jupyter file and the report in PDF format. Upload it to Compass 2g and it will be transmitted to BB-8 through a secret antenna outside ECEB.

The deadline is Wednesday March 13, 11:59PM.

Mission Evaluation (Grading Rubric)

The commander (your TAs) will evaluate your MCL / Particle filter implementation task performance in the following manner:
15% on correct sampling of motion model
15% on correct updating using measurement model
15% on correct particle resampling
30% on correct result in turtle graphics. If your jupyter file can’t run, you will get 0.
20% on project report (5% for each part)
5% on comments and code style. Name your variables nicely.