The General Problem Solver (GPS) was a theory of human problem solving stated in the form of a simulation program (Ernst & Newell, 1969; Newell & Simon, 1972). This program and the associated theoretical framework had a significant impact on the subsequent direction of cognitive psychology. It also introduced the use of productions as a method for specifying cognitive models.
The theoretical framework was information processing and attempted to explain all behavior as a function of memory operations, control processes and rules. The methodology for testing the theory involved developing a computer simulation and then comparing the results of the simulation with human behavior in a given task. Such comparisons also made use of protocol analysis (Ericsson & Simon, 1984) in which the verbal reports of a person solving a task are used as indicators of cognitive processes.
GPS was intended to provide a core set of processes that could be used to solve a variety of different types of problems. The critical step in solving a problem with GPS is the definition of the problem space in terms of the goal to be achieved and the transformation rules. Using a means-end-analysis approach, GPS would divide the overall goal into subgoals and attempt to solve each of those. Some of the basic solution rules include: (1) transform one object into another, (2) reduce the different between two objects, and (3) apply an operator to an object. One of the key elements need by GPS to solve problems was an operator-difference table that specified what transformations were possible.
Application
While GPS was intended to be a general problem-solver, it could only be applied to “well-defined” problems such as proving theorems in logic or geometry, word puzzles and chess. However, GPS was the basis other theoretical work by Newell et al. such as SOAR and GOMS. Newell (1990) provides a summary of how this work evolved.
Example
Here is a trace of GPS solving the logic problem to transform L1= R*(-P => Q) into L2=(Q \/ P)*R (Newell & Simon, 1972, p420):
Goal 1: Transform L1 into LO
Goal 2: Reduce difference between L1 and L0
Goal 3: Apply R1 to L1
Goal 4: Transform L1 into condition (R1)
Produce L2: (-P => Q) *R
Goal 5: Transform L2 into L0
Goal 6: Reduce difference between left(L2) and left(L0)
Goal 7: Apply R5 to left(L2)
Goal 8: Transform left(L2) into condition(R5)
Goal 9: Reduce difference between left(L2) and condition(R5)
Rejected: No easier than Goal 6
Goal 10: Apply R6 to left(L2)
Goal 11: Transform left(L2) into condition(R5)
Produce L3: (P \/ Q) *R
Goal 12: Transform L3 into L0
Goal 13: Reduce difference between left(L3) and left(L0)
Goal 14: Apply R1 to left(L3)
Goal 15: Transform left(L3) into condition(R1)
Produce L4: (Q \/ P)*R
Goal 16: Transform L4 into L0
Identical, QED
Principles
- Problem-solving behavior involves means-ends-analysis, i.e., breaking a problem down into subcomponents (subgoals) and solving each of those.
References
- Ericsson, K. & Simon, H. (1984). Protocol Analysis. Cambridge, MA: MIT Press.
- Ernst, G. & Newell, A. (1969). GPS: A Case Study in Generality and Problem Solving. New York: Academic Press.
- Newell, A. (1990). Unified Theories of Cognition. Cambridge, MA: Harvard University Press.
- Newell, A. & Simon, H. (1972). Human Problem Solving. Englewood Cliffs, NJ: Prentice-Hall.