If a heuristic is not admissible, can it be consistent?

No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent.

Definitions

Given a graph $G=(V, E)$ representing the search space, where $V$ and $E$ are respectively the set of vertices and edges, and the function $w: E \times E \rightarrow \mathbb{R}$ that defines the weight (or cost) of each edge of $G$, an admissible heuristic $h_{\text{a}}$ is defined as

$$h_{\text{a}}(n) \leq h^*(n), \forall n \in V$$

where $h^*(n)$ is the optimal cost to reach a goal from $n$ (so $h^*(n)$ is the optimal heuristic). On the other hand, a consistent heuristic $h_{\text{c}}$ is defined as

\begin{align} h_{\text{c}}(n) &\leq w(n, s) + h_{\text{c}}(s), \forall n, s, \text{ and} \\ h_{\text{c}}(g) &= 0, \end{align} where $s$ is a successor of $n$ and $g$ is any goal node.

Theorem

A consistent heuristic is an admissible heuristic.

Proof

Let $h$ be a consistent heuristic. Given that $h$ is consistent, then $h(g) = 0$, for any goal node $g$, so it does not overestimate the cost of reaching the goal at any of the goal nodes (given that, if you already are at a goal node, the cost is $0$, and $h(g) = 0$ is not greater than $0$). Let $g_{n}$ be an arbitrary neighbour of an arbitrary goal node $g$. Given that $h$ is consistent, then $h(g_{n}) \leq w(g_{n}, g) + h(g)$. Given that $h(g)$ does not overestimate the cost to reach the goal from $g$, then $w(g_{n}, g) + h(g)$ also does not overestimate the cost of reaching the goal from $g_n$, given that $w(g_{n}, g)$ is the true cost of the edge $(g_{n}, g) \in E$ and the cost to reach the goal from $g_n$ must be at least $w(g_{n}, g)$. This reasoning can be applied inductively (or recursively) on $g_n$ (then on the neighbouring nodes of $g_n$, and so on), so $h$ must be admissible.

If a heuristic is not admissible, can it be consistent?

No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent.

Definitions

Given a graph $G=(V, E)$ representing the search space, where $V$ and $E$ are respectively the set of vertices and edges, and the function $w: E \times E \rightarrow \mathbb{R}$ that defines the weight (or cost) of each edge of $G$, an admissible heuristic $h_{\text{a}}$ is defined as

$$h_{\text{a}}(n) \leq h^*(n), \forall n \in V$$

where $h^*(n)$ is the optimal cost to reach a goal from $n$ (so $h^*(n)$ is the optimal heuristic).

On the other hand, a consistent heuristic $h_{\text{c}}$ is defined as

\begin{align} h_{\text{c}}(n) &\leq w(n, s) + h_{\text{c}}(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\ h_{\text{c}}(g) &= 0, \forall g \in \mathcal{G}, \end{align} where $s$ is a successor of $n$, $g$ is any goal node and $\mathcal{G}$ is the set of goal nodes of the graph $G$.

Theorem

A consistent heuristic is an admissible heuristic.

Proof

Let $h$ be a consistent heuristic. Given that $h$ is consistent, then $h(g) = 0$, for any goal node $g$, so it does not overestimate the cost of reaching the goal at any of the goal nodes (given that, if you already are at a goal node, the cost is $0$, and $h(g) = 0$ is not greater than $0$). Let $g_{n}$ be an arbitrary neighbour of an arbitrary goal node $g$. Given that $h$ is consistent, then $h(g_{n}) \leq w(g_{n}, g) + h(g)$. Given that $h(g)$ does not overestimate the cost to reach the goal from $g$, then $w(g_{n}, g) + h(g)$ also does not overestimate the cost of reaching the goal from $g_n$, given that $w(g_{n}, g)$ is the true cost of the edge $(g_{n}, g) \in E$ and the cost to reach the goal from $g_n$ must be at least $w(g_{n}, g)$. This reasoning can be applied inductively (or recursively) on $g_n$ (then on the neighbouring nodes of $g_n$, and so on), so $h$ must be admissible.

If a heuristic is not admissible, can it be consistent?

No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent.

Definitions

Given a graph $G=(V, E)$ representing the search space, where $V$ and $E$ are respectively the set of vertices and edges, and the function $w: E \times E \rightarrow \mathbb{R}$ that defines the weight (or cost) of each edge of $G$, an admissible heuristic $h_{\text{a}}$ is defined as

$$h_{\text{a}}(n) \leq h^*(n), \forall n \in V$$

where $h^*(n)$ is the optimal cost to reach a goal from $n$ (so $h^*(n)$ is the optimal heuristic). On the other hand, a consistent heuristic $h_{\text{c}}$ is defined as

\begin{align} h_{\text{c}}(n) &\leq w(n, s) + h_{\text{c}}(s), \forall n, s, \text{ and} \\ h_{\text{c}}(g) &= 0, \end{align} where $s$ is a successor of $n$ and $g$ is any goal node.

Theorem

A consistent heuristic is an admissible heuristic.

Proof

Let $h$ be a consistent heuristic. Given that $h$ is consistent, then $h(g) = 0$, for any goal node $g$, so it does not overestimate the cost of reaching the goal at any of the goal nodes (given that, if you already are at a goal node, the cost is $0$, and $h(g) = 0$ is not greater than $0$). Let $g_{n}$ be an arbitrary neighbour of an arbitrary goal node $g$. Given that $h$ is consistent, then $h(g_{n}) \leq w(g_{n}, g) + h(g)$. Given that $h(g)$ does not overestimate the cost to reach the goal from $g$, then $w(g_{n}, g) + h(g)$ also does not overestimate such a cost, given that $w(g_{n}, g)$ is the true cost of the edge $(g_{n}, g) \in E$. This reasoning can be applied inductively on $g_n$ (then on the neighbouring nodes of $g_n$, and so on), so $h$ must be admissible.

If a heuristic is not admissible, can it be consistent?

No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent.

Definitions

Given a graph $G=(V, E)$ representing the search space, where $V$ and $E$ are respectively the set of vertices and edges, and the function $w: E \times E \rightarrow \mathbb{R}$ that defines the weight (or cost) of each edge of $G$, an admissible heuristic $h_{\text{a}}$ is defined as

$$h_{\text{a}}(n) \leq h^*(n), \forall n \in V$$

where $h^*(n)$ is the optimal cost to reach a goal from $n$ (so $h^*(n)$ is the optimal heuristic). On the other hand, a consistent heuristic $h_{\text{c}}$ is defined as

\begin{align} h_{\text{c}}(n) &\leq w(n, s) + h_{\text{c}}(s), \forall n, s, \text{ and} \\ h_{\text{c}}(g) &= 0, \end{align} where $s$ is a successor of $n$ and $g$ is any goal node.

Theorem

A consistent heuristic is an admissible heuristic.

Proof

Let $h$ be a consistent heuristic. Given that $h$ is consistent, then $h(g) = 0$, for any goal node $g$, so it does not overestimate the cost of reaching the goal at any of the goal nodes (given that, if you already are at a goal node, the cost is $0$, and $h(g) = 0$ is not greater than $0$). Let $g_{n}$ be an arbitrary neighbour of an arbitrary goal node $g$. Given that $h$ is consistent, then $h(g_{n}) \leq w(g_{n}, g) + h(g)$. Given that $h(g)$ does not overestimate the cost to reach the goal from $g$, then $w(g_{n}, g) + h(g)$ also does not overestimate the cost of reaching the goal from $g_n$, given that $w(g_{n}, g)$ is the true cost of the edge $(g_{n}, g) \in E$ and the cost to reach the goal from $g_n$ must be at least $w(g_{n}, g)$. This reasoning can be applied inductively (or recursively) on $g_n$ (then on the neighbouring nodes of $g_n$, and so on), so $h$ must be admissible.