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

MOTION PLANNING WITH INCOMPLETE INFORMATION 57

In motion planning with uncertainty, the guarantee of a solution—which is
predicated on the algorithm convergence—should be distinguished from the guar-
antee of the solution optimality. As we will see, the former is feasible even in
a very complex environment, whereas the latter is not feasible with the best of
algorithms. No optimality of the solution can be promised even if only a small
piece of information about the environment is missing. One’s path that may look
ill-conceived with hindsight may not have been planned any better with the infor-
mation available at the time. A person visiting a big building for the first time
should not be blamed for wandering around in search of a desired office. We are
also familiar with similar patterns taking place in time, rather than in space. If a
stock market investor had tomorrow’s information, he would have become rich
quickly. Given that he doesn’t, his actual behavior may look less than optimal a
few days or weeks later.
If the path optimality is not a good criterion, how does one judge the per-
formance of a motion planning algorithm with uncertainty? Given the real-time
nature of SIM algorithms, they are expected to allow reasonably fast process-
ing and to produce “reasonable quality” paths. The first requirement is easier
to grasp: It is clear that a robot cannot afford to spend a minute on calculation
of a step of a continuous path that takes 20 ms to execute. For the algorithm
performance, standard complexity theory performance estimates call for lower
and upper bounds on the problem itself and on specific algorithms, as a function
of the problem complexity. 5
What is a “reasonable” path? In general, how do we assess algorithms’ perfor-
mance? The problem complexity is presented in complexity theory as a function
of the number of elements in the problem at hand. In our case the scene complex-
ity cannot be assessed in these terms because it may never be known, and even
the notion itself of the scene complexity is very unclear. Unstructured environ-
ments typically include “shapeless” objects: Representing them with analytical
entities is difficult because, again, objects are not known in advance.
Doing this would be also pointless because this representation is unrelated to
what is easy or difficult for SIM algorithms. What we may think of as a complex
shape may be as easy or difficult for a SIM algorithm as a simple shape. As
another option, one might argue that because in any realistic system the robot
moves in discrete steps, those steps might be used to build a real-time objects’
approximation. This choice is also hard to defend because the size and number
of those steps may differ from one robot control system to the other. What is left
is to estimate the quality of the path itself that the algorithm generates.
A better measurement of algorithm efficiency in the case with uncertainty is a
function tied to the length of paths that the algorithm generates. More precisely,
the criterion measures the extent of the robot’s “wandering” under a given algo-
rithm: It assesses the maximum number of times, n, of the robot’s retracing some
segments of its path. When comparing algorithms, this upper bound will actually

5 Less rigorous ways may include, for example, a direct comparison of an algorithm’s results with
those of other existing algorithms, or with the performance of an “average” human traveler.