Answers.Body: <p>For a heuristic to be admissible, it must never overestimate the distance from a state to the nearest goal state.</p>
  
  <p>For a heuristic to be consistent, the heuristic's value must be less than or equal to the cost of moving from that state to the state nearest the goal that can be reached from it, plus the heurstic's estimate for that state.</p>
  
  <p>What this means is that, as you move along the sequence of nodes from start to goal that the heuristic recommends, a consistent heuristic should monotonically decrease in value. A consistent heuristic is thus also always admissible.</p>
  
  <p>Notice that this means that if a heuristic is <em>not admissible</em> (like yours), it is also <em>not consistent</em> (by the contrapositive). </p>
  
  <p>Therefore, if you already know your heuristic is not admissible, you should not be surprised that it is not consistent.</p>
  
  <p>It seems most likely that you may have confused the definition of consistent for monotone. A consistent heuristic is <em>both</em> monotone and admissible.</p>
  
  <p>As Neil Says, if you want to know why your specific heuristic is inadmissible, you should post another question about it, or modify this one.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-09T17:16:19.317Z
Answers.LastActivityDate: 2019-11-09T17:16:19.317Z
Answers.UserDisplayName: John Doucette
Answers.Body: <blockquote>
    <p>If a heuristic is not admissible, can it be consistent?</p>
  </blockquote>
  
  <p>No. Consistency implies admissibility. In other words, if a heuristic is <a href="https://en.wikipedia.org/wiki/Consistent_heuristic" rel="nofollow noreferrer">consistent</a>, it is also <a href="https://en.wikipedia.org/wiki/Admissible_heuristic" rel="nofollow noreferrer">admissible</a>. However, admissibility does <strong>not</strong> imply consistency. In other words, an admissible heuristic is not necessarily consistent.</p>
  
  <h2>Definitions</h2>
  
  <p>Given a graph <span class="math-container">$G=(V, E)$</span> representing the search space, where <span class="math-container">$V$</span> and <span class="math-container">$E$</span> are respectively the set of vertices and edges, and the function <span class="math-container">$w: E \times E \rightarrow \mathbb{R}$</span> that defines the weight (or cost) of each edge of <span class="math-container">$G$</span>, an admissible heuristic <span class="math-container">$h_{\text{a}}$</span> is defined as </p>
  
  <p><span class="math-container">$$h_{\text{a}}(n) \leq h^*(n), \forall n \in V$$</span> </p>
  
  <p>where <span class="math-container">$h^*(n)$</span> is the optimal cost to reach a goal from <span class="math-container">$n$</span> (so <span class="math-container">$h^*(n)$</span> is the optimal heuristic). </p>
  
  <p>On the other hand, a consistent heuristic <span class="math-container">$h_{\text{c}}$</span> is defined as </p>
  
  <p><span class="math-container">\begin{align}
  h_{\text{c}}(n) &amp;\leq w(n, s) + h_{\text{c}}(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\
  h_{\text{c}}(g) &amp;= 0, \forall g \in \mathcal{G},
  \end{align}</span>
  where <span class="math-container">$s$</span> is a successor of <span class="math-container">$n$</span>, <span class="math-container">$g$</span> is any goal node and <span class="math-container">$\mathcal{G}$</span> is the set of goal nodes of the graph <span class="math-container">$G$</span>.</p>
  
  <h2>Theorem</h2>
  
  <p>A consistent heuristic is an admissible heuristic.</p>
  
  <h3>Proof</h3>
  
  <p>Let <span class="math-container">$h$</span> be a consistent heuristic. Given that <span class="math-container">$h$</span> is consistent, then <span class="math-container">$h(g) = 0$</span>, for any goal node <span class="math-container">$g$</span>, 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 <span class="math-container">$0$</span>, and <span class="math-container">$h(g) = 0$</span> is not greater than <span class="math-container">$0$</span>). Let <span class="math-container">$g_{n}$</span> be an arbitrary neighbour of an arbitrary goal node <span class="math-container">$g$</span>. Given that <span class="math-container">$h$</span> is consistent, then <span class="math-container">$h(g_{n}) \leq w(g_{n}, g) + h(g)$</span>. Given that <span class="math-container">$h(g)$</span> does not overestimate the cost to reach the goal from <span class="math-container">$g$</span>, then <span class="math-container">$w(g_{n}, g) + h(g)$</span> also does not overestimate the cost of reaching the goal from <span class="math-container">$g_n$</span>, given that <span class="math-container">$w(g_{n}, g)$</span> is the true cost of the edge <span class="math-container">$(g_{n}, g) \in E$</span> and the cost to reach the goal from <span class="math-container">$g_n$</span> must be at least <span class="math-container">$w(g_{n}, g)$</span>. This reasoning can be applied inductively (or recursively) on <span class="math-container">$g_n$</span> (then on the neighbouring nodes of <span class="math-container">$g_n$</span>, and so on), so <span class="math-container">$h$</span> must be admissible.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-10T16:10:13.787Z
Answers.Text: A proof by induction usually requires you to prove 2 cases: 1) a _base case_ (prove that a property holds for a base case of the statement) and 2) _induction step_ (assume that a property holds for $n$ and prove it also holds for $n+1$ or $n-1$). This proof by induction does not have a proper _induction step_, but I hope it is intuitive enough. This is more like a recursive proof.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-24T23:26:01.500Z
Answers.Text: $h$ being consistent doesn't require that $h(g) = 0$. If $h(g) = 10$ you could still have a consistent heuristic everywhere that was not admissible. But, typically we *assume* that $h(g) = 0$.
Answers.UserDisplayName: Nathan S.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-24T23:34:48.690Z
Answers.Text: @NathanS. I defined the consistent heuristic in a certain way (but I am not saying it can't be defined differently). The rest should follow unless there's a mistake in my reasoning (which I don't exclude).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-24T23:50:00.390Z
Answers.Text: Yes; I'm just being a bit pedantic. I would just change your proof to say that $h(g) = 0$ is by your definition of consistent. The literature on this isn't always *consistent*. : )
Answers.UserDisplayName: Nathan S.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-07T12:01:32.580Z
Answers.Text: @NathanS. Just to clarify. If you don't define $h(g) = 0$, then consistency does not necessarily imply admissibility, i.e. the set of consistent heuristics would not be a subset of the set of admissible heuristics, unless $h(g) \leq h^*(g)$. Do you agree? By the way, could you please provide an example of a paper or book where a consistent heuristic is not defined such that $h(g) = 0$, and so what are the implications in terms of the relationship between consistency and admissibility? It's been a while since I had to deal with these topics, but my knowledge is a bit rusty now.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-10T18:46:54.100Z
Answers.Text: Yes, when $h(g)=0$ then consistency implies admissibility. Pearl's 1984 textbook equates consistency and the triangle inequality, and separately assumes that **all** heuristics have $h(g)=0$. Martelli, 1977 similarly defines consistency only by the triangle inequality, as do most other papers that define consistency. Wikipedia is an outlier, and thus doesn't necessarily represent published literature.
Answers.UserDisplayName: Nathan S.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-10T16:06:38.123Z
Answers.LastActivityDate: 2019-11-10T16:24:57.893Z
Answers.LastEditDate: 2019-11-10T16:24:57.893Z
Answers.UserDisplayName: nbro
Body: <p>I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in mind the values, but the solution says it's not consistent either. Can someone tell why? </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-09T13:00:50.500Z
Comments.Text: A consistent heuristic is always admissible, but an admissible heuristic does not have to be consistent. Someone may be able to give some examples for you in an answer. However, if you want to know why *your* heuristic is neither, you need to share details of the problem and your attempted solution
Comments.UserDisplayName: Neil Slater
Tags: <search><proofs><admissible-heuristic><consistent-heuristic><heuristic-functions>
Title: If an heuristic is not admissible, can it be consistent?
UserDisplayName: Awa
ThreadText: # If an heuristic is not admissible, can it be consistent?
  
  (Asked by: username_0 on 2019-11-09)
  
  I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in mind the values, but the solution says it's not consistent either. Can someone tell why?
  
  **Tags:** search, proofs, admissible-heuristic, consistent-heuristic, heuristic-functions
  
  > **Comments:**
  > **username_1**: A consistent heuristic is always admissible, but an admissible heuristic does not have to be consistent. Someone may be able to give some examples for you in an answer. However, if you want to know why *your* heuristic is neither, you need to share details of the problem and your attempted solution  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-11-09. Score: 2
  
  For a heuristic to be admissible, it must never overestimate the distance from a state to the nearest goal state.
  
  For a heuristic to be consistent, the heuristic's value must be less than or equal to the cost of moving from that state to the state nearest the goal that can be reached from it, plus the heurstic's estimate for that state.
  
  What this means is that, as you move along the sequence of nodes from start to goal that the heuristic recommends, a consistent heuristic should monotonically decrease in value. A consistent heuristic is thus also always admissible.
  
  Notice that this means that if a heuristic is *not admissible* (like yours), it is also *not consistent* (by the contrapositive).
  
  Therefore, if you already know your heuristic is not admissible, you should not be surprised that it is not consistent.
  
  It seems most likely that you may have confused the definition of consistent for monotone. A consistent heuristic is *both* monotone and admissible.
  
  As username_1 Says, if you want to know why your specific heuristic is inadmissible, you should post another question about it, or modify this one.
  
  
  ---
  
  ### Answer by username_3 on 2019-11-10. Score: 2
  
  > If a heuristic is not admissible, can it be consistent?
  
  No. Consistency implies admissibility. In other words, if a heuristic is [consistent](https://en.wikipedia.org/wiki/Consistent_heuristic), it is also [admissible](https://en.wikipedia.org/wiki/Admissible_heuristic). 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.
  
  > **Comments:**
  > **username_3**: A proof by induction usually requires you to prove 2 cases: 1) a _base case_ (prove that a property holds for a base case of the statement) and 2) _induction step_ (assume that a property holds for $n$ and prove it also holds for $n+1$ or $n-1$). This proof by induction does not have a proper _induction step_, but I hope it is intuitive enough. This is more like a recursive proof.  
  > **username_4**: $h$ being consistent doesn't require that $h(g) = 0$. If $h(g) = 10$ you could still have a consistent heuristic everywhere that was not admissible. But, typically we *assume* that $h(g) = 0$.  
  > **username_3**: @NathanS. I defined the consistent heuristic in a certain way (but I am not saying it can't be defined differently). The rest should follow unless there's a mistake in my reasoning (which I don't exclude).  
  > **username_4**: Yes; I'm just being a bit pedantic. I would just change your proof to say that $h(g) = 0$ is by your definition of consistent. The literature on this isn't always *consistent*. : )  
  > **username_3**: @NathanS. Just to clarify. If you don't define $h(g) = 0$, then consistency does not necessarily imply admissibility, i.e. the set of consistent heuristics would not be a subset of the set of admissible heuristics, unless $h(g) \leq h^*(g)$. Do you agree? By the way, could you please provide an example of a paper or book where a consistent heuristic is not defined such that $h(g) = 0$, and so what are the implications in terms of the relationship between consistency and admissibility? It's been a while since I had to deal with these topics, but my knowledge is a bit rusty now.  
  > **username_4**: Yes, when $h(g)=0$ then consistency implies admissibility. Pearl's 1984 textbook equates consistency and the triangle inequality, and separately assumes that **all** heuristics have $h(g)=0$. Martelli, 1977 similarly defines consistency only by the triangle inequality, as do most other papers that define consistency. Wikipedia is an outlier, and thus doesn't necessarily represent published literature.  
  
  ---
  
  