General Problem Solver
Der General Problem Solver (GPS) ist eine von Herbert A. Simon und Allen Newell ab 1957 entwickelte Software zur Realisierung einer allgemeinen Problemlösungsmethode im Rahmen der damals beginnenden Forschung zur Künstlichen Intelligenz. Die Software wurde von Simon und Newell in dem Artikel GPS, a Program That Simulates Human Thought beschrieben. In diesem Versuch, der schließlich als gescheitert angesehen wurde, flossen sowohl kognitionswissenschaftliche Aspekte als auch Methoden zur mathematischen Formalisierung von Problemen und Problemlösen. Die Software und das entwickelte theoretische Rahmenwerk hatte maßgeblichen Einfluss auf die Entwicklung der kognitiven Psychologie sowie der Künstlichen Intelligenz. Das Scheitern des allgemeinen Problemlösungsansatzes führte schließlich zur Entwicklung von Expertensystemen, die auf einem engeren Wissensgebiet zu besseren Ergebnissen gelangen sollten.
Arbeitsweise
Der GPS basierte auf dem Prinzip der Problemreduktion. Dabei wird ein Problem so in Teilprobleme zerlegt, dass es gelöst werden kann, indem man die gewonnenen einzelnen Teilprobleme löst. Diese Methode steht der sogenannten Problemtransformation gegenüber, bei der ein Problem in ein anderes Problem transformiert wird, dessen Lösung man schon kennt oder leichter finden kann. Aufgrund der Anwendung von Problemreduktion lässt sich der GPS der Gruppe der zustandsbasierten Problemlöser zuordnen: Ein Problem wird dabei durch einen Raum möglicher Zustände formalisiert, zwischen denen mittels Operationen Übergänge herbeigeführt werden. Der Einsatz der Operationen zielte im Falle von GPS eben auf Problemreduktion.
Eine Reihe von Autoren hat später dargelegt, dass dieser Ansatz keineswegs so allgemein war, wie man in der ersten Euphorie und aufgrund des anmaßenden Namens geglaubt hatte. So kommentierte etwa McDermott in einem berühmt gewordenen Artikel Artificial Intelligence Meets Natural Stupidity? nicht ohne Spott, dass das Programm wohl anstelle von GPS besser LFGNS (Local Feature Guided Network Searcher) hätte heißen sollen. Tatsächlich konnte GPS nur auf wohldefinierte Probleme wie etwa das Beweisen simpler Theoreme aus Logik und Geometrie, Wortpuzzle oder Schach angewandt werden.
Beispiel
Simon und Newell geben ein Beispiel für die Lösung des logischen Problems der Transformation von L1= R*(-P ⇒ Q) in L2=(Q \/ P)*R (Newell & Simon, 1972, Seite 420). Dieses Beispiel gibt einen Einblick in die Arbeitsweise des GPS:
- 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
Literatur
- A. Newell, J. C. Shaw und H. A. Simon: Report on a general problem-solving program (1958) online (PDF)
- A. Newell und H. A. Simon (1961). GPS, a program that simulates human thought, in: E. Feigenbaum und J. Feldmann, Hrsg. (1995) Computers and Thought, ISBN 0262560925.
- A. Newell und H. A. Simon (1972). Human problem solving. Englewood Cliffs, N.J., Prentice-Hall.