I'm at the point where I'm really confusing myself as to why consistency is required for A* optimality to be guaranteed. I understand the definition of consistency to be H(n) - H(n') <= C(n, n') but it's just not clicking as to why this is guaranteed for optimality to me.
Can someone explain in very simple terms the reasoning and potentially a counterexample as to how admissibility isn't enough?
Unless you are doing something very unusual, an admissible heuristic will also be consistent. In fact, the problem to understand the difference, and why consistency is needed, is that coming up with examples is not trivial.
Note: you say "why admissible is not enough", so I take it you have a basic understanding of why admissible heuristics result in optimal paths, so I will focus on the relationship between admissible and consistent.
Admissible means you do not overestimate the distance from the current node to the target. This is important so that you never disregard important nodes during exploration: if your heuristic tells you you are too far away, you will explore other more promising alternatives, potentially missing the optimal path, whereas underestimating the distance to the target means you will explore more unsuccessful candidates until you find the optimal path. Actually, a heuristic that returns always distance = 0 will work! (But would not be very efficient.)
Consistency is a bit trickier. In a nutshell, your equation means that the estimation to go from A to B should always be, at least, as long as the (known) cost from A to C and then going to B. Otherwise the estimation from A to B seems broken!
Consistency implies admissibility. Imagine the point A and the target B, with the cost from A to B known in this case. Remember the heuristic from B to B is zero. If the heuristic is to be consistent, the cost from A to B plus the heuristic from B to B must be more than the heuristic from A to B.
So the heuristic is admissible in this case. You can extend this example by induction to prove the point (see here for more details).
Let us explore now an inconsistent, admissible example (admissibility does not imply consistency!). Consider this graph (known distances in solid lines):
Let's think what happens from node D. The estimation from D is 8 (distance units).
Now imagine we want to go to B before going to the target. This should either be the optimal route from D or make the path from D longer. Adding waypoints to your optimal route should never make the way shorter!
For the route going through B first, the distance is D to B (1 unit, known) plus an estimated 5 from B to the target, total: 6 units, less than 8.
See that:
Can the example above be admissible? Sure, just imagine all dotted lines are actually 20 distance units. All heuristics are underestimating, but consistency does not hold.
Note that consistency is not required in general, but only in more efficient implementations of A* (using a closed list of explored nodes) that avoid double-checking nodes. Why?
Imagine you know A and B. And A is more promising than B. Now we discover C, neighbour of B. If the heuristic is consistent, we know B is still less interesting than A. Without consistency, it could be that "B-passing-by-C" is now better than "B-direct-route" was, so we are not sure about A vs B anymore. That is an informal explanation of how inconsistency can mess up the process (and force you to re-examine nodes).
Further reading:
