An alternative to Bug1 is the *Bug2 strategy*, which is
illustrated in Figure 12.22. The robot always attempts to
move along a line that connects the initial and goal positions. When
the robot is on this line, the goal direction will be either the same
as from the initial state or it will differ by radians (if the
robot is on the other side of the goal). The first step is the same
as for Bug1. In the second step, the robot follows the perimeter only
until the line is reached and it is able to move in the direction
toward the goal. From there, it goes to Step 1. As
expressed so far, it is possible that infinite cycles occur.
Therefore, a small modification is needed. The robot remembers the
distance to the goal from the last point at which it departed from the
boundary, and only departs from the boundary again if the candidate
point that is closer to the goal. This is applied iteratively until
the goal is reached or it is deemed to be impossible.

For the Bug2 strategy, the total distance traveled is no more than

(12.26) |

in which is the number of times the th obstacle crosses the line segment between the initial position and the goal position. An example that illustrates the trouble caused by the crossings is shown in Figure 12.23.

Steven M LaValle 2012-04-20