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

MOTION PLANNING WITH INCOMPLETE INFORMATION 69

(b) the robot uses only a small amount of local information about obstacles
delivered by its sensors, and (c) the complexity of motion planning is a constant
function of the complexity of obstacles (interpreted as above, as the maximum
number of times the robot visits some pieces of its path). We will build these
algorithms in the following chapters. For now, it is clear that, if feasible, such
procedures will likely save the robot a tremendous amount of data processing
compared to models with complete information.
The only complete (nonheuristic) algorithm for path planning in an uncertain
environment that was produced in this earlier period seems to be the Pledge
algorithm described by Abelson and diSessa [36]. The algorithm is shown to
converge; no performance bounds are given (its performance was assessed later
in Ref. 56). However, the algorithm addresses a problem different from ours:
The robot’s task is to escape from an arbitrary maze. It can be shown that the
Pledge algorithm cannot be used for the common mobile robot task of reaching
a specific point inside or outside the maze.
That the convergence of motion planning algorithms with uncertainty cannot
be left to one’s intuition is underscored by the following example, where a
seemingly reasonable strategy can produce disappointing results. Consider this
9
algorithm; let us call it Optimist :

1. Walk directly toward the target until one of these occurs:
(a) The target is reached. The procedure stops.
(b) An obstacle is encountered. Go to Step 2.
2. Turn left and follow the obstacle boundary until one of these occurs:
(a) The target is reached. The procedure stops.
(b) The direction toward the target clears. Go to Step 1.

Common sense suggests that this procedure should behave reasonably well, at
least in simpler scenes. Indeed, even complex-looking examples can be readily
designed where the algorithm Optimist will successfully bring the robot to the
target location. Unfortunately, it is equally easy to produce simple scenes in
which the algorithm will fail. In the scene shown in Figure 2.23a, for example,
the algorithm would take the robot to infinity instead of the target, and in the scene
of Figure 2.23b the algorithm forces the robot into infinite looping. (Depending
on the scheme’s details, it may produce the loop 1 or the loop 2.) Attempts
to fix this scheme with other common-sense modifications—for example, by
alternating the left and right direction of turns in Step 2 of the algorithm—will
likely only shift the problem: the algorithm will perhaps succeed in the scenes
in Figure 2.23 but fail in some other scenes.
This example suggests that unless convergence of an algorithm is proven
formally, the danger of the robot going astray under its guidance is real. As
we will see later, the problem becomes even more unintuitive in the case of

9 The procedure has been frequently suggested to me at various meetings.