Textbook of AI

The General Problem Solver (GPS), developed by Allen Newell, Cliff Shaw and Herbert Simon at the RAND Corporation and Carnegie Tech from 1957 to roughly 1969, was the first AI program designed explicitly to imitate the structure of human problem-solving as observed in psychological protocols (subjects thinking aloud while solving puzzles). It was the successor to their earlier Logic Theorist (1956) but with much broader ambition: a single uniform architecture meant to apply to any problem expressible in its representational scheme.

GPS's central technique was means–ends analysis:

1. Represent the problem as a current state and a desired goal state.
2. Compute the difference between current and goal, a structured object identifying what is wrong (e.g. "wrong arithmetic operator at position 3", "left disc is on the wrong peg").
3. Consult a table of operators, indexed by the differences each operator is known to reduce.
4. Apply an operator that addresses the most important difference.
5. If the operator's preconditions are not satisfied in the current state, recursively invoke GPS on the sub-goal "satisfy these preconditions", then retry the original operator.
6. Repeat until the difference is zero (the goal is reached) or no progress can be made.

GPS was remarkable for its time in that the same architecture solved problems in propositional and predicate logic, algebra, the missionaries-and-cannibals river-crossing puzzle, the Tower of Hanoi, symbolic integration, integration by parts, and several geometric construction problems. It demonstrated that intelligence could be modelled by a domain-independent search procedure operating on a domain-specific table of operators and goal differences, a separation of mechanism from content that has remained central to AI ever since.

Limits

The architecture's limits became clear over the 1960s. Specifying operators and difference tables for each new domain proved laborious; the means–ends procedure was brittle on problems where the locally correct move increases the immediate difference (the so-called peak problem); and the lack of any learning mechanism meant that GPS made the same mistakes on each new problem. The frame problem, keeping track of which facts remain true after an action, exposed itself in GPS in a particularly raw form, since the system had to maintain the full state representation explicitly across each operator application.

Legacy

GPS nevertheless established planning as a central AI sub-field. Its conceptual descendants include the STRIPS planner (Fikes and Nilsson, 1971) which formalised operators as add-lists and delete-lists; GPS's later cognitive architectures SOAR (Newell, Laird and Rosenbloom, 1983) and ACT-R (Anderson, 1976 onwards); the entire literature on hierarchical task networks (HTNs); and modern PDDL-based planners. Newell and Simon's broader research programme, the physical symbol system hypothesis that "a physical symbol system has the necessary and sufficient means for general intelligent action", was the philosophical thesis that GPS was meant to demonstrate, and it earned them the 1975 Turing Award.