General Problem Solver

from Wikipedia, the free encyclopedia

The General Problem Solver ( GPS ) is software developed by Herbert A. Simon and Allen Newell from 1957 to implement a general problem-solving method as part of the research on artificial intelligence that was beginning at that time . The software was described by Simon and Newell in the article GPS, a Program That Simulates Human Thought . In this attempt, which was ultimately regarded as a failure, both cognitive science aspects and methods for the mathematical formalization of problems and problem solving were incorporated . The software and the developed theoretical framework had a decisive influence on the development of cognitive psychology and artificial intelligence. The failure of the general problem-solving approach ultimately led to the development of expert systems that were supposed to achieve better results in a narrower field of knowledge.

Working method

The GPS was based on the principle of problem reduction . A problem is broken down into sub-problems in such a way that it can be solved by solving the individual sub-problems obtained. This method is opposed to the so-called problem transformation , in which one problem is transformed into another problem whose solution is already known or can be found more easily. Due to the application of problem reduction, the GPS can be assigned to the group of state-based problem solvers: A problem is formalized by a space of possible states, between which transitions are brought about by means of operations. In the case of GPS, the use of the operations was aimed at reducing the problem.

A number of authors have later stated that this approach was by no means as general as was believed in the initial euphoria and due to the presumptuous name. For example, McDermott commented in a famous article Artificial Intelligence Meets Natural Stupidity? not without ridicule that the program should have been called LFGNS (Local Feature Guided Network Searcher) instead of GPS. In fact, GPS could only be applied to well-defined problems such as proving simple theorems of logic and geometry, word puzzles, or chess.

example

Simon and Newell give an example for the solution of the logical problem of the transformation from L1 = R * (- P ⇒ Q) into L2 = (Q \ / P) * R (Newell & Simon, 1972, page 420). This example gives an insight into how the GPS works:

  • Goal 1: Transform L1 into L0
  • Goal 2: Reduce difference between L1 and L0
  • Goal 3: Apply R1 to L1
  • Goal 4: Transform L1 into condition (R1)
  • Produce L2: (-P ⇒ Q) * R
  • Goal 5: Transform L2 into L0
  • Goal 6: Reduce difference between left (L2) and left (L0)
  • Goal 7: Apply R5 to left (L2)
  • Goal 8: Transform left (L2) into condition (R5)
  • Goal 9: Reduce difference between left (L2) and condition (R5)
  • Rejected: No easier than Goal 6
  • Goal 10: Apply R6 to left (L2)
  • Goal 11: Transform left (L2) into condition (R5)
  • Produce L3: (P \ / Q) * R
  • Goal 12: Transform L3 into L0
  • Goal 13: Reduce difference between left (L3) and left (L0)
  • Goal 14: Apply R1 to left (L3)
  • Goal 15: Transform left (L3) into condition (R1)
  • Produce L4: (Q \ / P) * R
  • Goal 16: Transform L4 into L0
  • Identical, QED

literature

  • A. Newell, JC Shaw and HA Simon: Report on a general problem-solving program (1958) online (PDF)
  • A. Newell and HA Simon (1961). GPS, a program that simulates human thought , in: E. Feigenbaum and J. Feldmann, eds. (1995) Computers and Thought , ISBN 0262560925 .
  • A. Newell and HA Simon (1972). Human problem solving . Englewood Cliffs, NJ, Prentice-Hall.