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

316 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

−1
By definition, P m (E p1 ∩ E p2 ) = P m −1 (E p1 ) ∩ P m −1 (E p2 ),and P m −1 (P m (E)) ⊂
E. Thus, if P m (E 1 ) ∩ P m (E 2 ) =∅,then ∅ = P m −1 (P m (E 1 ) ∩ P m (E 2 )) = P m −1
(P m (E 1 )) ∩ P m −1 (P m (E 2 )) ⊂ E 1 ∩ E 2 .
To use this lemma for designing a sensor-based motion planning algorithm,
we need to describe minimal projections for different obstacle types. For a Type
1 or Type 2 obstacle O,we have P c (O) = P m (O). For a Type 3 obstacle, we
consider three events that cover all possible cases, using as an example a Type
3 + obstacle; denote it O + .

• O + intersects the floor J f . Because of the monotonicity property, P m (O + ) =
O + ∩ J f . In other words, the minimal projection of O + is exactly the inter-
section area of O + with the floor J f .
• O + intersects with a Type 3 − obstacle, O − . Then, P m (O + ∪ O − ) =
P c (∂O + ∩ ∂O − ). That is, the combined minimal projection of O + and O −
is the conventional projection of the intersection curve between O + and O − .
• Neither of the above cases apply. Then P m (O + ) =∅.
A similar argument can be carried out for a Type 3 − obstacle.
−1

Define J pf = J p − P m (O J ) and J = P m (J pf ). It is easy to see that J pf =
f
P c (J f ). Therefore, J = P −1 (J pf ) = P −1 (P c (J f )).

f m m
Theorem 6.3.3. J f = J ; that is, J f is topologically equivalent to a generalized
∼

f
cylinder.
−1
Define O = O J − P m (P m (O J )). Clearly, J f = J f ∪ O and P m (O ) =∅.

J
J
J

By Theorem 6.3.2, each component of O can be deformed either to the floor
J
{l 3 = 0} or to the ceiling {l 3 = 1} and thus does not affect the topology of J f .
∼
Thus, J f = J and, by definition, J presents a generalized cylinder in J.
f f
From the motion planning standpoint, Theorem 6.3.3 indicates that the third
dimension, l 3 ,of J f is not easier to handle than the other two because J f
possesses the monotonicity property along l 3 axis. It also implies that as a direct
result of the monotonicity property of joint space obstacles, the connectivity of
J f can be decided via an analysis of 2D surfaces.
We now turn to establishing a necessary and sufficient condition that ties the
existence of paths in the plane J p with that in 3D joint space J. This condition
will provide a base for generalizing planar motion planning algorithms to 3D
space. Assume that points (arm positions) j s and j t lie outside of obstacles.
Theorem 6.3.4. Given points j s , j t ∈ J f and a joint space obstacles O J ⊂ J,
a path exists between j s and j t in J f if and only if there exists a path in J pf
between points P c (j s ) and P c (j t ).
To prove the necessary condition, let p J (t), t ∈ [0, 1],beapathin J f .From
Lemma 6.3.6, P m (p J (t)) ∩ P m (O J ) =∅. Hence the path P m (p J (t)) connects
P c (j s ) and P c (j t ) in J pf .