15-494 Cognitive Robotics
Spring 2011
Course Links:  Main Lectures Labs Homeworks

Tekkotsu Links:   Wiki Tutorial Resources Bugs CVS
Reference:

Cognitive Robotics: Homework 5


Due date: Monday, February 21.

Particle Filter Bingo

This is an open-ended assignment. I hope to engage your creativity. The task is to make particle filters understandable to naive robot users, such as high school students getting their first exposure to robot localization. You are going to develop a game that helps students simulate a particle filter. Below I describe one way this game could work. You are welcome to pursue this design, but if you think you might have a better idea, you can go with that instead.

Environment: There is a maze with a bunch of landmarks. You can use the Emaze as your environment: see Root Control > Framework Demos > Navigation > Emaze.

Teacher mode setup: The teacher picks a point in the maze by typing in x, y, and theta values as a text message. Alternatively, she can ask the behavior to pick these values. Your behavior sets the agent shape to the chosen coordinates and heading outputs a hexadecimal string that encodes, in a deliberately obscure way, the location and heading values. The teacher then announces this string to the class.

Student mode setup: Students run the behavior and send it the hexadecimal string as a text message. Now the behavior knows the chosen location and heading, but it does not reveal this to the student. It generates 10 random particles and displays them on the world map. It also prints out a table like this:

ParticlexythetaTotal
Score
1-52.5300.20.5770.0
...
10108.1690.72.3840.0

Teacher moves: Each round of play begins with the teacher sending a text message to the behavior. The behavior responds with a landmark number, a bearing, and a distance. (Rather than reporting exact values, these values should have some noise added to them.) The teacher announces these values to the class.

Student moves: The students input the landmark number, bearing, and distance via a text message. The behavior responds by updating the scores of the actual particles (visible on the world map) and printing out a new table showing the contribution of each landmark to the total score. Suppose the first observed landmark was number 8. Then the table would look like:

ParticlexythetaLmk 8Total
Score
1-52.5300.20.577-61.2-61.2
...
10108.1690.72.384-14.3-14.3

If the next landmark was number 3, the table would look like:

ParticlexythetaLmk 8Lmk 3Total
Score
1-52.5300.20.577-61.2-7.1-68.3
...
10108.1690.72.384-14.3-80.5-94.8

Concluding the game: the game ends when the teacher's behavior runs out of landmarks, or when four landmarks have been announced. The student with the highest scoring particle announces its coordinates and heading and is declared the winner. The teacher then discloses the actual coordinates and heading so students can see how close the particle filter came to estimating the robot's true pose.

Issues and advice:

  1. Make sure to only generate points inside the maze boundary. (You can generate points at random, one at a time, and reject them until you find one that lies inside the polygon that defines the maze bounds.)

  2. Make sure to only generate landmarks that are visible from the robot's location, i.e., there must be no wall between the robot and the landmark. I will supply you with code for this test.

  3. Look at the source for PilotDemo to see how to parse text messages conveniently.

  4. Consider possible enhancements. For example, you could add an ellipse for each landmark showing a confidence interval for the position and bearing. The region where these ellipses overlap would be the robot's most likely location.

  5. Come up with a good way to illustrate resampling.


Dave Touretzky and Ethan Tira-Thompson