5. Informed (Heuristic) Search and A*

Source: AIMA 4th Ed., Chapter 3 (Sections 3.5.1–3.5.4, 3.5.6) Status: Complete

Overview

Informed search algorithms use a heuristic function h(n) that estimates the cost from node n to the nearest goal state. This additional domain knowledge allows the search to focus on promising directions and dramatically reduce the number of nodes expanded compared to uninformed methods.

h(n) = estimated cost of the cheapest path from state n to a goal state
h(goal) = 0 for all goal states

Greedy Best-First Search

Core idea: At each step, expand the node that appears closest to the goal according to h.

Evaluation function: f(n) = h(n)

function GREEDY-BEST-FIRST-SEARCH(problem, h) returns solution or failure
    return BEST-FIRST-SEARCH(problem, h)

Properties

Intuition: Greedy best-first is like driving always toward where the goal looks closest on the map, without accounting for the road you have already traveled. You might end up on an inefficient route.

When it works well: When h is very accurate, greedy search can be dramatically faster than uninformed methods in practice, though without optimality guarantees.

A* Search

Core idea: Combine what we know (g(n) = actual cost from start to n) with what we estimate (h(n) = estimated cost from n to goal) to guide the search.

Evaluation function: f(n) = g(n) + h(n)

f(n) is the estimated total cost of the cheapest solution passing through node n.

function A*-SEARCH(problem, h) returns solution or failure
    return BEST-FIRST-SEARCH(problem, lambda n: g(n) + h(n))

Worked Example (Romania)

Starting from Arad, goal is Bucharest. Heuristic h = straight-line distance to Bucharest.

At each step, we expand the node with the smallest f = g + h: - Arad: g=0, h=366, f=366 - After expanding Arad: Sibiu f=393, Timisoara f=447, Zerind f=449 - Expand Sibiu (f=393): Fagaras f=415, Rimnicu-Vilcea f=413, Oradea f=671, Arad (already in reached) - Expand Rimnicu-Vilcea (f=413): Pitesti f=415, Craiova f=526, Sibiu (higher cost path) - … - Bucharest found via Pitesti with total cost 418

A* correctly finds the optimal 418km path, while greedy search (following h alone) would pick a suboptimal route through Fagaras (total 450km).

Search Contours

A* explores nodes in approximately elliptical contours around the start state, where the long axis points toward the goal. The boundary of expanded nodes is roughly the set where g(n) + h(n) = C for increasing C.

Compare: - UCS (h=0): circular contours, expanding uniformly in all directions - Greedy (g=0): focused on goal but no cost bound - A*: elliptical contours, narrowing as h becomes more accurate

Admissibility: The Key Condition for Optimality

Definition: A heuristic h is admissible if it never overestimates the true cost to reach the goal from any node:

h(n) <= h*(n)   for all nodes n

where h*(n) is the true optimal cost from n to the nearest goal.

Theorem: A* with an admissible heuristic is cost-optimal.

Proof sketch (by contradiction)

Suppose A* returns a suboptimal solution via goal node G2 with cost f(G2) = g(G2) > C* (where C* is optimal cost). Let G be an optimal goal node and let n be some node on the optimal path to G that is still on the frontier.

Since h is admissible: f(n) = g(n) + h(n) <= g(n) + h*(n) = C* < g(G2)

So n has lower f than G2. But A* expanded G2 before n — contradiction. Therefore, A* cannot return a suboptimal solution. QED.

Consistency (Monotonicity): The Stronger Condition

Definition: A heuristic h is consistent (or monotone) if for every node n and every successor n’ generated by action a:

h(n) <= cost(n, a, n') + h(n')

This is a triangle inequality: the estimated cost from n to the goal cannot exceed the cost of going through n’.

Relationship: Consistency implies admissibility. Admissibility does not imply consistency (though inconsistent admissible heuristics are rare in practice).

Why consistency matters

With a consistent heuristic, the f-values along any path are non-decreasing:

f(n') = g(n') + h(n') = g(n) + cost(n,a,n') + h(n') >= g(n) + h(n) = f(n)

Consequence: **once a node is expanded by A*, we have found the optimal path to it**. The reached table can be used without re-expansion. This simplifies the algorithm and is the standard assumption for A*.

With an inconsistent admissible heuristic, A* may need to re-expand states when a cheaper path is found later (analogous to Bellman-Ford vs. Dijkstra’s).

Optimally Efficient Property

Theorem (Dechter and Pearl, 1985): A* with a consistent heuristic is optimally efficient among all optimal algorithms using the same heuristic function h, in the sense that no algorithm with the same h can avoid expanding the nodes that A* expands.

Formally: every algorithm that is guaranteed to find optimal solutions must expand every node n with f(n) < C*. A* expands exactly those nodes (with possible additions due to tie-breaking at the f = C* boundary).

Implication: to expand fewer nodes than A*, you must use better heuristic information — not a smarter algorithm.

Weighted A* and Satisficing Search

Core idea: Trade optimality for speed by weighting h more heavily.

Evaluation function: f(n) = g(n) + W * h(n) for W > 1

With W > 1, the search is more focused toward the goal (more greedy) and expands fewer nodes, but the solution found may cost more than optimal.

Guarantee: If h is admissible, weighted A* finds a solution with cost at most W × C* (W-admissible).

Satisficing Search Taxonomy

Speedy search: uses h_speedy = estimated number of actions to goal (ignores cost), and runs greedy best-first on this. Minimizes search time at the expense of solution quality.

Bidirectional Heuristic Search (Section 3.5.6)

Applying A* in both directions simultaneously. The key complications are:

1. Using f_F(n) = g_F(n) + h_F(n) for forward nodes and f_B(n) = g_B(n) + h_B(n) for backward nodes.
2. Naive bidirectional A* is not guaranteed to find the optimal solution when the frontiers meet — the joining path may not be optimal.

The lb lower bound: For any forward node m and backward node n, the cost of any solution passing through both is at least:

lb(m, n) = max(g_F(m) + g_B(n), f_F(m), f_B(n))

The f_2 evaluation function (for the BIBF approach):

f_2(n) = max(2*g(n), g(n) + h(n))

This ensures we never expand a node from either frontier with g(n) > C*/2. The algorithm “meets in the middle” in the sense that when the two frontiers touch, no expanded node has g > C*/2.

Result: Bidirectional search with f_2 and an admissible h is complete and optimal.

When to use bidirectional search: - With a mediocre heuristic: bidirectional significantly outperforms unidirectional A - With a very good heuristic: unidirectional A is already focused; bidirectional adds little - With a poor heuristic: both have similar complexity

A* Summary

f(n) = g(n) + h(n)
     = (actual cost from start to n) + (estimated cost from n to goal)
     = estimated total cost of optimal solution through n

The space problem: A* stores all generated nodes. For large problems, memory is exhausted before time. This motivates memory-bounded variants (IDA, RBFS, SMA) covered in the next section.