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

Russel and Norvig, 2ed page 99 says:

The second solution is to ensure that the optimal path to any repeated state is always the first one followed -- as is the case with uniform-cost search. This property holds if we impose an extra requirement on h(n), namely the requirement of consistency (also called monotonicity).

When you're talking about functions, monotone means that a function increases or decreases, but not both. In other words, the ordering in the range stays the same throughout the domain. For this reason in your problem, the solution maintains the shortest path no matter what step you start at.

The admissibility property of a heuristic means that the cost to reach the goal is never overestimated (i.e. it's optimistic) (page 98).

Answer 2

Admissibility :

A search algorithm is admissible if it is guaranteed to find a minimal path to a solution whenever such a solution exists. Breadth first search is admissible, because it looks at every state at level n before considering any state at level n+1.

Monotonicity : This property asks if an algorithm is locally admissible---that is, it always underestimates the cost between any two states in the search space. Recall that A* does not require that g(n) = g*(n). A heuristic function, h is monotone if: 1.For all states ni and nj, where nj is a descendant of ni, h(ni) - h(nj) <= cost(ni,nj).

2.The heuristic evaluation of the goal state is 0: h(Goal) = 0.