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

INTRODUCTION 11

If the task warrants a geometric approach to motion planning, this will likely
offer distinctive advantages. One big advantage is that since everything is known,
one should be able to execute the task in an optimal way. Also, while an increased
dimensionality raises computational difficulties—say, when going from two-
dimensional to three-dimensional space or increasing the robot or its workspace
complexity—in principle the solution is still feasible using the same motion
planning algorithm.
On the negative side, realizing a geometric approach typically carries a high,
not rarely unrealistic, computational cost. Since we don’t know beforehand what
information is important and what is not for motion planning, everything should
be in. As we humans never ask for “complete knowledge” when moving around,
it is not obvious how big that knowledge can be even in simple cases. For
example, to move in a room, the database will have to include literally every nut
and bolt in the room walls, every screw holding a seat in every chair in the room,
small indentations and extensions on the robot surface etc. Usually this comes
to a staggering amount of information. The number of those details becomes a
measure of complexity of the task in hand.
Attempts have been made to connect geometric approaches with incomplete
sources of information, such as sensing. The inherent need of this class of
approaches in a full representation of geometric data results in somewhat arti-
ficial constructs (such as “continuous” or “X-ray” or “seeing-through” sensors)
and often leads to specialized and hard-to-ascertain heuristics (see some such
ideas in Ref. 3).
With even the most economical computational procedures in this class, many
tasks of practical interest remain beyond the reach of today’s fastest computers.
Then the only way to keep the problem manageable is to sacrifice the guarantee
of solution. One can, for example, reduce the computational effort by approxi-
mating original objects with “artificial” objects of lower complexity. Or one can
try to use some beforehand knowledge to prune nonpromising path options on
the connectivity graph. Or one can attempt a random or pseudorandom search,
checking only a fraction of the connectivity graph edges. Such simplification
schemes leave little room for directed decision-making or for human intuition.
If it works, it works. Otherwise, a path that has been left out in an attempt to
simplify the problem may have been the only feasible path. The ever-increasing
power of today’s computer make manageable more and more applications where
having complete information is feasible.
The properties of geometric approaches can be summarized as follows (see
also Section 2.8):
(a) They are applicable primarily to situations where complete information
about the task is available.
(b) They rely on geometric properties (dimensions and shapes) of objects.
(c) They can, in principle, deliver the best (optimal) solution.
(d) They can, in principle, handle tasks of arbitrary dimensionality.