Is an admisible heuristic always monotone (consistent)? -

for a* search algorithm, provided heuristic h, supose h admisible.

that is:

h(n) ≤ h*(n) every node n, h* real cost n goal.

does ensure heuristic monotone?

that is:

f(n) ≤ g(n') + h(n') every sucesor n' of n, f(n)= h(n) + g(n) , g(n) accumulated cost.

no.

assume have 3 successor states s1, s2, s3 , goal state g s1 -> s2 -> s3 -> g.
s1 starting node.

consider following values h(s) , h*(s) (i.e. true cost):
h(s1) = 3 , h*(s1) = 6
h(s2) = 4 , h*(s2) = 5
h(s3) = 3 , h*(s3) = 3
h(g) = 0 , h*(g) = 0

following path goal can have that:

g(s1) = 0, g(s2) = 1, g(s3) = 3, g(g) = 6, coinciding true cost above.

although heuristic function admissible (h(s) <= h*(s)), f(n) not monotonic. instance f(s1) = h(s1) + g(s1) = 3 while f(s2) = h(s2) + g(s2) = 5 f(s1) < f(s2). same holds between f(s2) , f(s3).

of course means have quite uninformative heuristic.