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

76 MOTION PLANNING FOR A MOBILE ROBOT

These attractive points of sensor-based planning stands out when comparing it
with the paradigm of motion planning with complete information (the Piano
Mover’s model). The latter requires the complete information about the scene,
and it requires it up front. Except in very simple cases, it also requires formidable
calculations; this rules out a real-time operation and, of course, handling moving
or shape-changing obstacles.
From the standpoint of theory, the main attraction of sensor-based planning
is the surprising fact that in spite of the local character of robot sensing and the
high level of uncertainly—after all, practically nothing may be known about the
environment at any given moment—SIM algorithms can guarantee reaching a
global goal, even in the most complex environment.
As mentioned before, those positive sides of the SIM paradigm come at a price.
Because of the dynamic character of incoming sensor information—namely, at
any given moment of the planning process the future is not known, and every new
step brings in new information—the path cannot be preplanned, and so its global
optimality is ruled out. In contrast, the Piano Mover’s approach can in principle
produce an optimal solution, simply because it knows everything there is to
1
know. In sensor-based planning, one looks for a “reasonable path,” a path that
looks acceptable compared to what a human or other algorithms would produce
under similar conditions. For a more formal assessment of performance of sensor-
based algorithms, we will develop some bounds on the length of paths generated
by the algorithms. In Chapter 7 we will try to assess human performance in
motion planning.
Given our continuous model, we will not be able to use the discrete cri-
teria typically used for evaluating algorithms of computational geometry—for
example, assessing a task complexity as a function of the number of vertices
of (polygonal or otherwise algebraically defined) obstacles. Instead, a new path-
length performance criterion based on the length of generated paths as a function
of obstacle perimeters will be developed.
To generalize performance assessment of our path planning algorithms, we
will develop the lower bound on paths generated by any sensor-based planning
algorithm, expressed as the length of path that the best algorithm would produce
in the worst case. As known in complexity theory, the difficulty of this task lies
in “fighting an unknown enemy”—we do not know how that best algorithm may
look like.
This lower bound will give us a yardstick for assessing individual path plan-
ning algorithms. For each of those we will be interested in the upper bound on the
algorithm performance—the worst-case scenario for a specific algorithm. Such
results will allow us to compare different algorithms and to see how far are they
from an “ideal” algorithm.
All sensor-based planning algorithms can be divided into these two nonover-
lapping intuitively transparent classes:

1 In practice, while obtaining the optimal solution is often too computationally expensive, the ever-
increasing computer speeds make this feasible for more and more problems.