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.