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

VISION AND MOTION PLANNING 111

Else if Target is unreachable the procedure stops.
Else if C = T i go to step S1.

Procedure Compute T i -21 includes the following steps:

• Step 1: If 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 |T i Q| of M-line that extends from point T i in the direction of
point T .
If an obstacle has been identified crossing the M-line at point Q, then define
a hit point, H = Q; assign X = Q,define T i = Q;gotoStep3.
Else define T i = Q; goto Step4.
• Step 3: Define point Q as the endpoint of the maximum length contigu-
ous segment of obstacle boundary, (T i Q), extending from T i in the local
direction.
If an obstacle has been identified crossing M-line at a point P ∈ (T i Q),
|PT| < |HT|, assign X = P ; if, in addition, |PT| does not cross the obstacle
at P , 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
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 = X.
If some points {P } on the M-line are identified such that |S T | < |QT|,

S ∈{P},and C is in the main semiplane, then find the point S ∈{P } that

produces the shortest distance |S T |;define T i = S ;gotoStep 2.

Else procedure stops.
In brief, procedure Compute T i -21 operates as follows. Step 1 is executed
at the last stage, when target T becomes visible (as at point A, Figure 3.15).
A special case in which points of the M-line noncontiguous to the previously
considered sets of points are tested as candidates for the next intermediate Target
T i is handled in Step 4. All the remaining situations relate to choosing the next
point T i among the Bug2 path points contiguous to the previously defined point
T i ; these are treated in Steps 2 and 3. Specifically, in Step 2 candidate points
along the M-line are processed, and hit points are defined. In Step 3, candidate
points along obstacle boundaries are processed, and leave points are defined. The
test for target reachability is also performed in Step 3. It is conceivable that at
some locations C of the robot the procedure will execute, perhaps even more than
once, some combinations of Steps 2, 3, and 4. While doing this, contiguous and
noncontiguous segments of the Bug2 path along the M-line and along obstacle
boundaries may be considered before the next intermediate target T i is defined.
Then the robot makes a physical step toward T i .