Artificial Intelligence · AI Foundations

Designing and Judging Heuristics

In AI because heuristics are engineered artefacts — derived from relaxations, ranked by dominance, and audited like any other code an optimal planner depends on.

The recipe behind every good heuristic is the same: relax the problem, solve the relaxation exactly, and the admissibility guarantee arrives with the derivation. This lesson runs that recipe, ranks its outputs — domination, and the max trick for combining them — and then turns diagnostic: how an inflated estimate silently buries the best path, and how to audit a heuristic you inherited before trusting it.

Artificial Intelligence
Medium level
5 concepts

1The relaxation recipe

Good heuristics are derived, not guessed. The recipe: delete a constraint from the problem — relax it — solve the relaxed problem exactly, and use that exact cost as h. Admissibility then comes free, because every legal solution of the real problem is still legal in the relaxed one, so the relaxed optimum can never exceed the true optimum.

Every classic heuristic is this recipe applied. Straight-line distance solves route-finding with the road network deleted. Manhattan distance solves grid navigation with the walls deleted. In the 8-puzzle, letting tiles teleport straight to their destinations yields the misplaced-tile count, while letting them slide through each other yields the sum of their Manhattan distances. For the travelling salesman, deleting the requirement that the route be one closed tour leaves the cheapest way to connect all cities — a minimum spanning tree, whose weight lower-bounds every tour.

Relaxation also gives a dial. Delete less and the relaxed problem is harder to solve at each node but its cost hugs the truth tighter; delete more and the estimate is cheap and loose. The engineering trade is evaluation time per generated node against expansions saved — a heuristic can be too expensive to be worth its own accuracy.

The recipe

RelaxDelete a constraint until the problem becomes exactly solvable at per-node speed.
Solve exactlyThe relaxed optimum must be computed, not itself estimated — the guarantee rides on exactness.
BoundReal solutions remain legal in the relaxation, so its optimum never exceeds the true one: h is admissible by construction.

Relaxations behind the classics
Problem	Constraint deleted	Resulting h
Route finding on roads	Must follow roads	Straight-line distance
Grid navigation	Walls block movement	Manhattan distance
8-puzzle	Tiles slide one step into the blank	Misplaced tiles (teleport) or Manhattan sum (slide through)
Travelling salesman	Route is one closed tour	Minimum spanning tree weight

Manhattan distance on a grid ignores every wall. Why is that a feature rather than a defect?

Walls are rare enough on a typical grid that ignoring them changes little
Deleting the walls makes an easier problem, and the exact cost of an easier problem can never exceed the real one
The true distance costs too much to compute at every node, so any estimate will serve
Ignoring walls makes the heuristic consistent, which matters more than admissibility

That is the whole recipe: relax a constraint, solve the easier problem exactly, and admissibility comes free because removing constraints can only make the goal cheaper to reach.

2Manhattan distance, run properly

On a grid with unit moves in four directions, Manhattan distance is h = |x_1 - x_2| + |y_1 - y_2| — not an approximation somebody liked, but the exact optimum of the walls-deleted relaxation: with nothing in the way, the best any path can do is cover the horizontal and vertical offsets one unit at a time.

Walls only ever lengthen real paths, so the estimate can only err low — the admissibility the recipe promised. It is consistent too, and the argument is one line: a single move changes one coordinate by exactly one, so h changes by at most 1 while the edge costs exactly 1, which is the consistency inequality with nothing to spare.

That consistency is why grid A* — game maps, warehouse robots, sliding puzzles — runs as graph search with no reopening and no ceremony. The worked square below carries the whole story: a 5-step estimate, a 7-step truth, and the gap between them is exactly the walls the relaxation deleted.

Figure. The dashed straight-through estimate counts 3 across and 2 up — h = 5 — and drives through the walls it is allowed to ignore. The real route pays 7, detouring around the right; the two extra moves are exactly what the relaxation deleted. Cells are schematic and share one scale.

The estimate and the walls

Start at column 0, row 2 of a grid; the target sits at column 3, row 0. Three wall cells force a detour around the right-hand side.

Horizontal offset |3 − 0|3
Vertical offset |0 − 2|2
h = 3 + 25
True shortest path, walls respected7 moves — h errs low, as admissibility demands

Pro tip. The gap 7 − 5 = 2 is not an error to be fixed; it is the two extra moves the walls cost, which the relaxation deliberately cannot see. A tighter h needs a tighter relaxation, not a fudge factor.

3Domination: ranking admissible heuristics

Between two admissible heuristics, bigger is better. h_2 dominates h_1 when h_2(n) \ge h_1(n) at every node, with both staying admissible — and dominance is the order that matters, because of a theorem: every node A* is certain to expand under h_2 (those whose f stays below the optimal cost) it would also expand under h_1. The stronger estimate can only prune, never add, up to tie-breaking at the optimum itself.

On the grid the ordering is concrete. For offsets a and b, |a| + |b| \ge \sqrt{a^2 + b^2}, so Manhattan distance dominates straight-line distance wherever diagonal moves do not exist. The weaker estimate leaves f smaller across the whole map, and smaller f keeps nodes alive on the frontier that the stronger estimate would have buried.

Dominance also settles how to combine candidates: take the pointwise maximum. \max(h_1, h_2) is admissible whenever both ingredients are — it still sits under h^* — and it dominates each of them by construction. An average is also admissible but weaker than the max — it throws strength away. Portfolios of relaxations combined by max are how serious planners actually ship heuristics.

Figure. Two admissible estimates of the same remaining cost, with the truth as the dashed ceiling: straight-line reports about 3.61, Manhattan 5, both safely under 7. The taller admissible bar is the better heuristic — closer to the ceiling means tighter f-values and fewer expansions.

Two admissible estimates, ranked

Same grid as the Manhattan concept: offsets 3 across and 2 up, with walls making the true remaining cost 7.

Straight-line: √(3² + 2²) = √13≈ 3.61
Manhattan: 3 + 25
Both against the truth: 3.61 ≤ 5 ≤ 7both admissible
5 ≥ 3.61 here — and at every node of a 4-connected gridManhattan dominates: never more expansions, usually fewer

Pro tip. max(h₁, h₂) here is simply Manhattan, since it wins everywhere. The max construction earns its keep when neither ingredient wins everywhere — different relaxations are blind to different obstacles.

4Bad heuristics

A heuristic fails at two poles. h = 0 everywhere is perfectly admissible and perfectly uninformative: A* collapses to uniform-cost search, correct and blind, paying for the missing compass in expansions. The opposite pole is overestimation — fast, focused, and no longer trustworthy, because an inflated estimate can bury the true best route down the queue until a worse one has already been returned.

The burial is mechanical, not probabilistic. Inflate h(B) from 3 to 20 on the lesson graph and the optimal route's frontier entry carries f = 5 + 20 = 25; the mediocre direct edge sits at f = 10 and pops first. A* returns 10 with the true 8 still waiting behind a lie — and nothing warns, because the search terminates normally, just wrongly.

Deliberate, measured inflation is a real technique: that is weighted A*, run with a known w and its cost-at-most-w-times-optimum receipt. The quick check below prices the honest version of the same trade — doubling an admissible h really does cut expansions, and the optimality guarantee is what pays for it. The defect is never the inflation; it is not knowing you did it.

Figure. Three runs on the same graph, scored by the cost of the path each returns. The honest heuristic and the empty one both return the optimal 8 — the empty one just works harder for it. The inflated heuristic is the only one that returns a worse answer, and it raises no error doing so.

One inflated estimate buries the best path

The lesson graph again (S→A 2, A→G 9, S→B 5, B→G 3, S→G 10), but a bug reports h(B) = 20 instead of 3. The other estimates stay h(S) = 7, h(A) = 8, h(G) = 0.

Expand S: f(A) = 2 + 8, f(B) = 5 + 20, f(G) = 10 + 010, 25, 10
The true best route (via B, cost 8) now waits atf = 25
A goal entry pops at f = 10returns the direct path, cost 10
Against the true optimum from the A* lesson: 10 vs 8suboptimal, and silently so

Pro tip. h(B) = 20 claims B is 20 away when it is 3 away — one overestimated node, and that was enough. Compare h against a handful of exact remaining costs before trusting any heuristic's speed.

Doubling an admissible heuristic usually makes A* expand far fewer nodes. What does that speed cost?

Nothing, because scaling a heuristic preserves admissibility
Termination, because A* can then loop forever on a cyclic graph
The path returned may be dearer than the true optimum, because the doubled estimate can now overshoot what remains
The frontier ordering, which becomes undefined once f-values are scaled

Inflating h is a real speed lever and a real trade. It buys fewer expansions by letting the search believe a promising branch is nearer than it is, and the optimality guarantee is what pays.

5Auditing a heuristic you inherited

In practice you rarely write h from a clean relaxation — you inherit it from a spec, a legacy codebase or a learned model, and the question becomes diagnostic: is this heuristic hurting, and how? Two symptoms cover most failures. Returned paths worse than a uniform-cost baseline on the same instances mean overestimation somewhere, because an admissible h can slow A* down but cannot make it wrong. Expansion counts close to that same baseline mean the opposite pole: h is too flat to steer.

The decisive test is exact and cheap on a sample: run Dijkstra backwards from the goal to obtain true remaining costs h^*, then compare pointwise — any node where h exceeds h^* convicts the heuristic. Sweep edges with h(n) \le c(n, n') + h(n') to test consistency, and assert h = 0 at every goal. Each check is mechanical; the lab below runs the first one against the inflated heuristic of the previous concept and finds the guilty node.

Repairs, in order of preference: fix the relaxation the estimate was supposed to come from; strengthen honestly by taking a max with another admissible estimate; or, if speed genuinely demands overestimation, switch to weighted A* so the inflation is explicit and the w × optimum bound is on the record.

The audit, in order

BaselineRun uniform-cost search on a few instances: its cost is ground truth, its expansion count the floor h must beat.
Sample h*A backwards Dijkstra from the goal gives exact remaining costs; any h above one of them is a conviction.
RepairFix the relaxation, max-combine with another admissible estimate, or move to weighted A* and own the bound.

Symptom to diagnosis
Symptom	Likely cause	Decisive check
Paths dearer than the uniform-cost baseline	Overestimation — admissibility broken	Compare h to exact h* from a backwards Dijkstra on sampled states
Expansions near the uniform-cost baseline	h too flat or near zero — no steering	Compare h against h* on solved instances; a flat profile means weak
Same node expanded repeatedly in graph search	Inconsistency — f falls along some edge	Sweep every edge for h(n) ≤ c(n, n′) + h(n′)

Coding lab. Audit a heuristic for admissibility runs in the app, with checks on your output.

Notes

Relax the problem, solve the relaxation exactly, use its cost as h — admissible by construction.
Between admissible heuristics, bigger is better: a dominating heuristic expands no more nodes; combine candidates with max.
An overestimate can silently return a suboptimal path; audit inherited heuristics against exact h* samples.

Formulas

Domination: h₂ dominates h₁ when h₂(n) ≥ h₁(n) at every node, both admissible
max(h₁, h₂) is admissible whenever both are, and dominates each of them

Exam traps & shortcuts

Combine admissible heuristics with a pointwise max, never an average — the max is still admissible and dominates every ingredient, while an average throws strength away.
If A* ever returns a costlier path than uniform-cost search on the same instance, the heuristic overestimates somewhere — find the node by sampling exact remaining costs with a backwards Dijkstra.
Derive h from a relaxation instead of tuning constants: a fudge factor has no admissibility argument, and the speed it buys is paid for with the guarantee.

Recap

The next lesson leaves search for knowledge and logic.

The recipe: Delete a constraint, solve the relaxed problem exactly, use its cost as h — admissible because every real solution stays legal in the relaxation.
Manhattan distance: The walls-deleted optimum: |Δx| + |Δy|. A unit move changes it by at most 1, so it is consistent, not merely admissible.
Domination: Bigger admissible is better: a dominating heuristic prunes at least as much. Combine candidates with max, never an average.
Judging a heuristic: Paths worse than uniform-cost search convict overestimation; expansions near it convict flatness. Audit against exact h* on a sample.

Practise Designing and Judging Heuristics

Reading is free and needs no account. Practice, mocks and progress live in the app.

2 quick checks with worked explanations
Timed mocks scored with the real marking scheme
Readiness tracked per topic, kept on your device

Continue with Google — freeNo card, no trial. Works offline once installed.