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

THREE-LINK XXP ARM MANIPULATORS 325

• C p ∩ ∂(O C1 ∪ O C2 )—the intersection curve between the floor and the Type
1 or Type 2 obstacle boundary, identified by the fact that the third link of
the robot reaches its lower joint limit (l 3 = 0) and simultaneously, one or
both of the other two links contact some obstacles.
∩ ∂J—the intersection curve between the Type 3 − obstacle bound-
• ∂O C3 −
ary and C-space boundary, identified by the fact that the robot’s third link
touches obstacles with its rear part and, simultaneously, one or more links
reach their joint limits; this case includes the intersection curve between a
Type 3 − obstacle boundary and the ceiling.
∩ ∂(O C1 ∪ O C2 )—the intersection curve between the Type 3 − obsta-
• ∂O C3 −
cle boundary and the Type 1 or Type 2 obstacle boundary, identified by the
fact that the third link of the robot touches obstacles with its rear part
and that, simultaneously, one or both of the other two links contact some
obstacles.
—the intersection curve between the Type 3 + obstacle
∩ ∂O C3 +
• ∂O C3 −
boundary and the Type 3 − obstacle boundaries, identified by the fact that
both front and rear parts of the third link contact obstacles.
• g ∩ J pf —the obstacle-free portion of the generic path, identified by the
fact that the robot is on the V-surface and that the third joint reaches its
lower limit (l 3 = 0).
—the intersection curve between V-surface and the Type 3 −
• V ∩ ∂O C3 −
obstacle boundaries, identified by the fact that the robot is on V-surface and
simultaneously touches the obstacle with the rear part of its third link.

Note that the sensing capability of the robot arm manipulator allows it to
easily identify the fact of being at any of the curves above.

6.3.7 Lifting 2D Algorithms into 3D
We have reduced the problem of motion planning for an XXP arm to the search
on a connectivity graph. The search itself can be done using any existing graph
search algorithm. The efficiency of a graph search algorithm is often in gen-
eral—and, as we discussed above, in the Piano Mover’s approach in particu-
lar—measured by the total number of nodes visited and the number of times
each node is visited, regardless of the number of times that each edge is visited.
In robotics, however, what is important is the total number of edge traverses,
because physically each edge presents a part of the path whose length the robot
may have to pass. For this reason, typical graph algorithms—for example, the
width-first search algorithm [114]—would be inefficient from the standpoint of
robot motion planning. On the other hand, depth-first search algorithms may
work better; Tarry’s rule [42] and Fraenkel’s rule [45], which we discussed in
Section 2.9.1, are two versions of such search algorithms. More efficient algo-
rithms can be obtained by taking into account specifics of the connectivity graph
topology [59].