|
 Features
Looking
Before You Leap
Although
the obstacle-skirting techniques discussed above can often do a passable
or even adequate job, there are situations where the only intelligent
approach is to plan the entire route before the first step is taken. In
addition, these methods do little to handle the problem of weighted regions,
where the difficulty is not so much avoiding obstacles as finding the
cheapest path among several choices where the terrain can vary in its
cost.
Fortunately, the fields of Graph Theory and conventional AI have several
algorithms that can be used to handle both difficult obstacles and weighted
regions. In the literature, many of these algorithms are presented in
terms of changing between states, or traversing the nodes of a graph.
They are often used in solving a variety of problems, including puzzles
like the 15-puzzle or Rubik's cube, where a state is an arrangement of
the tiles or cubes, and neighboring states (or adjacent nodes) are visited
by sliding one tile or rotating one cube face. Applying these algorithms
to path-finding in geometric space requires a simple adaptation: a state
or a graph node stands for the entity being in a particular tile, and
moving to adjacent tiles corresponds to moving to the neighboring states,
or adjacent nodes.
Working from the simplest algorithms to the more robust, we have:
- Breadth-first
search. Beginning
at the start node, this algorithm first examines all immediate neighboring
nodes, then all nodes two steps away, then three, and so on, until a
goal node is found. Typically, each node's unexamined neighboring nodes
are pushed onto an Open list, which is usually a FIFO (first-in-first-out)
queue. The algorithm would go something like what is shown in Listing
1. Figure
4 shows how the search proceeds. We can see that it does find
its way around obstacles, and in fact it is guaranteed to find a shortest
path-that is, one of several paths that tie for the shortest in length-if
all steps have the same cost. There are a couple of obvious problems.
One is that it fans out in all directions equally, instead of directing
its search towards the goal; the other is that all steps are not
equal-at least the diagonal steps should be longer than the orthogonal
ones.
- Bidirectional
breadth-first search. This
enhances the simple breadth-first search by starting two simultaneous
breadth-first searches from the start and the goal nodes and stopping
when a node from one end's search finds a neighboring node marked from
the other end's search. As seen in Figure
5, this can save substantial work from simple breadth-first
search (typically by a factor of 2), but it is still quite inefficient.
Tricks like this are good to remember, though, since they may come in
handy elsewhere.
- Dijkstra's
algorithm. E.
Dijkstra developed a classic algorithm for traversing graphs with edges
of differing weights. At each step, it looks at the unprocessed node
closest to the start node, looks at that node's neighbors, and sets
or updates their respective distances from the start. This has two advantages
to the breadth-first search: it takes a path's length or cost into account
and updates the goodness of nodes if better paths to them are found.
To implement this, the Open list is changed from a FIFO queue to a priority
queue, where the node popped is the one with the best score-here, the
one with the lowest cost path from the start. (See
Listing 2.) We see in Figure
6 that Dijkstra's algorithm adapts well to terrain cost. However,
it still has the weakness of breadth-width search in ignoring the direction
to the goal.
- Depth-first
search. This
search is the complement to breadth-first search; instead of visiting
all a node's siblings before any children, it visits all of a node's
descendants before any of its siblings. To make sure the search terminates,
we must add a cutoff at some depth. We can use the same code for this
search as for breadth-first search, if we add a depth parameter to keep
track of each node's depth and change Open from a FIFO queue to a LIFO
(last-in-first-out) stack. In fact, we can eliminate the Open list entirely
and instead make the search a recursive routine, which would save the
memory used for Open. We need to make sure each tile is marked as "visited"
on the way out, and is unmarked on the way back, to avoid generating
paths that visit the same tile twice. In fact, Figure
7 shows that we need to do more than that: the algorithm still
can tangle around itself and waste time in a maddening way. For geometric
path-finding, we can add two enhancements. One would be to label each
tile with the length of the cheapest path found to it yet; the algorithm
would then never visit it again unless it had a cheaper path, or one
just as cheap but searching to a greater depth. The second would be
to have the search always look first at the children in the direction
of the goal. With these two enhancements checked, one sees that the
depth-first search finds a path quickly. Even weighted paths can be
handled by making the depth cut-off equal the total accumulated cost
rather than the total distance.
- Iterative-deepening
depth-first search. Actually,
there is still one fly in the depth-first ointment-picking the right
depth cutoff. If it is too low, it will not reach the goal; if too high,
it will potentially waste time exploring blind avenues too far, or find
a weighted path which is too costly. These problems are solved by doing
iterative deepening, a technique that carries out a depth-first search
with increasing depth: first one, then two, and so on until the goal
is found. In the path-finding domain, we can enhance this by starting
with a depth equal to the straight-line distance from the start to the
goal. This search is asymptotically optimal among brute force searches
in both space and time.
- Best-first
search.
This is
the first heuristic search considered, meaning that it takes into account
domain knowledge to guide its efforts. It is similar to Dijkstra's algorithm,
except that instead of the nodes in Open being scored by their distance
from the start, they are scored by an estimate of the distance remaining
to the goal. This cost also does not require possible updating as Dijkstra's
does. Figure
8 shows its performance. It is easily the fastest of the forward-planning
searches we have examined so far, heading in the most direct manner
to the goal. We also see its weaknesses. In 8A, we see that it does
not take into account the accumulated cost of the terrain, plowing straight
through a costly area rather than going around it. And in 8B, we see
that the path it finds around the obstacle is not direct, but weaves
around it in a manner reminiscent of the hand-tracing techniques seen
above.
 
The
Star of the Search Algorithms (A* Search)
|
|
|
|
|
