How does A* search work given there are multiple goal states?

Question

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)<f(A)$, 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.

Answer 1

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 2

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.