Menu
Any consistent heuristic is also admissible. But when is a heuristic admissible but not consistent (monotone)?
Please provide an example in which this is the case.
238
In an admissible heuristic, the estimated cost from the current node to the goal state is never greater than the actual cost. All consistent heuristics are admissible heuristics, however, all admissible heuristics are not necessarily consistent heuristics.
A heuristic h is admissible (optimistic) if: 0 ≤ h(n) ≤ h∗(n) where h∗(n) is the true cost to a nearest goal Note: Coming up with admissible heuristics is most of what's involved in using A* in practice. Examples: Optimize: number of flips.
An admissible heuristic is used to estimate the cost of reaching the goal state in an informed search algorithm. In order for a heuristic to be admissible to the search problem, the estimated cost must always be lower than or equal to the actual cost of reaching the goal state.
If you assign a decreasing heuristic function of the depth of the optimal soution path (but attempt to do not violate overestimate condition for admissibility), thereby the result heuristic is admissible but is not consistent.
As Russel and Norvig point out in Artificial Intelligence: A Modern Approach (the most commonly used AI textbook) it is challenging to come up with a heuristic that is admissible but not consistent.
Obviously, you can select values for nodes in a graph such that the heuristic they represent is admissible but not consistent. This paper by Felner et al has a nice example of the two ways that this is possible, but it's a little dense, so I'll summarize:
c1 because it is giving a lower (i.e. less informative) lower bound on the cost to get to the goal than its parent node is. The cost estimate of getting to the goal through the parent node is at least 10 (because the cost of the path to p is 5 and the heuristic estimate at p is also 5). The cost estimate for getting to the goal through c1, however, is just 8 (cost of parent (5), plus cost of path from parent (1), plus heuristic estimate at c1 (2)).c2, because going from c2 to p has the same problem as above.Felner et al also provide a few concrete examples of an admissible but inconsistent heuristic. Consider the 8-puzzle problem:
In this puzzle there are 8 sliding tiles numbered 1-8, and one empty space. The tiles start out out of order (as in the image on the left). The goal is to get the puzzle into the state shown above on the right exclusively by sliding tiles into the empty space. The classic heuristic for this problem (Manhattan distance of each tile to the location where it is supposed to be) is admissible and consistent.
However, you could come up with a different heuristic. Maybe you just want to look at Manhattan distance (i.e. the number of squares away) of the 1, the 2, and the 3 to the locations in which they are supposed to be in the goal state. The heuristic, while less informative than Manhattan distance of all tiles, is still admissible and consistent.
But let's say that you choose an additional group of squares, perhaps 5, 6, and 7. And then let's say that the way you calculate the heuristic at each node is by randomly selecting one of those sets (1,2, and 3) or (5, 6, and 7) and computing their Manhattan distance to their goal locations. This heuristic is still admissible - it can only ever underestimate or match the number of moves needed to get to the goal state. However, it is no longer consistent - there isn't a clear relationship between the heuristic estimates at each node.
160
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
