How does consistency imply that a heuristic is also admissible?

Question

A heuristic function $h (n)$ is...

• Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the goal.
• Admissible if $h(n)$ never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.

Answer 1

To proof the statement in your question, let us proof that consistency implies admissibility whereas the opposite is not necessarily true. This would make consistency a stronger condition than the latter.

Consistency implies admissibility:

Let me start by emphasizing that $h(t)=0$ if the heuristic function $h$ is admissible (where $t$ is a goal) since edge costs are assumed to be non-negative and thus, the optimal cost from one node to itself is necessarily 0. This certainly holds in case the heuristic function is admissible but we want to proof that consistency necessarily implies admissibility. For this, let us assume further that $h(t)=0$ for any goal ---and this fact will be used in the base case below.

The proof proceeds by induction:

Base case: take any predecessor of the goal node $t$. Let $n$ denote it, so that $t$ is a successor of $n$. If the heuristic function is consistent, then $h(n)\leq c(n,t) + h(t)=c(n,t) + 0 =c(n,t)$ and hence, $h$ behaves admissibly in this case.

Note that the base case does not assume that the edge $\langle n, t\rangle$ is necessarily the optimal solution from $n$ to $t$ and, indeed, there might be a different path from $n$ to $t$ with a lower cost. The importance of the base case, is that $h(n)\leq c(n,t)$ for all ancestors of node $t$! This result will be reused in the induction step.

Induction step: consider a node $n$. The optimal cost to reach the goal $t$ from $n$, $h^*(n)$, is computed as: $\min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\}$, where $\mathrm{SCS}(n)$ is the set of successors of node $n$. As consistency is assumed by hypothesis, then $h(n)\leq c(n,n')+h(n')$. Furthermore, as $h(n')\leq h^*(n')$ is assumed by the induction step then $h(n)\leq c(n,n')+h^*(n')$ and this is true for all successors $n'$ of node $n$. In other words: $h(n)\leq \min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\} = h^*(n)$, so that $h(n)\leq h^*(n)$.

Admissibility does not necessarily imply consistency:

For this, a simple example suffices. Consider a graph which consists of a single path with 10 nodes: $\langle n_0, n_1, n_2, ..., n_9\rangle$, where the goal is $n_9$. Let us assume wlog that all edge costs are equal to 1. Obviously $h^*(n_0)=9$, and let us make $h(n_0)=8$, $h(n_i)=1, 1\leq i<9$ and $h(n_9)=0$. Clearly, the heuristic function is addmissible:

1. $h(t)=0$
2. $h(n_i)=1\leq h^*(n_i)=(9-i)$, $\forall i, 1\leq i<9$.
3. Finally, $h(n_0)=8\leq h^*(n_0)=9$.

However, $h(n)$ is not consistent and $h(n_0)=8 > c(n_0, n_1)+h(n_1)=1+1=2$.

Hope this helps,