Page 373 - Introduction to AI Robotics

356
10
Metric Path Planning

Figure 10.4 String tightening as a relaxation of an initial path.

forming the perimeter aren’t connected to another a polygon (i.e., they are
part of a wall), so they should be off limits to the planning algorithm. Also,
as can be seen by the above figure, some of the line segments are quite long.
It would make a difference to the overall path length where the robot cuts
across the polygon. It is hard for the planner to discretize a continuous line
segment. So the issue becomes how to specify candidate points on the poly-
gon. One solution is to find the middle of each line segment which borders
another polygon. Note that each of these midpoints becomes a node, and
if edges are drawn between them, an undirected graph emerges. A path
planning algorithm would determine the best path to take.
One disadvantage of a meadow map, indeed of any Cspace representa-
tion, is evident on inspection of Fig. 10.3: any path which is chosen will be
somewhat jagged. Each of the inflection points is essentially a waypoint.
One outcome of the partitioning process is that the free space is divided up
in a way that makes sense geometrically, but not necessarily for a robot to
actually travel. Why go halfway down the hall, then angle off? This may be
mathematically optimal on paper, but in practice, it seems downright silly.
Chuck Thorpe at CMU devised a solution to paths generated from any kind
of discretization of free space. 138 Imagine that the path is a string. Now imag-
ine pulling on both ends to tighten the string (the technical name for this is
PATH RELAXATION path relaxation) This would remove most of the kinks from the path without
violating the safe zone property of convex polygons.
Meadow maps have three problems which limit their usefulness. One
problem is that the technique to generate the polygons is computationally