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. Computer programs are one component of software, which also includes software documentation, documentation and oth ...
created in 1959 by
Herbert A. Simon,
J. C. Shaw, and
Allen Newell
Allen Newell (March 19, 1927 – July 19, 1992) was a researcher in computer science and cognitive psychology at the RAND Corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Depart ...
(
RAND Corporation
The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is finance ...
) intended to work as a universal problem
solver machine. In contrast to the former
Logic Theorist
Logic Theorist is a computer program written in 1956 by Allen Newell, Herbert A. Simon, and Cliff Shaw.
, and It was the first program deliberately engineered to perform automated reasoning and is called "the first artificial intelligence prog ...
project, the GPS works with
means–ends analysis.
Overview
Any problem that can be expressed as a set of
well-formed formula
In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language. A formal language can ...
s (WFFs) or
Horn clauses, and that constitute a directed graph with one or more sources (that is, axioms) and sinks (that is, desired conclusions), can be solved, in principle, by GPS. Proofs in the
predicate logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
and Euclidean geometry problem spaces are prime examples of the domain the 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 science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from prem ...
machines. GPS was the first computer program which separated its
knowledge
Knowledge can be defined as awareness of facts or as practical skills, and may also refer to familiarity with objects or situations. Knowledge of facts, also called propositional knowledge, is often defined as true belief that is distin ...
of problems (rules represented as input data) from its strategy of how to solve problems (a generic solver
engine
An engine or motor is a machine designed to convert one or more forms of energy into mechanical energy.
Available energy sources include potential energy (e.g. energy of the Earth's gravitational field as exploited in hydroelectric power ...
). 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 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
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...
s by
means-ends analysis 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 intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech ...
.
See also
*
Logic Theorist
Logic Theorist is a computer program written in 1956 by Allen Newell, Herbert A. Simon, and Cliff Shaw.
, and It was the first program deliberately engineered to perform automated reasoning and is called "the first artificial intelligence prog ...
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
The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is finance ...
, 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
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technolog ...
.)
* Newell, A., and Simon, H. A. (1972) Human problem solving Englewood Cliffs, NJ: Prentice-Hall
*
{{Computable knowledge
History of artificial intelligence