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

322 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

T b T T T

g 1 g 2 g 1 g 2
a a a a
S S
g 4 g 3 g 3
T T
T b T b
(a)
g 1 g 2
(b)
S
T
g g
2
1
T
S
a g g 1
S 2
g 3 S S
g 3 g a g
b 3 3
T T
T b T
g 1 g 2
(c) g 1 g 2
S S (d)
Figure 6.17 Paths g 1 ,g 2 ,and g 3 constitute a complete set of generic paths. A hexagon
is obtained by (a) cutting the square along g 1 ,g 2 ,and g 3 , (b) pasting along b,and (c)
pasting along a. (d) The resulting hexagon.

Now consider the effects of the above operation on obstacles (see Figure 6.18a).
Obstacle boundaries and the generic paths partition our hexagon into occupied
areas (shaded areas in Figure 6.18b) and free areas (numbered I, II, III, IV and V
in Figure 6.18b). Each free area is not necessarily simple, but it must be homeo-
morphic to a disc, possibly with one or more smaller discs removed (e.g., area I of
Figure 6.18b has the disc that corresponds to obstacle O 2 removed). The free area’s
inner boundaries are formed by obstacle boundaries; its outer boundary consists of
segments of obstacle boundaries and segments of the generic paths.
Any arbitrary obstacle-free path p that connects points S and T consists of one
or more segments, p 1 ,p 2 ,. ..,p n , in the hexagon. Let x i , y i be the end points of
segment p i ,where x 1 = S, x i+1 = y i for i = 1, 2,...,n − 1, and y n = T .Since
p is obstacle-free, x i and y i must be on the outer boundary of the free area

that contains p i . Therefore, x i and y i can be connected by a path segment p of
i

the outer boundary of the free area. The path p = p p . ..p that connects S

1 2 n
and T and consists of segments of the generic paths and segments of obstacle
boundaries is therefore entirely on the connectivity graph G.