General Problem Solver

El General Problem Solver (GPS), en espanyol Solucionador General de Problemes, és un programa d'ordenador creat en 1957 per Herbert Simon, J.C. Shaw, i Allen Newell en l'objectiu de construir una màquina capaç de resoldre problemes de caràcter general. Qualsevol problema simbòlic formal pot ser resolt, en principi, per el GPS. Per eixemple: provar teoremas, resoldre problemes geomètrics, treballar en llògica proposicional i jugar al escacs. Es basava en el treball teòric previ de Simon i Newell sobre màquines llògicas. El GPS va ser el primer programa de computadora en el que es va separar el coneiximent dels problemes de la seua estratègia sobre cóm resoldre'ls. Es va implementar en el llenguage de programació IPL (Information Processing Language).

El GPS va conseguir resoldre problemes senzills, com el de les Torres de Hanói, que podia ser expressat d'una manera lo suficientment formalisada, pero no podia resoldre els problemes del món real.

L'usuari definia els objectes i les operacions que es podria fer en i sobre els objectes i el GPS generava la heurística per mig d'un anàlisis dels mijos i els objectius, a fi de resoldre els problemes. Per a això, se centrava en les operacions disponibles, trobant qué entrades eren acceptables, i quins resultats es generaven. Es creaven llavors sub-objectius per a conseguir aproximar-se més i més a la meta anteriorment definida.

El paradigma GPS va evolucionar fins a convertir-se en l'arquitectura simbòlic-cognitiva SOAR (State Operator And Result).

Procés

Simon i Newell proponen l'eixemple sobre cóm transformar la proposició llògica L1= R*(-P => Q) en L2=(Q / P)R (Newell i Simon, 1972, pàgina 420). Esta transformació seria processada per el GPS de la següent manera:

• Objectiu 1: Transforma L1 en L0
• Objectiu 2: Reduïx la diferència entre L1 i L0
• Objectiu 3: Aplica R1 a L1
• Objectiu 4: Transforma L1 en una condició (R1)
• Producte L2: (-P => Q) R
• Objectiu 5: Transforma L2 en L0
• Objectiu 6: Reduïx la diferència entre (L2) i (L0)
• Objectiu 7: Aplica R5 a (L2)
• Objectiu 8: Transforma (L2) en una condició (R5)
• Objectiu 9: Reduïx la diferència entre (L2) i (R5)
• Rebujat: No és més simple que l'Objectiu 6
• Objectiu 10: Aplica R6 a (L2)
• Objectiu 11: Transforma (L2) en una condició (R5)
• Producte L3: (P / Q) R
• Objectiu 12: Transforma L3 en L0
• Objectiu 13: Reduïx la diferència entre (L3) i (L0)
• Objectiu 14: Aplica R1 a (L3)
• Objectiu 15: Transforma (L3) en una condició (R1)
• Producte L4: (Q / P)R
• Objectiu 16: Transforma L4 en L0
• Identifica, QED

Referències

• 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.

• A. Newell i H. A. Simon (1961). GPS, a program that simulates human thought, en E. Feigenbaum i J. Feldmann, Hrsg. (1995) Computers and Thought, ISBN 0262560925.

• Newell, A. (1963). A guide to the general problem-solver program GPS-2-2. RAND Corporation, Santa Mónica, Califòrnia. Technical Report No. RM-3337-PR.

• Ernst, G.W. i Newell, A. (1969). GPS: a case study in generality and problem solving. Academic Press. (versió revisada d'una dissertació de Ernst de 1966, Carnegie Institute of Technology.)

• Newell, A., i Simon, H. A. (1972) Human problem solving. Englewood Cliffs, NJ: Prentice-Hall.

• Norvig, Peter. (1992). Paradigms of artificial intelligence programming: case studies in Common Lisp. pp 109-110.

Vore també

• Sistema expert
• Resolució numèrica d'equacions no llineals