Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
General Problem Solver
Summary
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.
Any problem that can be expressed as a set of well-formed formulas (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 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 machines. GPS was the first computer program which 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.
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 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.