General Problem Solver

What it was

The General Problem Solver (GPS) was a program built to work as a universal problem-solving machine ^[1]. It is credited as the first computer program to separate its knowledge of problems, represented as input rules, from its strategy for solving them, a generic solver engine ^[1]. That split is the heart of the idea: rather than writing a separate program for each task, the designers wanted one engine that could be pointed at any problem whose objects and operations had been described to it.

Where it came from

GPS was created in 1957 by Herbert A. Simon, J. C. Shaw and Allen Newell of the RAND Corporation, while a shorter description of the program dates it to 1959 ^[1]. It rested on Simon and Newell's theoretical work on logic machines and was implemented in the third-order programming language IPL ^[1]. The program grew out of an earlier one, the Logic Theorist, which discovers proofs to theorems in the sentential calculus ^[2]. RAND report P-1584, dated 30 December 1958 and revised 9 February 1959, describes a program called GPS-I, for General Problem Solving Program I ^[2]. RAND's own bibliography lists the Newell, Shaw and Simon paper Report on a General Problem-Solving Program as RAND Paper P-1584 of February 1959 ^[3], and a 1959 report by the same three authors appears among the references on the program ^[1].

The move from the Logic Theorist to GPS was a move from one narrow task to a claim of generality. The Logic Theorist proved theorems; GPS was meant to be handed a description of a problem domain and to find its own way to a solution.

How it worked

In contrast to the earlier Logic Theorist, GPS worked with means-ends analysis ^[1]. The idea is to compare what you have with what you want, find the difference between them, and look for an operation that reduces that difference; if the operation cannot be applied yet, its preconditions become a new subgoal. The RAND report lists means-ends analysis and planning as the two general problem-solving techniques then making up the program's repertoire ^[2].

The user defined the objects and operations, and GPS generated heuristics, examined what inputs operations accepted and what outputs they produced, and created subgoals to approach the goal ^[1]. The report cites the separation of problem content from problem-solving technique as a way of increasing the generality of the program ^[2].

GPS solved simple problems, such as the Towers of Hanoi, that could be sufficiently formalised ^[1]. Puzzles of that kind suit the design well: the objects, the legal moves and the goal state can all be written down exactly, so the solver has something precise to reason about.

Limits

It could not solve real-world problems, because the search was easily lost in combinatorial explosion: the number of walks through the inferential digraph became computationally untenable ^[1]. A graph of inferences branches at every step, and without enough guidance the number of paths to examine grows far faster than the machine can follow. Being general also meant being weakly guided, and weak guidance is exactly what a large search space punishes.

Place in the field

The GPS paradigm eventually evolved into the Soar architecture for artificial intelligence ^[1]. The program is remembered less for the puzzles it solved than for the architecture it proposed: a body of domain knowledge on one side, a general problem-solving engine on the other, and a separation between the two that later work could build on.