Homework 2

Ross Knepper

12 Sep 07

16-735

The Bug 2 Algorithm

I chose to implement the Bug 2 algorithm for this homework because its performance is better in the average case than Bug 1 and it's easier to implement than Tangent Bug (hey, it's the truth!).

In implementing Bug 2, I assumed that the obstacles are open sets. The chief advantage of this assumption for the Bug algorithms is that a point robot can simply and safely traverse the boundary of an obstacle when it needs to follow a wall. Thus, no offset from the obstacle is required.

The algorithm is implemented using a state machine, as follows:

ALGORITHM Bug2(World of polygonal obstacles, start, goal)

Initialize the path to just the start node.
Let sgLine = the line from the start, through the goal, ending at a point on the far side of the goal and as far away from the goal as the start is.
Let pt = start
Let state = DRIVE

while (pt != goal) do
	Select the current value of state:
	DRIVE: # No current obstructing obstacle
		Clear visited (a set of Points)
		Examine line from pt to goal
		if (line intersects an obstacle)
			Let firstDistToGoal = path length remaining from intersection to goal
			Let lastLine = line
			Let pt = intersection point
			Let state = SWITCH
		else
			Let pt = goal
		Call function recordPoint(pt)

	SWITCH: # Transitioning from driving to wall-following
		Let lastVertex = vertex to the left of the intersection on this obstacle
		Let state = FOLLOW

	FOLLOW: # Wall following behavior on polygonal obstacles
		Let nextVertex = move one vertex to the right from lastVertex 
		Let potentialLine = the line from lastPt to nextVertex
		if (the line intersects sgLine AND the intersection is closer to the goal than the value of firstDistToGoal)
			Let newLine = line from pt to goal
			if (newLine does not intersect the current obstacle)
				Let potentialLine = line from lastPt to intersection
				Let pt = intersection point
				Let state = DRIVE
		if (potentialLine does intersects any obstacle besides the current obstacle which it is following)
			Let pt = intersection point
			Let lastLine = potentialLine
			Let state = SWITCH
		if (pt has not been set yet in this loop iteration)
			Let pt = nextVertex
			Let lastVertex = nextVertex
			Let state = FOLLOW
		Call function recordPoint(pt)
done

End.

function recordPoint(pt)
	If pt is in visited (Point set)
		Exit with FAILURE
	Insert pt into visited
	Let lastPt = pt
	Add pt as a new node in the path, joined by a straight line
	If pt is the goal
		Exit with SUCCESS
	Return

Movies

The successful planning movie is here.

A successful planning movie with multiple obstacles is here.

The failure case is shown here.