AO*: AND-OR Graphs, Expansion Order, S Values

1. AND-OR graphs in one table

Each node carries a heuristic \(h\). Unexpanded nodes use \(h\); expanded nodes recompute from children; primitives use actual cost. Edge cost is stated per question (2 units in all four graphs below, always recheck).

2. The AO* loop

1. Expand S first. Recompute its value from its options and mark the cheapest option.
2. Next expansion: walk down the marked option to the first unsolved node and expand it. At an AND group with two unsolved branches, take the highest cost branch first (tie-breaker 2).
3. Recompute the expanded node (AND sums, OR mins), then backpropagate up to S. Re-mark the cheapest option at every ancestor.
4. Ties in cost anywhere: smaller node label first (tie-breaker 1). Stop when S is solved through solved children.

3. What the three questions want, plus the fourth

1. First three expanded: always starts with S, then two nodes found by walking the marked path. Primitives are never expanded.
2. S after 1st, 2nd, 3rd: write down S right after each backpropagation. Three numbers, in order.
3. Final S: keep expanding down the marked path until every node on it is solved. The last S is the answer.
4. Admissible or not (asked in some papers): \(h\) is admissible iff \(h(n)\) never exceeds the true cheapest cost of solving \(n\), for every node. Solve the graph first, then check each \(h\) against its true cost. One violation means inadmissible.

Official keys seen on four papers: admissible twice, inadmissible twice; the sometimes admissible option was never the key. On all four graphs below, every \(h\) sits at or below its true cost (checked by script), so each of them is admissible: 2024T2 FN (S 10 against 56, C 10 against 56, B 10 against 44), 2024T1 FN (B 30 against 36 is the tightest), 2024T3 FN (E 12 against exactly 12 is the tightest), 2024T3 AN (B 8 against 16, E 10 against 12).

4. Worked example: 2024T2 FN, Q65 to Q67

4a. The graph as a table (solve from this, then check the animation)

Cover the animation. Expand three nodes down the marked path and track S after each. Official answers: S,C,A; 12,28,36; 56.

4b. Animation: values update, best path in thick lines

4c. The three questions

4d. Solution

1. Expand S. Options: AND(A,B) = (2+14)+(2+10) = 28; C = 2+10 = 12. S = 12 via C.
2. Expand C (on the marked path). C = AND(F,G) = (2+20)+(2+32) = 56. Backprop: S = min(28, 56) = 28 via AND(A,B).
3. Expand A. Marked AND branches cost A: 2+14 = 16 vs B: 2+10 = 12. Highest first: A. A = OR = min(2+40, 2+20) = 22 via E. AND(A,B) = (2+22)+(2+10) = 36. S = min(36, 56) = 36. First three: S,C,A. S values: 12,28,36.
4. Finish. A solved via E; expand B: B = AND(E,F) = (2+20)+(2+20) = 44. AND(A,B) = (2+22)+(2+44) = 70. S = min(70, 56) = 56 via C, all solved. Final: 56.

5. Practice: three more graphs

Expand three nodes down the marked path, track S after each, then run to termination with a pen before opening the answer.

Graph P1: 2024T1 FN, Q108 to Q110 (edge cost 2)

Q: First three expanded? S after 1st, 2nd, 3rd? Final S?

Graph P2: 2024T3 FN, Q74 to Q76 (edge cost 2)

Q: First three expanded? S after 1st, 2nd, 3rd? Final S?

Graph P3: 2024T3 AN, Q74 to Q76 (edge cost 2)

Q: First three expanded? S after 1st, 2nd, 3rd? Final S?

6. Exam checklist (write this on the rough sheet)

1. Read edge cost, both tie-breakers, and mark AND arcs before computing anything.
2. Expand S first. Recompute with AND sums and OR mins, mark the cheapest option.
3. Each next expansion: walk the marked option down; at an AND split take the highest cost unsolved branch; ties by label.
4. Write S down after every backpropagation. That list is two of the three answers.
5. Stop when the marked option runs only through solved nodes. That S is final.