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

BASIC ALGORITHMS 85

ob 2
T
H 2
L 2

L 1

ob 1

H 1
S

Figure 3.2 The path of the robot (dashed lines) under algorithm Bug1. ob 1 and ob 2 are
obstacles, H 1 and H 2 are hit points, L 1 and L 2 are leave points.

Bug1 Procedure
1. From point L i−1 , move toward point T (Target) along the straight line until
one of these occurs:
(a) Point T is reached. The procedure stops.
(b) An obstacle is encountered and a hit point, H i , is defined. Go to Step 2.
2. Using the local direction, follow the obstacle boundary. If point T is
reached, stop. Otherwise, after having traversed the whole boundary and
having returned to H i , define a new leave point L i = Q m .Go toStep3.
3. Based on the contents of registers R 2 and R 3 , determine the shorter way
along the boundary to point L i , and use it to reach L i . Apply the test
for target reachability. If point T is not reachable, the procedure stops.
Otherwise, set i = i + 1 and go to Step 1.

Analysis of Algorithm Bug1

Lemma 3.3.1. Under Bug1 algorithm, when MA leaves a leave point of an obsta-
cle in order to continue toward point T , it will never return to this obstacle again.
Proof: Assume that on its way from point S to point T , MA does meet some
obstacles. We number those obstacles in the order in which MA encounters them.
Then the following sequence of distances appears:

D, d(H 1 ), d(L 1 ), d(H 2 ), d(L 2 ), d(H 3 ), d(L 3 ), . . .