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

COLLISION AVOIDANCE 49

volume and tremendous complexity and can tax the most advanced computers.
The less knowledge about its surroundings the robot needs for successful collision
avoidance, the more attractive the corresponding strategy. In this sense, collision
avoidance is an information-theoretical problem.
Once the robot knows enough about objects in its surroundings, it has to figure
out how to avoid those objects, while not jeopardizing its primary task. If moving
my hand to replace a book on the shelf is about to cause my elbow to bump into
a nearby file cabinet, there are great many ways to avoid the collision—I just
need to think about this. I may think hard and slowly, or I may react instantly
based on my instincts and experience; either way, I am using my intelligence to
avoid collision. This example suggests that collision avoidance is a problem of
artificial intelligence.
Collision avoidance relates to moving in space among objects; hence it is not
surprising that collision avoidance is heavily tied to concepts and techniques from
geometry and topology. Objects in the robot workspace that are to be avoided
may be static, or they may be moving. Moving obstacles add to complexity of the
collision avoidance problem. Some techniques are amenable to moving obstacles
and some are not. While this book addresses static obstacles, we will stress the
applicability of some strategies to moving obstacles. Most of the time we will
limit the discussion to the effects of kinematics, leaving out the robot dynamics.
Some collision avoidance problems with dynamics are considered in Chapter 4.
The information-theoretical base of the collision avoidance problem gives rise
to one classification of motion planning strategies that turns out to be very pro-
ductive. The classification divides all approaches into two groups, each presenting
a distinct paradigm:

• Motion planning with complete information, also called in literature the
Piano Mover’s model or off-line planning approach. Here the path is com-
puted all at once before the motion starts; in principle, an optimal path can
be found in this way.
• Motion planning with incomplete information, also called sensor-based
motion planning or on-line motion planning,or path planning with uncer-
tainty,orthe Sensing–Intelligence–Motion (SIM) paradigm. Here the
decision-making is done continuously as the robot moves along, based on
on-line information, such as from sensors. By its very nature, an optimal
solution is ruled out in this formulation. 1

A simple relation governs the choice of one or the other approach in robot
applications. If all the information necessary to produce the desired path is avail-
able beforehand one would want to produce the path beforehand and would
hence choose the Piano Movers approach. On the other hand, if the information

1 The term “reactive planning” that is used sometimes in literature in reference to sensor-based motion
planning is unfortunate: It emphasizes the operation’s local nature, suggests that intelligence is not
necessary, and hides the global component of motion planning, with its algorithmic connections to
convergence and computational complexity.