Page 369 - Introduction to AI Robotics

352
10
Metric Path Planning
landmarks in the world. Topological navigation focused on subgoals which
are gateways or locations where the robot could change its primary heading.
The terms “optimal” and “best” have serious ramifications for robotics.
In order to say a path is optimal, there is an implied comparison. As will
be seen, some metric methods are able to produce an optimal path because
they consider all possible paths between points. This can be computationally
expensive. Fortunately, some algorithms (especially one named “A*” for rea-
sons that will be discussed later) are more clever about rejecting non-optimal
paths sooner than others.
Surprisingly, an optimal path may not appear optimal to the human eye;
for example, a mathematically optimal path of a world divided into tiles or
grids may be very jagged and irregular rather than straight. The ability to
produce and compare all possible paths also assumes that the planning has
access to a pre-exisiting (or a priori) map of the world. Equally as important,
it assumes that the map is accurate and up to date. As such, metric methods
are compatible with deliberation, while qualitative methods work well with
more reactive systems. As a deliberative function, metric methods tend to
be plagued by the same sorts of difficulties that were seen in Hierarchical
systems: challenges in world representation, handling dynamic changes and
surprises, and computation complexity.
COMPONENTS OF Metric path planners have two components: the representation (data struc-
METRIC PATH ture) and the algorithm. Path planners first partition the world into a structure
PLANNERS
amenable for path planning. They use a variety of techniques to represent
the world; no one technique is dominant, although regular grids appear to
be popular. The intent of any representation is to represent only the salient
features, or the relevant configuration of navigationally relevant objects in
the space of interest; hence the term configuration space. Path planning al-
gorithms generally work on almost any configuration space representation,
although as with any algorithm, some methods work better on certain data
structures. The algorithms fall into two broad categories: those which treat
path planning as a graph search problem, and those which treat path plan-
ning as a graphics coloring problem. Regardless of what algorithm is used,
there is always the issue in a Hybrid architecture of when to use it. This is
sometimes called the issue of interleaving reaction and planning.