# What makes a path finding heuristic Monotonic vs. Non-monotonic?

I am currently working on an algorithm that solves a path through the maze. So far I have implemented a Manhattan and Pythagorean Heuristic. I was wondering what makes a heuristic monotonic and how would one go about making a heuristic non-monotonic.

A heuristic $$\h\$$ is monotonic when, in addition to being admissible (meaning the estimate is always equal or lesser to the actual minimum cost) the heuristic satisfies the relation:

$$h(x) <= d(x,y) + h(y)$$

fo all adjacent nodes $$\x\$$ and $$\y\$$, where $$\d(x,y)\$$ is the distance from node $$\x\$$ to node $$\y\$$.

More can be found here.

Update: (thanks to ilmari-karonen):
• "is monotonic when, in addition to being admissible..." - Usually the definition of 'consistent' is given to be just your h(x) <= d(x,y) + h(y) constraint, plus the constraint that h(goal) = 0. Then the heuristic is provably admissible; this form is given because, when proving consistency, it's much easier to show that h(goal) = 0 than it is to show that the heuristic is admissible :) – BlueRaja - Danny Pflughoeft Sep 6 '13 at 5:21