Résolution de problèmes généraux
Le General Problem Solver (GPS) est un programme informatique créé en 1957 par Herbert Simon , JC Shaw et Allen Newell dans le but de construire une machine capable de résoudre des problèmes généraux. Tout problème symbolique formel peut être résolu, en principe, par GPS. Par exemple : prouver des théorèmes , résoudre des problèmes géométriques, travailler avec la logique propositionnelle et jouer aux échecs . Il était basé sur les travaux théoriques antérieurs de Simon et Newell sur les machines logiques .. Le GPS a été le premier programme informatique dans lequel la connaissance des problèmes était séparée de sa stratégie sur la façon de les résoudre. Il a été implémenté dans le langage de programmation IPL ( Information Processing Language ) .
Le GPS a réussi à résoudre des problèmes simples, comme le problème de la tour de Hanoï , qui pouvaient être exprimés de manière suffisamment formalisée, mais il ne pouvait pas résoudre les problèmes du monde réel.
L'utilisateur a défini les objets et les opérations pouvant être faites avec et sur les objets et le GPS a généré l' heuristique par une analyse des moyens et des objectifs, afin de résoudre les problèmes. Pour ce faire, il s'est concentré sur les opérations disponibles, en trouvant quelles entrées étaient acceptables et quels résultats ont été générés. Des sous-objectifs ont ensuite été créés pour se rapprocher de plus en plus de l'objectif précédemment défini.
Le paradigme GPS a évolué vers l' architecture symbolique-cognitive SOAR ( State Operator And Result ).
Processus
Simon et Newell proposent l'exemple de la transformation de la proposition logique L1= R*(-P => Q) en L2=(Q \/ P)*R (Newell et Simon, 1972, page 420). Cette transformation serait traitée par le GPS comme suit :
- Objectif 1 : Transformer L1 en L0
- Objectif 2 : Réduire l'écart entre L1 et L0
- Objectif 3 : Appliquer R1 à L1
- Objectif 4 : Transformer L1 en condition (R1)
- Produit L2 : (-P => Q) *R
- Objectif 5 : Transformer L2 en L0
- Objectif 6 : Réduire l'écart entre (L2) et (L0)
- Objectif 7 : Appliquer R5 à (L2)
- Objectif 8 : Transformer (L2) en condition (R5)
- Objectif 9 : Réduire l'écart entre (L2) et (R5)
- Rejeté : pas plus simple que l'objectif 6
- Objectif 10 : Appliquer R6 à (N2)
- Objectif 11 : Transformer (L2) en condition (R5)
- Produit L3 : (P \/ Q) *R
- Objectif 12 : Transformer L3 en L0
- Objectif 13 : Réduire l'écart entre (L3) et (L0)
- Objectif 14 : Appliquer R1 à (L3)
- Objectif 15 : Transformer (L3) en condition (R1)
- Produit L4 : (Q \/ P)*R
- Objectif 16 : Transformer L4 en L0
- Identifier, CQFD
Références
- Newell, A.; Shaw, JC; Simon, H.A. (1959). Rapport sur un programme général de résolution de problèmes. Actes de la Conférence internationale sur le traitement de l'information . pp. 256-264.
- A. Newell et H.A. Simon (1961). GPS, un programme qui simule la pensée humaine , dans E. Feigenbaum et J. Feldmann, Hrsg. (1995) Ordinateurs et pensée , ISBN 0262560925 .
- En ligneNewell, A. (1963). Un guide du programme général de résolution de problèmes GPS-2-2 . RAND Corporation, Santa Monica, Californie. Rapport technique n° RM-3337-PR.
- Ernst, GW & Newell, A. (1969). GPS : une étude de cas en généralité et en résolution de problèmes . Presse académique. (Version révisée d'une thèse d'Ernst de 1966, Carnegie Institute of Technology.)
- Newell, A., et Simon, HA (1972) Résolution de problèmes humains . Falaises d'Englewood, New Jersey : Prentice Hall.
- Norvig, Pierre. (1992). Paradigmes de la programmation en intelligence artificielle : études de cas en Common Lisp . pages 109-110.
