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

292 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

Type III − Monotonicity. For any obstacle interacting with the rear part of link l 3 ,
there is one axis (direction), l 3 , along which the corresponding C-obstacle behaves

monotonically, as follows: if a position (l ,l ,l ) cannot be reached by the arm
1 2 3

due to an obstacle interference, then no position (l ,l ,l ) such that l <l can
1 2 3 3 3
be reached either.
The motion sufficient for maneuvering around a Type III − obstacle and for
guaranteeing convergence is motion along the curves of intersection between the
corresponding C-obstacle and either the M-plane or the V-plane (its part above
M-plane), or the ceiling of the C-space cubicle.
Interaction of Both Parts of Link l 3 with Obstacles. This is the case when
in C-space a “stalactite” obstacle meets a “stalagmite” obstacle and they form
a single obstacle. (Again, similar shapes are found in some caves.) Then the
best route around the obstacle is likely to be in the region of the ”waist” of the
new obstacle.
Let us consider this case in detail. For both parts of link l 3 to interact with
obstacles, or with different pieces of the same obstacle, the obstacles must be
of both types, Type III + and Type III − . Consider an example with two such
obstacles shown in Figure 6.10. True, these C-space obstacles don’t exactly look
like the stalactites and stalagmites that one sees in a natural cave, but they do
have their major properties: One “grows” from the floor and the other grows
from the ceiling, and they both satisfy the monotonicity property, which is how
we think of natural stalactites and stalagmites.
Without loss of generality, assume that at first only one part of link l 3 —say,
the rear part—encounters an obstacle (see obstacle O 2 , Figure 6.10). Then the
arm will start maneuvering around the obstacle following the intersection curve
between the V-plane and the obstacle (path segment aH, Figure 6.10). During
this motion the front part of link l 3 contacts the other (or another part of the
same) obstacle (here, obstacle O 1 , Figure 6.10).
At this moment the C-point is still in the V-plane, and also at the intersection
curve between both obstacles, one of Type III + and the other of Type III − (point
H, Figure 6.10; see also the intersection curve H 2 cdL 2 fg, Figure 6.12). As with
any curve, there are two possible local directions for following this intersection
curve. If both of them lead to walls, then the target is not reachable. In this
example the arm will follow the intersection curve—which will depart from
V-plane, curve HbcL—until it meets V-plane at point L, then continue in the
V-plane, and so on.
Since for the intersection between Type III + and Type III − obstacles the
monotonicity property works in the opposite directions—hence the minimum
area “waist” that they form—the following statement holds (it will be used
below explicitly in the algorithm):

Corollary 6.2.2. If there is a path around the union of a Type III + and a Type III −
obstacles, then there must be a path around them along their intersection curve.