Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
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 1

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.

share|improve this answer
    
...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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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