Q4 — AO* with Edge Cost 10: a Marker That Switches Twice

AND(A,B) looks cheap, gets abandoned for C, then re-wins after B's true cost lands — S settles at 80.

The Question

AND–OR decomposition. Double circles = primitive. Every edge costs 10. Tie-breakers: node labels; for AND nodes expand the highest-cost unsolved branch first.

AND arcs: S = AND(A, B) or OR(C). B = AND(E, F). C = AND(F, G). A is an OR node over D and E. All of D, E, F, G are primitive.

#	Question	Official answer
4.1	Nodes expanded (incl. S)	`S,C,B` (also accepted `C,B`)
4.2	Value of S after each expansion	`45,50,80`
4.3	Final value of S	`80`

The Topic in 60 Seconds

AO* = expand along marked arcs + revise (OR: min child+edge; AND: sum children+edges). Markers can switch whenever a refined cost overtakes a rival option. Primitive children make a node instantly SOLVED.

Deep-dive: AO* and Goal Trees.

The Trace — three expansions

h: S=10, A=10, B=20, C=35; D=20, E=10, F=30, G=20 primitive. Edge = 10.

Expansion 1 — S.

AND(A, B): $(10+10) + (20+10) = 50$
OR(C): $35 + 10 = 45$

Mark OR(C) → S = 45 ✓

Expansion 2 — C. C: AND(F, G) $= (30+10)+(20+10) = 70$ ; F, G primitive → C = 70, SOLVED. Propagate: $S = \min(50,\ 70+10) = \mathbf{50}$ ✓ — still via AND(A, B) (50 < 80). Marker switches to AND(A, B).

Expansion 3 — B (marked path A(10), B(20); B costlier → tie-breaker 2). B: AND(E, F) $= (10+10)+(30+10) = 60$ ; E, F primitive → B = 60, SOLVED. Propagate: AND(A, B) $= (10+10) + (60+10) = 90$ ; OR(C) $= 70+10 = 80$ : $S = \min(90,\ 80) = \mathbf{80}$ ✓ C is solved → S SOLVED = 80. (A was never expanded!)

Final value of S = 80. Solution subtree: S → C → F,G.

Interactive trace:

1 / 4

h: S=10, A=10, B=20, C=35; D=20, E=10, F=30, G=20 primitive. Edge = 10. S: AND(A,B) = (10+10)+(20+10) = 50 | OR(C) = 35+10 = 45 → mark OR(C). S = 45

expanding nowlive on marked pathprimitive (born SOLVED)marked arcs

Two marker flips in three expansions

C wins at step 1 (45 < 50); after C is priced at 70, the AND(A,B) branch (50) briefly takes the marker; after B is priced at 60, that branch balloons to 90 and the marker returns to the now-solved C. If you expand A instead of B at step 3 (wrong tie-break — B is costlier), you get 4.2 wrong.

Answers, decoded

4.1 — expansions: S, C, B (the accepted C,B drops S from the count).
4.2 — S after each: 45, 50, 80.
4.3 — final: 80 via S → C → F,G.

Tricks & Tips

Answers: 4.1 S,C,B · 4.2 45,50,80 · 4.3 80