What is the difference between monotonicity and the admissibility of a heuristic?

user_2635 0
Viewed 21484

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.

heuristics computer-science artificial-intelligence
3 Answers

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.

user_30573370
Related