Answers.Body: <p>You did not compute <span class="math-container">$g(n)$</span> correctly.</p>
  <p>A* expands according to the evaluation function <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$g(n)$</span> is the cost of the path from the start node to <span class="math-container">$n$</span>. Initially, you add <span class="math-container">$A$</span> to the frontier <span class="math-container">$F = \{A \}$</span>. Then you pop from the frontier according to <span class="math-container">$f(n)$</span>, so you pop <span class="math-container">$A$</span>, and add its children to the frontier, which are <span class="math-container">$B$</span>, <span class="math-container">$C$</span> and <span class="math-container">$D$</span>, i.e. <span class="math-container">$F = \{B, C, D \}$</span>. Now, you have</p>
  <ol>
  <li><span class="math-container">$f(B) = g(B) + 0 = 1$</span></li>
  <li><span class="math-container">$f(C) = g(C) + 0 = 2$</span></li>
  <li><span class="math-container">$f(D) = g(D) + 0 = 3$</span></li>
  </ol>
  <p>So, you pop <span class="math-container">$B$</span> from the frontier and explore it, i.e. add <span class="math-container">$E$</span> to the frontier, so <span class="math-container">$F = \{C, D, E \}$</span>. Now, you have</p>
  <ol>
  <li><span class="math-container">$f(C) = g(C) + 0 = 2$</span></li>
  <li><span class="math-container">$f(D) = g(D) + 0 = 3$</span></li>
  <li><span class="math-container">$f(E) = g(E) + 0 = 1 + 3 = 4$</span></li>
  </ol>
  <p>So, you pop <span class="math-container">$C$</span>. And so on.</p>
  <p>(I didn't want to give more answers, but, hey, I like A*)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-04T23:18:49.010Z
Answers.LastActivityDate: 2022-02-04T23:18:49.010Z
Answers.UserDisplayName: nbro
Body: <p>In &quot;AI: A Modern Approach&quot;, 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. They want to show that all nodes on the optimal path are expanded. Towards a contradiction, they consider a node n on the optimal path that is not expanded, and say that its evaluation f(n) must be strictly greater than the optimal cost C*, for &quot;otherwise, n would have been expanded&quot;.</p>
  <p>In other words, they <strong>claim</strong> that <em>a node n with f(n) less or equal than C* will be expanded.</em> That claim is obviously not true in general? Take the heuristic that is identically zero; it is trivially admissible. Now consider a model with initial state A, which can transition to states B, C and D with costs 1, 2 and 3, respectively. Then B, C and D all transition to the goal state E, all with cost 3. The A* algorithm will simply expand B, then E. So it certainly finds an optimal path. Note that states C and D have no chance to be expanded. Nevertheless, they have evaluations 2 and 3, which are both less than 4, the optimal cost. So the claim does not hold.</p>
  <p>I would like confirmation of my analysis - is the proof given in the book incorrect?</p>
  <p>Just to be clear, I am not saying that A* is not always cost-optimal for any admissible heuristic, although I would love to see a reference (I've found research papers but they are about other notions of optimality, such as number of nodes expanded.) I am just saying that the proof given in the book is wrong.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-04T21:57:11.087Z
Comments.Text: Could you be clearer about what your question is please. It appears you want a critique of whether your counter-example is valid, but you don't actually say.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-05T09:53:41.463Z
Comments.Text: Indeed I just want confirmation that the proof given in the book is incomplete. In the meantime I understood that the cost-optimality (confusingly also called admissibility) of A* under an admissible heuristic is quite easy to see, and outlined on this forum by [John Doucette](https://ai.stackexchange.com/questions/6026/why-is-a-optimal-if-the-heuristic-function-is-admissible)
Comments.UserDisplayName: vdbuss
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-05T12:32:11.583Z
Comments.Text: I have folded that into your question. You can treat it as a suggestion of how to phrase "It (doesn't) work this way - am I right?" questions on the site. Feel free to roll back if you think it changes the question too much. I am keen though that you use question phrasing and not a general "looking for comments" ending (whcih would be more appropriate on a forum)
Comments.UserDisplayName: Neil Slater
Tags: <search><proofs><a-star><norvig-russell><optimality>
Title: Is there an error in A* optimality proof Russel-Norvig 4th edition?
UserDisplayName: vdbuss
ThreadText: # Is there an error in A* optimality proof Russel-Norvig 4th edition?
  
  (Asked by: username_0 on 2022-02-04)
  
  In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A\* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. They want to show that all nodes on the optimal path are expanded. Towards a contradiction, they consider a node n on the optimal path that is not expanded, and say that its evaluation f(n) must be strictly greater than the optimal cost C\*, for "otherwise, n would have been expanded".
  
  In other words, they **claim** that *a node n with f(n) less or equal than C\* will be expanded.* That claim is obviously not true in general? Take the heuristic that is identically zero; it is trivially admissible. Now consider a model with initial state A, which can transition to states B, C and D with costs 1, 2 and 3, respectively. Then B, C and D all transition to the goal state E, all with cost 3. The A\* algorithm will simply expand B, then E. So it certainly finds an optimal path. Note that states C and D have no chance to be expanded. Nevertheless, they have evaluations 2 and 3, which are both less than 4, the optimal cost. So the claim does not hold.
  
  I would like confirmation of my analysis - is the proof given in the book incorrect?
  
  Just to be clear, I am not saying that A\* is not always cost-optimal for any admissible heuristic, although I would love to see a reference (I've found research papers but they are about other notions of optimality, such as number of nodes expanded.) I am just saying that the proof given in the book is wrong.
  
  **Tags:** search, proofs, a-star, norvig-russell, optimality
  
  > **Comments:**
  > **username_1**: Could you be clearer about what your question is please. It appears you want a critique of whether your counter-example is valid, but you don't actually say.  
  > **username_0**: Indeed I just want confirmation that the proof given in the book is incomplete. In the meantime I understood that the cost-optimality (confusingly also called admissibility) of A* under an admissible heuristic is quite easy to see, and outlined on this forum by [John Doucette](https://ai.stackexchange.com/questions/6026/why-is-a-optimal-if-the-heuristic-function-is-admissible)  
  > **username_1**: I have folded that into your question. You can treat it as a suggestion of how to phrase "It (doesn't) work this way - am I right?" questions on the site. Feel free to roll back if you think it changes the question too much. I am keen though that you use question phrasing and not a general "looking for comments" ending (whcih would be more appropriate on a forum)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-02-04. Score: 2
  
  You did not compute $g(n)$ correctly.
  
  A\* expands according to the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the start node to $n$. Initially, you add $A$ to the frontier $F = \{A \}$. Then you pop from the frontier according to $f(n)$, so you pop $A$, and add its children to the frontier, which are $B$, $C$ and $D$, i.e. $F = \{B, C, D \}$. Now, you have
  
  1. $f(B) = g(B) + 0 = 1$
  2. $f(C) = g(C) + 0 = 2$
  3. $f(D) = g(D) + 0 = 3$
  
  So, you pop $B$ from the frontier and explore it, i.e. add $E$ to the frontier, so $F = \{C, D, E \}$. Now, you have
  
  1. $f(C) = g(C) + 0 = 2$
  2. $f(D) = g(D) + 0 = 3$
  3. $f(E) = g(E) + 0 = 1 + 3 = 4$
  
  So, you pop $C$. And so on.
  
  (I didn't want to give more answers, but, hey, I like A\*)
  
  
  ---
  
  