Textbook of AI

Means–ends analysis (MEA) is a problem-solving technique formalised by Allen Newell, J. C. Shaw, and Herbert Simon in the General Problem Solver (GPS, 1957–59) and in their landmark monograph Human Problem Solving (1972). It is one of the central conceptual contributions of early symbolic AI and remains an idea worth knowing.

The procedure

Given a current state $s$ and a goal state $g$, MEA proceeds:

1. Compute the difference $d = \mathrm{diff}(s, g)$ between the current and goal states.
2. If $d$ is empty, stop, the goal is achieved.
3. Consult a table of connections that associates types of differences with operators known to reduce them.
4. If the chosen operator's preconditions are satisfied in $s$, apply it; otherwise recursively invoke MEA to make the preconditions true (a subgoal).
5. Repeat from step 1.

The technique's hallmark is goal regression: the agent reasons backward from the goal, decomposing it into subgoals as needed. Newell and Simon argued that this imitates a recognisable pattern of human reasoning, "I want to be at work; the difference is location; the operator that reduces location-differences is taking the train; the train requires a ticket; …", and offered MEA as evidence that human and machine cognition can be studied in the same terms (the physical symbol system hypothesis).

A small example

Consider the monkey-and-bananas problem (a classic AI exercise). Goal: monkey holds bananas. Current state: monkey on floor, bananas hanging from ceiling, box in corner. The difference is "not holding bananas"; the relevant operator is grasp, but its precondition is "monkey at the bananas' altitude". This unsatisfied precondition becomes a subgoal: the operator is climb-box; its precondition is "box under bananas"; that subgoal needs push-box; and so on. The agent unwinds the recursion and executes the plan.

Place in AI history

MEA was the search heuristic of GPS and shaped a generation of planning systems. Its descendants include:

• STRIPS (Fikes and Nilsson, 1971), formalised operators with preconditions and effects as first-order logic, the "STRIPS representation" still used today.
• Hierarchical task network (HTN) planners, decompose tasks into sub-tasks recursively.
• Partial-order planners (e.g. SNLP, UCPOP) of the 1990s.
• More loosely, the chain-of-thought and task-decomposition strategies used in modern large-language-model agent frameworks owe a clear debt to the MEA tradition.

Strengths and limits

MEA is most effective when the problem decomposes naturally into subgoals whose individual solutions compose to a global solution, when the heuristic of "always reduce the largest difference" reliably approaches the goal. It struggles in domains where the right sequence of moves temporarily increases the difference to the goal, the "valley" problems in which one must move away from the apparent target before reaching it. Sliding-puzzle solutions and many real-world planning problems exhibit such valleys, motivating richer techniques: heuristic search with admissible evaluation functions ($A^*$), planning under uncertainty (MDPs, POMDPs), and learned policies. But the basic insight of MEA, measure, choose, recurse, evaluate, survives in many of these descendants.