0 votes
1 view
in AI and Deep Learning by (20.5k points)

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.

1 Answer

0 votes
by (45.1k points)

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

...