Q9 — PROBLEM DECOMPOSITION

The Question

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

Nodes with 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.

• 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.
• Each edge has a unit cost. Solve for $S$.

The Topic in 60 Seconds

AO* maintains one cost per node and always expands the cheapest unsolved non-primitive leaf lying on S's current best partial solution graph:

$\text{cost}(n) = \begin{cases} \text{actual given value} & n \text{ primitive (leaf)} \\ h(n) & n \text{ non-primitive leaf} \\ \min_{c}\big(1 + \text{cost}(c)\big) & n \text{ OR node} \\ \sum_{c}\big(1 + \text{cost}(c)\big) & n \text{ AND node} \end{cases}$

After expanding a leaf, back the new costs up to S and re-pick. Terminate when the best solution graph contains only solved/primitive nodes.

Deep-dive: browse the Concepts section for AO* search.

Solutions

The run, expansion by expansion

Expansion 1 — S. Price S's three options from leaf estimates:

$\text{value}(S) = 101$, best child C.

Expansion 2 — C (cheapest leaf on S's best graph). C is AND of $G$ (still a leaf: $h=80$) and $H$ (primitive 100):

$\text{cost}(C) = (1+80) + (1+100) = 81 + 101 = 182$

Back-up: $S = \min(\underbrace{222}_{\text{AND}},\ \underbrace{1+182}_{183},\ \underbrace{161}_{\text{OR }D}) = 161$ → best flips to D.

Expansion 3 — D. D is AND of primitives $I$ (140) and $H$ (100):

$\text{cost}(D) = (1+140) + (1+100) = 141 + 101 = 242$

Back-up: $S = \min(222,\ 183,\ 242) = 183$ → best returns to C.

Expansion 4 — G (the only expandable leaf left on S's best graph; H, I are primitive). G is OR of leaves $J$ (100), $K$ (90), plus its own estimate 80:

$\text{cost}(G) = \min(80,\ 1+100,\ 1+90) = \min(80, 101, 91) = 91 \ \text{via } K$

Back-up: $\text{cost}(C) = (1+91) + (1+100) = 92 + 101 = 193$, so $S = 1 + 193 = 194$. The chain $K \Rightarrow G \Rightarrow C \Rightarrow S$ is now entirely solved/primitive → terminate.

Answers

9.1 — Expansion order: S, C, D (continuing: S, C, D, G). No ties ever arose, so both tie-breakers stay idle. Primitives A, E, F, H, I are never expanded by rule.

Answer: S,C,D / S,C,D,G

9.2 — Value of S after each of the first three expansions: 101, 161, 183 (fourth gives 194).

Answer: 101,161,183 / 101,161,183,194

9.3 — Final value of S: 194

True cost check along the returned solution: $1_{(S,C)} + \big[(1 + (1 + 90))_{G \text{ via } K} + (1 + 100)_{H}\big] = 1 + 92 + 101 = 194$ ✓

Answer: 194

9.4 — Is the heuristic admissible? → A (No)

Admissibility requires $h(n) \le h^*(n)$ for every non-primitive node. Test B: its true solve cost is

$h^*(B) = (1 + 40)_{E} + (1 + 60)_{F} = 41 + 61 = 102 \;<\; h(B) = 200$

A 98-unit overestimate → the heuristic is not admissible. (The other estimates behave: $h^*(G) = 91 \ge 80$, $h^*(C) = 193 \ge 100$, $h^*(D) = 242 \ge 160$, $h^*(S) = 194 \ge 100$.)

Answer: A

Interactive AO* trace

Each step shows the expansion, exact arithmetic, and how S's backed-up value moves: 101 → 161 → 183 → 194.

Tricks & Tips

Answers: 9.1 S,C,D / S,C,D,G · 9.2 101,161,183 / 101,161,183,194 · 9.3 194 · 9.4 A