Q4 — AO* on an AND–OR Decomposition

A marked AND-branch that gets abandoned mid-search — AO* walks away from B,C when A's real cost lands at 54.

The Question

AND–OR decomposition of S. Double circles = primitive (actual costs, born SOLVED). Every edge costs 2. Tie-breakers: node labels; for AND nodes expand the highest-cost unsolved branch first.

AND arcs (from the figure): S = AND(B, C) or OR(A). A = AND(D, E). B = AND(E, F). C has the single child G. All of D, E, F, G are primitive.

#	Question	Official answer
4.1	Nodes expanded (incl. S)	`S,B,A`
4.2	Value of S after each expansion	`34,37,56`
4.3	Final value of S	`56`

The Topic in 60 Seconds

AO* alternates expand (walk marked arcs from the root to a live node) and revise (recompute each option — OR: best child + edge; AND: sum of children + edges — mark the cheapest, propagate up). A node becomes SOLVED when its marked option's children are all solved. Unlike A*, the marked option can switch when refined costs overtake a rival branch.

Deep-dive: AO* and Goal Trees.

The Trace — three expansions

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

Expansion 1 — S.

AND(B, C): $(20+2) + (10+2) = 34$
OR(A): $35 + 2 = 37$

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

Expansion 2 — B (marked path: B(20), C(10); B is costlier → tie-breaker 2). B: AND(E, F) $= (30+2) + (10+2) = 44$ ; E, F primitive → B = 44, SOLVED. Propagate: AND(B, C) $= (44+2)+(10+2) = 58$ — now worse than OR(A) = 37! The marker switches: $S = \min(58,\ 37) = \mathbf{37} \checkmark \text{ (marked } \to A\text{)}$

Expansion 3 — A (now on the marked path). A: AND(D, E) $= (20+2)+(30+2) = 54$ ; D, E primitive → A = 54, SOLVED. Propagate: $S = \min(58,\ 54+2) = \mathbf{56}$ , and since A is solved → S SOLVED = 56 ✓

Final value of S = 56. Solution subtree: S → A → D,E.

Interactive trace — watch the green marked arcs jump from the B,C branch to A:

1 / 4

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

expanding nowlive on marked pathprimitive (born SOLVED)marked arcs

The marker switch is the exam trap

After expansion 2, the once-cheap AND(B,C) branch (34) ballooned to 58 — because B's real cost (44) is more than double its guess (20). AO* didn't expand C next; it abandoned the branch entirely and switched to A. If you blindly expand along the original marked path, you get 4.2 wrong.

Answers, decoded

4.1 — expansions: S, B, A (C never expanded — its branch was abandoned).
4.2 — S after each: 34, 37, 56.
4.3 — final: 56 via the solution subtree S → A → D,E.

Tricks & Tips

Answers: 4.1 S,B,A · 4.2 34,37,56 · 4.3 56