Page 116 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

BASIC ALGORITHMS 91

Bug2 Procedure
1. From point L j−1 , move along the M-line (straight line (S, T )) until one of
these occurs:
(a) Target T is reached. The procedure stops.
j
(b) An obstacle is encountered and a hit point, H , is defined. Go to Step 2.
2. Using the accepted local direction, follow the obstacle boundary until one
of these occurs:
(a) Target T is reached. The procedure stops.
j
(b) M-line is met at a point Q such that distance d(Q) < d(H ),and
straight line (Q, T ) does not cross the current obstacle at point Q.
j
Define the leave point L = Q.Set j = j + 1. Go to Step 1.
j
(c) MA returns to H and thus completes a closed curve along the obstacle
boundary, without having defined the next hit point, H j+1 . Then, the
target point T is trapped and cannot be reached. The procedure stops.

Unlike with algorithm Bug1, more than one hit and more than one leave point
can be generated on a single obstacle under algorithm Bug2 (see the example in
Figure 3.6). Note also that the relationship between perimeters of the obstacles
and the length of paths generated by Bug2 is not as clear as in the case of
algorithm Bug1. In Bug1, the perimeter of an obstacle met by MA is traversed
at least once and never more than 1.5 times. In Bug2, more options appear. A
path segment around an obstacle generated by MA is sometimes shorter than the
obstacle perimeter (Figure 3.5), which is good news: We finally see something
“intelligent.” Or, when a straight-line path segment of the path meets an obstacle
almost tangentially and MA happened to be walking around the obstacle in an
“unfortunate” direction, the path can become equal to the obstacle’s full perimeter
(Figure 3.7). Finally, as Figure 3.6a demonstrates, the situation can get even
worse: MA may have to pass along some segments of a maze-like obstacle more
than once and more than twice. (We will return to this case later in this section.)

Analysis of Algorithm Bug2

Lemma 3.3.3. Under Bug2, on its way to the target, MA can meet only a finite
number of obstacles.
Proof: Although, while walking around an obstacle, MA may at times find itself
at distances much larger than D from point T (Target), its straight-line path
segments toward T are always within the same circle of radius D centered at T .
j
j
This is guaranteed by the algorithm’s condition that d(L ,T ) > d(H ,T ) (see
Step 2 of Bug2 procedure). Since, by the model, any disc of finite radius can
intersect with only a finite number of obstacles, the lemma follows. Q.E.D.
Corollary 3.3.3. The only obstacles that MA can meet while operating under
algorithm Bug2 are those that intersect the disc of radius D centered at the target.