Problem Reduction

Problem reduction solves a hard problem by breaking it into a set of smaller sub-problems, such that solving all of them (or, in an OR case, any one of them) solves the original problem. This yields an AND-OR graph instead of the plain OR-graph used by ordinary state-space search.

AND-OR Graphs

Here, solving P means solving A or solving both B1 and B2.

Classic Example: The Tower of Hanoi

Moving n disks from peg A to peg C reduces to: (1) move top n-1 disks A to B, AND (2) move the largest disk A to C, AND (3) move n-1 disks B to C. All three sub-goals must be achieved — a textbook AND decomposition.

The AO* Algorithm

AO (And-Or-star) generalises A to AND-OR graphs, searching for the cheapest way to solve the top-level problem given the AND/OR structure.

1. Start with the initial node; compute its heuristic estimate.
2. Traverse the graph, following the current best (marked) path from the top node,
   picking the successor with the lowest cost estimate at OR nodes,
   and requiring ALL successors at AND nodes.
3. Expand a chosen unexpanded node on this path; compute heuristic estimates for its new successors.
4. Propagate the revised cost estimates back up the graph (an AND node's cost = sum of
   its children's costs + own cost; an OR node's cost = minimum of its children's costs).
5. Re-mark the best path in light of the updated costs.
6. Repeat until the top-level node is marked SOLVED (all required sub-problems solved)
   or determined to have no solution.

Problem Reduction vs Ordinary State-Space Search

Problem reduction is powerful precisely because many real problems (compiling a program from modules, proving a theorem from lemmas, planning a project from tasks) are naturally AND-structured — reducing to sub-problems, all of which must be solved, is more natural than searching one giant flat state space.