Q4 — AO* on the AND–OR Decomposition

Four expansions down the A-branch — and the E refinement that flips A onto its primitive I escape hatch.

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

#	Question	Official answer
4.1	Nodes expanded	`S,A,D,E` (also `A,D,E`)
4.2	Value of S after each expansion	`10,9,10,12` (also `9,10,12`)
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 when refined costs overtake rivals. Primitive children make a node instantly SOLVED.

Deep-dive: AO* and Goal Trees.

The Trace

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

Expansion 1 — S.

AND(B, C): $(8+2)+(4+2) = 16$
OR(A): $8+2 = 10$

Mark OR(A) → S = 10 ✓

Expansion 2 — A.

AND(D, E): $(2+2)+(1+2) = 7$
OR(I): $8+2 = 10$

Mark AND(D, E) → A = 7 → $S = \min(16, 9) = \mathbf{9}$ ✓

Expansion 3 — D (marked path S→A→D,E; costliest branch D(2) > E(1)). D is primitive → instantly SOLVED. Nothing to revise: AND(D, E) stays $(2+2)+(1+2) = 7$ , A stays 7 and S stays 9 through this step — the paper still counts the selection as an expansion.

Expansion 4 — E. E: AND(H, I) $= (1+2)+(8+2) = 13$ ; H, I primitive → E = 13, SOLVED. Propagate: AND(D, E) $= (2+2)+(13+2) = 19$ — now worse than OR(I) $= 10$ ! Marker flips: $A = \min(19, 10) = \mathbf{10} \text{ via primitive } I \Rightarrow \text{A SOLVED}$ $S = \min(16,\ 10+2) = \mathbf{12}$ ✓ — S SOLVED

Final value of S = 12. Solution subtree: S → A → I.

Interactive trace:

1 / 5

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

expanding nowlive on marked pathprimitive (born SOLVED)marked arcs

Answers, decoded

4.1 — expansions: S, A, D, E (D is selected on the marked path and immediately SOLVED as primitive; the alternate A,D,E drops S).
4.2 — S runs 10 → 9 → 9 (unchanged through D) → 12: 10 when OR(A) is marked at S; 9 once A prices at 7; still 9 after the no-op D step; 12 when E's true cost (13) flips A onto I ( $A = 10 \Rightarrow S = A + 2 = 12$ ). The official key writes the story as 10,9,10,12 — its third entry records A flipping to 10 during the final revision — while the alternate key 9,10,12 reports from the A-expansion onward. Both describe the same three distinct snapshots.
4.3 — B (inadmissible): $h(F) = 8 > h^*(F) = 5$ ( $F \to J$ ) and $h(G) = 10 > h^*(G) = 8$ — overestimates ⇒ inadmissible.

Tricks & Tips

Answers: 4.1 S,A,D,E · 4.2 10,9,10,12 · 4.3 B