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 execute. Computer programs are one component of software, which also includes documentation and other intangible components. A computer progra ...

created in 1959 by Herbert A. Simon,

J. C. Shaw John Clifford Shaw (February 23, 1922 – February 9, 1991) was a systems programmer at the RAND Corporation. He is a coauthor of the first artificial intelligence program, the Logic Theorist, and was one of the developers of General Problem Solv ...

, 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 Departmen ...

(

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 financ ...

) intended to work as a universal problem

solver A solver is a piece of mathematical software, possibly in the form of a stand-alone computer program or as a software library, that 'solves' a mathematical problem. A solver takes problem descriptions in some sort of generic form and calculates t ...

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 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 be ...

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 quanti ...

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 premis ...

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 disti ...

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 The Tower of Hanoi (also called The problem of Benares Temple or Tower of Brahma or Lucas' Tower and sometimes pluralized as Towers, or simply pyramid puzzle) is a mathematical game or puzzle consisting of three rods and a number of disks of va ...

that could be sufficiently formalized, it could not solve any real-world problems because search was easily lost in the

combinatorial explosion In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to ...

. 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* Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth ...

). 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 immediat ...

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 machine A machine is a physical system using Power (physics), power to apply Force, forces and control Motion, moveme ...

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

, 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 Technology ...

.) * Newell, A., and Simon, H. A. (1972) Human problem solving Englewood Cliffs, NJ: Prentice-Hall * {{Computable knowledge History of artificial intelligence

Overview

See also

References