5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ ...or better yet, here. \$\endgroup\$ – Ilmari Karonen Sep 5 '13 at 22:20
  • \$\begingroup\$ @IlmariKaronen: Comments being intended as temporary, I have incorporated your link in my answers. Thank you. \$\endgroup\$ – Pieter Geerkens Sep 5 '13 at 22:25
  • \$\begingroup\$ 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. \$\endgroup\$ – congusbongus Sep 6 '13 at 0:13
  • 1
    \$\begingroup\$ "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 :) \$\endgroup\$ – BlueRaja - Danny Pflughoeft Sep 6 '13 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.