Résolution des problèmes généraux - General Problem Solver

General Problem Solver ( GPS ) est un programme informatique créé en 1959 par Herbert A. Simon , JC Shaw et Allen Newell ( RAND Corporation ) destiné à fonctionner comme une machine universelle de résolution de problèmes . Contrairement à l'ancien projet Logic Theorist , le GPS fonctionne avec une analyse des moyens-fins .

Aperçu

Tout problème qui peut être exprimé sous la forme d'un ensemble de formules bien formées (WFF) ou de clauses de Horn , et qui constituent un graphe dirigé avec une ou plusieurs sources (c'est-à-dire des axiomes) et des puits (c'est-à-dire des conclusions souhaitées), peut être résolu, en principe, par GPS. Les preuves dans les espaces problématiques de la logique des prédicats et de la géométrie euclidienne sont des exemples parfaits du domaine de l'applicabilité du GPS. Il était basé sur les travaux théoriques de Simon et Newell sur les machines logiques . GPS a été le premier programme informatique à séparer sa connaissance des problèmes (règles représentées comme des données d'entrée) de sa stratégie de résolution de problèmes (un moteur de résolution générique ). Le GPS a été implémenté dans le langage de programmation du troisième ordre, IPL .

Alors que le GPS résolvait des problèmes simples tels que les tours de Hanoi qui pouvaient être suffisamment formalisés, il ne pouvait résoudre aucun problème du monde réel car la recherche était facilement perdue dans l' explosion combinatoire . En d'autres termes, le nombre de "promenades" dans le digraphe inférentiel est devenu intenable du point de vue du calcul. (En pratique, même une simple recherche dans l'espace d'états telle que les tours de Hanoi peut devenir irréalisable sur le plan informatique, bien que des élagages judicieux de l'espace d'états puissent être réalisés par des techniques d'IA élémentaires telles que A * et IDA * ).

L'utilisateur a défini des objets et des opérations qui pourraient être effectuées sur les objets, et des heuristiques générées par GPS par analyse des moyens-fins afin de résoudre des problèmes. Il s'est concentré sur les opérations disponibles, sur les intrants acceptables et sur les extrants générés. Il a ensuite créé des sous-objectifs pour se rapprocher de plus en plus de l'objectif.

Le paradigme GPS a finalement évolué vers l' architecture Soar pour l' intelligence artificielle .

Voir également

• Théoriste de la logique

Les références

• Newell, A .; Shaw, JC; Simon, HA (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. 256-264.
• Newell, A. (1963). 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 et Newell, A. (1969). GPS: une étude de cas en généralité et résolution de problèmes. Presse académique. (Version révisée de la thèse d'Ernst en 1966, Carnegie Institute of Technology .)
• Newell, A., et Simon, HA (1972) Résolution de problèmes humains Englewood Cliffs, NJ: Prentice-Hall
• Noyes, James L. (1992). Intelligence artificielle avec Common Lisp . Lexington : DC Heath. pp. 343–371. ISBN   978-0-669-19473-9 .