Page 389 - Introduction to AI Robotics

372

goal 10 Metric Path Planning
start
missing
wall

Figure 10.14 Opportunity to improve path. The gray line is the actual path, while
the dashed line represents a more desirable path.

well with wavefront planners, which treat path planning as an expanding
heat wave from the initial location.
Metric path planning tends to be expensive, both in computation and in
storage. However, they can be interleaved with the reactive component of
a Hybrid architecture, where the Cartographer gives the Sequencer a set of
waypoints. Two problems in interleaving metric path planning with reactive
execution are subgoal obsession and when to replan. Optimal path planning
techniques for a priori fixed maps are well understood, but it is less clear how
to update or repair the path(s) without starting over if the robot encounters
a significant deviation from the a priori map. One solution is to continuously
replan if resources permit and sensor reliability is high; another is event-
driven replanning which uses affordances to detect when to replan.
Cspace representations and algorithms often do not consider how to rep-
resent and reason about terrain types, and special cases such as the robot ac-
tually conserving or generating energy going downhill are usually ignored.
A possibly even more serious omission is that popular path planners are
applicable for only holonomic vehicles.

10.8 Exercises

Exercise 10.1
Represent your indoor environment as a GVG, regular grid, and quadtree.