Q4 — AO* with a Double Marker Switch

AND(B,C) wins, survives C's refinement, then G's true cost of 18 flips B onto primitive K — S lands at 28.

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: S = AND(B, C) or OR(A). A = AND(E, I) or OR(D). E = AND(H, I). B = AND(F, G) or OR(K). G = AND(J, K). C = AND(K, L). Primitives: H, I, J, K, L.

#	Question	Official answer
4.1	Nodes expanded	`S,C,B,G` (also `C,B,G`)
4.2	Value of S after each expansion	`22,24,26,28` (also `24,26,28`)
4.3	Conclusion about the heuristic	B — inadmissible

The Topic in 60 Seconds

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

Deep-dive: AO* and Goal Trees.

The Trace — four expansions

h: S=10, A=30, B=6, C=12, E=4, F=1, G=3; H=2, I=4, J=6, K=8, L=2 primitive. Edge = 2.

Expansion 1 — S.

AND(B, C): $(6+2)+(12+2) = 22$
OR(A): $30+2 = 32$

Mark AND(B, C) → S = 22 ✓

Expansion 2 — C (costlier AND branch: 12 > 6). C: AND(K, L) $= (8+2)+(2+2) = 14$ ; K, L primitive → C = 14, SOLVED. Propagate: $S = (6+2)+(14+2) = \mathbf{24}$ ✓

Expansion 3 — B. B: AND(F, G) $= (1+2)+(3+2) = 8$ vs OR(K) $= 8+2 = 10$ → mark AND(F, G), B = 8. Propagate: $S = (8+2)+(14+2) = \mathbf{26}$ ✓

Expansion 4 — G (marked path S→B→F,G; G(3) costlier than F(1)). G: AND(J, K) $= (6+2)+(8+2) = 18$ ; J, K primitive → G = 18, SOLVED. Propagate: AND(F, G) $= (1+2)+(18+2) = 23$ — worse than OR(K) $= 10$ ! Marker flips: $B = \min(23, 10) = \mathbf{10} \text{ via primitive } K \Rightarrow \text{B SOLVED}$ $S = \min\big(\underbrace{(10+2)+(14+2)}_{\text{AND(B,C)} = 28},\ 32\big) = \mathbf{28}$ B and C both solved → S SOLVED = 28 ✓✓

Final value of S = 28. Solution subtree: S → B→K and C→K,L.

Interactive trace:

1 / 5

h: S=10, A=30, B=6, C=12, E=4, F=1, G=3; H=2, I=4, J=6, K=8, L=2 primitive. Edge = 2. S: AND(B,C) = (6+2)+(12+2) = 22 | OR(A) = 30+2 = 32 → mark AND(B,C). S = 22

expanding nowlive on marked pathprimitive (born SOLVED)marked arcs

Answers, decoded

4.1 — expansions: S, C, B, G (alternate C,B,G drops S).
4.2 — S after each: 22, 24, 26, 28 (alternate 24,26,28 from C onwards).
4.3 — B (inadmissible): $h(A) = 30 > h^*(A) = 18$ . A's only solvable option is AND(E, I), and E's true cost is $E = \text{AND}(H,I) = (2+2)+(4+2) = 10$ , so $A = (10+2)+(4+2) = 18$ — a massive overestimate.

Tricks & Tips

Answers: 4.1 S,C,B,G · 4.2 22,24,26,28 · 4.3 B