Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

3.6.1 A* Search

A* search is a combination of lowest-cost-first and best-first searches that considers both path cost and heuristic information in its selection of which path to expand. For each path on the frontier, A* uses an estimate of the total path cost from a start node to a goal node constrained to start along that path. It uses cost(p), the cost of the path found, as well as the heuristic function h(p), the estimated path cost from the end of p to the goal.

For any path p on the frontier, define f(p)=cost(p)+h(p). This is an estimate of the total path cost to follow path p then go to a goal node.

If n is the node at the end of path p, this can be depicted as follows: 

        actual        estimate
 start ---------> n -----------> goal
        cost(p)        h(p)
      ------------------------->
                f(p)

If h(n) is an underestimate of the path costs from node n to a goal node, then f(p) is an underestimate of a path cost of going from a start node to a goal node via p.

A* is implemented by treating the frontier as a priority queue ordered by f(p).

Example 3.15: Consider using A* search in Example 3.4 using the heuristic function of Figure 3.12. In this example, the paths on the frontier are shown using the final node of the path, subscripted with the f-value of the path. The frontier is initially [o10321], because h(o103)=21 and the cost of the path is zero. It is replaced by its neighbors, forming the frontier
[b321, ts31,o10936].

The first element represents the path ⟨o103,b3⟩; its f-value is f(⟨o103,b3⟩)=cost(⟨o103,b3⟩)+h(b3)=4+17=21. Next b3 is selected and replaced by its neighbors, forming the frontier

[b121, b429, ts31, o10936].

Then the path to b1 is selected and replaced by its neighbors, forming the frontier

[c221, b429, b229, ts31, o10936].

Then the path to c2 is selected and replaced by its neighbors, forming

[c121, b429, b229, c329, ts31, o10936].

Up to this stage, the search has been continually exploring what seems to be the direct path to the goal. Next the path to c1 is selected and is replaced by its neighbors, forming the frontier

[b429, b229, c329, ts31, c335, o10936].

At this stage, there are two different paths to the node c3 on the queue. The path to c3 that does not go through c1 has a lower f-value than the one that does. Later, we consider the situation when one of these paths can be pruned.

There are two paths with the same f-value. The algorithm does not specify which is selected. Suppose the path to b4 is selected next and is replaced by its neighbors, forming

[b229, c329, ts31, c335, o10936, o10942].

Then the path to b2 is selected and replaced by its neighbors, which is the empty set, forming

[c329, ts31, c335, b435, o10936, o10942].

Then the path to c3 is removed and has no neighbors; thus, the new frontier is

[ts31, c335, b435, o10936, o10942].

Note how A* pursues many different paths from the start.

A lowest-cost path is eventually found. The algorithm is forced to try many different paths, because several of them temporarily seemed to have the lowest cost. It still does better than either lowest-cost-first search or best-first search.

Example 3.16: Consider Figure 3.8, which was a problematic graph for the other heuristic methods. Although it initially searches down from s because of the heuristic function, eventually the cost of the path becomes so large that it picks the node on an actual optimal path.

The property that A* always finds an optimal path, if one exists, and that the first path found to a goal is optimal is called the admissibility of A*. Admissibility means that, even when the search space is infinite, if solutions exist, a solution will be found and the first path found will be an optimal solution - a lowest-cost path from a start node to a goal node.

Proposition. (A* admissibility): If there is a solution, A* always finds a solution, and the first solution found is an optimal solution, if
  • the branching factor is finite (each node has only a finite number of neighbors),
  • arc costs are greater than some ε>0, and
  • h(n) is a lower bound on the actual minimum cost of the lowest-cost path from n to a goal node.
Proof. Part A: A solution will be found. If the arc costs are all greater than some ε> 0, eventually, for all paths p in the frontier, cost(p) will exceed any finite number and, thus, will exceed a solution cost if one exists (at depth in the search tree no greater than m/ε, where m is the solution cost). Because the branching factor is finite, only a finite number of nodes must be expanded before the search tree could get to this size, but the A* search would have found a solution by then.

Part B: The first path to a goal selected is an optimal path. The f-value for any node on an optimal solution path is less than or equal to the f-value of an optimal solution. This is because h is an underestimate of the actual cost from a node to a goal. Thus, the f-value of a node on an optimal solution path is less than the f-value for any non-optimal solution. Thus, a non-optimal solution can never be chosen while a node exists on the frontier that leads to an optimal solution (because an element with minimum f-value is chosen at each step). So, before it can select a non-optimal solution, it will have to pick all of the nodes on an optimal path, including each of the optimal solutions.

It should be noted that the admissibility of A* does not ensure that every intermediate node selected from the frontier is on an optimal path from the start node to a goal node. Admissibility relieves the algorithm from worrying about cycles and ensures that the first solution found will be optimal. It does not ensure that the algorithm will not change its mind about which partial path is the best while it is searching.

To see how the heuristic function improves the efficiency of A*, suppose c is the cost of a shortest path from a start node to a goal node. A*, with an admissible heuristic, expands every path from a start node in the set

{p: cost(p)+h(p)<c}

and some of the paths in the set

{p: cost(p)+h(p)=c}.

Improving h affects the efficiency of A* if it reduces the size of the first of these sets.