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.

Answer 3

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.