Page 386 - Introduction to AI Robotics

10.6 Interleaving Path Planning and Reactive Execution
y for non-holonomic robots, because
< 50.5. There is no common heuristic < 369
the maneuverability of each platform is different. A more vexing aspect of
subgoal obsession is when the goal is blocked and the robot can’t reach the
terminating condition. For example, consider a subgoal at the opposite end
of a hall from a robot, but the hall is blocked and there is no way around.
Because the robot is executing reactively, it doesn’t necessarily realize that it
isn’t making progress. One solution is for the Sequencer to estimate a maxi-
mum allowable time for the robot to reach the goal. This can be implemented
either as a parameter on the behavior (terminate with an error code after n
seconds), or as an internal state releaser. The advantage of the latter solu-
tion is that the code can become part of a monitor, leading to some form of
self-awareness.
Related to subgoal obsession is the fact that reactive execution of plans
often lacks opportunistic improvements. Suppose that the robot is heading
for Subgoal 2, when an unmodeled obstacle diverts the robot from its in-
tended path. Now suppose that from its new position, the robot can perceive
Subgoal 3. In a classic implementation, the robot would not be looking for
Subgoal 3, so it would continue to move to Subgoal 2 even though it would
be more optimal to head straight for Subgoal 3.
The need to opportunistically replan also arises when an a priori map turns
out to be incorrect. What happens when the robot discovers it is being sent
through a patch of muddy ground? Trying to reactively navigate around
the mud patch seems unintelligent because choosing left or right may have
serious consequences. Instead the robot should return control to the Car-
tographer, which will update its map and replan. The issue becomes how
does a robot know it has deviated too far from its intended path and needs
to replan?
Two different types of planners address the problems of subgoal obses-
D* ALGORITHM sion and replanning: the D* algorithm developed by Tony Stentz 136 which is
a variant of the A* replanning algorithm, and an extension to the Trulla al-
gorithm. Both planners begin with an a priori map and compute the optimal
path from every location to the goal. D* does it by executing an A* search
from each possible location to the goal in advance; this converts A* from be-
ing a single-source shortest path algorithm into an all-paths algorithm. This
is computationally expensive and time-consuming, but that isn’t a problem
since the paths are computed when the robot starts the mission and is sitting
still. Since Trulla is a wavefront type of planner, it generates the optimal path
between all pairs of points in Cspace as a side effect of computing the path
from the starting location to the goal.