General Problem Solver: Difference between revisions
From HandWiki
imported>MedAI link |
change |
||
| Line 1: | Line 1: | ||
{{Short description|Computer program created in 1959}} | |||
'''General Problem Solver''' ('''GPS''') is a [[Computer program|computer program]] created in 1957 by [[Biography:Herbert A. Simon|Herbert A. Simon]], [[Biography:Cliff Shaw|J. C. Shaw]], and [[Biography:Allen Newell|Allen Newell]] ([[Organization:RAND Corporation|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]].<ref name="Nilsson2009">{{cite book|author=Nils J. Nilsson|title=The Quest for Artificial Intelligence|url=https://books.google.com/books?id=nUJdAAAAQBAJ|date=30 October 2009|publisher=Cambridge University Press|isbn=978-1-139-64282-8|pages=121–}}</ref> | '''General Problem Solver''' ('''GPS''') is a [[Computer program|computer program]] created in 1957 by [[Biography:Herbert A. Simon|Herbert A. Simon]], [[Biography:Cliff Shaw|J. C. Shaw]], and [[Biography:Allen Newell|Allen Newell]] ([[Organization:RAND Corporation|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]].<ref name="Nilsson2009">{{cite book|author=Nils J. Nilsson|title=The Quest for Artificial Intelligence|url=https://books.google.com/books?id=nUJdAAAAQBAJ|date=30 October 2009|publisher=Cambridge University Press|isbn=978-1-139-64282-8|pages=121–}}</ref> | ||
==Overview== | ==Overview== | ||
Any problem that can be expressed as a set of [[Well-formed formula|well-formed formula]]s (WFFs) or [[Horn clause]]s, and that | Any problem that can be expressed as a set of [[Well-formed formula|well-formed formula]]s (WFFs) or [[Horn clause]]s, and that constitutes a [[Directed graph|directed graph]] with one or more sources (that is, [[Axiom|hypothese]]s) and sinks (that is, desired conclusions), can be solved, in principle, by GPS. Proofs in the predicate logic and [[Euclidean geometry]] 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]] machines. GPS was the first computer program that separated its [[Philosophy:Knowledge|knowledge]] of problems (rules represented as input data) from its strategy of how to solve problems (a generic solver [[Software engine|engine]]). GPS was implemented in the third-order programming language, [[Information Processing Language|IPL]].<ref name="Norvig1992">{{cite book |last = Norvig |first = Peter |title = Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp |location = San Francisco, California |publisher = Morgan Kaufmann |year = 1992 |url = https://books.google.com/books?id=QzGuHnDhvZIC |pages = 109–149 |isbn = 978-1-55860-191-8 }}</ref> | ||
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|combinatorial explosion]]. Put another way, the number of "walks" through the inferential digraph became computationally untenable. (In practice, even a straightforward [[State space search|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* search algorithm|A*]] and IDA*). | 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|combinatorial explosion]]. Put another way, the number of "walks" through the inferential digraph became computationally untenable. (In practice, even a straightforward [[State space search|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* search algorithm|A*]] and IDA*). | ||
The user defined objects and operations that could be done on the objects, and GPS generated [[Heuristic|heuristic]]s by [[Means–ends analysis|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 user defined objects and operations that could be done on the objects, and GPS generated [[Heuristic|heuristic]]s by [[Means–ends analysis|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. | ||
| Line 11: | Line 13: | ||
==See also== | ==See also== | ||
* [[Logic Theorist]] | * [[Logic Theorist]] | ||
* [[History of artificial intelligence]] | |||
==References== | ==References== | ||
{{Reflist}} | {{Reflist}} | ||
* Newell, A.; Shaw, J.C.; Simon, H.A. (1959). [http://bitsavers.informatik.uni-stuttgart.de/pdf/rand/ipl/P-1584_Report_On_A_General_Problem-Solving_Program_Feb59.pdf Report on a general problem-solving program. ''Proceedings of the International Conference on Information Processing.''] pp. 256–264. | * Newell, A.; Shaw, J.C.; Simon, H.A. (1959). [http://bitsavers.informatik.uni-stuttgart.de/pdf/rand/ipl/P-1584_Report_On_A_General_Problem-Solving_Program_Feb59.pdf Report on a general problem-solving program. ''Proceedings of the International Conference on Information Processing.''] pp. 256–264. | ||
* Newell, A. (1963). [https://stacks.stanford.edu/file/druid:zk239tp3547/zk239tp3547.pdf A Guide to the General Problem-Solver Program GPS-2-2]. | * Newell, A. (1963). [https://stacks.stanford.edu/file/druid:zk239tp3547/zk239tp3547.pdf A Guide to the General Problem-Solver Program GPS-2-2]. [[Organization:RAND Corporation|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.) | * 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 | * 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 }} | * {{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 }} | ||
[[Category:History of artificial intelligence]] | [[Category:History of artificial intelligence]] | ||
{{Sourceattribution|General Problem Solver}} | {{Sourceattribution|General Problem Solver}} | ||
Latest revision as of 23:48, 13 April 2026
Short description: Computer program created in 1959
General Problem Solver (GPS) is a computer program 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.[1]
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 problem spaces are prime examples of the domain of applicability of GPS. It was based on Simon and Newell's theoretical work on logic machines. GPS was the first computer program that separated its knowledge 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.[2]
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 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.
See also
References
- ↑ Nils J. Nilsson (30 October 2009). The Quest for Artificial Intelligence. Cambridge University Press. pp. 121–. ISBN 978-1-139-64282-8. https://books.google.com/books?id=nUJdAAAAQBAJ.
- ↑ Norvig, Peter (1992). Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp. San Francisco, California: Morgan Kaufmann. pp. 109–149. ISBN 978-1-55860-191-8. https://books.google.com/books?id=QzGuHnDhvZIC.
- 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
- Noyes, James L. (1992). Artificial Intelligence with Common Lisp. Lexington: D. C. Heath. pp. 343–371. ISBN 978-0-669-19473-9. https://books.google.com/books?id=eIbBm7wvTjcC.
 |  |
