Q4 — AO* on an AND–OR Decomposition

Trace AO* expansion by expansion — marked arcs, cost revision, and why S finally settles at 44.

The Question

An AND–OR graph: problem S decomposed into subproblems. Numbers = heuristic cost estimates; double circles are primitive (actual costs, born SOLVED, never expanded). Every edge costs 2. Tie-breakers: node labels; for AND nodes expand the highest-cost unsolved branch first.

The AND arcs (from the figure): at S, the pair (S→B, S→C) is joined by an arc — S is solved by B and C together, or by A alone. At A: (A→D, A→E) AND. At F: (F→H, F→I) AND. B is an OR node over E and F; C has the single child F; E has the single child G.

#	Question	Official answer
4.1	First three nodes expanded (incl. S)	`S,C,F` (also accepted: `C,F,B`)
4.2	Value of S after the 1st, 2nd, 3rd expansions	`30,26,38` (also accepted: `26,38,40`)
4.3	Final value of S	`44`

The Topic in 60 Seconds

AO* alternates two phases:

Expand: walk down from the root along marked arcs only (the currently-believed-best decomposition) to an unexpanded (live) node; expand it.
Revise: for every node whose children changed (deepest first), recompute each option —
- OR option: child cost + edge cost (take the best one)
- AND option: $\sum(\text{child costs}) + \sum(\text{edge costs})$ (all needed) mark the cheapest, and propagate the new cost up to the root.

Primitive nodes enter the graph already SOLVED; a node becomes SOLVED when all children of its marked option are SOLVED.

Deep-dive: AO* and Goal Trees.

The Trace — five expansions to a solved root

Initial costs: S=40, A=50, B=8, C=18, E=8, F=12; primitives D, G, H, I born SOLVED at 10 each.

Expansion 1 — S. Options:

AND(B, C): $(8+2) + (18+2) = 30$
OR(A): $50 + 2 = 52$

Mark AND(B, C) → S = 30 ✓ (value after 1st expansion).

Expansion 2 — C (marked path hits B and C; tie-breaker 2: C is the costlier branch, 18 > 8). C's only option: $F + 2 = 12 + 2 = 14$ → C = 14. Propagate: $S = (8+2) + (14+2) = \mathbf{26}$ ✓

Expansion 3 — F (marked path: B(8), F(14→ via C); F costlier than B). F's AND(H, I): $(10+2)+(10+2) = 24$ , both primitive → F = 24, SOLVED. Propagate:

$C = 24 + 2 = 26$ , SOLVED (its only child F is solved)
$S = (8+2) + (26+2) = \mathbf{38}$ ✓

Expansion 4 — B (only unsolved node left on the marked path). B is OR:

via E: $8 + 2 = 10$ ← cheaper
via F: $24 + 2 = 26$

Mark E → B = 10. Propagate: $S = (10+2) + (26+2) = 40$ .

Expansion 5 — E (marked path S→B→E). E's child: $G + 2 = 12$ , G primitive → E = 12, SOLVED. Propagate:

$B = \min(12+2,\ 24+2) = 14$ via E → B SOLVED
$S = (14+2) + (26+2) = \mathbf{44}$ — and since B, C are solved, S is SOLVED. Stop.

Final value of S = 44 ✓. Solution subtree: S → B→E→G and C→F→H,I.

The cost went 30 → 26 → 38 → 40 → 44 — up, down, then up. Why?

The heuristic here is a mix: expanding C and F raised estimates (children cost more than the parent's optimistic guess), while B's cheap E branch lowered S. AO* simply keeps revising until the root is solved — monotonic increase is not guaranteed unless every $h$ underestimates.

Interactive AO* trace — watch the marked arcs (green) and S's value evolve, with the scrap-paper working under each step:

1 / 7

h: S=40, A=50, B=8, C=18, E=8, F=12. D, G, H, I primitive (10, actual). Edge cost = 2 everywhere. S options: AND(B,C) = (8+2)+(18+2) = 30 | OR(A) = 50+2 = 52 → mark AND(B,C). S = 30

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

Answers, decoded

4.1 — expansions in order: S, C, F (the accepted C,F,B variant counts S's own expansion as step 0 and lists the next three: C, F, B).
4.2 — S after each: 30, 26, 38 (the accepted 26,38,40 variant reports after C, F, B instead).
4.3 — final: 44.

Tricks & Tips for This Question Family

Answers: 4.1 S,C,F · 4.2 30,26,38 · 4.3 44