Page 382 - Introduction to AI Robotics

365
10.5 Wavefront Based Planners
This is particularly useful when A* is applied to a graph created from a reg-
ular grid, where the resulting graph is highly connected.
One very attractive feature of the A* path planner is that it can be used
with any Cspace representation that can be transformed into a graph. The
major impact that Cspace has on the A* planner is how many computations
it takes to find the path.
A limitation of A* is that it is very hard to use for path planning where
there are factors other than distance to consider in generating the path. For
example, the straight line distance may be over rocky terrain or sand that
poses a risk to the robot. Likewise, the robot may wish to avoid going over
hills in order to conserve energy, but at the same time might wish to go down
hills whenever possible for the same reason. In order to factor in the impact

of terrain on the path costs, the heuristic function h (n) has to be changed.
But recall that the new heuristic function must continue to satisfy the admis-

sibility condition: h h. If the new h just takes the worst case energy cost
or safety cost, it will be admissible, but not particularly useful in pruning
paths. Also, gaining energy going downhill is essentially having an edge in
the graph with a negative weight, which A* can’t handle. (Negative weights
pose an interesting problem in that the robot can get into a loop of rolling
down a hill repeatedly because it’s an energy-efficient solution rather than
actually making forward progress! Bellman-Ford types of algorithms deal
with this situation.)

10.5 Wavefront Based Planners

Wavefront propagation styles of planners are well suited for grid types of
representations. The basic principle is that a wavefront considers the Cspace
to be a conductive material with heat radiating out from the initial node to
the goal node. Eventually the heat will spread and reach the goal, if there
is a way, as shown in the sequence in Fig. 10.11. Another analogy for wave-
front planners is region coloring in graphics, where the color spreads out to
neighboring pixels. An interesting aspect of wavefront propagation is that
the optimal path from all grid elements to the goal can be computed as a
side effect. The result is a map which looks like a potential field. One of the
many wavefront types of path planners is the Trulla algorithm developed
by Ken Hughes. 106 It exploits the similarities with a potential field to let the
path itself represent what the robot should do as if the path were a sensor
observation.