4.9 Admissible and consistent heuristics

What this is and why it exists

The optimality guarantee people quote for informed search is conditional, and this topic states the two conditions, proves the first one, and shows you how to test the second. Most people can state both conditions and prove neither. The proof is short and it is the kind of thing examinations ask for, and after it the topic becomes practice — small numerical problems on small graphs, which are quick once the definitions are firm.

The vocabulary

• Heuristic — the estimate of remaining cost from a state, written h of n.
• True remaining cost — the actual cheapest cost from that state to a goal, written h star of n.
• Admissible — the heuristic never exceeds the true remaining cost.
• Consistent — the estimate never drops by more than the cost of the step taken.
• Step cost — the cost of one action, from one state to its successor.
• Non-decreasing along a path — the combined score never falls as you move forward.
• Dominance — one admissible heuristic being at least as large as another everywhere.

The mental model

Admissibility is optimism that never overshoots. A heuristic is admissible when, for every state, its estimate is at most the true cheapest remaining cost. It may guess low, by any amount, and it may never guess high. Straight-line distance is admissible for a road map because no road can be shorter than the straight line. Counting how many tiles are out of place in a sliding puzzle is admissible because each misplaced tile needs at least one move.

Why does never overestimating buy optimality? Because the algorithm expands states in order of their combined score, and it stops when it selects a goal state for expansion. Suppose it is about to select a goal reached by a suboptimal path, while a cheaper solution exists. The cheaper solution has some state on its path sitting on the open list — every partial path is represented there by its frontier state. For that state, the score is the cost so far plus an estimate that, by admissibility, is at most the true remaining cost, so its score is at most the cost of the optimal solution. Meanwhile the suboptimal goal's score is its own path cost, which is greater than the optimal cost, because a goal's remaining estimate is zero. So the state on the better path scores lower and would have been selected first. The contradiction shows the algorithm cannot select a suboptimal goal before the optimal one. The reason optimality follows is that an optimistic estimate can never make a good path look worse than it is — it can only make it look better, so a good path is never overlooked.

Note carefully what that argument assumed: every state on the optimal path is available on the open list, and no state was refused. That holds for tree search, where nothing is discarded. It does not automatically hold when repeated states are pruned.

Consistency is the stronger condition that fixes exactly that gap. A heuristic is consistent when, for every state and every action leading to a successor, the estimate at the state is at most the cost of that step plus the estimate at the successor. It is a triangle inequality: going directly cannot be estimated as more expensive than going via one step and then estimating from there. It is a local condition — you check it one step at a time, which is what makes it testable.

Its consequence is the property you actually use: the combined score never decreases along a path. Take a state, move to a successor: the cost so far increases by the step cost, and the estimate falls by at most the step cost, so the sum cannot fall. Scores are non-decreasing as you go forward.

That is what makes graph search safe. If scores never decrease along any path, then when a state is selected for expansion, the path by which it was reached is already the cheapest path to it — no later, cheaper route to it can appear, because any such route would have had a lower score and been expanded earlier. So discarding repeated states throws away nothing, and pruning becomes sound.

Consistency implies admissibility, which is worth knowing so you do not check both: if the estimate never drops faster than the step cost, then chaining that inequality along any path to a goal shows the estimate at the start never exceeds the true cost. The reverse does not hold — admissible heuristics exist that are not consistent — although in practice nearly every naturally constructed admissible heuristic turns out to be consistent, and a deliberately inconsistent one is usually a constructed example rather than something you meet.

So the two results, paired with where each applies. Admissible gives optimality for tree search, where repeated states are not pruned. Consistent gives optimality for graph search, where they are. Knowing which guarantee you have depends on which condition your heuristic satisfies and which search you are running, and that pairing is the examinable content of this topic.

How to work the numerical problems, which are a whole class of exercises rather than a footnote.

To test admissibility, you need the true remaining cost from each state, which on a small graph you compute by finding the actual cheapest path from that state to the goal. Then compare, state by state. One state where the estimate exceeds the truth is enough to fail the whole heuristic.

To test consistency, you do not need true costs at all — walk every edge and check the local condition on each: the estimate at the source, minus the estimate at the destination, must be at most the cost of that edge. One violating edge fails it. This is the faster test and it is fully local, which is the practical reason to prefer it.

Two more facts worth carrying. Between two admissible heuristics, the larger one everywhere is better: it is closer to the truth, so it prunes more, and it expands no more states than the smaller. And taking the maximum of several admissible heuristics is itself admissible, which is a cheap way to build a stronger one out of weak ones. Relaxing the problem — removing a constraint and solving the easier version exactly — is the standard way to construct an admissible heuristic in the first place, since the relaxed cost can never exceed the real one.

What you should now be able to explain or do

State admissibility precisely and give two examples. Prove tree-search optimality under admissibility, and say which assumption the proof makes. State consistency as a local triangle inequality. Show that consistency makes the combined score non-decreasing along a path, and explain why that makes pruning repeated states sound. Say which condition implies the other. Pair each condition with the search it makes optimal. Test a heuristic on a small graph for both conditions, using the faster local test for consistency. Build a stronger admissible heuristic from weaker ones, and construct one by relaxation.

Check yourself