Page 368 - Introduction to AI Robotics

10 Metric Path Planning

Chapter objectives:
Define Cspace, path relaxation, digitization bias, subgoal obsession, termination
condition.

Explain the difference between graph and wavefront planners.
Represent an indoor environment with a generalized Voronoi graph,a regu-
lar grid,ora quadtree, and create a graph suitable for path planning.

Apply the A* search algorithm to a graph to find the optimal path between
two locations.

Apply wavefront propagation to a regular grid.

Explain the differences between continuous and event-driven replanning.

10.1 Objectives and Overview

QUANTITATIVE Metric path planning,or quantitative navigation, is the opposite of topologi-
NAVIGATION cal navigation. As with topological methods, the objective is to determine
a path to a specified goal. The major philosophical difference is that metric
methods generally favor techniques which produce an optimal, according to
some measure of best, while qualitative methods seem content to produce
a route with identifiable landmarks or gateways. Another difference is that
WAYPOINTS metric paths are usually decompose the path into subgoals consisting of way-
points. These waypoints are most often a fixed location or coordinate (x,y).
These locations may have a mathematical meaning, but as will be seen with
meadow maps, they may not have a sensible correspondence to objects or