A* Search (Russell Norvig)

As discussed in Russell Norvig Chapter 03: Solving Problems by Searching

Definition

A Search Algorithm following an Informed (Heuristic) Search Strategy.

The following definition is from RN, p. 103:

The most common informed search algorithm is A* Search (pronounced “A-star search”), a best-first search that uses the evaluation function

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

where g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of the shortest path from n to a goal state, so we have

f(n) = estimated cost of the best path that continues from n to a goal.

Properties

A* search is complete, assuming all action costs are \(> \epsilon > 0\) and the state space is finite or has a solution.

Whether it is cost-optimal depends on properties of the heuristic. One key property is admissibility:

An admissible heuristic is one that never overestimates the cost to reach a goal. (An admissible heuristic is therefore optimistic.)

If the heuristic is admissible then A* Search is cost-optimal. For a proof by contradiction see p. 106.

A stronger property than admissibility is consistency:

A heuristic h(n) is consistent if, for every node n and every successor n' of n generated by an action a, we have: \(h(n) \leq c(n,a,n’)+h(n’)\).

RN describe this as a form of triangle inequality, stipulating that a side of a triangle cannot be longer than the sum of the other two sides. Here h(n) is one side of the triangle, while the cost of moving from n to n' plus the estimate h(n') are the other two sides.

Every consistent heuristic is admissible, though not vice versa. For a discussion of whether or not to avoid inconsistent heuristics, and how to mitigate the issues they raise, see p. 106.

Further properties of A* search are discussed on pp 107-8 in the context of drawing contours in the search space to understand paths to the goal. In particular, if C* is the cost of the optimal path, RN state that:

• A* expands all nodes that can be reached from the initial state on a path where every node on the path has \(f(n) < C^*\). We say these are surely expanded nodes.

• A* might then expand some of the nodes right on the “goal contour” (where \(f(n) = C^*\)) before selecting a goal node.

• A* expands no nodes with \(f(n) > C^*\).

We can therefore say that A* with a consistent heuristic is optimally efficient in the sense that any algorithm that extends search paths from the initial state, and uses the same heuristic information, must expand all nodes that are surely expanded by A*.

A* is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. The concept of pruning, ie eliminating possibilities from consideration without having to examine them, is critical for many areas of AI.

So what’s the catch? For many problems the number of nodes expanded can be exponential in the length of the solution.

Weighted A* Search

There are ways around this issue of node expansion. For example, we might be willing to accept solutions that are not optimal, but good enough. These are called satisficing solutions. These can be found if we allow the heuristic to be inadmissible (ie to overestimate).

We can do this by applying a weight to the heuristic value, where \(W\) is some weight > 1. This gives us \(f(n) = g(n) + W * h(n)\).

A weighted A* search will likely find a solution faster, but slightly costlier than the optimum. We can think of it as a “somewhat-greedy search”, not ignoring path cost completely, but focusing the search towards a goal. Indeed we can think of weighted A* search as a generalization of other search algorithms that consider path cost (g) and the heuristic estimate (h):

Bidirectional heuristic Search

RN present some of the issues with applying the bidirectional approach to A* and other heuristic searches on p. 114-5. In summary:

In general, if we have a very good heuristic, then A* search produces search contours that are focused on the goal, and adding bidirectional search does not help much. With an average heuristic, bidirectional search that meets in the middle tends to expand fewer nodes and is preferred. In the worst case of a poor heuristic, the search is no longer focused on the goal, and bidirectional search has the same asymptotic complexity as A*. (p 115)