Page 384 - Introduction to AI Robotics

367
10.6 Interleaving Path Planning and Reactive Execution
An attractive feature of wavefront propagation is how it treats terrain types.
A modeled obstacle can have a conductivity of 0.0 (no heat can be propagated
through that grid element), while an open area has infinite conductivity. But
undesirable terrains, which are traversable, but not desirable to go across,
can be given a low value of conductivity. This means that heat will travel
slower through undesirable regions. But it may turn out that this is the best
path, even with the loss through the undesirable regions. A wavefront nat-
urally handles the tradeoffs between a longer path through desirable terrain
versus taking shortcuts through less desirable terrain.
The examples in Fig. 10.12 use the Trulla planner. Undesirable terrain is
shown on the Trulla display in gray, obstacles in black and open areas in
white. The intensity of gray reflects the degree of undesirability of the ter-
rain. In Fig. 10.12a, the robot Clementine can move over an extension cord
but would prefer not to, as shown by the gray region. The path planner ac-
cordingly routes her around the cord. In Fig. 10.12 this isn’t possible due to
the placement of obstacles. Therefore, she has to cut through.

10.6 Interleaving Path Planning and Reactive Execution

Most path planning algorithms are employed in a strictly plan once, then
reactively execute style. Almost all techniques break a path into segments;
even a wavefront planner actually produces a goal location (waypoint) for
each directional vector. This is well suited for a Hybrid architecture with a
Cartographer handing off path segments, or an entire path, for a Sequencer.
The Sequencer can then employ a series of move-to-goal behaviors, deacti-
vating and re-instantiating the behavior as a new subgoal is met. Unfortu-
nately there are two problems with reactive execution of a metric path as
SUBGOAL OBSESSION described above: subgoal obsession and the lack of opportunistic replanning.
OPPORTUNISTIC Subgoal obsession is when the robot spends too much time and energy trying
REPLANNING
to reach the exact subgoal position, or more precisely, when the termination
conditions are set with an unrealistic tolerance. The problem with termina-
tion conditions for subgoals is best defined by an example. Suppose the next
waypoint is at location (35, 50). If the robot has shaft encoders or GPS, this
should be straightforward to do in theory. In practice, it is very hard for
a robot, even a holonomic robot, to reach any location exactly because it is
hard to give the robot precise movement. The robot may reach (34.5, 50). The
behavior sees the goal is now 0.5 meters ahead, and move again to attempt
to reach (35, 50). On that move, it may overshoot and end up at (35.5,50.5).