# 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.

• You could ask this on SO. Commented Sep 5, 2013 at 11:41
• possible duplicate of Is the Manhattan distance monotonic when used as heuristic function? Commented Sep 5, 2013 at 14:51
• May I ask why you want to know how to make a heuristic non-monotonic? Or is it the opposite you're after: how to make a heuristic monotonic? Commented Sep 6, 2013 at 0:11

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 :) Commented Sep 6, 2013 at 5:21