The Bug1 strategy

A strategy called Bug1 was developed in [667] 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.

Figure 12.21: A bad example for Bug1. The perimeter of each obstacle is spanned one and a half times.

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

$$d + \frac{3}{2} \sum_{i=1}^{M} p_i ,$$ (12.25)

in which $d$ is the Euclidean distance from the initial position to the goal position, $p_i$ is the perimeter of the $i$th obstacle, and $M$ is the number of obstacles. This means that the boundary of each obstacle is followed no more than $3/2$ times. Figure 12.21 shows an example in which each obstacle is traversed $3/2$ 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 $3/2$ would have to be replaced by $2$ because the robot could nearly traverse the full boundary twice in the worst case.

Figure 12.22: An illustration of the Bug2 strategy.