Does differential mean differentiation here?

No. It refers to subtracting distances.

Can the bound be zero for distinct nodes?

Yes, if their distances to every selected landmark match.

Must the graph have geographic coordinates?

No. The calculation uses shortest-path distances within the graph.

AI Glossary / Graphs and symbolic AI / Advanced

Differential heuristic

Definition

A differential heuristic estimates the remaining shortest-path cost by comparing precomputed distances to selected landmark nodes. In an undirected graph with nonnegative edge costs and finite relevant distances, each landmark supplies the absolute difference between its distance from the current node and its distance from the goal. Taking the largest such difference gives an admissible lower bound.

What it means

An admissible estimate does not exceed the true minimum remaining cost under the stated assumptions. It can help a search algorithm prioritize promising states without requiring a complete table of distances between every possible pair of nodes.
The landmark is a reference point, not necessarily a place the eventual route should visit. The method uses what the two distances imply about separation. It does not propose traveling from the current node to the landmark and then to the goal. A lower bound can be useful even when it is substantially smaller than the actual shortest-path cost.

How it works

Choose several landmarks and compute shortest-path distances from each to the graph's nodes. For a current node n, goal g, and landmark L, calculate |d(n,L) - d(g,L)|. The differential heuristic is the maximum of these values across the chosen landmarks.
The justification is the triangle inequality for shortest-path distances. Neither node's distance to a landmark can exceed its distance to the other node plus that other node's landmark distance. Combining the two inequalities bounds the absolute difference by d(n,g). The largest of several valid lower bounds is still a valid lower bound.
With N nodes and k landmarks, an ordinary full table stores kN distances. Building it requires shortest-path computations; the cost depends on graph structure, weights, and the algorithm used. Directed graphs need direction-aware bounds and distances to and from landmarks. The undirected absolute-difference formula should not simply be transferred to one-way networks. Unreachable pairs also require explicit handling rather than subtracting infinite values.

Three practical examples

Game navigation: A pathfinding system precomputes landmark distances on a stable map with obstacles. These distances reflect traversable routes rather than only straight-line geometry. Changes to the map require checking whether stored information still supplies valid bounds.
Indoor route planning: A building-navigation prototype represents corridors and permitted connections as a graph. Landmarks provide reusable information for many start-goal queries. The representation must account for direction restrictions and the cost measure that the actual query uses.
Search-service design: A team compares a landmark table against an existing heuristic on repeated graph queries. It measures preprocessing, memory, query time, and returned path costs. A stronger numerical estimate may reduce search work, but extra lookup costs can affect the overall tradeoff.

Think of it this way

Suppose two locations are different distances from the same reference station. Their separation cannot be less than the difference between those distances, assuming the distances follow the same undirected travel rules. Several reference stations provide several lower bounds; the strongest valid bound is the most informative one.

Worked example

Construct an undirected graph with edges L-A costing 2, A-B costing 3, and B-G costing 4. Add a branch B-M costing 2. There are no other edges. The task is to estimate the shortest-path cost from A to G, using landmarks L and M.
For landmark L, the stored distances are d(A,L) = 2 and d(G,L) = 9. Their absolute difference is |2 - 9| = 7.
For landmark M, the stored distances are d(A,M) = 5 and d(G,M) = 6. Their absolute difference is |5 - 6| = 1. The combined differential heuristic is max(7, 1) = 7.
The actual shortest path A-B-G costs 3 + 4 = 7, so the estimate happens to be exact. The M-only bound remains admissible but is much weaker. Adding the two bounds would produce 8, which exceeds the true cost and loses admissibility. Taking the maximum is essential here.
Now add a direct A-G edge costing 1. The new shortest-path cost is 1. Reusing the old table would still yield 7, an overestimate. With updated distances, d(G,L) becomes 3, while d(A,L) remains 2, giving bound 1. The M distances become 5 and 6 respectively, also giving bound 1.
This example demonstrates a valid lower bound, the difference between maximum and sum, and the need to reconsider cached information after graph changes.

Illustrative case study

Fictional Birch Navigation adds landmark estimates to a route-planning prototype. The initial evaluation uses a fixed graph, but later maintenance introduces new links without rebuilding the distance table. Some stored estimates then exceed newly available route costs.
The team ties each table to a graph version and checks its update procedure. It compares search results against independently computed shortest paths on a representative test set, including cases affected by new links. It also measures whether additional landmarks justify their memory and computation costs.
This fictional scenario illustrates cache validity and evaluation. It does not claim that a specific number or placement of landmarks is best for every network.

Common misconceptions and mistakes

“The chosen route must pass through a landmark.” Landmarks supply bounds, not mandatory waypoints.
“Add every landmark estimate for a stronger heuristic.” Summation can overestimate the true cost.
“The estimate is always exact.” Landmark placement and graph geometry affect its strength.
“More landmarks always make the system faster.” Additional storage and evaluation have costs.
“Stored distances remain valid after any update.” New connections or cheaper edges can invalidate old lower bounds.

Business use

Consider this method when many route queries reuse a graph and preprocessing can be amortized across them. Define the graph version, cost units, direction rules, and landmark selection process.
Evaluate total service performance and path quality together. Establish how tables are refreshed or invalidated, and handle disconnected regions explicitly. A mathematically valid heuristic is one ingredient of a correct search service, not proof that the whole implementation is correct.

Check your understanding

Which landmark gives the stronger original bound?

Answer: L, with 7 rather than 1.

Why is the sum 8 unsuitable?

Answer: It exceeds the actual path cost 7.

What invalidates the original table in the example?

Answer: A new edge makes the true shortest path cheaper than the stored estimate.

Related terms

Admissible heuristic
Landmarks
Triangle inequality
Shortest Paths
Preprocessing
landmark
A* search
shortest path
distance table

Learn next

Choose two landmarks on a small weighted graph. Calculate their separate bounds for several queries, compare the maximum with exact shortest-path costs, and repeat after adding a shortcut.

Weighted graph

Sources

Sturtevant and colleagues, Memory-Based Heuristics for Explicit State Spaces: https://ijcai.org/Proceedings/09/Papers/107.pdf JGraphT, ALT admissible heuristic and directed-distance handling: https://jgrapht.org/javadoc-1.4.0/org/jgrapht/alg/shortestpath/ALTAdmissibleHeuristic.html AIMA glossary, differential heuristic: https://github.com/aimacode/aima-glossary/blob/master/glossary.md

Previous: Differential entropy Next: Differential privacy