22

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.

mmcdole
  • 91,488
  • 60
  • 186
  • 222
  • 1
    Dana the Sane's post should help a lot. To show admissibility, just prove that your heuristic always guesses a solution that takes fewer steps than the actual optimal path. For the sliding puzzle, and the # of tiles out of place heuristic, its as simple as saying a piece that is out of place must move to get to its place, therefore my heuristic's guess must be optimal or guess that it takes fewer steps than it actually does. To prove not admissible, show a counter example (its rarely difficult to find one quickly for inadmissible heuristics). – Nick Larsen Oct 19 '09 at 21:32
  • For further discussion of the distinction between monotonicity (also called consistency) and admissibility and contexts in which they do not overlap, see my answer here: http://stackoverflow.com/questions/20516027/consistent-and-admissible-heuristics/20532330#20532330 . – seaotternerd Jun 12 '14 at 20:01
  • Is this relevant on StackOverflow? Sounds more like cs.stackexchange questions – CodyBugstein Sep 25 '15 at 21:15
  • 3
    @Imray, when this question was asked (2009), cs.stackexchange.com didn't exist. – mmcdole Sep 27 '15 at 01:02

3 Answers3

21

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

Dana the Sane
  • 14,762
  • 8
  • 58
  • 80
  • And from the same book, they did a good job of exemplifying admissibility using the Manhattan distance in the NxN sliding panels game. Thats a great chapter for understanding heuristics in general. – Nick Larsen Oct 19 '09 at 21:26
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.

jinu
  • 21
  • 1
-2

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.

Rahul
  • 5
  • 2
  • 1
    I think you are maybe not being careful about the difference between "knowledge" and "belief". Why has an agent changed its belief from the traffic light being red to it being green? Is the contradiction between the two a contradiction between two pieces of knowledge? The term usually used in AI for this phenonmenon is "belief revision". – Charles Stewart Oct 27 '10 at 11:34