A consistent heuristic estimates a successor’s remaining cost as no more than the predecessor’s estimate plus the transition cost: h(u) ≤ cost(v,u) + h(v). section 14.5.1
In A*, consistency works with admissibility to preserve optimal solutions without requiring heuristic values to decrease monotonically along every traversal. section 14.5.1
Road distance and straight-line distance
For a road graph, use road distance as edge cost and straight-line distance to the goal as the heuristic. Euclidean triangle inequality makes the heuristic consistent, even when a graph detour causes a successor’s estimate to increase. section 14.5.1
straight_line(u, goal) ≤ road_distance(v, u) + straight_distance(v)
The inequality makes the consistency requirement concrete for checking an A* heuristic. section 14.5.1
