Answers.Body: <p>A consistent heuristic <em>must not overestimate</em> the true cost to get to the goal from a particular node - the heuristic estimate is always less than or equal to the cost to get to another node plus the estimated cost from that node to the goal (which itself cannot be an overestimate).</p>
  <p>Basically, a consistent heuristic will not spuriously discard truly good options because it overestimates their cost and treats them as bad options. An inconsistent heuristic might overestimate the cost of some path, and instead explore another, costlier path and miss the optimal solution. A consistent heuristic allows paths to turn out longer than expected (since you can explore them and then go elsewhere if needed), but it does not allow paths to turn out shorter than expected (since you may miss them entirely if you get to the goal first).</p>
  <p>With a consistent heuristic, the estimated final cost of of a partial solution (f(n) = g(n) + h(n)) is monotonically non-decreasing along the best path. The consistent heuristic can't overestimate costs, so true the cost must always be as large or larger than the estimated cost. If you move along the best path closer to the goal, the estimated final cost must not decrease - if you get closer to the goal and find your estimated final cost has decreased, it must mean that you overestimated the remaining cost somewhere along the way, which means the heuristic is not consistent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-13T15:35:29.490Z
Answers.LastActivityDate: 2022-10-13T15:35:29.490Z
Answers.UserDisplayName: Nuclear Hoagie
Answers.Body: <p>Imagine three states: <code>A</code>, <code>B</code>, and <code>G</code>, where the start state is <code>A</code> and the goal state is <code>G</code>.</p>
  <p>Suppose you have the heuristic <span class="math-container">$h(n)$</span> that maps state <span class="math-container">$n$</span> to an estimated numerical cost of going from state <code>n</code> to the goal state. So you input <span class="math-container">$n$</span> into the function and it returns an estimated cost <span class="math-container">$h(n)$</span>.</p>
  <p>Now, for this heuristic function to be deemed &quot;consistent&quot; or &quot;monotonic&quot;, it needs to meet one criterion that you may consider logical and geometrical if you will. And that is, in simplified terms:</p>
  <ul>
  <li>The <em>heuristic</em> &quot;distance&quot; from <code>A</code> to <code>G</code> &quot;directly&quot; must be shorter than or equal to the sum of: a step to a third state <code>B</code> and the <em>heuristic</em> distance from that state <code>B</code> to the goal state <code>G</code>.</li>
  </ul>
  <p>Only then, a heuristic function is consistent in the estimates it's providing. It needs to adhere to the triangle inequality.</p>
  <p>Formally, the inequality defines the relationship between <span class="math-container">$h(n)$</span>, <span class="math-container">$h(n')$</span>, and <span class="math-container">$c(n, n')$</span>, or three sides of a triangle if you draw vertices as states or nodes and label the edges as appropriate. So you end up with <span class="math-container">$h(n) \leq c(n, n') + h(n')$</span> where <span class="math-container">$c(n, n')$</span> is the cost of going from state <code>n</code> to state <code>n'</code>.</p>
  <p><a href="https://i.sstatic.net/uMVYu.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/uMVYu.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-08T20:51:26.437Z
Answers.LastActivityDate: 2023-11-08T20:52:06.890Z
Answers.LastEditDate: 2023-11-08T20:52:06.890Z
Answers.UserDisplayName: Mohamed Ali
Body: <p>Could someone give the intuition behind consistency of heuristic function in the A* algorithm?</p>
  <p>From <a href="https://en.wikipedia.org/wiki/Consistent_heuristic" rel="nofollow noreferrer">wikipedia</a>:</p>
  <blockquote>
  <p>Every node i will give an estimate that, after accounting for the cost
  to reach i + 1, is always lesser than the estimate at node i + 1.</p>
  </blockquote>
  <p>I understand what this means, but is there any intuitive meaning behind it? And how does this lead to monotonicity of the evaluation function = f(n) = g(n) + h(n)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-12T19:55:59.723Z
Comments.Text: Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
Comments.UserDisplayName: Community
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-13T15:14:36.693Z
Comments.Text: @Community modified, is it better now?
Comments.UserDisplayName: learner
Tags: <search><a-star>
Title: What does consistency of heuristic intuitively mean in the A* algorithm and why are consistent heuristics monotonic?
UserDisplayName: learner
ThreadText: # What does consistency of heuristic intuitively mean in the A* algorithm and why are consistent heuristics monotonic?
  
  (Asked by: username_0 on 2022-10-12)
  
  Could someone give the intuition behind consistency of heuristic function in the A\* algorithm?
  
  From [wikipedia](https://en.wikipedia.org/wiki/Consistent_heuristic):
  
  > Every node i will give an estimate that, after accounting for the cost
  > to reach i + 1, is always lesser than the estimate at node i + 1.
  
  I understand what this means, but is there any intuitive meaning behind it? And how does this lead to monotonicity of the evaluation function = f(n) = g(n) + h(n)?
  
  **Tags:** search, a-star
  
  > **Comments:**
  > **username_1**: Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.  
  > **username_0**: @username_1 modified, is it better now?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-10-13. Score: 0
  
  A consistent heuristic *must not overestimate* the true cost to get to the goal from a particular node - the heuristic estimate is always less than or equal to the cost to get to another node plus the estimated cost from that node to the goal (which itself cannot be an overestimate).
  
  Basically, a consistent heuristic will not spuriously discard truly good options because it overestimates their cost and treats them as bad options. An inconsistent heuristic might overestimate the cost of some path, and instead explore another, costlier path and miss the optimal solution. A consistent heuristic allows paths to turn out longer than expected (since you can explore them and then go elsewhere if needed), but it does not allow paths to turn out shorter than expected (since you may miss them entirely if you get to the goal first).
  
  With a consistent heuristic, the estimated final cost of of a partial solution (f(n) = g(n) + h(n)) is monotonically non-decreasing along the best path. The consistent heuristic can't overestimate costs, so true the cost must always be as large or larger than the estimated cost. If you move along the best path closer to the goal, the estimated final cost must not decrease - if you get closer to the goal and find your estimated final cost has decreased, it must mean that you overestimated the remaining cost somewhere along the way, which means the heuristic is not consistent.
  
  
  ---
  
  ### Answer by username_3 on 2023-11-08. Score: 0
  
  Imagine three states: `A`, `B`, and `G`, where the start state is `A` and the goal state is `G`.
  
  Suppose you have the heuristic $h(n)$ that maps state $n$ to an estimated numerical cost of going from state `n` to the goal state. So you input $n$ into the function and it returns an estimated cost $h(n)$.
  
  Now, for this heuristic function to be deemed "consistent" or "monotonic", it needs to meet one criterion that you may consider logical and geometrical if you will. And that is, in simplified terms:
  
  * The *heuristic* "distance" from `A` to `G` "directly" must be shorter than or equal to the sum of: a step to a third state `B` and the *heuristic* distance from that state `B` to the goal state `G`.
  
  Only then, a heuristic function is consistent in the estimates it's providing. It needs to adhere to the triangle inequality.
  
  Formally, the inequality defines the relationship between $h(n)$, $h(n')$, and $c(n, n')$, or three sides of a triangle if you draw vertices as states or nodes and label the edges as appropriate. So you end up with $h(n) \leq c(n, n') + h(n')$ where $c(n, n')$ is the cost of going from state `n` to state `n'`.
  
  [![enter image description here](https://i.sstatic.net/uMVYu.png)](https://i.sstatic.net/uMVYu.png)
  
  
  ---
  
  