Q5 — AO* Problem Decomposition

The Question

The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or more simpler problems. Nodes are uniquely identified by labels (S, A, B, …). The number in each node is the heuristic estimate of the cost of solving that node.

Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a primitive node is added to the graph by its parent when the parent is expanded, and the primitive node is labeled as SOLVED and it will not be expanded subsequently.

The cost of each edge is 2 units.

Tie-breaker 1: For nodes with the same cost, expand in the ascending order of node labels.

Tie-breaker 2: For AND nodes, expand the unsolved branch with the highest cost.

The Topic in 60 Seconds

AO* alternates expand (one unsolved node on the currently marked best partial solution) and revise (recompute costs upward, re-mark the best arcs). AND arcs need all their branches solved; primitives arrive SOLVED at true cost.

Deep-dive: AO* and Goal Trees.

Setup

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

Once expanded, S has two options:

• OR arc through A: $2 + h(A) = 2 + 38 = 40$
• AND arc $\{B, C\}$: $(2 + h(B)) + (2 + h(C)) = (2+12) + (2+20) = 36$

Expansion 1 — S → S revised to 36

Generate A, B, C. Compare OR $40$ vs AND $36$: S = min(40, 36) = 36, marker on the AND arc S → AND(B, C). ✓

Expansion 2 — C → S revised to 28

Both branches of the marked AND are candidates; tie-breaker 2 says take the highest-cost unsolved branch: C ($20$) over B ($12$). Generate F.

• C's options: OR via F: $2 + 10 = 12$ → C drops 20 → 12, marked C→F.
• Revise S: AND $= (2+12) + (2+12) = 28$ vs OR $= 40$ → S = 28, marker stays AND. ✓

Expansion 3 — F → S revised to 30

Unsolved nodes on the marked solution: B ($12$) and F ($10$) — these belong to different nodes' fan-outs, so tie-breaker 2 does not apply; best-first picks the cheapest, F. Generate G (primitive 10, SOLVED) and H (primitive 20, SOLVED).

• F's options: OR via G: $2+10 = 12$; OR via H: $2+20 = 22$ → F = 12 via G, SOLVED.
• Propagate: C $= 2 + 12 = 14$, SOLVED.
• Revise S: AND $= (2+h(B)) + (2+14) = 14 + 16 = 30$ vs OR $= 40$ → S = 30 ✓

Expansion 4 — B closes it → final S = 32

Marked candidates now: B only. Expand B: generate E ($h=20$) and F (already solved at 12).

• B's options: OR via E: $2+20 = 22$; OR via F: $2+12 = 14$ → B = 14 via F, SOLVED.
• Revise S: AND $= (2+14) + (2+14) = 32$ vs OR $= 40$ → S = 32; both AND branches solved → stop. ✓

Solution: S solves through the AND arc $\{B, C\}$, both branches draining into F → G. Clean cost check: $S = (2 + \underbrace{14}_{C}) + (2 + \underbrace{14}_{B}) = 16 + 16 = 32$, where each of B, C costs $2 + \underbrace{(2 + 10)}_{F=12} = 14$ ✓

Answers, decoded

Interactive trace

Tricks & Tips

Answers: 5.1 S,C,F · 5.2 36,28,30 · 5.3 32