Consistent (Monotonic) Heuristics
What you'll learn: How the consistency property strengthens admissible heuristics and makes A* more efficient.
The Core Idea
A consistent (or monotonic) heuristic goes beyond being merely admissible—it satisfies a triangle inequality-like property. Formally, for every node n and every successor n':
h(n) ≤ cost(n, n') + h(n')
This means the estimated cost from n to the goal can't be greater than the cost to move to n' plus the estimate from n' to the goal.
Think of it like a GPS navigation system: if you're 10 miles from your destination, and you drive 3 miles closer, your new estimate shouldn't say you're now 15 miles away. The estimates must "make sense" as you move through the graph.
Why Consistency Matters for A*
When a heuristic is consistent, A* gains a powerful guarantee: the first time A expands a node, it has found the shortest path to that node*. No re-expansions are needed.
This happens because consistency ensures that f(n) values are non-decreasing along any path. Since f(n) = g(n) + h(n), and the heuristic "decreases smoothly," A* explores nodes in optimal order.
The Efficiency Impact
- No duplicate work: Each node is expanded at most once
- Optimality preserved: Consistency implies admissibility, so solutions remain optimal
- Cleaner implementation: You can skip the "reopen" logic where nodes get re-added to the priority queue with better paths
Every consistent heuristic is admissible, but not every admissible heuristic is consistent. Consistency is the stronger, more desirable property.
Key Takeaway: A consistent heuristic satisfies h(n) ≤ cost(n,n') + h(n'), ensuring A* expands each node only once while maintaining optimality—a major efficiency win.