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

THREE-LINK XXP ARM MANIPULATORS 321

The proof is analogous to that of Theorem 6.3.5. Let B denote the 2D space
∼
obtained by patching all the “holes” in B f so that B = C p . It is obvious that
∼
∼
B = C p = T is a deformation retract of C. We obtain the following statement
parallel to Theorem 6.3.6.

Theorem 6.3.12. Given two points j , j ∈ B f , if there exists a path p C ⊂ C f
t
s

connecting j and j , then there must exist a path p B ⊂ B f , such that p B ∼ p J .

t
s
A path between two given points j s = (j 1s ,j 2s ,l 3s ), j t = (j 1t ,j 2t ,l 3t ) ∈ C f

can be obtained by finding the path between the two points j = (j 1s ,j 2s ,l ),
s
3s

j = (j 1t ,j 2t ,l ) ∈ B f . Because of the monotonicity property (Theorem 6.3.10),
s
3t

j and j always exist and can be respectively connected within C f with j s and

t
s
j t via vertical line segments. Hence the following statement:
Corollary 6.3.4. The problem of finding a path in C f between points j s , j t ∈ C f
can be reduced to that of finding a path in its subset B f .
6.3.6 Connectivity Graph
At this point we have reduced the problem of motion planning for an XXP
arm in 3D space to the study of a 2D subspace B that is homeomorphic to a
common torus.
Consider the problem of moving a point on a torus whose surface is populated
with obstacles, each bounded by simple closed curves. The torus can be repre-
sented as a square with its opposite sides identified in pairs (see Figure 6.17a).
Note that the four corners are identified as a single point. Without loss of gen-
erality, let the start and target points S and T be respectively in the center and
the corners of the square. This produces four straight lines connecting S and T ,
each connecting the center of the square with one of its corners. We call each
line a generic path and denote it by g i , i = 1, 2, 3, 4.
Define a connectivity graph G on the torus by the obstacle-free portions of
any three of the four generic paths and the obstacle boundary curves. We have
the following statement:
Theorem 6.3.13. On a torus, if there exists an obstacle-free path connecting two
points S and T , then there must exist such a path in the connectivity graph G.

Without loss of generality, let g 1 , g 2 ,and g 3 be the complete set of generic
paths, as shown in Figure 6.17a, where the torus is represented as a unit square
with its opposite sides identified.
The generic paths g 1 , g 2 ,and g 3 cut the unit square into three triangular pieces.
Rearrange the placements of the three pieces by identifying the opposite sides
of the square in pairs along edges a and b, respectively (see Figures 6.17b and
6.17c). We thus obtain a six-gon (hexagon), with three pairs of S and T as its
vertices and generic paths g 1 , g 2 ,and g 3 as its edges. The hexagon presentation
is called the generic form of a torus.