# How does consistency imply that a heuristic is also admissible?

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.

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.

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,

• why are edge costs assumed to be non negative? Commented May 24, 2020 at 11:04
• Well, I did just because it is conventional to do so. Heuristics are usually applied with non-negative edge costs. Good question indeed ... ! Commented May 24, 2020 at 21:36
• h(n)≤c(n,t) does not trivially imply that h(n)≤h*(h). Can you explain why this is so, since you need to prove that to assume h(n′)≤h*(n′) by the induction step. [Here] (stackoverflow.com/questions/64596325/…) is a possible explanation. Commented May 16, 2022 at 3:45
• Not sure I get your point Federico ... it seems to me you are asking that it is not trivial to show that $h(n)\leq c(n,t)$ necessarily implies that $h(n)\leq h^*(n)$, ... well the first part is known as consistency. Second is known as admissibility and the whole question is all about that. The answer I provided is an attempt to prove precisely that ... Maybe there are obscure or even a wrong point in my reply ... is there? Commented May 17, 2022 at 8:17
• @FedericoCiuffardi $h(n') \le h^\star(n')$ is the induction hypothesis. Throughout the proof we assume that $h(\cdot)$ is consistent, i.e. $h(a) \le c(a,b) + h^\star(b)$ for any $a$ and any of its successors $b$. The induction step then shows that $h(n') \le h^\star(n')$ implies $h(n) \le h^\star(n)$, i.e. admissibility of the $h(\cdot)$ at $n'$ implies admissibility of $h(\cdot)$ as any of its predecessors $n$. Recall the induction is working backwards from the goal node. Commented Feb 22, 2023 at 19:21