Admissibility, and Why A* Is Optimal

Two kilometres of over-optimism at one town out of nine costs the optimal answer. That is how tight the condition is, and it is why the word appears in MU's own label. Admissibility is not a nicety; it is the hypothesis of the theorem, and losing it loses the conclusion immediately.

Why the straight-line distance is admissible without checking every town

The program checked nine towns. The general argument is two lines and is what makes the heuristic safe on a map of nine thousand towns.

Every road between two towns is at least as long as the straight line between them, because a straight line is the shortest path between two points. So any journey by road from n to the goal is at least as long as the straight line from n to the goal. Therefore the straight-line distance is at most the cheapest road distance, which is the definition.

That is the argument the 1968 paper itself gives, in its own example of cities connected by roads, and it is also the general reason relaxation works: the straight line is the exact answer to the relaxed problem in which you may fly.

It depends on a property of the map, not of geometry. If a road could be shorter than the straight line, the argument fails. The standing map was built with every winding factor at least 1 precisely so that it holds, and that construction is declared in Formulating a Problem for Search rather than assumed here.

The proof that A* is optimal

Tree search, admissible h. Proof by contradiction, and it is short enough to reproduce in an examination.

Suppose A returns a suboptimal goal node t, with g(t) greater than C, the cost of an optimal solution.

1. Let n be a node on an optimal path that is still on the frontier at the moment t is selected. Such an n must exist: the start is on the optimal path, and the optimal path's nodes cannot all have been expanded, because then the optimal goal would have been generated and, being cheaper, would have been selected before t.
2. Because n is on an optimal path, g(n) is the true cheapest cost to n, and the remaining cost from n is h(n). So g(n) + h(n) = C*.
3. By admissibility, h(n) <= h(n). So f(n) = g(n) + h(n) <= g(n) + h(n) = C*.
4. For the goal t, h(t) = 0, so f(t) = g(t), which by assumption is greater than C*.
5. Hence f(n) <= C < f(t), so n had a strictly smaller f than t and A would have selected n rather than t. That contradicts the assumption.

Step 3 is the only place admissibility is used, and it is used exactly once. That is the answer to "where does admissibility come in": it is what lets f(n) be bounded above by C* for a node on the optimal path, and everything else is bookkeeping.

Step 4 uses h(goal) = 0. A heuristic that reported a positive value at the goal would break the proof at that step, which is why that requirement is part of the definition and not a convention.

Optimally efficient, which is a different and stronger claim

The 1968 paper proves something beyond optimality, and it is worth knowing because it explains why nothing has replaced A*.

Section III shows that A is not only admissible but optimal in the sense that no other admissible algorithm expands fewer nodes using the same information. The paper's own words: A is not only admissible but optimal, in the sense that no other admissible algorithm expands fewer nodes.

The claim has a condition, the paper's consistency assumption, and that condition is the whole of the next chapter. What it means in practice: given the same heuristic, any algorithm that guarantees an optimal answer must expand every node whose f is below C, because any one of them might hide a cheaper route, and A expands exactly those and no more. There is no cleverer ordering to be found.

What admissibility does not give you

Three things it is routinely assumed to guarantee and does not.

It does not make A fast. The 8-puzzle heuristic h0 = 0 is admissible and makes A into uniform cost search. Admissibility guarantees the answer, not the work.

It does not survive graph search on its own. With a reached set that never reconsiders a settled node, an admissible but inconsistent heuristic can make A* return a suboptimal route. That is the next chapter, and it is why MU prints both words.

It does not mean the estimate is good. Look at the slack column: the heuristic is short by 5 km at Amba and by 4 at three more towns. It is admissible everywhere and mediocre in several places.

Distinctions

What it does not mean

Admissible does not mean accurate. It means never too high. A heuristic can be admissible and useless, and h = 0 is the extreme case.

It is not a property of the algorithm in modern usage, although it was in 1968. Both usages exist and mean different things.

It does not require h to be a lower bound on the cost of the particular path found. It is a lower bound on the cost of the CHEAPEST remaining path, which is a smaller number and therefore a stronger requirement.

Overestimating a little is not a little wrong. Two kilometres at one town lost the optimal route on a nine-town map. The guarantee is all or nothing.

Admissibility alone is not enough for graph search. The commonest error on this topic, and the reason the next chapter exists.

Quick revision

• Admissible: h(n) <= h*(n) at every node. Never overestimates; optimistic; a lower bound.
• Two consequences: h(goal) = 0, and h = 0 everywhere is admissible, which makes uniform cost search a special case of A*.
• Straight-line distance is admissible because no road is shorter than the straight line, so no road journey is shorter than flying. That argument, and this book's map, are both in the 1968 paper's own example.
• Proved on the standing map by computing h* at all nine towns. Slack ranges from 0 at Fanas and Gokul to 5 at Amba.
• Breaking it by 2 km at one town changes the answer from 25 km to 26 km. The guarantee is all or nothing.
• The proof: if A returned a suboptimal t, some node n on the optimal path is still on the frontier, f(n) = g(n) + h(n) <= g(n) + h(n) = C* < g(t) = f(t), so n would have been chosen. Admissibility is used once, in the middle inequality.
• Optimally efficient: no admissible algorithm using the same heuristic expands fewer nodes, subject to the consistency assumption.
• Admissibility does not give speed, and does not suffice for graph search.

Test yourself

1. Define an admissible heuristic. A heuristic h is admissible if h(n) is at most h*(n), the true cost of the cheapest path from n to a goal, at every node n. It never overestimates the remaining cost.

2. Show that h(n) = 0 for all n is admissible, and say what A becomes. True remaining costs are never negative, so 0 is a lower bound everywhere and the heuristic is admissible. A then orders on g alone, which is uniform cost search.

3. Why is straight-line distance admissible on a road map? Because a straight line is the shortest path between two points, so every road is at least as long as the straight line between its ends, and therefore any road journey from a town to the goal is at least the straight-line distance. The estimate is thus never above the true cost.

4. Prove that A with an admissible heuristic returns an optimal solution in tree search. Suppose it returns t with g(t) greater than the optimal cost C. Some node n on an optimal path remains on the frontier, and for it g(n) + h(n) equals C. By admissibility h(n) is at most h(n), so f(n) is at most C. Since h(t) is 0, f(t) equals g(t), which exceeds C*. So f(n) is less than f(t) and n would have been selected instead, a contradiction.

5. Where exactly is admissibility used in that proof, and what would happen without it? Only in the step bounding f(n) by C. Without it h(n) could exceed h(n), f(n) could exceed C, and there would be nothing to stop A selecting the dearer goal first.

6. This chapter overestimated one town's heuristic by 2 km out of nine towns. What happened, and what does it show? A* returned 26 km by Chinch, Erandol and Gokul instead of the optimal 25 km by Bori, Devi and Fanas. It shows that the guarantee is all or nothing: a small violation at a single node is enough to lose the optimal answer.

7. Does admissibility guarantee that A* is optimal in graph search? Explain. No. With a reached set that never reconsiders a state already settled, an admissible but inconsistent heuristic can cause a suboptimal route to be returned, because a state can be closed by an expensive route before the cheap route to it is found. Graph search needs consistency, or else the ability to reopen closed nodes.