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

This might help you to understand the differences and/or similarities: Artificial intelligence illuminated (4.12.4 Monotonicity)

Answer 2

A heuristic is monotonic, in the sense most relevant to the context you're talking about, if it never overestimates (always underestimates or correctly estimates) the cost between any two given states. For the A* algorithm, a heuristic is admissible, and therefore guarantees finding the optimal path, if it is monotonic.

Monotonicity is a property of functions in general; admissibility is a property of functions with respect to certain algorithms.

Answer 3

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 4

Monotonic learning is when an agent may not learn any knowledge that contradicts what it already knows. For example, it may not replace a statement with its negation. Thus, the knowledge base may only grow with new facts in a monotonic fashion. The advantages of monotonic learning are:

1.greatly simplified truth-maintenance

2.greater choice in learning strategies

Non-monotonic learning is when an agent may learn knowledge that contradicts what it already knows. So it may replace old knowledge with new if it believes there is sufficient reason to do so. The advantages of non-monotonic learning are:

1.increased applicability to real domains,

2.greater freedom in the order things are learned in

A related property is the consistency of the knowledge. If an architecture must maintain a consistent knowledge base then any learning strategy it uses must be monotonic.