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