Harvey Mudd College
Computer Science 154 - Robotics
Assignment B

The buggy butler

Lab #2 write-up
SooYoung Jung
02/26/01

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

General Algorithms

Both algorithms, bug1 and bug2, is very similar and they are based on the wall-following altorithm that I have done for previous homework, and also, bug2 is based on the algorithm bug1.

bug1 algorithm: the bug will calculate an angle to the end point and toward to the end point to using the angle. If the bug hit the obstacle, the bug will remember this position and wall-follow entire obatacle. While the bug wall-following, the bug will calculate the shortest path the the end position.  When the bug has returned the position at which it originally hit the obstacle, the bug will return the position where the length to the end position is shortes using wall-following behavior.  When it reaches the shortest-length position, the bug will calculate the angle to the end position and toword to the end positon again.

bug2 algorithm: bug2 algorithm does exactly what this homework required.

Link to Sources

bug1 | bug2

Problem that I encountered

1. This bug programs has one known "bug".
   When the shortest length or s-line is at the edge (while the bug is turing the edge), sometimes it does not make angle turn to toward the end point. Probably this is encountered with in here.

        Line #430 & #444 (similar code)

        while(addUp(9, 13) < (ADD_UP_MAX - 1))
        {
            vm(tv, 0, 0);
        }

        while it is turing, it is not checking shortest length and angle(s-line).
        Even though, I added up checking statements within these while loops, it is not quite finding shortest or s-line and         sometimes it massed up whole program so I decided to get rid of them.

2. After running program for a while, I just realized that the bug can hit the obstacle any parts (left, right, top, and bottom) so I added some more codes that robot can distinguish where the obstacle is located. The codes are following:

        if ((addUp(5, 9) < ADD_UP_MAX - 5) && followAngle)
            turnTo(RIGHT, RIGHT_ANGLE * 2);

Examples

Both algorithms works quite well on any maps as following

Bug1

Bug2

Part 2 -- Buttling

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