Means-Ends Analysis and the General Problem Solver

The Simplest Explanation

Compare where you are with where you want to be. List the differences. Attack the largest one first using whatever operator reduces that kind of difference — then recursively handle that operator's preconditions, then continue on what remains.

That's Means-Ends Analysis, the strategy of Newell & Simon's General Problem Solver (GPS) — planning the way humans intuitively do.

The Strategy

1. Compare current state $s$ with goal $G$; list differences
2. Order differences by magnitude
3. Reduce the largest difference first using an operator chosen from the operator-difference table
4. Recursively achieve the chosen operator's preconditions
5. Apply it; recompute differences; repeat

The recursion produces an AND structure: achieve preconditions AND then solve rest-from-new-state.

The Operator-Difference Table (travel example)

Worked Trip: IIT Madras → Parashar Lake (Himachal)

1. Biggest difference ≈ 2500 km → flight (Chennai → Delhi)
2. Flight's preconditions (be at Chennai airport) → smaller difference ~15 km → taxi
3. After landing in Delhi, remaining ~2000 km? No — next leg Delhi→Mandi by bus
4. Last stretch Mandi→Parashar Lake (~50 km) → taxi/walk

Notice the shape: the middle of the plan (the flight) gets chosen FIRST; prefix and suffix are filled in recursively around it. Forward/backward state-space planners commit to a direction — means-ends commits to the most significant difference instead.

Why It Yields AND-OR Trees

"Achieve G from s" decomposes into:

Achieve G from s
 ├─ AND ─ Achieve preconditions of O (recursive)
 └─ AND ─ Apply O, then achieve G from s'

Both branches mandatory → AND node; alternative operators for the same difference are OR options. This is exactly the structure AO* searches — means-ends analysis is a generator of AND-OR problems, AO* is the solver.

Properties