AND-OR Trees and the AO* Algorithm

When one goal splits into many mandatory subgoals — A* grows up, leaves path-land, and starts solving subtrees. Asked in every paper

The Simplest Explanation

So far every solution was a path. Now goals decompose: "plan an evening out" = pick an activity AND a movie AND a restaurant. All three must succeed. That changes the search space into an AND-OR tree:

OR node: any ONE child suffices (a choice — like normal search)
AND node: ALL children must be solved together (a decomposition)

A solution is no longer a path — it is a solution subtree rooted at the start.

Remember This

OR = choose one branch (either/or). AND = need all branches (every subgoal). AO* finds the cheapest solution SUBTREE, and it decides using backed-up costs of whole branches — never raw h values.

Why Not Just Use A*?

Aspect	A*	AO*
Graph type	OR graph	AND-OR graph
Solution	Path from start to goal	Subtree rooted at start
Expansion rule	Expand lowest- $f$ open node anywhere	Follow marked paths down to live nodes
Cost bookkeeping	$f(n) = g(n) + h(n)$ per node	Backed-up cost = best child costs + edge costs
Terminates when	Goal dequeued from Open	Root labeled solved

AO* (Martelli & Montanari, 1978) — the star means admissible: with underestimating $h$ , it returns the least-cost solution subtree.

The Algorithm: Two Phases per Iteration

Forward phase — decide WHERE to look:

From the root, trace only marked arcs (currently-believed-best choices) down to unexpanded (live) nodes
Pick one live node and expand it

Backward phase — update what you believe:

For each modified node (deepest first):
- Compute cost of each option: for an OR choice, child cost + edge; for an AND choice, sum over all conjuncts + edges
- Mark the cheapest option
If all successors on the marked option are solved, mark this node solved too
Propagate cost changes up to ancestors
Stop when the root becomes solved

The #1 Exam Insight

Expansion order follows MARKED paths from the root — not global lowest-f. And the decision to switch branches uses BACKED-UP costs: a low-h node can sit on a hopeless expensive branch and never get expanded.

Interactive Demo

Click through a full AO* run. Watch the marker, the backed-up root cost, and notice A is never expanded:

AO* TraceStep 0 / 3

Expanding

Generated, unsolved

Solved / marked path

Start. Only the root S exists. Edge costs are all 1. Solved (primitive) nodes cost 0. Unexpanded nodes carry heuristic estimates h.

Backed-up cost of root

Node A

Node B

Reading the Trace

Step 2 shows the marker logic: S compares via-A (7) vs via-B (5), marks B.
Step 3 shows propagation: refining B lowers S's estimate 5 → 4.
Step 4 shows solved-labeling cascade: G solved → B solved → S solved. Total solution cost 4, subtree S→B→G→{leaves}.

Overestimating vs Underestimating (the lecture's key experiment)

Run AO* on the same graph with different edge costs:

Edge cost	h values are...	Costs during refinement	Marker behavior	Guarantee
1	overestimates	keep coming DOWN as nodes are refined	first promising branch stays best — never switches	fast, but may miss optimum
10	underestimates	keep going UP as nodes are refined	switches back and forth as reality emerges	slower, guaranteed optimal

This mirrors Weighted A*: big overestimates ≈ large $w$ (fast, suboptimal); underestimates ≈ admissible $h$ (optimal). Exam questions frequently give you both traces and ask which marker switch happens at which step.

Worked Mini-Trance by Hand

Graph: S has OR-children X ( $h{=}9$ ) and Y ( $h{=}5$ ). Expanding Y yields an AND pair {P, Q}, both primitive (cost 0), edge costs all 1.

Expand S: via-X = 9+1 = 10; via-Y = 5+1 = 6. Mark S→Y. Backed-up(S) = 6.
Follow marked path to Y; expand it → P, Q appear. Option through {P,Q}: 0+1 + 0+1 = 2 < 6. Mark it.
P, Q are primitive → solved. Y solved. Propagate: S = 2+1 = 3, marked successor Y is solved → S solved.

Answer: minimum-cost solution subtree = S→Y→{P,Q}, cost 3.

Where AND-OR Trees Show Up

Planning: achieve goal = AND of subgoals; alternative operators = OR
Means-Ends Analysis (Newell & Simon's GPS): reduce largest difference (then apply op AND then finish rest) — inherently AND-shaped
Logical deduction / proof search: proving a conjunction = AND node; multiple inference rules proving the same sentence = OR node

QuizAt an AND node, the backed-up cost equals...

QuizAO* chooses WHICH node to expand next by...

QuizWith UNDERestimating heuristics, AO*'s cost estimates during refinement tend to...