Qu’était le General Problem Solver, et comment tentait-il de résoudre n’importe quel problème?

Le General Problem Solver (GPS) était un programme d’Allen Newell, Cliff Shaw et Herbert Simon, commencé vers 1957 et décrit en entier pour la première fois dans un rapport daté de décembre 1958, qui tentait de résoudre bien des types de problèmes avec une seule méthode. Il comparait où il en était avec où il voulait arriver, choisissait une action qui réduirait l’écart et découpait les buts difficiles en sous-buts plus faciles, une stratégie appelée analyse moyens-fins.

Qu’était le General Problem Solver, et comment tentait-il de…

Après que leur Logic Theorist eut démontré des théorèmes de logique, Allen Newell, Herbert Simon et Cliff Shaw se sont posé une question plus vaste. Leur premier programme ne connaissait que la logique; ses astuces étaient liées à ce seul sujet. Un même programme pourrait-il posséder des compétences générales de résolution de problèmes et les appliquer à n’importe quoi, pourvu qu’on lui décrive le problème?

Leur réponse a été le General Problem Solver (résolveur général de problèmes), ou GPS. Son nom était une déclaration d’ambition. Il n’a pas été à la hauteur du mot « général », mais sa conception a façonné la recherche en IA pendant des décennies.

Quand et où il a été créé

La même équipe qui avait créé le Logic Theorist a créé le GPS : Newell et Shaw à la RAND Corporation de Santa Monica, en Californie, et Simon au Carnegie Institute of Technology de Pittsburgh. Les sources donnent des dates différentes. Bien des histoires datent le programme de 1957, année où le travail a commencé. La première description complète, un document de la RAND intitulé « Report on a General Problem-Solving Program », est datée du 30 décembre 1958 et a été révisée le 9 février 1959. Elle a ensuite paru en 1959 dans les actes publiés d’un congrès international d’informatique, l’International Conference on Information Processing, et c’est pourquoi certaines références présentent le GPS comme un programme de 1959.

Le rapport appelle le programme GPS-I. Il était écrit en IPL, le langage de traitement de listes que l’équipe avait créé pour le Logic Theorist.

D’où venait l’idée

Le GPS est né d’une expérience de psychologie. L’équipe a demandé à des étudiants universitaires de résoudre des problèmes de logique symbolique en réfléchissant à voix haute, en disant tout ce qui leur passait par la tête. Les enregistrements de ces séances montraient une constante : les gens ne cherchaient pas au hasard. Ils se demandaient sans cesse ce qui différait entre ce qu’ils avaient et ce qu’ils voulaient, et quel outil pourrait combler cet écart.

Le GPS a été conçu pour imiter ce comportement le plus fidèlement possible. Newell, Shaw et Simon y voyaient une théorie de la pensée humaine écrite sous forme de programme, et un outil pratique de résolution de problèmes.

Comment il fonctionnait

Le GPS décrivait chaque problème dans les mêmes termes :

Les objets : les situations ou les choses en jeu, comme une expression logique, une équation ou une position aux échecs.
Les opérateurs : les actions qui transforment un objet en un autre. Le rapport compare un opérateur à une scie qui transforme des billots en planches.
Les différences : les façons dont deux objets ne concordent pas.

Ses buts de base étaient de transformer l’objet A en objet B, d’appliquer un opérateur à un objet et de réduire une différence entre deux objets. Chaque but était associé à des méthodes, et chaque méthode pouvait créer de nouveaux sous-buts, qui faisaient de nouveau appel aux mêmes méthodes. Les programmeurs appellent ce genre d’autoréférence la récursivité.

La stratégie centrale est l’analyse moyens-fins. Le rapport l’illustre par l’exemple d’un parent qui doit conduire son enfant à la prématernelle. Voici le raisonnement, étape par étape :

Étape	Différence constatée	Opérateur choisi	Nouveau sous-but
1	L’enfant est à la maison, l’école est loin	Prendre la voiture	Rendre la voiture utilisable
2	La voiture ne démarre pas	Installer une nouvelle batterie	Se procurer une batterie
3	Pas de batterie sous la main	En faire poser une par un garage	Prévenir le garage
4	Le garage n’est pas au courant du problème	Utiliser le téléphone	(Appeler le garage)

Chaque rangée résout un plus petit problème qui débloque celui du dessus. Le GPS faisait exactement cela avec des expressions logiques et des identités trigonométriques. Dans un exemple du rapport, simplifier une expression trigonométrique jusqu’à 1 a demandé 33 buts et sous-buts.

Le GPS ajoutait aussi la planification. L’analyse moyens-fins ne regarde qu’une étape plus loin; le GPS pouvait donc d’abord résoudre une version simplifiée du problème, en laissant de côté certains détails, puis se servir de cette solution approximative comme guide pour la solution complète.

À essayer : choisissez une petite tâche, comme recevoir des gens à souper demain. Écrivez l’état final, puis notez la plus grande différence entre maintenant et ce moment-là, l’action qui la réduirait et le nouveau sous-but que cette action crée. Recommencez jusqu’à arriver à quelque chose que vous pouvez faire tout de suite.

Pourquoi il a compté

L’idée la plus durable du GPS était une séparation. Le programme gardait ses connaissances sur un problème particulier, les objets et les opérateurs, à part de sa stratégie générale de résolution. Pour travailler sur un nouveau type de casse-tête, on fournissait une nouvelle description, pas un nouveau programme. Cette division entre une base de connaissances et un moteur de raisonnement est devenue une conception courante dans les programmes d’IA ultérieurs, y compris les « systèmes experts » à base de règles, conçus pour saisir le savoir-faire d’un spécialiste.

Le GPS a aussi placé l’analyse moyens-fins et les sous-buts au cœur de la planification en IA, et il est devenu un exemple fondateur des sciences cognitives, l’étude de l’esprit comme système de traitement de l’information. Newell et Simon ont poursuivi cette approche pendant de nombreuses années, publiant en 1972 une vaste étude sur la résolution de problèmes chez l’humain, et une architecture d’IA ultérieure appelée Soar est issue de la même lignée de recherche.

Pourquoi le General Problem Solver ne pouvait-il pas résoudre des problèmes du monde réel?

Le GPS fonctionnait bien avec les casse-têtes qu’on peut décrire entièrement : un ensemble fixe d’objets, une liste connue d’opérateurs et un critère clair de réussite. Les démonstrations logiques, l’algèbre simple et des casse-têtes comme les tours de Hanoï entrent dans ce moule. La plupart des vrais problèmes, non. Planifier des vacances ou diagnostiquer une maladie fait intervenir des faits que personne n’a énumérés, des actions aux résultats incertains et des buts qui changent.

Même dans les casse-têtes formels, le GPS se heurtait à ce que les chercheurs appellent l’explosion combinatoire. Chaque choix en ouvre plusieurs autres, si bien que le nombre de chemins possibles se multiplie à chaque étape. Les auteurs eux-mêmes ont noté que leurs exemples ne montraient que le bon chemin et cachaient la part d’essais et d’erreurs, et ils ont décrit la résolution de problèmes comme une lutte contre des possibilités qui croissent de façon exponentielle.

Enfin, le GPS ne savait presque rien d’aucun sujet en particulier. Ses auteurs espéraient qu’il pourrait apprendre avec le temps des raccourcis utiles propres à chaque domaine, mais il n’y arrivait pas en pratique. La leçon que bien des chercheurs en ont tirée, c’est que les méthodes générales ne suffisent pas : une véritable expertise exige énormément de connaissances précises. Cette leçon a poussé l’IA vers les systèmes experts riches en connaissances et, aujourd’hui, vers des systèmes qui apprennent à partir de grandes quantités de données.