Computer Science 154
Short assignment 6
Due Monday., Mar. 10 in class

Name(s)  _____________________________________

Reading for this week, linked here:
An Introduction to the Kalman Filter
by Greg Welch and Gary Bishop.

1.    The intermediate write-up for Lab Project #2 is due on Friday, March 7. Lab Project #2 is due Friday, March 14.
   
   
2.    Improving the Bug Algorithms (sometimes)    10 points

   Consider the two bug algorithms described in class. As a reminder, Bug 1 always circumnavigated obstacles; Bug 2 left an obstacle as soon as it reached the S-line at a point closer than the hit point.

   In analyzing these algorithms we considered at worlds for which Bug1 traversed less distance than Bug 2 -- call these worlds "Bug 2 killers." We also looked at situations in which Bug2 traversed less distance than Bug1 -- call these worlds "Bug 1 killers."

   Construct an algorithm that performs better than Bug 1 in some "Bug 1 killer" worlds and better than Bug 2 in some "Bug 2 killer" worlds. If you like, you may combine the two bug algorithms. Alternatively, you may start from scratch. Your algorithm should assume that it has the same information available that the Bug algorithms do (a known direction to the goal and known encoder readings). It does not have to outperform Bug 1 or Bug 2 for situations in which those strategies do well, but your algorithm should always reach the goal (as long as the goal is reachable).

   Also, draw/describe an environment in which your algorithm does better than Bug 1. Draw/describe another (likely different) environment in which your algorithm does better than Bug 2.

   
   
   
   
   
   
   
   
   
   
   
   


3.    Kalman Filtering    10 points

   This problem asks you to use a Kalman filter to estimate the position of walls around a Nomad 200 robot (we'll use the simulator for this).

   Start from the code in the directory /cs/cs154/as/shortHW6. In it, the file kalman.cc has the robot traveling slowly to the right along the x-axis. In addition, it plots in small circles from the sonar readings to the walls above it when using the map kalmanmap. It also shows the robot's naive estimates of the wall above it with overlaid lines. Finally, the code allows control over the amount of error in its sonar and encoder readings with parameters read in from the file kalmanparams.txt.

   Program and tune a Kalman filter to improve on the robot's estimates of the wall positions over time. Use the example line-drawing code to overlay your line estimates onto the world map as the robot moves. Hand in by email or by posting to a webpage the code you write and a short description of how well it works.

   
   URL (or simply email your code)
   
   

   Completely Optional Extra Credit

   Provide a visual indication of the uncertainty of your filter's current estimate of the wall's position. How you want to do this -- additional lines, points, etc. -- is entirely up to you.