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

306 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

In particular, in Section 6.3.1 we define the arm configuration L j = L(j) as
3
an image of a continuous mapping from J-space to 3D Cartesian space ,which
is the connected compact set of points the arm would occupy in 3D space when
its joints take the value j. A real-world obstacle is the interior of a connected
3
compact point set in . Joint space obstacles are thus defined as sets of points in
joint space whose corresponding arm configurations have nonempty intersections
with real-world obstacles. The task is to generate a continuous collision-free
motion between two given start and target configurations, denoted L s and L t .
Analysis of a J-space in Section 6.3.2 will show that a J-space exhibits
distinct topological characteristics that allow one to predict global characteristics
of obstacles in J based on the arm local contacts with (that is, sensing of)
obstacles in the workspace. Furthermore, similar to the Cartesian arm case in
Section 6.2, for all XXP arms the obstacles in J exhibit a property called the
monotonicity property, as follows: For any point on the surface of the obstacle
image, there exists one or more directions along which all the remaining points
of J belong to the obstacle. The geometric representation of this property will
differ from arm to arm, but it will be there and topologically will be the same
property. These topological properties bring about an important result formulated
in Section 6.3.3: The free J-space, J f , is topologically equivalent to a generalized
cylinder. This result will be essential for building our motion planning algorithm.
Deformation retracts D of J and D f of J f , respectively, are defined in
Section 6.3.4. By definition, D f is a 2D surface that preserves the connectiv-
ity of J f . That is to say, for any two points j s ,j t ∈ J f , if there exists a path
p J ⊂ J f connecting j s and j t , then there must exist a path p D ⊂ D f connecting
j s and j t ,and p D is topologically equivalent to p J in J f . Thus the dimensionality
of the planning problem can be reduced.
When one or two X joints in XXP are revolute joints, X = R, J is somewhat
less representative of W, only because the mapping from J to W is not unique.

That is, it may happen that L(j) = L(j ) for j = j .Let S J ={j ∈ J|L(j) =
L s } and T J ={j ∈ J|L(j) = L t }. The task in J-space is to find a path between
any pair of points j s ∈ S J and j t ∈ T J . We define in Section 6.3.5 a configuration
space or C-space, denoted by C, as the quotient space of J over an equivalent
relation that identifies all J-space points that correspond to the same robot arm
configuration. It is then shown that B and B f , the quotient spaces of D and D f
over the same equivalent relation, are, respectively, deformation retracts of C and
C f . Therefore, the connectivity between two given robot configurations in C can
be determined in C f .
A connectivity graph G will be then defined in Section 6.3.6, and it will
be shown that G preserves the connectivity of D f and J f . We will conclude
that the workspace information available to the 3D robot is sufficient for it to
identify and search the graph, and therefore the problem of 3D arm motion plan-
ning can be reduced to a graph search—something akin to the maze-searching
problem in Chapter 3. Finally, in Section 6.3.7 we will develop a systematic
approach, which, given a 2D algorithm, builds its 3D counterpart that preserves
convergence.