1 History
1.1 Origins and Developers
The General Problem Solver (GPS) was created between 1957 and 1959 by Allen Newell, Cliff Shaw, and Herbert A. Simon at the RAND Corporation and later at Carnegie Mellon University. Newell and Simon were pioneers in artificial intelligence and cognitive psychology; Shaw was a programmer who implemented the system. The project grew out of their earlier work on the Logic Theorist (1956) and was motivated by the desire to build a system that could solve a wide range of problems using a single, general-purpose mechanism. GPS was one of the first programs to separate problem-solving knowledge from domain-specific content.
1.2 Relation to the Logic Theorist
The Logic Theorist (LT) was the first AI program designed to prove theorems in propositional logic. GPS built upon LT’s approach but aimed for greater generality. While LT was restricted to logic and used a heuristic search based on “difference reduction” tailored to logical expressions, GPS formalized this idea into a domain-independent algorithm. GPS could accept any problem described in terms of states and operators, whereas LT was hardcoded for its specific domain. In essence, GPS extended the core mechanism of LT into a general framework, making it a milestone in the evolution from specialized to general problem solving.
1.3 Subsequent Influence on AI Research
GPS had a profound impact on the development of artificial intelligence. It introduced means-ends analysis, which became a foundational concept in planning and heuristic search. The system influenced early work in cognitive architecture, particularly the development of Soar and ACT-R, which adopted similar goal-subgoal structures. GPS also inspired the field of automated planning, where state-space search and operator application remain central. Although GPS itself was limited by computational constraints and domain dependence of differences, its ideas shaped decades of AI research in problem solving and symbolic reasoning.
2 Core Concepts
2.1 Means‑Ends Analysis
Means‑ends analysis is the core strategy used by GPS. It works by comparing the current state to the goal state, detecting differences, and selecting operators that reduce those differences. The system recursively applies this process, setting up subgoals when an operator’s preconditions are not met. This approach contrasts with blind search by directing effort toward closing the gap between current and desired states.
2.1.1 Difference Detection
GPS identifies differences between the current state and the goal state using a predefined set of difference types. For example, in the Towers of Hanoi, a difference might be “a disk is on the wrong peg.” The system classifies each difference into a category that can be looked up in the difference table to find relevant operators.
2.1.2 Operator Selection
Once a difference is detected, GPS consults a difference table that maps each type of difference to a list of operators known to reduce that difference. The system then attempts to apply the most promising operator. If the operator’s preconditions are not satisfied, GPS sets a subgoal to achieve those preconditions, recursively applying means-ends analysis.
2.1.3 Goal Reduction and Subgoaling
When an operator cannot be applied immediately, GPS creates a subgoal to make the operator applicable. This subgoal is itself solved using means-ends analysis. The process continues until a sequence of operators is found that transforms the initial state into the goal state. GPS uses a stack of goals and subgoals, which allows it to backtrack when a subgoal fails.
2.2 Problem Representation
GPS requires problems to be represented in a formal language consisting of states, operators, and a difference table. This representation allows the system to operate on any problem that can be described in those terms.
2.2.1 State Space
A problem is defined by an initial state and a goal state, each described as a set of objects and relations. For example, in the Towers of Hanoi, a state includes the positions of each disk on pegs. GPS searches through this state space by applying operators to generate new states.
2.2.2 Operators and Preconditions
Operators are transformation rules that change the state. Each operator has a set of preconditions (conditions that must hold before it can be applied) and a set of effects (changes to the state). For instance, an operator “move disk from peg A to peg B” requires that disk is on top and peg B has a larger disk or is empty.
2.2.3 Difference Table
The difference table is a critical data structure in GPS. It lists all possible difference types that can arise between states and, for each type, identifies which operators are likely to reduce that difference. The table is hand-coded for each problem domain, which makes GPS domain-dependent in its knowledge even though its algorithm is general.
3 Applications
3.1 Classic Problems Solved
GPS was successfully applied to several well-known puzzles and mathematical problems. Its performance demonstrated the feasibility of means-ends analysis, though it often struggled with larger instances due to combinatorial explosion.
3.1.1 Towers of Hanoi
The Towers of Hanoi puzzle involves moving a stack of disks from one peg to another without placing a larger disk on a smaller one. GPS solved small instances (e.g., three disks) by detecting the difference of largest disk not on the target peg, then recursively moving smaller disks out of the way. The solution required planning multiple moves, which GPS handled through subgoaling.
3.1.2 Missionaries and Cannibals
The classic river-crossing puzzle requires moving three missionaries and three cannibals across a river using a boat that carries two people, without leaving cannibals outnumbering missionaries on either bank. GPS could find a solution by representing boat locations and numbers of missionaries/cannibals as state variables. It detected differences such as “unbalanced counts” and selected appropriate boat-loading operators.
3.1.3 Cryptarithmetic
GPS could solve simple cryptarithmetic puzzles (e.g., SEND + MORE = MONEY) by representing digit assignments as state and constraints as differences. However, its performance was limited because the problem required reasoning about numeric sums, and the difference table had to be tailored to handle carry operations. GPS solved only very small instances.
3.2 Limitations
Despite its historical importance, GPS had significant limitations that prevented it from solving complex real-world problems.
3.2.1 Domain Dependence of Differences
The difference table is hand-crafted for each domain. This means that although the overall algorithm is general, the system still requires domain-specific knowledge engineering. GPS cannot learn or adapt differences automatically; a new problem class requires a new table. This undermines the claim of being a “general” problem solver.
3.2.2 Combinatorial Explosion
GPS uses depth-first search with means-ends analysis, but it does not prune aggressively. As the number of objects and operators grows, the state space expands exponentially. Many problems (e.g., larger Towers of Hanoi with more disks) became intractable because the number of subgoals and recursive calls blew up. GPS lacked heuristics to rank subgoals effectively, leading to excessive backtracking.
4 Legacy
4.1 Impact on Artificial Intelligence
GPS established key concepts that shaped the field of AI for decades. Its influence is seen in both symbolic AI and cognitive modeling.
4.1.1 Symbolic AI Paradigm
GPS exemplified the symbolic AI approach, where knowledge is represented explicitly as symbols and reasoning is done through logical operations. It reinforced the idea that intelligence could be achieved by manipulating symbols according to rules. This paradigm dominated AI research through the 1970s and 1980s and laid the groundwork for expert systems and theorem provers.
4.1.2 Cognitive Architecture (Soar, ACT‑R)
Newell and Simon’s work on GPS directly inspired later cognitive architectures. Soar, developed by Newell and colleagues, adopted a similar goal-subgoal structure and used a variant of means-ends analysis (universal subgoaling). ACT‑R, by John Anderson, also incorporated goal stacks and difference reduction. Both architectures aim to model human cognition and have been applied in psychology, human-computer interaction, and AI.
4.2 Comparison with Modern Problem Solvers
Modern AI systems have superseded GPS in efficiency and scope, but GPS’s ideas remain relevant.
4.2.1 Heuristic Search Algorithms
GPS’s means-ends analysis is a form of heuristic search. Today’s algorithms, such as A* and greedy best-first search, use more sophisticated heuristics and explicit cost functions. They are typically faster and can handle larger state spaces. GPS lacked a cost-to-goal estimate; it only reduced differences without considering solution length.
4.2.2 Automated Planning Systems
Automated planning systems, such as STRIPS (1971) and its successors (e.g., PDDL-based planners), evolved from GPS. They use a more formal description of actions (preconditions and effects) and employ advanced search techniques like forward chaining, backward chaining, or graph-based methods (e.g., Graphplan). These systems can solve problems with thousands of actions, whereas GPS struggled with dozens. However, the core idea of recursive subgoaling remains central.