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

272 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

Assume the bug’s target location is somewhere on the other side of the obstacle.
One way for it to continue its motion is to first pass around the obstacle. The bug
has only two options: It can pass the obstacle from the left or it can pass it from the
right, clockwise or counterclockwise. If neither option leads to success—let us
assume it is a smart bug, with a reasonably good motion planning skills—the goal
is not achievable. In this case, by slightly exaggerating the bug’s stubbornness,
we will note that eventually the bug will come back to the point on the obstacle
where it started. It took only one simple going around, all in one direction, to
explore the whole obstacle. That is the essence of the 2D case.
Imagine now a fly that is flying around a room—that is, in 3D space. Imagine
that on its way the fly encounters a (3D) obstacle—say, a child’s balloon hanging
on a string. Now there is an infinite number of routes the fly can take to pass
around the obstacle. The fly would need to make a great many loops around the
obstacle in order to explore it completely. That’s the fundamental difficulty of the
3D case; in theory it takes an infinitely long path to explore the whole obstacle,
1
even if its dimensions and volume are finite and modest. The point is that while
in the 2D case a mobile robot has a theoretically guaranteed finite solution, no
such solution can be guaranteed for a 3D mobile robot. The 3D sensor-based
motion planning problem is in general intractable.
The situation is more complex, but also not as hopeless, for 3D arm manip-
ulators. Try this little experiment. Fix your shoulder and try to move your hand
around a long vertical pole. Unlike a fly that can make as many circles around
the pole as it wishes, your hand will make about one circle around the pole
and stop. What holds it from continuing moving in the same direction is the
arm’s kinematics and also the fact that the arm’s base is “nailed down.” The
length of your arm links is finite, the links themselves are rigid, and the joints
that connect the links allow only so much motion. These are natural constraints
on your arm movement. The same is so for robot arm manipulators. In other
words, the kinematic constraints of an arm manipulator impose strong limitations
on its motion.
This fact makes the problem of sensor-based motion planning for 3D arm
manipulators manageable. The hope is that the arm kinematics can be effectively
exploited to make the problem tractable. Furthermore, those same constraints
promise a constructive test of target reachability, similar to those we designed
above for mobile robots and 2D arm manipulators.
As noted by Brooks [102], the motion planning problem for a manipulator with
revolute joints is inherently difficult because (a) the problem is nondecomposable,
(b) there may be difficulties associated with rotations, (c) the space representation
and hence the time execution of the algorithm are exponential in the number of
robot’s degrees of freedom of the objects involved, and (d) humans are especially
poor at the task when much reorientation is needed, which makes it difficult to

1 One may argue that the fly can use its vision to space its loops far enough from each other, making
the whole exercise quite doable. This may be true, but not so in general: The room may be dark, or
the obstacle may be terribly wrinkled, with caves and overhangs and other hooks and crannies so
that the fly’s vision will be of little help.