CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Nov 2, 1998)

"A* Search"


 

Quick Review of Related Algorithms

Blind searches:  Depth-First Search, Breadth-first search, Uniform-cost search

Informed searches: Best first search.

Searches without weighted costs:  DFS, Breadth-F S, Best-F S.

Searches with weighted costs:  Uniform-cost search.
 


 

Combining Criteria:  Path distances + Heuristically Evaluated Cost

Let n be the node for which we want the overall cost:
Let s be the start node.
Let q be the goal node closest to n.

Define f(n) = total cost of the shortest path from the start node s to a goal node q such that the path goes through n.

Let g(n) = cost from start node to n.
Let h(n) = cost from n to nearest goal node.

Then f(n) = g(n) + h(n)

Here's a picture.

  s ---  g(n) ------- n ------- h(n) -------  q

  +---------------- f(n) ----------------+

As the search proceeds, working out from s, and reaching each node n of many in turn, neither g(n) nor h(n) are known.

What CAN be determined are:
^
g(n) = the actual distance along the best path found so far from s to n.

^
h(n) = the result of applying the heuristic evaluation function to n; this is an estimate of h(n).

Adding these together we get
^          ^          ^
f(n) = g(n) + h(n)

(Note: the estimate of f(n) is read as "f hat of n".)


 

A* Algorithm Brief Formulation

The A* algorithm is a best-first search in a state space with weighted costs, using an evaluation function of the form
^          ^          ^
f(n) = g(n) + h(n)
as described above.

It is used to find a shortest path from the start node to a goal node.


 

A* Algorithm Expanded Formulation

As each new state is identified, it is pushed onto an OPEN list.
The next state to explore is obtained by popping it off the OPEN list.

1. Initialize: Set the list OPEN to contain only the start node s. Set CLOSED to empty. Set G[s] to 0. Set PRED[s] to NULL; set found to false;
2. If OPEN is empty and not found, then print failure and halt.
3. Else let L be the set of nodes on OPEN for which F is the least.
    If L has only one element, let X be that element.
    Else if L contains any goal nodes, let X be one of them.
    Otherwise let X be any member of L.
4. Remove X from OPEN and put X on CLOSED.
5. If X is a goal node, print the path from s to X (by calling extract=path) and halt.
6. Let SUCCESSORS be the successors of X.
7. For each Y in SUCCESSORS, do:
       If Y is not already on OPEN or on CLOSED then
          set G[Y] to G[X] + distance(X,Y);
          set F[Y] to G[Y] + h(Y);
          set PRED[Y] to X;
          put Y on OPEN;
       else
          set Z to PRED[Y];
          set temp to F[Y] - G[Z] - distance(Z,Y)
                                  + G[X] + distance(X,Y);
          if temp < F[Y] then
             set G[Y] to G[Y] - F[Y] + temp;
             set F[Y] to temp;
             set PRED[Y] to X;
             if Y is on CLOSED then
               insert Y on OPEN and take Y off of CLOSED;
 
 
 


 

Admissibility:  A* Finds Optimal Paths When It Can

An optimal path is a lowest-cost path from the start node to a goal node.
A search algorithm is admissible provided it always finds such a path when one exists.

Note:  If there are no goal nodes in a particular state space, that does not prove the inadmissibility of any search algorithm.

Note:  The Uniform-Cost algorithm is admissible.  It finds a shortest path to each it reaches, and it gets there the first time by a shortest path.

Therefore A* is admissible provided h^ (n) is low enough.  (if h^ (n) = 0 for all n, then A* reduces to uniform-cost search).

As the value of h^ (n) increases, A* remains admissible provided h^ (n) never exceeds h(n).
 


 

Optimality: A* Avoids Unnecessary Work

In principle, the larger h^ (n) is, the more informed the search is.

However, if h^ (n) were to get "unbalanced", that could throw off the search and cause it to examine nodes that it should not.

Suppose we have two A* search algorithms, A1 and A2 such that A1 is more informed than A2.  If they satisfy the "consistency assumption", then A1 does not open any node not opened by A2.

An A* algorithm satisfies the consistency assumption provided for any two nodes n1 and n2 the difference in their h^ values never exceeds the distance between them.

It is in this sense that we sometimes speak of "optimality of A* search."
(Do not confuse this with admissibility -- the limited guarantee of finding an optimal path).
 
 

 

Last modified: November 2, 1998

Steve Tanimoto

tanimoto@cs.washington.edu