Q5 — AO* on an AND–OR Decomposition

S=10, A=12, B=2, C=6 — OR(C) wins at 8, the marker flips to AND(A,B) at 14, and S lands at 16.

The Question

AND–OR decomposition. Double circles = primitive. Edge = 2. Tie-breakers: labels; AND nodes expand the highest-cost unsolved branch first.

#	Question	Official answer
5.1	First three expanded	`S,C,A`
5.2	S after each	`12,14,14`
5.3	Final S	`16`

The Topic in 60 Seconds

AO* loops two moves: expand one unsolved node on the currently marked best partial solution, then revise costs back up the graph and re-mark. Unlabeled arcs are OR arcs; AND-tagged arcs must ALL be solved together. Primitive children arrive SOLVED at their true cost.

Deep-dive: AO* and Goal Trees.

Setup

$h$ : S = 10, A = 12, B = 2, C = 6, E = 10, F = 10; primitives D = 30, G = 10, H = 20 (SOLVED on generation). Edge cost = 2 everywhere.

S's two options once expanded:

OR arc through A: $2 + h(A) = 2 + 12 = 14$
AND arc $\{B, C\}$ : $(2 + h(B)) + (2 + h(C)) = (2+2) + (2+6) = 12$

Expansion 1 — S → S revised to `12`

Generate A, B, C. Compare $14$ (OR) vs $12$ (AND): S = min(14, 12) = 12, marker goes to the AND arc S → AND(B, C). ✓

Expansion 2 — C → S revised to `14`

Both B and C hang on the marked AND arc; tie-breaker 2 says expand the highest-cost unsolved branch: C ( $6$ ) over B ( $2$ ). Generate F.

C's options: OR via F: $2 + 10 = 12$ → C = 12, marked C→F.
Revise S: AND $= (2+2) + (2+12) = 18$ vs OR $= 14$ → S = min(14, 18) = 14, marker flips to OR arc S→A. ✓

Expansion 3 — A → S stays at `14`

The marked path now runs S→A; expand A. Generate D (primitive, SOLVED, 30) and E.

A's options: OR via D: $2 + 30 = 32$ ; OR via E: $2 + 10 = 12$ → A = 12, marked A→E.
Revise S: OR $= 2 + 12 = 14$ ; AND still $18$ → S = 14 ✓

Expansion 4 — E closes everything → final S = `16`

Expand E: generate G (primitive, SOLVED, 10).

E $= 2 + 10 = 12$ , SOLVED → A $= 2 + 12 = 14$ , SOLVED → S's OR arc $= 2 + 14 = 16$ .
S $= \min(16, 18) = \mathbf{16}$ ; every node on the marked arc is solved → stop. ✓

Answers, decoded

#	Answer	Where it came from
5.1	`S,C,A`	expansions along the marked path, AND tie-break sends C before B
5.2	`12,14,14`	after S: min(14, 12); after C: min(14, 18); after A: min(14, 18)
5.3	`16`	E solves G-side: S = 2 + (2 + (2 + 10)) = 16 < AND's 18

Interactive trace

1 / 6

h: S=10 A=12 B=2 C=6 E=10 F=10 primitives: D=30 G=10 H=20 (SOLVED when generated) edge cost = 2

expandinggenerated, unsolvedexpandedsolved / solution arc

Tricks & Tips

Answers: 5.1 S,C,A · 5.2 12,14,14 · 5.3 16