Sean Hyde
16-735 Robotic Motion Planning
September 9, 2007
Homework #2
I implemented the Bug 2 algorithm. The idea behind this algorithm that there is line between the start and end locations. When an obstacle is encountered, the obstacle is circumnavigated until the line is reached again. The line only counts as being reached if the new encounter is closer to the goal then when the object was first circumnavigated. If it is, continue along the line until the goal is reached. If an object is circumnavigated completely without finding a spot on the line closer than where it was first encountered, there is no path to the goal.
I chose this algorithm because it seemed more intuitive to an actual mobile platform than Bug 1. Particularly, Bug 1 assumes that you can circumnavigate an object completely, when to do so isn't required to reach the goal.
Path Length Considerations:
The shortest path length is of course D, the distance between the start and the goal. This would be no obstacles.
The longest path is the path to the goal plus half the perimeter of each obstacle times the number of intersections of that obstacle with the goal line:
D + ∑i .5(ni)(Pi)
This turns out to be potentially longer than Bug 1, but generally shorter.
Algorithm Implementation Details:
1. Draw a line between the start and end.
2. Examine all of the line segments formed by the vertices of the obstacle(s).
3. Find the closest intersection to your current location that is still between your location and the goal.
4. Determine which direction (in terms of the obstacle's vertex list) is "turning right". Note that this is actually non-trivial, espcially when one considers vertical and horizontal obstacle edges and paths.
5. Move around the object until the goal line is encountered again.
6. Check if you are nearer to the goal (but still between the start and end)
7. If so, continue along line to next obstacle (or goal).
8. If not, continue around. If original location on obstacle encountered, report failure.
9. If goal encountered, report success.
Video Results:
Two success and one failure video. The videos also show the user interface that allows an arbitrary number of obstacles.
Source Files: HW2b.m bug_2.m HW2gui.m HW2gui.fig addObstacle.m