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

52 A QUICK SKETCH OF MAJOR ISSUES IN ROBOTICS

By the late 1980s and early 1990s, it was slowly becoming clear that the
domains to benefit from the Piano Mover’s approach related not so much to
robotics as to some other specialized areas where “clean” information would be
available. One would read less about robots and more about a strategy for a
quick extraction of an assembly unit from an aircraft engine without disassembly
of the whole engine; or of optimizing the design of a car door opening so as
to simplify the installation of car seats; or of finding the route that a protein
molecule follows when folding into a complex shape during the DNA mapping
of proteins. Note that in these cases the complete aircraft engine database, or
a complete car body database, or a complete database of the protein geometry
would be available beforehand.
The way the Piano Movers strategies proceed is as follows. Before the motion
planning proper is attempted, the task’s configuration space (C-space) is cal-
culated. Assume for now that the robot—or, in general, an object for which
the motion planning task is contemplated—is a rigid body moving in two-
dimensional (2D) space (see object A, Figure 2.15a). In C-space the robot shrinks
to a point, whereas the surrounding objects—we call them obstacles—are grown
accordingly, to compensate for the shrinking robot.
Free subspace of C-space is the complement to the grown obstacles. Any path
that lies in a continuous subset of free space is a physically realizable path for
object A. In order to decide which areas of free space are connected and which
are disconnected, and whether and how two patches of free space can be passed
from one to another, an additional intermediate structure is built, the connectivity
graph of C-space. A path is then declared to exist if the start and the destination
nodes on the connectivity graph are connected [11, 13].

O 2

T T

O 1
A
S S

(a) (b)
Figure 2.15 (a) The task is to move object A from its starting position S to the target
position T , while keeping its orientation constant. (b) The C-space of task (a): Object A
shrinks to a point, and obstacles O 1 and O 2 grow accordingly. Notice a simple fact: For
A to be able to pass between O 1 and O 2 in the physical space (a), the grown obstacles
in (b) must not overlap.