Understanding Consistent Heuristics in AI
In heuristic search, a consistent heuristic, also called a monotone heuristic, satisfies the triangle inequality for every edge. For any node n and successor n', the heuristic must obey:
h(n) <= c(n, n') + h(n')
where c(n, n') is the step cost. When h(goal) = 0, this property implies admissibility, meaning the heuristic never overestimates the true cost to the goal.
Consistency is important for A* search because it guarantees that f(n) = g(n) + h(n) is nondecreasing along any path. As a result, graph-search A* does not need to reopen closed nodes and remains optimal when its other assumptions hold.
Common examples include Manhattan distance for grid pathfinding with 4-connected moves and straight-line distance in Euclidean graphs where edge costs are distances. For 8-connected grids with diagonal moves, octile distance is consistent when the diagonal cost is sqrt(2).