A strategy called Bug1 was developed in
 and is illustrated in Figure 12.20. The
execution is as follows:
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.
- 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
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
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
An illustration of the Bug2 strategy.
Steven M LaValle