General Problem Solver
In plain wordsA 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap.
A program developed by Allen NewellAllen Newell, prop. n.: An American computer scientist who, with Herbert Simon, wrote early AI programs that solved problems the way people do, and who sought a single theory of how the mind works., Cliff Shaw and Herbert A. SimonHerbert A. Simon, prop. n.: An American scientist of decision-making who, with Allen Newell, wrote some of the first AI programs and argued that minds and computers both think by manipulating symbols. from 1957 as an attempt at a domain-independent problem solver. Problems were posed as objects, goals and operators that transform objects, and GPS attacked them by means–ends analysis: find the most important difference between the current state and the goal, select an operator relevant to reducing it, and, if that operator cannot yet be applied, set up a subgoal of making it applicable. The key design choice was to keep that strategy fixed and feed in each task's knowledge as data — tables of differences and of the operators that reduce them — so one program could take on logic proofs, the Tower of Hanoi and river-crossing puzzles. It shaped later automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., including the STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true. planner, and cognitive architectures such as Soar; its limits were the labor of formalizing real problems by hand and the combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers. of search on larger ones.
GPS showed that one search strategy could work across many puzzles, provided someone first described each puzzle for it.
Origin
Introduced in Newell, Shaw and Simon's 'Report on a General Problem-Solving Program', presented at the International Conference on Information Processing in Paris in 1959. It grew out of the Logic TheoristLogic Theorist, prop. n.: A 1956 computer program that proved theorems from a classic logic textbook by searching cleverly rather than trying every possibility. Many historians count it as the first AI program. and from the authors' think-aloud studies of how people solve problems.
Usage note
Its generality covered only formalized, well-defined problems; the distance between that and everyday problem solving became a lasting theme in critiques of symbolic AIsymbolic AI, n.: An approach to AI that writes knowledge down as human-readable symbols and rules, such as 'every bird has wings', and reasons by manipulating them step by step instead of learning patterns from data..
Related
- Logic TheoristLogic Theorist, prop. n.: A 1956 computer program that proved theorems from a classic logic textbook by searching cleverly rather than trying every possibility. Many historians count it as the first AI program.
- automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
- STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.
- symbolic AIsymbolic AI, n.: An approach to AI that writes knowledge down as human-readable symbols and rules, such as 'every bird has wings', and reasons by manipulating them step by step instead of learning patterns from data.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- physical symbol system hypothesisphysical symbol system hypothesis, n.: The 1976 claim by two AI pioneers that a machine which stores and rearranges symbols according to rules has everything needed for general intelligence, and that anything generally intelligent must be such a machine.
Sources
- Newell, A., Shaw, J. C. & Simon, H. A. (1959). Report on a General Problem-Solving Program. Proceedings of the International Conference on Information Processing, Paris: UNESCO.
Mentioned in
Allen NewellAllen Newell, prop. n.: An American computer scientist who, with Herbert Simon, wrote early AI programs that solved problems the way people do, and who sought a single theory of how the mind works., automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., good old-fashioned AIgood old-fashioned AI, n.: A nickname for the classic style of AI, dominant from the 1950s to the 1980s, that tried to make computers intelligent by writing knowledge and rules down by hand., Herbert A. SimonHerbert A. Simon, prop. n.: An American scientist of decision-making who, with Allen Newell, wrote some of the first AI programs and argued that minds and computers both think by manipulating symbols., Logic TheoristLogic Theorist, prop. n.: A 1956 computer program that proved theorems from a classic logic textbook by searching cleverly rather than trying every possibility. Many historians count it as the first AI program., task decompositiontask decomposition, n.: Breaking a big, vague job into smaller, concrete steps that can each be done and checked — the way a recipe splits a meal into stages., means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken., RAND CorporationRAND Corporation, prop. n.: An American research organization, long funded mainly by the US government, where early AI programs were written and which now advises governments on AI and security.