General Problem Solver (GPS) is a
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. It is one component of software, which also includes software documentation, documentation and other intangibl ...
created in 1957 by
Herbert A. Simon,
J. C. Shaw, and
Allen Newell (
RAND Corporation) intended to work as a universal problem
solver machine. In contrast to the former
Logic Theorist project, the GPS works with
means–ends analysis
Means–ends analysis (MEA) is a problem solving technique used commonly in artificial intelligence (AI) for limiting search in AI programs.
It is also a technique used at least since the 1950s as a creativity tool, most frequently mentioned in e ...
.
Overview
Any problem that can be expressed as a set of
well-formed formulas (WFFs) or
Horn clauses, and that constitutes a
directed graph with one or more sources (that is,
hypotheses) and sinks (that is, desired conclusions), can be solved, in principle, by GPS. Proofs in the
predicate logic and
Euclidean geometry
Euclidean geometry is a mathematical system attributed to ancient Greek mathematics, Greek mathematician Euclid, which he described in his textbook on geometry, ''Euclid's Elements, Elements''. Euclid's approach consists in assuming a small set ...
problem spaces are prime examples of the domain of applicability of GPS. It was based on Simon and Newell's theoretical work on
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
machines. GPS was the first computer program that separated its
knowledge
Knowledge is an Declarative knowledge, awareness of facts, a Knowledge by acquaintance, familiarity with individuals and situations, or a Procedural knowledge, practical skill. Knowledge of facts, also called propositional knowledge, is oft ...
of problems (rules represented as input data) from its strategy of how to solve problems (a generic solver
engine). GPS was implemented in the third-order programming language,
IPL.
While GPS solved simple problems such as the
Towers of Hanoi that could be sufficiently formalized, it could not solve any real-world problems because the search was easily lost in the
combinatorial explosion. Put another way, the number of "walks" through the inferential digraph became computationally untenable. (In practice, even a straightforward
state space search such as the Towers of Hanoi can become computationally infeasible, albeit judicious prunings of the state space can be achieved by such elementary AI techniques as
A* and
IDA*).
The user defined objects and operations that could be done on the objects, and GPS generated
heuristics by
means–ends analysis
Means–ends analysis (MEA) is a problem solving technique used commonly in artificial intelligence (AI) for limiting search in AI programs.
It is also a technique used at least since the 1950s as a creativity tool, most frequently mentioned in e ...
in order to solve problems. It focused on the available operations, finding what inputs were acceptable and what outputs were generated. It then created subgoals to get closer and closer to the goal.
The GPS paradigm eventually evolved into the
Soar architecture for
artificial intelligence
Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
.
See also
*
Logic Theorist
References
* Newell, A.; Shaw, J.C.; Simon, H.A. (1959)
Report on a general problem-solving program. ''Proceedings of the International Conference on Information Processing.'' pp. 256–264.
* Newell, A. (1963)
A Guide to the General Problem-Solver Program GPS-2-2 RAND Corporation, Santa Monica, California. Technical Report No. RM-3337-PR.
* Ernst, G.W. and Newell, A. (1969). ''GPS: a case study in generality and problem solving.'' Academic Press. (Revised version of Ernst's 1966 dissertation,
Carnegie Institute of Technology.)
* Newell, A., and Simon, H. A. (1972) Human problem solving Englewood Cliffs, NJ: Prentice-Hall
* {{cite book , last = Noyes , first = James L. , title = Artificial Intelligence with Common Lisp , location =
Lexington , publisher = D. C. Heath , year = 1992 , pages = 343–371 , url = https://books.google.com/books?id=eIbBm7wvTjcC , isbn = 978-0-669-19473-9
History of artificial intelligence