Artificial Intelligence · AI Foundations

AND-OR Graphs and AO*

In AI because some goals decompose into parts that must all be solved — and A* cannot see an AND — so the search has to return a solution graph, not a path.

A* returns a path: a sequence of OR choices, one successor at a time. Some campus jobs are not paths. 'Submit the project' can be done by writing a report and running a live demo, or by uploading one recorded video — the first option is two tasks that both have to happen. That is an AND-OR graph: OR nodes pick a method, AND nodes demand every part. AO* is the informed search that returns a solution graph for that structure. Hill climbing, last lesson, still lived on a single state; this lesson is back in constructive search, with a different object to construct.

Artificial Intelligence
Medium level
5 concepts

1AND versus OR

An OR node is the kind of choice A* already knows: any one child solves the parent. 'Submit the project' is an OR — the report-and-demo method or the video method, not both. An AND node is the new object: every child must be solved. 'Write the report AND run the demo' is one method whose parts are not alternatives.

The two marks travel together. A realistic reduction mixes them: the top goal is an OR of methods, and some methods are AND bundles of subgoals, which may themselves be OR. The graph is not a tree of states with single-successor edges; it is a reduction of a problem into smaller problems.

Figure. Submit is an OR: either the AND-bundle or the 8-hour video. The bundle is an AND: report (4h) and demo (3h) both required. Topology only — costs are labels, not drawn to scale.

What a node demands
Node	Solved when	Campus reading
OR	Any one child is solved	Pick a submission method
AND	Every child is solved	Report and demo, both

2Why A* cannot carry an AND

A* expands a node into successor states and keeps one path from the start. If you flatten the campus job into ordinary edges — Submit to Report, Submit to Demo, Submit to Video — A* will return one of those three as a path. It has no primitive that says 'Report and Demo together are one option'. The AND is lost in the flattening.

You can try to encode the pair as a single mega-state 'report-plus-demo'. That works until a subgoal itself splits, or is shared by two methods, or can be solved in more than one way. The honest object is a subgraph: a set of chosen OR decisions plus every AND child those decisions require. That subgraph is a solution graph, and it is what AO* returns.

What flattening loses
Encoding	Can represent	Cannot represent
A* path on flat edges	One of Report, Demo, Video	Report AND Demo as one method
AO* solution graph	A chosen OR plus every AND child	Nothing the AND required

3A solution is a subgraph

A solution graph is a subgraph that starts at the goal, at every OR node includes exactly one child, at every AND node includes every child, and ends on leaves that are already solved — here, primitive tasks with a known hours cost. Two legal solutions live on the campus graph: the AND-bundle of report plus demo, and the single video leaf.

Cost follows the same split. An OR node's cost is the cost of the child it picked. An AND node's cost is the sum of its children's costs, because every part is required. The bundle costs 4 + 3 = 7 hours; the video costs 8. The cheaper solution graph is the bundle.

Figure. The two legal solution graphs scored in hours. The sage bundle at 7 is the cheaper complete subgraph. The terracotta video at 8 is also complete — just more expensive. Values are the hours from the ledger.

Two legal solution graphs

Submit is OR(AND(Report 4h, Demo 3h), Video 8h). Leaves have exact costs; no heuristic yet.

Bundle AND-cost = 4 + 37 hours
Video OR-alternative8 hours
Submit picks the cheaper childbundle, 7 hours

Pro tip. 7 beats 8 even though the bundle has more nodes. AND sums parts; it does not mean 'more nodes, more cost' once an expensive singleton sits on the other branch.

4What AO* does

AO* grows a partial solution graph from the start and, at each step, expands one unsolved tip of the current best partial solution. After an expansion it backs costs up: AND nodes sum, OR nodes keep the cheapest child. Unsolved leaves carry an admissible heuristic h — an optimistic remaining-hours estimate — so a partial bundle can be compared with a partial video before either is fully solved.

The algorithm stops when the best partial solution has no unsolved tips: every AND it committed to is finished and every OR it committed to has a chosen child. That finished subgraph is the returned solution. Like A*, the optimality claim rides on h never overestimating a remaining leaf. Unlike A*, the thing proved cheapest is a graph, not a path.

AO* loop

Pick a tipIn the current best partial solution, expand one unsolved leaf.
Back upRecompute AND sums and OR minima up to the root, using h on any leaf still open.
Revise the bestAn OR root may switch children after the backup. Stop when the best subgraph has no open tips.

Backup with a heuristic on the video

Report and demo are solved at 4h and 3h. Video is unsolved with admissible h(Video) = 6. Submit is OR.

Bundle cost (both children solved)7
Video forecast = h(Video)6
Submit currently prefers Video at 6expand Video next
Video solves at true cost 8; backupSubmit switches to bundle at 7

Pro tip. The switch is the point of the backup. A first look at h = 6 made the video look cheaper; the true 8 lost, and the AND-bundle — already sitting at 7 — became the solution. Admissibility kept 6 at or below 8, so the switch was safe.

5When to reach for AO*

Reach for an AND-OR search when a goal decomposes into methods and some methods have required parts — theorem proving, hierarchical task networks, a compiler's instruction-selection DAG, the campus project with a bundled option. Stay with A* when every decision is 'pick one successor' and the answer is a path. Stay with hill climbing when the answer is a state and there is no reduction to grow.

AO* is not a second A* with a different name. The object it constructs, the cost it backs up, and the place an AND appears are the differences that decide the call.

Figure. Reach for AND-OR search when a goal decomposes into methods and some methods have required parts. Stay with A* when every decision is pick one successor and the answer is a path. Stay with hill climbing when the answer is a state and there is no reduction to grow.

A goal can be solved by task A alone, or by doing both B and C. A* on a graph with edges to A, B and C is run. What can it not represent?

That B and C together are one method, so a solution may have to include both
That A is a legal method
That each task has a cost
That the search should stop at a goal

A* returns one path, so it can pick A or B or C. The AND 'B and C together' is a subgraph, which is the object AO* is for.

Notes

An AND-OR graph records problem reduction: OR means pick one way; AND means solve every part.
A solution is a subgraph that reaches solved leaves, not a single path.
AO* grows a partial solution graph and backs up costs through AND and OR nodes.

Formulas

OR node: cost = cheapest solved child
AND node: cost = sum of the children's costs (every part is required)

Exam traps & shortcuts

If the goal is 'do A and B', A* on a flattened graph will pick a path through one of them — it cannot require both.
Read an AND arc as a single hyper-edge: the parent is solved only when every child is.
AO* is still a heuristic search: unsolved leaves carry an admissible h, the same honesty A* needed.

Recap

Next: the water-jug experiment.

AND vs OR: OR: any one child solves the parent. AND: every child must be solved.
Solution graph: A subgraph with one child at each OR, every child at each AND, ending on solved leaves — not a path.
Cost: OR takes the cheapest child; AND sums its children. The campus bundle is 7 hours, the video 8.
AO*: Expand a tip of the current best partial solution, back costs up, stop when that subgraph has no open tips.

Practise AND-OR Graphs and AO*

Reading is free and needs no account. Practice, mocks and progress live in the app.

1 quick check with worked explanations
Timed mocks scored with the real marking scheme
Readiness tracked per topic, kept on your device

Continue with Google — freeNo card, no trial. Works offline once installed.