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

THREE-LINK XXP ARM MANIPULATORS 317

(t), t ∈ [0, 1],beapathin J pf .Then
To show the sufficiency, let p J p
−1
P m −1 (p J p (t)) presents a “wall” in J.Define E = P m (p J p (t)) ∩ O J and let E −1
be the complement of E in P −1 (t)). We need to show that E −1 consists
m (p J p
of one connected component. Assume that this is not true. For any t ∗ ∈ [0, 1],
(t ∗ ), l 3∗ ) ∈ E −1 .
since p J p (t ∗ )∈P m (O J ), there exists l 3∗ such that point (p J p
The only possibility for E −1 to consist of two or more disconnected compo-

nents is when there exists t ∗ and a set (l 3∗ ,l ,l ), l >l 3∗ >l , such that

3∗ 3∗ 3∗ 3∗

(t ∗ ), l 3∗ ) ∈ E −1 (t ∗ ), l ) ∈ E.However,
(p J p while (p J p (t ∗ ), l ) ∈ E and (p J p
3∗ 3∗
this cannot happen because of the monotonicity property of obstacles. Hence
E −1 must be connected.
6.3.4 Retraction of J f
Theorem 6.3.4 indicates that the connectivity of space J f can indeed be captured
via a space of lower dimension, J pf . However, space J pf cannot be used for
motion planning because, by definition, it may happen that J pf ∩ O J =∅;that
is, some portion of J pf is not obstacle-free. In this section we define a 2D space
D f ⊂ J f that is entirely obstacle-free and, like J pf , captures the connectivity
of J f .

Definition 6.3.10. [57]. A subset A of a topological space X is called a retract
of X if there exists a continuous map r : X −→ A, called a retraction, such that
r(a) = a for any a ∈ A.

Definition 6.3.11. [57]. A subset A of space X is a deformation retract of X if
there exists a retraction r and a continuous map

f : X × I → X (6.5)

such that
f(x, 0) = x #
x ∈ X
f(x, 1) = r(x) (6.6)
f(a, t) = a, a ∈ A and t ∈ I

In other words, set A ⊂ X is a deformation retract of X if X can be continu-
ously deformed into A. We show below that D f is a deformation retract of J f .

Let J p , J pf ,and J be as defined in the previous section; then we have the
f
following lemma.
Lemma 6.3.7. J p is a deformation retract of J, and J pf is a deformation retract

of J .
f
Define r(j 1 ,j 2 ,l 3 ) = (j 1 ,j 2 , 0). It follows from Lemma 6.3.2 that r is a retrac-
tion. Since for Type 1 and 2 obstacles P m −1 (P m (O J )) = O J , then, if J contains