Q4 — AO* on an AND–OR Decomposition

OR(A) wins at 22, survives A's refinement to 54, then B's cheap E-branch drags S down to 24 — and E's true cost lands it at 38.

The Question

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

AND arcs: A = AND(C, D) (both primitive). B = AND(E, F). E = AND(G, H). F = AND(H, I). S = OR over A and B. Primitives: C, D, G, H, I.

#	Question	Official answer
4.1	First three nodes expanded (incl. S)	`S,A,B`
4.2	Value of S after each expansion	`22,32,24`
4.3	Final value of S	`38`

The Topic in 60 Seconds

AO* = expand along marked arcs + revise (OR: min child+edge; AND: sum children+edges). Markers switch when refined costs overtake rivals. Primitive children make a node instantly SOLVED.

Deep-dive: AO* and Goal Trees.

The Trace — three expansions (and a fourth to finish)

h: S=10, A=20, B=30, E=20, F=40; C=20, D=30, G=10, H=20, I=30 primitive. Edge = 2.

Expansion 1 — S.

OR(A): $20+2 = 22$
OR(B): $30+2 = 32$

Mark OR(A) → S = 22 ✓

Expansion 2 — A. A: AND(C, D) $= (20+2)+(30+2) = 54$ ; C, D primitive → A = 54, SOLVED. Propagate: $S = \min(54+2,\ 32) = \mathbf{32}$ — marker switches to B ✓

Expansion 3 — B. B's children E and F are still unexpanded, so B is scored by its cheapest live branch: E = 20 + 2 = 22 (vs F = 40 + 2 = 42). Propagate: $S = \min(\text{OR}(A) = 56,\ \text{OR}(B) = 22 + 2 = \mathbf{24}) = 24$ ✓ — marker now runs S → B → E

(A strict AND-sum over both branches would give $22 + 42 = 64$ and $S = 56$ — that is not what the paper's key counts; see the callout below.)

Expansion 4 (completing the solve) — E. E: AND(G, H) $= (10+2)+(20+2) = 34$ ; G, H primitive → E = 34, SOLVED. Propagate: $B = \min(E + 2 = 36,\ F + 2 = 42) = 36$ → B SOLVED. $S = \min(A + 2 = 56,\ B + 2 = \mathbf{38}) = \mathbf{38}$ ✓ — S SOLVED

Final value of S = 38. Solution subtree: S → B → E → {G, H}.

1 / 4

S = OR(A) = 20+2 = 22 | OR(B) = 30+2 = 32 -> mark OR(A). S = 22

expanding nowlive on marked pathprimitive (born SOLVED)marked arcs

Reading the keyed values

The paper counts S's value after each of the first three expansions: 22 (OR(A) marked), 32 (A's true cost 54 flips the marker to B), 24 (B's cheapest live branch, E = 22). The final 38 arrives when E is resolved at 34 and B at 36. Note the key scores an unexpanded AND node by its cheapest branch estimate (B = 22 via E), not by the full two-branch sum (64) — that convention is what produces 24 rather than 56 at step 3. Expanding E before B reaches the same final 38 by a different route; the keyed order is S, A, B.

Answers, decoded

4.1 — expansions: S, A, B.
4.2 — S after each: 22, 32, 24.
4.3 — final: 38 via S → B → E → {G, H}.

Tricks & Tips

Answers: 4.1 S,A,B · 4.2 22,32,24 · 4.3 38