Consistent heuristic

In computer science, a consistent (or monotone) heuristic function is a strategy for search that approaches the solution in an incremental way without taking any step back. Formally, for every node N and every successor P of N generated by any action a, the estimated cost of reaching the goal from N is no greater than the step cost of getting to P plus the estimated cost of reaching the goal from P. In other words:

$h(N) \leq c(N,P) + h(P)$ and

$h(G) = 0.\,$

where

• h is the consistent heuristic function
• N is any node in the graph
• P is any child of N
• G is any goal node.

A consistent heuristic is also admissible. This is proved by induction on m, the length of the best path from node to goal. By assumption, $h(N_m) \leq h^*(N_m)$, where h ^* (n) denotes the cost of the shortest path from n to the goal. Therefore,

$h(N_{m+1}) \leq c(N_{m+1}, N_m) + h(N_m) \leq c(N_{m+1}, N_m) + h^*(N_m) = h^*(N_{m+1})$,

making it admissible. (N_{m + 1} is any node whose best path to the goal, of length m+1, goes through some immediate child N_m whose best path to the goal is of length m.)

Note: not all admissible heuristics are consistent. However, an admissible heuristic h, can be made into a consistent heuristic, h', through the following adjustment:

$h'(P) \gets \max(h(P), h'(N) - c(N,P))$

(Known as the pathmax^[1] equation.)

Consequences of monotonicity

Comparison of an admissible but inconsistent and a consistent heuristic evaluation function.

Consistent heuristics are called monotone because the estimated final cost of a partial solution, f(N_j) = g(N_j) + h(N_j) is monotonically non-decreasing along the best path to the goal, where $g(N_j)=\sum_{i=2}^j c(N_{j-1},N_j)$ is the cost of the best path from start node N₁ to N_j. It's necessary and sufficient for a heuristic to obey the triangle inequality in order to be consistent.^[2]

In the A* search algorithm, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that Dijkstra's algorithm requires in solving the shortest path problem (no negative cost cycles). In fact, if the search graph is given cost c'(N,P) = c(N,P) + h(P) − h(N) for a consistent h, then A* is equivalent to best-first search on that graph using Dijkstra's algorithm^[1]. In the unusual event that an admissible heuristic is not consistent, a node will need repeated expansion every time a new best (so-far) cost is achieved for it.

References

1. ^ ^{a b} Russell, Stuart; Peter Norvig (1995). Artificial intelligence: a modern approach. Prentice-Hall. ISBN 0-13-103805-2. 
2. ^ Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. ISBN 0-201-05594-5. 

External links

• CS141 Lecture from Brown University [1]