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

COMBINING GOOD FEATURES OF BASIC ALGORITHMS 101

containing this point will never be larger than two; in other words, MA will never
pass the same point of the obstacle boundary more than three times, producing
the upper bound

P ≥ D + 3 · p i (3.12)
i

Algorithm BugM1 is executed at every point of the continuous path. Instead of
using the fixed M-line (straight line (S, T )), as in Bug2, BugM1 uses a straight-
j j j
line segment (L ,T ) with a changing point L ; here, L indicates the jth leave
i
i
i
point on obstacle i. The procedure uses three registers, R 1 , R 2 ,and R 3 ,tostore
j
intermediate information. All three are reset to zero when a new hit point H is
i
defined:
• Register R 1 stores coordinates of the current point, Q m , of minimum dis-
tance between the obstacle boundary and the Target.
j
• R 2 integrates the length of the obstacle boundary starting at H .
i
• R 3 integrates the length of the obstacle boundary starting at Q m . (In case
of many choices for Q m , any one of them can be taken.)
The test for target reachability that appears in Step 2d of the procedure is
o
explained lower in this section. Initially, i = 1, j = 1; L = Start. The BugM1
o
procedure includes these steps:
j−1 j−1
1. From point L , move along the line (L o , Target) toward Target until
i−1
one of these occurs:
(a) Target is reached. The procedure stops.
j
(b) An ith obstacle is encountered and a hit point, H , is defined. Go to
i
Step 2.
2. Using the accepted local direction, follow the obstacle boundary until one
of these occurs:
(a) Target is reached. The procedure stops.
j−1 j−1
(b) Line (L o , Target) is met inside the interval (L o , Target), at a point
j
Q such that distance d(Q) < d(H ), and the line (Q, Target) does not
j
cross the current obstacle at point Q. Define the leave point L = Q.
i
Set j = j + 1. Go to Step 1.
j−1 j−1
(c) Line (L o , Target) is met outside the interval (L o ,Target).Goto
Step 3.
j
(d) The robot returns to H and thus completes a closed curve (of the
i
obstacle boundary) without having defined the next hit point. The target
cannot be reached. The procedure stops.