Page 387 - Introduction to AI Robotics

370
start 10 Metric Path Planning
unmodeled
obstacle

goal
b.

a.
Figure 10.13 Layout showing unmodeled obstacle. a.) Gray line shows expected
path, long dashed line the actual path with Trulla, and short dashed line shows purely
reactive path. b.) Clementine opportunistically turning.

Computing the optimal path from every location to the goal actually helps
with reactive execution of the path. It means that if the robot can localize
itself on the a priori map, it can read the optimal subgoal for move-to-goal
on each update. If the robot has to swing wide to avoid an unmodeled obsta-
cle in Fig. 10.13, the robot automatically becomes redirected to the optimal
path without having to replan. Note how the metric path becomes a virtual
sensor, guiding the move-to-goal behavior replacing the direct sensor data.
This is a rich mechanism for the deliberative and reactive components of
Hybrid architectures to interact.
This approach eliminates subgoal obsession, since the robot can change
“optimal” paths reactively and opportunistically move to a closer waypoint.
As with most things in life, too much of a good thing is bad. At some
point though, the sheer number of unmodeled obstacles might force the ro-
bot to get trapped or wander about, changing subgoals but making no real
progress. The D* solution to this problem is to continuously update the map
and dynamically repair the A* paths affected by the changes in the map. D*
CONTINUOUS represents one extreme on the replanning scale: continuous replanning.
REPLANNING Continuous replanning has two disadvantages. First, it may be too compu-
tationally expensive to be practical for a robot with an embedded processor