Can an admissible heuristic underestimate badly?

Yes. That preserves admissibility but may provide weak search guidance.

Is low average prediction error enough?

No. Admissibility forbids overestimation of the true minimum in the relevant states.

Is every admissible heuristic consistent?

No. Consistency imposes an additional relationship between neighboring states.

AI Glossary / Graphs and symbolic AI / Intermediate

Admissible heuristic

Definition

An admissible heuristic is a search estimate that never overestimates the true minimum remaining cost of reaching a goal. Written mathematically, h(n) ≤ h*(n), where h(n) is the estimate at state n and h*(n) is the actual cheapest remaining cost. It provides an optimistic bound, not necessarily an accurate prediction of the eventual route taken.

What it means

Search algorithms often need guidance about which unfinished path looks promising. A heuristic supplies an estimate of the work or cost still ahead. Admissibility places a strict limit on that estimate: it must not exceed the best possible remaining cost under the problem's cost model.

The guarantee applies across the relevant states, not merely on average or on a sample of test cases. A predictor that is usually close but sometimes overestimates is not thereby admissible.

The estimate need not equal the truth. For a problem with nonnegative costs, assigning zero everywhere is admissible but usually gives little guidance. More informative lower bounds can help search focus its effort while retaining the required optimistic property.

How it works

Define the actual objective and cost units before designing the heuristic. An estimate in kilometers does not directly bound travel time in minutes. A lower-bound argument must connect the estimate to the quantity the search minimizes.

One approach solves a relaxed problem with some constraints removed, provided that relaxation cannot make the best solution more expensive. Its optimal cost can then bound the original problem from below. The validity depends on the relaxation and cost mapping, not on simplification alone.

A* combines the cost already incurred, g(n), with the remaining estimate, h(n), to form f(n) = g(n) + h(n). Under appropriate search and cost assumptions, admissible guidance supports finding a least-cost solution.

Consistency is a related stronger local condition: across an edge, h(n) ≤ c(n,n′) + h(n′), with zero at goals. An admissible heuristic can be inconsistent. Graph-search implementations may therefore need to reopen states when a better path is discovered; admissibility does not excuse incorrect duplicate handling.

Three practical examples

1. In a distance-based route problem, straight-line distance can be a lower bound when every permitted route has length at least that geometric distance. Shortcuts with different cost meanings require reconsideration.

2. A scheduling search uses a provable minimum amount of remaining processing work as guidance, after checking how parallel machines affect the bound.

3. A puzzle solver removes selected movement restrictions to create an easier problem. The relaxed optimum is useful only if its costs cannot exceed the original optimum.

Think of it this way

Think of saying, “Even in the best case, this job needs at least this much work.” The estimate helps eliminate unrealistically cheap expectations without claiming to predict every difficulty.

The analogy has a boundary: admissibility is a mathematical lower-bound property, not a cautious tone of voice. A confident estimate can be admissible, while a modest-sounding estimate can still be too large for one state and violate the guarantee.

Worked example

Consider an original toy graph with edges S→A costing 2, A→G costing 6, S→B costing 5, and B→G costing 2. There are no other edges, and G is the goal. The cheapest remaining costs are h*(G)=0, h*(A)=6, h*(B)=2, and h*(S)=7.

Set heuristic values h(G)=0, h(A)=5, h(B)=1, and h(S)=6. Each value is no greater than its corresponding true minimum, so this heuristic is admissible on the four states.

After expanding S, A* evaluates the path through A at f=2+5=7 and the path through B at f=5+1=6. It therefore examines B first and can reach G with total cost 7. The alternative through A costs 8.

If h(B) were changed to 3, admissibility would fail at B because 3 exceeds the true remaining cost 2. An algorithm might still find the optimal route on this particular graph, but that lucky outcome would not restore the heuristic's missing guarantee.

Illustrative case study

Fictional case: Alder Routing replaces a planner's lower-bound estimate with a learned travel-time predictor. The predictor improves average accuracy, but reviewers find that it sometimes overestimates the cheapest remaining time.

The team stops describing the predictor as admissible. It either retains a separately justified bound for exact search or evaluates the changed planner under a clearly stated approximation policy. This invented case illustrates the distinction between predictive accuracy and a search guarantee, without claiming that learned heuristics are inherently unsuitable.

Common misconceptions and mistakes

Admissible does not mean exact, fast, or safe for every search implementation. A weak admissible heuristic may explore many alternatives, and evaluating a sophisticated bound can itself be expensive.

Admissibility and consistency are not interchangeable. Testing a few paths also does not prove a universal lower-bound property.

Do not assume that a heuristic remains admissible after changing edge costs, action rules, or the goal definition. Nor can arbitrary admissible bounds always be added: their sum may double-count the same unavoidable cost. Combining bounds requires its own justification.

Business use

The concept matters when a planning product claims to find the cheapest solution rather than simply a good one. Reviewers should ask how the lower bound is established and whether the implementation preserves the assumptions required by the search algorithm.

Use small problems with known exact solutions to catch mistakes, then examine the mathematical reasoning supporting the full domain. Track the cost model's version alongside the heuristic. A correct proof for yesterday's model may not apply after introducing new actions, discounts, or resource interactions.

Check your understanding

The cheapest remaining path costs 9 units, and a heuristic returns 11. Is it admissible at this state?

Answer: No. It overestimates by 2 units. Good estimates elsewhere do not repair this violation.

Related terms

Heuristic
Consistency
Relaxed problem
Graph search
A* search
path cost
lower bound
optimality

Learn next

Next, check both admissibility and consistency on a small weighted graph. Then study why graph search may need to reopen a state when a cheaper path reaches it.

Sources

Poole and Mackworth, A* Search and its stated optimality assumptions: https://artint.info/html1e/ArtInt_57.html

Felner and colleagues, Inconsistent Heuristics in Theory and Practice, primary author-hosted paper: https://tzin.bgu.ac.il/~felner/2011/ARTINT_2581.pdf

Core lower-bound and inconsistency explanations were checked. The graph and business scenario are original.

Previous: Admissible decision rule Next: Advantage actor-critic