#### The Bug1 strategy

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

1. Move toward the goal until an obstacle or the goal is encountered. If the goal is reached, then stop.
2. 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.
Determining that the entire perimeter has been traversed may seem to require a pebble or marker; however, this can be inferred by finding the point at which the goal sensor reading repeats. The worst case is conceptually simple to understand. The total distance traveled by the robot is no greater than (12.25)

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