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

318 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

only Type 1 and Type 2 obstacles—that is, J f = J − (O J1 ∪ O J2 )—it follows

that J f = J and J pf is a deformation retract of J f . In the general case, all
f
obstacle types (including Type 3) can be present, and J pf is not necessarily a
deformation retract of J f .

∩ J f , and Q 2 = J p ∩ J f . Then,
Theorem 6.3.5. Let Q 1 = ∂O J3 −

D f = Q 1 ∪ Q 2
is a deformation retract of J f .

and J p . It is easy
Q 1 and Q 2 , are respectively, the obstacle-free portion of ∂O J3 −

to see that D f = J pf .Since J f = J (Theorem 6.3.3) and J pf is a deformation
∼
∼
f

retract of J (Lemma 6.3.7), then D f is a deformation retract of J f .
f
Let D denote the 2D space obtained by patching all the “holes” in D f so that
∼
D = J p . It is obvious that D is a deformation retract of J.

Theorem 6.3.6. Given two points j ,j ∈ D f , if there exists a path p J ⊂ J f
s t

connecting j and j , then there exists a path p D ⊂ D f , such that p D ∼ p J .

s t
From Theorem 6.3.5, D f is a deformation retract of J f .Let r be the retraction
as in Ref. 57, II.4; then p = r(p) must be an equivalent path in D f .

On the other hand, if j and j are not connected in J f , then by definition j s

t
s

and j are not connected in D f either. Hence the connectivity of j and j can

t
s
t
be determined completely by studying D f , which is simpler than J f because
the dimensionality of D f is lower than that of J f . Furthermore, a path between
two given points j s = (j 1s ,j 2s ,l 3s ), j t = (j 1t ,j 2t ,l 3t ) ∈ J f can be obtained by

finding the path between the two points j = (j 1s ,j 2s ,l ), j = (j 1t ,j 2t ,l ) ∈
s 3s s 3t
D f . Because of the monotonicity property (Theorem 6.3.2), j and j always exist

s t
and they can be respectively connected within J f with j s and j t via vertical line
segments. Hence the following statement:
Corollary 6.3.2. The problem of finding a path in the 3D subset J f between
points j s ,j t ∈ J f can be reduced to one of finding a path in its 2D subset D f .
6.3.5 Configuration Space and Its Retract
Our motion planning problem has thus been reduced to one of moving a point
in a 2D subset of J-space, J. However, as pointed out in Section 6.3.1, the joint
space J is not very representative when revolute joints are involved, because the
mapping from J to workspace W is not unique. Instead, we define configuration
space C:
Definition 6.3.12. Define an equivalence relation F in J as follows: for j =

(j 1 ,j 2 ,j w ), j = (j ,j ,j ) ∈ J, jFj if and only if (j i − j )%2π = 0,for i =
1 2 3 i