Page 303 - Introduction to AI Robotics

286
7
The Hybrid Deliberative/Reactive Paradigm
served as an excellent example of why deliberation and reaction were largely
separate, and reinforced a “plan once, execute lots” mentality. However, ad-
vances in technology and new domains are causing researchers to rethink
the strict separation.
By the early 1990’s, many algorithms existed which if given a two or even
three dimensional map could compute an optimal path for a robot to take
through the world. These path planning algorithms exhibited several draw-
backs. One was that they were all computationally expensive, taking be-
tween 5 and 15 minutes to execute. This prevented the robot from continu-
ously generating the path. But as was seen with Shakey, if the robot tried to
execute a pre-computed path, it would be vulnerable to unexpected changes
in the world. That map would represent the best, currently available know-
ledge about the world: where obstacles were, unpassable terrain, etc. But
a map is at best a representation of a closed world; it can’t show what has
changed since it was built, unless a robot goes there and senses it. So the
robot can generate an optimal path, but it may discover an unmodeled ob-
stacle blocking that path. If the robot was just using the precomputed path to
navigate, it would have to stop, update the map with the newly discovered
obstacle, then replan the optimal path, resulting in slow progress.
If the robot used reactive behaviors to navigate, there was no guarantee
that it would make it to the goal any faster. Even if it headed off in the right
direction, it might spend time getting into and out of box canyons. By letting
the robot solely react to the world, it might make poor choices.
The common solution was to mix path planning and reaction by having
a planning algorithm in the cartographer generate a complete optimal route
for the robot to take, but then decompose that route into segments, usually
WAYPOINT straight lines. The end of each path segment is called a waypoint,because
it is a point along the way to the final goal. Each waypoint can be a goal
to reach, which can be accomplished by behaviors (move-to-goal(), avoid-
obstacles()). When the robot reaches the first goal, the sequencer agent can
give the behavioral manager the coordinates or landmarks for the next goal,
and so on. Notice this allows computationally expensive path planning to
occur only once, and then the behaviors take care of actually navigating.
As will be seen in Part II, this strategy has its own set of drawbacks. But
for the most part it is a well-accepted means of partitioning deliberation and
reaction in navigation. However, with the advent of the Intel Pentium and
Sparc microprocessors, the computational demands of path planning algo-
rithms have been mitigated. Algorithms which ran on the order of once
every 10 minutes can now execute once every second. As a result, the mis-