Harvey Mudd College
Computer Science 154 - Robotics
Assignment B

The buggy butler

Part 1 -- The bug algorithms

Several species of insects use the sun to maintain a correct heading in an effort to navigate from place to place, even as they have to adjust their paths to avoid things like bug zappers and swatters. This first part of the project asks you to emulate -- at least at a coarse level -- this insect behavior by implementing two path-planning algorithms. Appropriately, the algorithms are named Bug1 and Bug2.

The algorithms

The idea behind both algorithms is that your robot knows the direction in which it should head towards its goal, but it does not know anything about the obstacles that lie between its current position and that goal. The basic idea is to start heading toward the goal (since the correct direction is known) and see whether any obstacles present themselves. We will call the line between the robot's initial position and the goal the S-line.

• Bug1 specifies that the robot should circumnavigate the entire obstacle. As it does so, it should remember whatever point along the obstacle's perimeter is closest to the goal. (The insect analogy would be a scent that grows stronger with proximity to a nest or meal... .) Once the robot has returned to (approximately) the point at which it originally hit the obstacle, it continues following the perimeter until it returns to that remembered closest point. Upon reaching that remembered point, it departs the obstacle and continues along a new line towards the goal. This process repeats if there are other obstacles in the way.
  
  
• Bug2 takes a more aggressive approach. If an obstacle presents itself along the S-line, the robot again "wall-follows" along the perimeter of that obstacle. Rather than circumnavigating the obstacle, however, Bug2 specifies that as soon as the robot reaches another point along the S-line that is closer than the original point of contact with the obstacle, the robot should leave the obstacle perimeter and continue heading toward the goal. This procedure repeats for any additional obstacles that arise.
  
  

This problem is to implement these two "Bug" algorithms using the wall-following code you wrote in the second half of Lab Project A as a starting point. As with that assignment, you can assume that the obstacles will consist of walls meeting at right angles (an indoor application). The S-line need not, however, be parallel or perpendicular to the obstacles' walls. In implementing these algorithms, there are a number of choices to make, e.g., which direction to start heading around an encountered obstacle. It doesn't matter which direction you choose, as long as you stay consistent. Another choice that comes up in Bug1 is which direction to return to the perimeter point closest to the goal. In that case, it is preferable to return along the shorter path, (though either way is acceptable for this assignment).

Maps, Initial Points, and Destination Points

To test your algorithms, there are two world maps available in /cs/cs154/as/B. For the first map (bugmapA), the goal point is (2750,4200); for the second map (bugmapB) it's (0,4700). For all of the test runs, the default starting point will be used, i.e., the position the robot takes after the zr() call. Both of these provided maps may be more complicated than you want to use on a first run to debug your algorithms -- feel free to try it out on your own maps, also.

Write-Up

In your write-up of this part of the assignment, be sure to include the following

• link(s) to your code
• a general explanation of any problems you encountered and how you dealt with them (There are at least a couple that may not be evident from the algorithms' descriptions.)
• an evaluation of how well your bug algorithms work
• example traces of the robot

Part 2 -- Buttling

This part of the assignment will be made into a third Nomad simulator assignment... .