Consider the following AO graph : Which is the best node to expand next by AO*…

To determine the best node to expand next using the AO algorithm*, we calculate the cost of each hyperedge (OR/AND branches) originating from the root node G.
Cost Calculations

The AO* algorithm selects the path with the minimum estimated cost $f(n)$.

1. OR Branch to A:

   • Cost = Edge Weight + $h(A)$

   • $f(G \to A) = 4 + 42 = \mathbf{46}$

2. AND Branch to B and C:

   • Cost = (Edge Weight to B + $h(B)$) + (Edge Weight to C + $h(C)$)

   • $f(G \to B, C) = (3 + 22) + (2 + 24)$

   • $f(G \to B, C) = 25 + 26 = \mathbf{51}$

Conclusion

Comparing the costs:

• Path to A: 46

• Path to B and C: 51

Since the path to A has the lower cost ($46 < 51$), the best node to expand next is A.