A* Search
A* (pronounced "A star") is a well known and well studied best-first
search algorithm. A* typically searches outward from the starting node
until it reaches the goal node, always expanding the current fringe
node that looks like it is along the best path from the start node
to the goal node. The best node is the current fringe node with
the minimum cost from the start node to the fringe node, plus the expected
remaining cost (the heuristic cost) to get from the fringe node to the
goal node.
The heuristic used to estimate the remaining cost from any node to the
goal plays a key role in A*. If the heuristic is always an underestimate
of the cost from any node to the goal, then it is said to be admissible,
and A* will find the optimal solution. However, if the heuristic is
too optimistic then A* will expand too many nodes and may run out of time
before a solution is found. If the heuristic is pessimistic then a
solution will be found quickly, but it will almost certainly be suboptimal.
CIRL
Work at CIRL has focused on using A* with flight planning problems where
the cost of evaluating edges is prohibitively expensive. Most A* work has
assumed
that the cost of evaluating an edge in the search graph is negligible,
and that the primary goal is to expand as few nodes as possible.
In our flight planning work the overriding goal has been to
minimize the number of expensive edge evaluations done. This goal is related,
but not identical, to that of minimizing the number of nodes expanded.
Several approaches to this problem have been explored.
- Approximations. Use approximate, cheap to calculate values instead of
exact and expensive to calculate values to find the best route. Use the
exact values only when returning the route to the caller. This approach
does not decrease the number of edges evaluated, but it does reduce the
cost of each evaluation to a manageable amount.
- Multi-pass A*. Perform several passes over the search space, possibly
in opposite directions. Approximate values are used in the first pass
and the results of that pass are then used to guide the second much
tighter pass. This reduces the number of expensive edge evaluations
to only those that are done on the final pass.
- Staggered node expansion. Traditional A* is driven by nodes. A list
of all the current fringe nodes is kept and
when a node is expanded the cost of every edge leading out from that node is
calculated at that time.
This approach modifies A* to be based on node-edge pairs, rather than purely
on nodes. When a node is first reached it is added to list of fringe nodes
along with an indication of which of its outgoing edges appears the most
promising. When that node-edge pair becomes the most promising pair in
the fringe it is removed from the list and that edge is evaluated.
If the node has any remaining unevaluated edges then the node is re-added
to the list of fringe nodes with the most promising remaining unevaluated
edge. Edges are also only evaluated if they clearly still show promise of
producing a better path to the node they go to. This approach
avoids expanding many edges that are eventually discarded by traditional A*
only after they have been calculated.
Pointers
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths,
by P.E. Hart, N.J. Nilsson, and B. Raphael, in IEEE Transactions on
SSC.
-
This is the paper that introduced A*.
- Parent areas:
- Systematic Search
- Application program:
- Worldwide Aeronautical Route Planner (WARP)
Back to the CIRL Overview Page.