Page 371 - Introduction to AI Robotics

354
10
Metric Path Planning
HOLONOMIC the robot is holonomic, or can turn in place. Many research robots are suffi-
ciently close to holonomic to meet this assumption. However, robots made
from radio-controlled cars or golf carts are most certainly not holonomic.
Much work is being done in non-holonomic path planning, where the pose
of the robot must be considered (i.e., can it actually turn that sharply without
colliding?), but there no one algorithm appears to be used in practice. This
chapter will restrict itself to holonomic methods.

10.3 Cspace Representations

The number of different Cspace representations is too large to include more
than a coarse sampling here. The most representative ones are Voronoi di-
agrams, regular grids, quadtrees (and their 3D extension, octrees), vertex
graphs, and hybrid free space/vertex graphs. The representations offer dif-
ferent ways of partitioning free space. Any open space not occupied by an
object (a wall, a chair, an un-navigable hill) is free space, where the robot is
free to move without hitting anything modeled. Each partition can be la-
beled with additional information: “the terrain is rocky,” “this is off-limits
from 9am to 5am,” etc.

10.3.1 Meadow maps
Many early path planning algorithms developed for mobile robots assumed
that the robot would have a highly accurate map of the world in advance.
This map could be digitized in some manner, and then the robot could apply
various algorithms to convert the map to a suitable Cspace representation.
An example of a Cspace representation that might be used with an a priori
MEADOW MAP map is the meadow map or hybrid vertex-graph free-space model.
Meadow maps transform free space into convex polygons. Convex poly-
gons have an important property: if the robot starts on the perimeter and
goes in a straight line to any other point on the perimeter, it will not go out of
the polygon. The polygon represents a safe region for the robot to traverse.
The path planning problem becomes a matter of picking the best series of
polygons to transit through. Meadow maps are not that common in robotics,
but serve to illustrate the principles of effecting a configuration space and
then planning a path over it.
The programming steps are straightforward. First, the planner begins with
a metric layout of the world space. Most planners will increase the size of
every object by the size of the robot as shown in Fig. 10.2; this allows the