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

VISION AND MOTION PLANNING 117

T

C

T i

H j

S
Figure 3.17 Illustration for Lemma 3.6.2: Observation 2.

segment’s endpoints are not included). Here H j is the lastly defined hit point.
Indeed, for such a crossing to take place, T i must lie in the secondary semiplane
(Figure 3.17). For this to happen, the Bug2 path would have to proceed from
H j first into the main semiplane and then enter the secondary semiplane some-
where outside of the line segment |H j T |; otherwise, the leave point, L j , would
be established and the Bug2 path would stay in the main semiplane at least until
the next hit point, H j+1 , is defined. Note, however, that any such way of entering
the secondary semiplane would produce segments of the Bug2 path that are not
contiguous (because of the visibility condition) to the rest of the Bug2 path. By
the algorithm, no points on such segments can be chosen as intermediate targets
T i —which means that if the point C is in the main semiplane, then the line
segments |CT i | and |H j T | never intersect.
Situations that fall into the case in question can in turn be divided into three
groups:
3a. Point C is located on the obstacle boundary, and C = T i .Thishap-
pens when the robot walks along a locally convex obstacle boundary (point C ,

Figure 3.18). Consider the curvilinear triangle X j C Q. Continuing the boundary

segment (X j C ) after the point C , the obstacle (and the corresponding seg-
ment of the Bug2 path) will either curve inside the triangle, with |QT| lying
outside the triangle (Figure 3.18a), or curve outside the triangle, leaving |QT|

inside (Figure 3.18b). Since the obstacle can cross neither the line |C Q| nor
the boundary segment (X j C ), it (and the corresponding segment of the Bug2

path) must eventually intersect the M-line somewhere between X j and Q before
intersecting |QT|. The rest of the argument is identical to case 2 above.
3b. Point C is on the obstacle boundary, and C = T i (Figure 3.18). Consider
the curvilinear triangle X j CQ. Again, the obstacle can cross neither the line of