Q5 — AO* on an AND–OR Decomposition

OR(C) wins at 16, the marker flips to AND(A,B) at 22, B resolves at 24 — and E's primitive escape lands S at 30.

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(A, B) or OR(C); A = AND(D, E); B = AND(E, F); C = AND(F, G). Primitives: H, I, J. (E and F are shared children: E under A and B; F under B and C.)

#	Question	Official answer
5.1	First three nodes expanded (incl. S)	`S,C,B` (also `C,B,A`)
5.2	Value of S after each expansion	`16,22,24` (also `22,24,26`)
5.3	Final value of S	`30`

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.

Step 0 — Cost table

Node	$h$	Node	$h$
S	10	F	20
A	8	G	10
B	10	H	20 ◉
C	14	I	10 ◉
D	16	J	10 ◉
E	12

Edge cost = 2 everywhere.

Expansion 1 and 2 — where the key and the mechanics agree

Expansion 1 (S). Price both options: AND(A,B) $= (8+2)+(10+2) = 22$ ; OR(C) $= 14+2 = 16$ . Mark OR(C) → S = 16 ✓
Expansion 2 (C) (marked path). C prices its conjunction: $C = (20+2)+(10+2) = 34$ , so OR(C) rises to $34+2 = 36 > 22$ — the marker flips onto AND(A,B) → S = 22 ✓

Both keyed values reproduce exactly. From here the paths split:

Strict AO* continues 36 → 40 → 42, not 24 → 30

Textbook revision prices every AND as the sum of all conjuncts and re-marks after each expansion:

Step	Expand	Revision	Marker / S
3	B (costlier marked branch: 10 > 8)	B = $(12+2)+(20+2) = 36$ → AND(A,B) $= (8+2)+(36+2) = 48$	48 > 36 → flip back to OR(C), S = 36
4	F (costliest live leaf under marked C)	F = $(10+2)+(10+2) = 24$ SOLVED → C $= 26+12 = 38$ → OR(C) $= 40$ ; shared child lifts B too: AND $= 10+42 = 52$	S = 40
5	G	G $= 10+2 = 12$ SOLVED → C $= 26+14 = 40$ SOLVED → OR(C) $= 42$	marked branch complete → S SOLVED = 42

The official key instead reads B through its cheapest sub-branch ( $B \approx E+2 = 14$ , giving the keyed 24) and settles at 30 — a value that falls out of neither the strict mechanics nor the cheapest-sub-branch accounting on this transcription, so it was almost certainly keyed from the original printed figure's estimates. Write the key's answer in the exam, but know the strict run: expansions S, C, B, F, G and final S = 42 via S→C→F→(I,J), G→J.

Interactive walk-through of the strict execution:

1 / 5

S options: AND(A,B) = (8+2)+(10+2) = 22 OR(C) = 14+2 = 16 ← MARK S = 16

expanding nowlive on marked pathprimitive (born SOLVED)marked / solved

Shared children

E is a child of both A and B; F of both B and C. Refining F therefore updates two parents at once (step 3 above lifts B from 36 to 40 without touching it) — the kind of detail this question uses to separate careful traces from rushed ones.

Answers, decoded

5.1 — keyed expansions: S, C, B (alternate C,B,A drops S).
5.2 — keyed S values: 16, 22, 24 (first two verified mechanically; the 24 comes from the paper's cheapest-sub-branch reading of B).
5.3 — keyed final: 30. Strict textbook execution on the drawn figure gives 42 — see the warning callout before deciding what to write.

Tricks & Tips

Answers: 5.1 S,C,B · 5.2 16,22,24 · 5.3 30