Admissibility of heuristic in the $A^*$ algorithm

Question

The CS188 course from Berkeley goes to great length in explaining why the optimality of $A^*$ algorithm is conditioned by the admissibility of heuristic.

Note: admissibility of heuristic means that:

$$\forall n, 0 \leq h(n) \leq h^*(n) $$

With $h^*(n)$ being the true optimal distance of $n$ to the goal.

The course's proof reasoning is sound and makes perfect sense.

However, this example uses a heuristic that is not admissible. For instance, the distance between the start state and the goal state is only $h^* = 2$ while the heuristic of the start state is $h = 17$ (see the example with the 8-puzzle, using Nilsson heuristic). Obviously, $17 \gt 2$ and therefore the heuristic is not admissible.

However, after having implemented the algorithm and tested it, it seems that it is able to find the optimal solution each time. Trying to alter the heuristic function only makes it worse than optimal.

So, if the admissibility of the heuristic a necessary condition for the guaranteed optimality of $A^*$, how comes that this example seems to refute this?

Did I miss something? Or perhaps, does the condition on the admissibility means that sometimes, the algorithm will be optimal even with an unadmissible heuristic, but only an admissible one guarantees the optimality?

I'd be curious to hear any thought about that.

Answer 1

It's exactly as you suspected:

Sometimes, the algorithm will find an optimal solution even with an unadmissible heuristic... only an admissible heuristic guarantees the optimality of the solution returned.

If you use an unadmissible heuristic, there's no guarantee what will happen. The solution you get back might be the best one; or it might not be. And, you probably won't have any way of telling whether the solution you got back was optimal or not, so you won't even know for sure when this is a problem and when it isn't.

If you use an unadmissible heuristic, you'll often (but not always) get sub-optimal solutions.