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

VISION AND MOTION PLANNING 115

sure that in such cases the candidate points on the M-line that are “approved” by
the algorithm do indeed lie on the Bug2 path.
This is assured by Step 4 of the procedure Compute T i -21, where a noncontigu-
ous point Q on the M-line is considered a possible candidate for an intermediate
target only if the robot’s current location C is in the main semiplane. The pur-
pose of this condition is to preserve convergence. We will now show that this
arrangement always produces intermediate targets that lie on the Bug2 path.
Consider a current location C of the robot along the VisBug-21 path, a current
intermediate target T i , and some visible point Q on the M-line that is being
considered as a candidate for the next intermediate target, T i+1 . Apparently, Q
can be accepted as the intermediate target T i+1 only if it lies further along the
Bug2 path than T i .
Recall that in order to ensure convergence, algorithm Bug2 organizes the set
of hit and leave points, H j and L j , along the M-line so as to form a sequence
of segments

|ST | > |H 1 T | > |L 1 T | > |H 2 T | > |L 2 T | > ·· · (3.25)

that shrinks to T . This inequality dictates two conditions that candidate points
for Q must satisfy in order for VisBug-21 to converge: (i) When the current
intermediate target T i lies on the M-line, then only those points Q should be
considered for which |QT| < |T i T |. (ii) When T i is not on the M-line, it lies on
the obstacle boundary, in which case there must be the latest crossing point X
between M-line and the obstacle boundary, such that the boundary segment (XT i )
is a part of the Bug2 path. In this case, only those points Q should be considered
for which |QT| < |XT|. Since points Q, T i ,and X are already known, both of
these conditions can be easily checked. Let us assume that these conditions are
satisfied. Note that the crossing point X does not necessarily correspond to a hit
point for either Bug2 or VisBug-21 algorithms. The following statement holds.

Lemma 3.6.2. For point Q to be further along the Bug2 path than the interme-
diate target T i , it is sufficient that the current robot position C lies in the main
semiplane.
Proof: Assume that C lies in the main semiplane; this includes a special case
when C lies on the M-line. Then, all possible situations can be classified into
three cases:

(1) Both T i and C lie on the M-line.
(2) T i lies on the M-line, whereas C does not.
(3) T i does not lie on the M-line. Let us consider each of these cases.
1. Here the robot is moving along the M-line toward T ; thus, T i is between
C and T (Figure 3.16a). Since T i is by definition on the Bug2 path, and both T i
and Q are visible from point C, then point Q must be on the Bug2 path. And,
because of condition (i) above, Q must be further along the Bug2 path than T i .