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

290 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

Stalactites and Stalagmites: Type III Obstacles

Front Part of Link l 3 —Type III + Obstacles. Assume for a moment that only
the front part of link l 3 can interfere with an obstacle (see, e.g., obstacle O 1 ,
Figures 6.2 and 6.4). Consider the cross sections of the obstacle with two hori-

zontal planes: one corresponding to the value l and the other corresponding to
3

the value l , with l <l . Denote these cross sections a and a , respectively.

3 3 3
Each cross section is a closed set limited by a simple closed curve; it may or
may not include points on the C-space boundary. Because link l 3 is a generalized
cylinder, the vertical projection of one cross section onto the other satisfies the

relationship a ⊆ a . This is a direct result of the Type III + obstacle monotonicity
property, which is formulated as follows:
Type III + Monotonicity. For any obstacle interacting with the front part of link l 3 ,
there is one axis (direction), namely l 3 , along which the corresponding C-obstacle

behaves monotonically, as follows: if a position (l ,l ,l ) cannot be reached by

1 2 3

the arm due to an obstacle interference, then no position (l ,l ,l ) such that
1 2 3

l >l can be reached either.
3 3
This property results in a special “stalactite” shape of Type III + obstacles. A
typical property of icicles and of beautiful natural stalactites that hang down from
the ceilings of many caves is that their horizontal cross section is continuously
reduced (in theory at least) from its top to its bottom. Each Type III + obstacle
behaves in a similar fashion. It forms a “stalactite” that hangs down from the
ceiling of the C-space cubicle, and its horizontal cross section can only decrease,
with its maximum horizontal cross section being at the ceiling level, l 3 = l 3max
(see cubicle Oabcdefg and obstacle O 1 , Figure 6.4). For any two horizontal cross

sections of a Type III + obstacle, taken at levels l and l such that l >l ,the

3 3 3 3
projection of the first cross section (l level) onto a horizontal plane contains no

3
points that do not belong to the similar projection of the second cross section (l
3
level). This behavior is the reflection of the monotonicity property.
Because of this topology of Type III + obstacles, the sufficient motion for
maneuvering around any such obstacle—that is, motion sufficient to guarantee
convergence—turns out to be motion along the intersection curves between the
corresponding C-obstacle and either the M-plane or the V-plane (specifically,
its part below M-plane), plus possibly some motion in the floor of the C-space
cubicle (Figure 6.9).
Rear Part of Link l 3 —Type III − Obstacles. A similar argument can be made
for the case when only the rear end of link l 3 interacts with an obstacle (see,
e.g., obstacle O 2 , Figures 6.2, 6.4, and 6.5). In C-space the corresponding Type
III − obstacle becomes a “stalagmite” growing upward from the C-space floor.
This shape is a direct result of the Type III − obstacle monotonicity property,
which is reversed compared to the above situation with the front part of link l 3 ,
as follows: