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

10 MOTION PLANNING—INTRODUCTION

complementary, human–robot teams may be more successful than each of them
separately and more successful than today’s typical master–slave human–robot
teleoperation systems are. When contributing skills that the other partner lacks,
each partner in the team will fully rely on the other. For example, a surgeon may
pass to a robot the subtask of inserting the cutting instrument and bringing it to
a specific location in the brain.
There are a number of generic tasks that require motion planning. Here we
are interested in a class of tasks that is perhaps the most common for people and
animals, as well as for robots: One is simply requested to go from location A to
location B, typically in an environment filled with obstacles. Positions A and B
can be points in space, as in mobile robot applications, or, in the case of robot
manipulators, they may include positions of every limb.
Limiting our attention to the go-from-A-to-B task leaves out a number of
other motion planning problems—for example, terrain coverage, map-making,
lawn mowing [1]; manipulation of objects, such as using the fingers of one’s hand
to turn a page or to move a fork between fingers; so-called power grips, as when
holding an apple in one’s hand; tasks that require a compressed representation
of space, such as constructing a Voronoi diagram of a given terrain [2]; and so
on. These are more specialized though by no means less interesting problems.
The above division of approaches to the go-from-A-to-B problem into two
complementary groups—(1) motion planning with complete information and
(2) motion planning with incomplete information—is tied in a one-to-one fashion
to still another classification, along the scientific tools in the foundation of those
approaches. Namely, strategies for motion planning with complete information
rely exclusively on geometric tools, whereas strategies for motion planning with
incomplete information rely exclusively on topological tools. Without going into
details, let us summarize both briefly.

1. Geometric Approaches. These rely, first, on geometric properties of space
and, second, on complete knowledge about the robot itself and obstacles in the
robot workspace. All those objects are first represented in some kind of database,
typically each object presented by the set of its simpler components, such as a
number of edges and sides in a polyhedral object. According to this approach,
then, passing around a hexagonal table is easier than passing around an octagonal
table, and much easier than passing around a curved table, because of these three
the curved table’s description is the most complex.
Then there is an issue of information completeness. We can hear sometimes,
“I can do it with my eyes shut.” Note that this feat is possible only if the objects
involved are fully known beforehand and the task in hand has been tried many
times. A factory assembly line or the list of disassembly of an aircraft engine are
examples of such structured tasks. Objects can be represented fully only if they
allow a final size (practical) description. If an object is an arbitrary rock, then
only its finite approximation will do—which not only introduces an error, but is
in itself a nontrivial computational task.