A strategy called *Bug1* was developed in
[667] and is illustrated in Figure 12.20. The
execution is as follows:

- Move toward the goal until an obstacle or the goal is encountered. If the goal is reached, then stop.
- Turn left and follow the entire perimeter of the contacted obstacle. Once the full perimeter has been visited, then return to the point at which the goal was closest, and go to Step 1.

The worst case is conceptually simple to understand. The total distance traveled by the robot is no greater than

in which is the Euclidean distance from the initial position to the goal position, is the perimeter of the th obstacle, and is the number of obstacles. This means that the boundary of each obstacle is followed no more than times. Figure 12.21 shows an example in which each obstacle is traversed times. This bound relies on the fact that the robot can always recall the shortest path along the boundary to the point from which it needs to leave. This seems reasonable because the robot can infer its distance traveled along the boundary from the goal sensor. If this was not possible, then the would have to be replaced by because the robot could nearly traverse the full boundary twice in the worst case.

Steven M LaValle 2012-04-20