What is the difference between monotonicity and the admissibility of a heuristic?

Question

I'm reading over my AI textbook and I'm curious about what the difference is between monotonicity and admissibility of heuristics (I know they aren't mutually exclusive).

As far as I can tell, an admissible heuristic simply means you are ensured to get the shortest path to a solution if one exists.

What I'm struggling with is the concept of the monotonic property. Can someone describe this to me in a way I might understand?

Similarly, how can I determine if a given heuristic is monotonic/admissible? One of the examples given in the book is the 8-Piece Sliding Puzzle. One heuristic I'm considering is the # of out of place tiles, and intuitively I can say that I know that it is admissible but I have no formal way of showing if it is admissible/Monotonic.

Answer 1

You understood admissible heuristic very well. Now coming to the concept of monotonic property, In the context of search algorithms monotonicity (also called consistency) is a condition applied to heuristic functions. 

A heuristic h(n) is monotonic if, for each and every node n and every successor n' of n generated by any action ‘a’, the estimated cost of reaching the goal from n is no longer greater than the step cost of getting to n' plus the estimated cost of reaching the goal from n',

h(n)<=(n,a, n’)+h(n’)

Because every monotonic heuristic is also admissible thus the monotonicity is a stricter requirement than admissibility. Some heuristic algorithms such as A* can be proven optimal provided that the heuristic they use is monotonic.

The heuristic function h(n) where,

h is admissible, if for all nodes n

n in the search tree the following inequality holds:

h(n)≤h∗(n).