# 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. – ziggystar Sep 5 '13 at 11:41
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? – congusbongus Sep 6 '13 at 0:11

## 1 Answer

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):
An even better link here:

Consistent (aka *monotonic) heuristics are usually preferred because as each node is reached, consistency guarantees that the path length to that point is equal to the minimal path-length from the start node. This means that a closed-set can be used to avoid expanding nodes more than once.

The most common use of an admissible but not consistent heuristic is when using a bidirectional A*; however in this instance each branch is self-consistent, and so it suffices to expand each node once from each branch.

-
...or better yet, here. – Ilmari Karonen Sep 5 '13 at 22:20
@IlmariKaronen: Comments being intended as temporary, I have incorporated your link in my answers. Thank you. – Pieter Geerkens Sep 5 '13 at 22:25
I suggest two improvements to this answer: how to make an admissible heuristic monotonic (using pathmax for example), and reason why we want heuristics to be monotonic. – congusbongus Sep 6 '13 at 0:13
"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