A heuristic is consistent or monotone if for every node n, every successor n' of n generated by any action a,

h(n) ≤ c(n,a,n') + h(n')

Theorem:

If h(n) is consistent, A* using GRAPH-SEARCH (keeps all checked nodes in memory to avoid repeated states) is optimal

Proof: If h is consistent, we have

f(n’) = g(n’) + h(n’) (by def.)

= g(n) + c(n,a,n') + h(n’) (g(n’)=g(n)+c(n.a.n’))

≥ g(n) + h(n)

= f(n) (consistency)

f(n’) ≥ f(n)

i.e., f(n) is non-decreasing along any path.