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

VISION AND MOTION PLANNING 121

Consider a scene with given Start S and Target T points, and consider a

third point, S , that lies on the M-line somewhere between S and T . Following
the term Bug2 path that we used before, we define a quasi-Bug2 path segment

as a contiguous segment that starts at S and produces a part of the path that
algorithm Bug2 would have generated if points S and T were its starting and

target points, respectively. Because point S does not need to be on the Bug2
path, a quasi-Bug2 path segment may or may not be a part of the Bug2 path.
The algorithm VisBug-22 will check points along the Bug2 path or a quasi-
Bug2 path segment until the best point on the M-line—that is, one that is the
closest to T —is identified. This point S then becomes the starting point of

another quasi-Bug2 path segment. Then the process repeats. As a result, unlike
algorithms Bug2 and VisBug-21, where each hit point has its matching leave
point, in VisBug-22 no such matching needs to occur. To be chosen as the
starting point S of the next quasi-Bug2 path segment, a point must satisfy certain

requirements that ensure convergence. These will be considered later, after we
describe the whole procedure.
The algorithm includes the Main body, which is identical to that of algorithm
VisBug-21 (refer to Section 3.6.2), and the procedure Compute T i -22. The pur-
pose of the latter is to produce the next intermediate target T i for a given current
position C; it is also responsible for the test for target reachability. Initially,
C = S = T i .

Procedure Compute T i -22:

• Step 1: If Target T is visible, define T i = T ; procedure stops.
Else if T i is on an obstacle boundary, go to Step 3.
Else go to Step 2.
• Step 2: Define point Q as the endpoint of the maximum-length contiguous
segment of the M-line, |T i Q|, extending from T i in the direction of T .
If an obstacle has been identified crossing the M-line at point Q, then define
a hit point, H = Q;define T i = Q;gotoStep 3.
Else define T i = Q; goto Step4.
• Step 3: Define point Q as the endpoint of the maximum length contiguous
segment of the obstacle boundary, (T i Q), extending from T i in the local
direction.
If an obstacle has been identified crossing the M-line at a point P ∈ (T i Q),
|P, T | < |HT |, and line |PT | does not cross the obstacle at P , then define
a leave point, L = P ,define T i = P , and go to Step 2.
If the lastly defined hit point H is identified again and H ∈ (T i Q), then the
target is not reachable; procedure stops.
Else define T i = Q; goto Step4.
• Step 4: If T i is on the M-line, define Q = T i ;otherwise define Q = H.