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

118 MOTION PLANNING FOR A MOBILE ROBOT

T

T
Q C’
Q
L j C
L j

T i

C’ X j
C
T i S

X j

S
(a) (b)

Figure 3.18 Illustration for Lemma 3.6.2: Cases 3a and 3b.

visibility |CQ| nor the boundary segment (X j C), and so the obstacle (and the
corresponding segment of the Bug2 path) will either curve inside the triangle,
with |QT| left outside of it, or curve outside the triangle, with |QT| lying inside.
The rest is identical to case 2.
3c. Point C is not on the obstacle boundary. Then, a curvilinear quadrangle is
formed, X j T i CQ (Figure 3.19). Again, the obstacle will either curve inside the
quadrangle, with |QT| outside of it, or curve outside the quadrangle, with |QT|
lying inside. Since neither the lines of visibility |CT i | and |CQ| nor the boundary
segment (X j T i ) can be crossed, the obstacle (and the corresponding segment of
the Bug2 path) will eventually cross |X j Q| before intersecting |QT| and form
the leave point L j . The rest of the argument is identical to case 2. Q.E.D.

If the robot is currently located in the secondary semiplane, then it is indeed
possible that a point that lies on the M-line and seems otherwise a good candidate
for the next intermediate target T i does not lie on the Bug2 path. This means
that point should not even be considered as a candidate for T i .Suchanexample
is shown in Figure 3.15: While at location C, the robot will reject the seemingly
attractive point Q (Step 2 of the algorithm) because it does not lie on the Bug2
path. We are now ready to establish convergence of algorithm VisBug-21.