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

50 A QUICK SKETCH OF MAJOR ISSUES IN ROBOTICS

happens to be coming in real time from robot sensors, and thus there is always
uncertainty about the robot’s surroundings, one is forced to turn to the second
approach, SIM.
In other words, as a rule, only one approach applies to a given task. Consider,
for example, a maze-searching task (called also a mouse-in-the-labyrinth prob-
lem). One starts at some starting point S inside the labyrinth and attempts to reach
2
some target point T , also in the labyrinth. Imagine we have in our possession
complete information about the labyrinth. We can feed these data into the com-
puter, produce the bird’s-eye view of the maze, and study the problem in great
detail using this map. We can investigate different paths between points S and T ,
figure out the optimal (shortest) path, and so on. This is planning with complete
information, and the Piano Mover’s model should be the preferred approach.
On the other hand, if all of a sudden you find yourself in a maze, at any given
moment you would see only the surrounding walls of the maze and perhaps
remember a few corridors that you have just passed. You do not know what is
ahead; input information is scant; what you learn comes from your sensors. Any
movement, including the unfortunate deviations into dead end corridor appen-
dices, becomes a part of the path. Doing anything approaching an optimal path
is of course out of the question. Here you deal with incomplete information and
produce the path as you go. This is planning with incomplete information, and
so you need to turn to the SIM techniques.
Since robot motion planning is the topic of this book, in Sections 2.8 and 2.9
we will further explore differences between these two paradigms for motion
planning, the Piano Mover’s model and the Sensing–Intelligence–Motion model.

Provable Versus Heuristic Algorithms. Another important distinction between
algorithms is between provable (other terms: nonheuristic, exact, algorithmic)
and heuristic approaches.
A provable motion planning algorithm is one for which there is a guarantee
that if a path between the starting and target points exist, the algorithm will
find one in finite time and without an exhaustive search—or else will conclude
in finite time that there is no path if such is the case. We then say that the
algorithm converges. To obtain such a guarantee, people go through the trouble
of proving the algorithm convergence. An algorithm itself should allow such
a proof; for example, the so-called “common sense” strategies—we call them
heuristic algorithms—do not allow a proof of convergence and are not likely to
be convergent.
Whereas for some applications, having a guarantee of convergence may be
a moot point—as, for example, when the user’s knowledge or intuition pretty
much replaces it—for more complex cases, seeking convergence reflects more
than a love for academic purity. As we will see in Chapter 7, in complex prob-
lems—most motion planning problems with robot arm manipulators fit this
2 In other variations of this problem, one starts inside the maze and tries to find an exit from it; or,
one starts outside the maze and tries to reach the location with a hidden treasure somewhere inside
the labyrinth.