Answers.Body: <p><strong>Question 1:</strong> First of all, you state that that the goal G2 will be found first by relying on the expansion order <code>R, B, D, G2</code>.</p>
  
  <p>This is wrong. It is extremely easy to see that this is wrong, because A* is a search algorithm that guarantees to find an optimal solution given that only admissible heuristics are used. (A heuristic is being admissible if it never over-estimates the optimal goal distance. This is the case in your example.) Since the true cost for reaching G1 is 11 and the true cost for reaching G2 is 13, clearly G1 must be found first.</p>
  
  <p>Thus, your expansion order is wrong as well. Let us first give the f-values for all nodes:
  <code>f(A)=11, f(B)=10, f(C)=11, f(D)=13</code></p>
  
  <p>Assuming that h(G1)=h(G2)=0 (i.e, the heuristic is "goal-aware"), we get <code>f(G1)=11</code> and <code>f(G2)=13</code>.</p>
  
  <p>Because A* expands search nodes by lowest f-values of the search nodes in the open list (the search nodes not yet expanded), we get the following expansion order:
  <code>R, B, A, C, G1</code></p>
  
  <p>You very-likely did a mistake that is done extremely often: after heaving expanded D, you add G2 to the open list. Because G1 is a goal node and you are already "seeing" it, you return it as a solution. But this is wrong! Goal nodes are <em>not</em> returned when being created, but when being selected for expansion! So, although the expansion of D generates G2, you are not allowed to return G2 as solution, because it has not been selected for expansion.</p>
  
  <p><strong>Question 2:</strong>
  Can G2 be found as well?</p>
  
  <p>As <em>NietzscheanAI</em> pointed out, you can simple continue search. That is, after heaving expanded  <code>R, B, A, C, G1</code>, A* will expand <code>D, G2</code>.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-01-18T14:52:53.387Z
Answers.LastActivityDate: 2017-01-18T14:52:53.387Z
Answers.UserDisplayName: Prof.Chaos
Answers.Body: <p>Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-16T21:16:23.997Z
Answers.LastActivityDate: 2016-11-16T21:16:23.997Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture.</p>
  
  <p><a href="https://i.sstatic.net/zX6wZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/zX6wZ.png" alt="enter image description here"></a></p>
  
  <p>These are the heuristic estimates:</p>
  
  <pre><code>h(B)=9
  h(D)=10
  h(A)=2
  h(C)=1
  </code></pre>
  
  <p>If we use the A* algorithm, the node <span class="math-container">$B$</span> will be expanded first because <span class="math-container">$f(B)=1+9=10$</span>, while node <span class="math-container">$A$</span> having <span class="math-container">$f(A)=9+2=11$</span> and <span class="math-container">$f(B)&lt;f(A)$</span>, right?</p>
  
  <p>After that, the search tree will go on in the order <code>R -&gt; B -&gt; D -&gt; G2</code>. Will the search go on to also find the goal state G1?</p>
  
  <p>Kindly let me know the order of the search if I am wrong.</p>
  
Tags: <search><heuristics><a-star>
Title: How does A* search work given there are multiple goal states?
UserDisplayName: hellojoshhhy
ThreadText: # How does A* search work given there are multiple goal states?
  
  (Asked by: username_0 on 2016-11-16)
  
  When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture.
  
  These are the heuristic estimates:
  h(B)=9
  h(D)=10
  h(A)=2
  h(C)=1
  
  If we use the A* algorithm, the node $B$ will be expanded first because $f(B)=1+9=10$, while node $A$ having $f(A)=9+2=11$ and $f(B), right?
  After that, the search tree will go on in the order R -> B -> D -> G2. Will the search go on to also find the goal state G1?
  Kindly let me know the order of the search if I am wrong.
  
  **Tags:** search, heuristics, a-star
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2017-01-18. Score: 2 | Accepted answer
  
  **Question 1:** First of all, you state that that the goal G2 will be found first by relying on the expansion order `R, B, D, G2`.
  
  This is wrong. It is extremely easy to see that this is wrong, because A\* is a search algorithm that guarantees to find an optimal solution given that only admissible heuristics are used. (A heuristic is being admissible if it never over-estimates the optimal goal distance. This is the case in your example.) Since the true cost for reaching G1 is 11 and the true cost for reaching G2 is 13, clearly G1 must be found first.
  
  Thus, your expansion order is wrong as well. Let us first give the f-values for all nodes:
  `f(A)=11, f(B)=10, f(C)=11, f(D)=13`
  
  Assuming that h(G1)=h(G2)=0 (i.e, the heuristic is "goal-aware"), we get `f(G1)=11` and `f(G2)=13`.
  
  Because A\* expands search nodes by lowest f-values of the search nodes in the open list (the search nodes not yet expanded), we get the following expansion order:
  `R, B, A, C, G1`
  
  You very-likely did a mistake that is done extremely often: after heaving expanded D, you add G2 to the open list. Because G1 is a goal node and you are already "seeing" it, you return it as a solution. But this is wrong! Goal nodes are *not* returned when being created, but when being selected for expansion! So, although the expansion of D generates G2, you are not allowed to return G2 as solution, because it has not been selected for expansion.
  
  **Question 2:**
  Can G2 be found as well?
  
  As *NietzscheanAI* pointed out, you can simple continue search. That is, after heaving expanded `R, B, A, C, G1`, A\* will expand `D, G2`.
  
  
  ---
  
  ### Answer by username_2 on 2016-11-16. Score: 5
  
  Yes. If you leave A\* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.
  
  
  ---
  
  