Consistent and Admissible Heuristics

Question

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.

Solution 1

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:

• This heuristic is inconsistent at 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)).
• Since this graph is undirected, this heuristic is also inconsistent at 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.

Solution 2

Admissible heuristic

never overestimates the cost to reach the goal. f(n) never overestimates the the cost of a solution along the current path through n. An obvious example of an admissible heuristic is the straight-line distance.

Consistency heuristic

• Consistent heuristic: for every node n and every successor n' of n generated by any action a: h(n) ≤ c(n,a,n') + h(n')
• Required only for applications of A* to graph search
• Every consistent heuristic is also admissible.

Solution 3

Long dead, but I'll give my two cents anyway. I think by far the easiest way to think of this is that an admissible heuristic says that you can't overshoot when getting to a particular defined goal node, while a consistent heuristic says that you can't overshoot when getting to ANY node. This makes the relationships clear: since the goal node is some node, a consistent heuristic is admissible. But since admissible only guarantees this property for one node, admissible does not imply consistency.

Solution 4

It is best to think of a consistent heuristic as an admissible heuristic which obeys the triangle inequality:

Cost(a -> c) <= Cost(a -> b) + Cost(b -> c)

for any three nodes a, b and c in the search space, with the understanding that the cost is computed using the actual cost between adjacent nodes and using the heuristic otherwise.

View more solutions

Comments

[Admin]

In fact, Felner et al write in section 6: "As illustrated in the quote from Artificial Intelligence: A Modern Approach [38] given earlier, there is a perception that inconsistent admissible heuristics are hard to create. However, it turns out that this is not true." - for the rest, great answer, thanks.

[ealfonso]

actually. this doesn't make sense. an admissible, not-consistent heuristic still can't "overshoot" for any node, where "overshoot" means the estimated cost is greater than the actual cost. consistency is concerned with the monotonicity of the heuristic's own estimates, not with the absolute, true cost, which is with what admissibility is concerned. it just happens that if for every step a heuristic is consistent, over k steps, it cannot overestimate a node's cost, and therefore consistent is always admissible.

[xyz]

In addition to @ealfonso's comment, heuristic is the estimated cost of reaching a goal from an arbitrary node, not the cost of reaching an arbitrary node in which case you would need two parameters, a start node and an end node. In the former case, which is what is commonly used, it doesn't make sense to talk about estimated costs to arbitrary nodes.

[Kataran]

I think the explanation is fine. Overshoots here means that the new total path cost should not be higher than it has to be, meaning you will always reach the most promising node.

[Frank H]

> Every consistent heuristic is also admissible. This bullet point cleared it all up for me. Now I understand very well, thanks!