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

102 MOTION PLANNING FOR A MOBILE ROBOT

3. Continue following the obstacle boundary. If the target is reached, stop.
Otherwise, after having traversed the whole boundary and having returned
j j
to point H , define a new leave point L = Q m .GotoStep4.
i i
4. Using the contents of registers R 2 and R 3 , determine the shorter way along
j j
the obstacle boundary to point L , and use it to get to L . Apply the
i
i
test for Target reachability (see below). If the target is not reachable, the
j
o
procedure stops. Otherwise, designate L = L ,set i = i + 1,j = 1, and
i
i
go to Step 1.
As mentioned above, the procedure itself BugM1 is obviously longer and
“messier” compared to the elegantly simple procedures Bug1 and Bug2. That
is the price for combining two algorithms governed by very different principles.
Note also that since at times BugM1 may leave an obstacle before it fully explores
it, according to our classification above it falls into the Class 2.
What is the mechanism of algorithm BugM1 convergence? Depending on the
scene, the algorithm’s flow fits one of the following two cases.

Case 1. If the condition in Step 2c of the procedure is never satisfied, then
the algorithm flow follows that of Bug2—for which convergence has been
j
already established. In this case, the straight lines (L , Target) always coin-
i
cide with the M-line (straight line (Start, Target)), and no local cycles
appear.
Case 2. If, on the other hand, the scene presents an in-position case, then
the condition in Step 2c is satisfied at least once; that is, MA crosses the
j−1 j−1
straight line (L o , Target) outside the interval (L o , Target). This indi-
cates that there is a danger of multiple local cycles, and so MA switches
to a more conservative procedure Bug1, instead of risking an uncertain
number of local cycles it might now expect from the procedure Bug2 (see
Lemma 3.3.4). MA does this by executing Steps 3 and 4 of BugM1, which
are identical to Steps 2 and 3 of Bug1.

After one execution of Steps 3 and 4 of the BugM1 procedure, the last leave point
j
on the ith obstacle is defined, L , which is guaranteed to be closer to point T
i
j
than the corresponding hit point, H [see inequality (3.7), Lemma 3.3.1]. Then
i
MA leaves the ith obstacle, never to return to it again (Lemma 3.3.1). From
o
now on, the algorithm (in its Steps 1 and 2) will be using the straight line (L ,
i
o
Target) as the “leading thread.” [Note that, in general, the line (L , Target) does
i
not coincide with the straight lines (L o ,T ) or (S, T )]. One execution of the
i−1
sequence of Steps 3 and 4 of BugM1 is equivalent to one execution of Steps 2
and 3 of Bug1, which guarantees the reduction by one of the number of obstacles
that MA will meet on its way. Therefore, as in Bug1, the convergence of this case
is guaranteed by Lemma 3.3.1, Lemma 3.3.2, and Corollary 3.3.2. Since Case 1
and Case 2 above are independent and together exhaust all possible cases, the
procedure BugM1 converges.