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

298 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

decision-making mechanism of A p into 3D space by complementing the set of
local directions by elements upward and downward. We now turn to the study
of five fundamental motions in 3D, which will be later incorporated into the 3D
algorithm.

Motion I—Along the M-Line. Starting at point S,the C-point moves along the
M-line, as in Figure 6.7, segment SH; this corresponds to P c (C-point) moving

along the P c (M-line) (segment S H , Figure 6.7). Unless algorithm A p calls for
terminating the procedure, one of these two events can take place:
1. A wall is met; this corresponds to P c (C-point) encountering an obstacle.
Algorithm A p now has to decide whether P c (C-point) will move along
P c (M-line), or turn left or right to go around the obstacle. Accordingly,
the C-point will choose to reverse its local direction along the M-line, or
to turn left or right to go around the wall. In the latter case we choose a
path along the intersection curve between the wall and the M-plane, which
combines two advantages: (i) While not true in the worst case, due to
obstacle monotonicity the M-plane typically contains one of the shortest
paths around the obstacle; and (ii) after passing around the obstacle, the
C-point will meet the M-line exactly at the point of its intersection with the
obstacle (point L, Figure 6.7), and so the path will be simpler. In general,
all three joints participate in this motion.
2. A Type III + or III − obstacle is met. The C-point cannot proceed along
the M-line any longer. The local objective of the arm here is to maneuver
around the obstacle so as to meet the M-line again at a point that is closer
to T than the encounter point. Among various ways to pass around the
obstacle, we choose here motion in the V-plane. The intersection curve
between the Type III obstacle and the V-plane is a simple planar curve. It
follows from the monotonicity property of Type III obstacles that when the
front (rear) part of link l 3 hits an obstacle, then any motion upward (accord-
ingly, downward) along the obstacle will necessarily bring the C-point to
the ceiling (floor) of the C-space. Therefore, a local contact information
is sufficient here for a global planning inference—that the local direction
downward (upward) along the intersection curve between the V-plane and
the obstacle is a promising direction. In the example in Figure 6.9a, the
resulting motion produces the curve abc.

Motion II—Along the Intersection Curve Between the M-Plane and a Wall. In
C p , this motion corresponds to P c (C-point) moving around the obstacle boundary

curve in the chosen direction (see Figure 6.12, segments H 1 aL 1 and H a L ).
1 1
One of these two events can take place:
1. The M-line is encountered, as at point L 1 , Figure 6.12; in C p this means
P c (M-line) is encountered. At this point, algorithm A p will decide whether