Un grand merci a Carole Lailler pour sa relecture, ses commentaires et ses suggestions ainsi que pour les références qu’elle m’a envoyées.
Salut les internautes. Dans le cadre de la préparation de mon cours de l’an prochain sur les systèmes multi-agents, j’ai décidé de passer en revue rapidement l’histoire des systèmes multi-agents afin de donner une vision un peu plus complète du domaine aux étudiants de l’ENSTA. Ma principale source pour rédiger ce cours est le livre de Michael Wooldridge An introduction to multiagent systems, dont la référence se trouve en fin de billet.
J’ai décomposé l’histoire des systèmes multi-agents, qui est intimement liée à celle de l’intelligence artificielle, en quatre grandes périodes. La première court de l’article de Turing Computing machinery and Intelligence en 1950 jusqu’à l’apparition des premiers systèmes de tableaux noirs autour de 1975, dans le cadre du projet Hearsay. La seconde va jusqu’à l’apparition, au milieu des années 1980 et voit l’essor de l’intelligence artificielle distribuée pour résoudre des problèmes difficilement soluble pour un unique agent intelligent. À la fin des années 1980 apparaissent des agents rationnels ne cherchant pas spécifiquement le bien commun. Cette période court jusque dans les années 1995. On voit apparaître les bases des systèmes multi-agents tels que nous les connaissons aujourd’hui. À partir de cette période, les systèmes multi-agents sont un domaine assez établi pour que ce paradigme soit utilisé dans de nombreux domaines, allant de la négociation automatique à la simulation de sociétés.
L’intelligence mono agent (1950-1975)
Cette première ère de l’intelligence artificielle est marquée par une intelligence purement mono-agent. L’intelligence artificielle, dont le nom est inventé lors du workshop du Dartmouth College en 1956, se focalise sur la résolution de problèmes par des algorithmes, sans se poser la question de la coopération. On peut cependant noter un intérêt théorique pour le partage dans un des article d’un des pères de l’IA, Allen Newell en 19621:
Metaphorically we can think of a set of workers, all looking at the same blackboard: each is able to read everything that is on it, and to judge when he has something worthwhile to add to it. This conception is just that of Selfridge’s Pandemonium: a set of demons, each independently looking at the total situation and shrieking in proportion to what they see that fits their natures…
Cette métaphore ne sera cependant pas mise en application jusqu’en 1973, avec le projet Hearsay.
1975-1985 L’intelligence artificielle distribuée
Dans ses débuts, l’intelligence artificielle s’intéresse principalement à la résolution de problèmes. Les programmes d’intelligence artificielle à travers le monde se penchent sur des problèmes particulier, tel que l’inférence logique ou l’apprentissage, et tentent de construire des problèmes qui soient capables de résoudre ces problèmes. Le comportement de l’agent qui en résulte et sa proximité avec celle de l’humain ne sont pas vraiment le souci des chercheurs en IA, et la perspective d’un tel agent n’est évoquée que par les philosophes qui s’emparent du sujet et le traitent sous un autre angle. C’est dans ce contexte que les premiers programmes d’intelligence artificielle distribuée naissent. Le premier se nomme Hearsay, et se fixe pour objectif la reconnaissance de la parole. Ce problème est complexe, et fait encore l’objet d’une recherche intense, quoique les techniques sous-jascentes soient éloignées de celles de l’époque. L’un des principaux problèmes soulevés par l’équipe de Hearsay est le nombre de compétences nécessaires pour traduire un stimulus auditif en texte. En effet, il est nécessaire de traiter à la fois les règles phonologiques, phonétiques, le contexte, la syntaxe, et la sémantique (cet aspect n’ayant que peu à voir avec ce qui est nommé ainsi aujourd’hui). La création d’un système capable de traiter toutes ces problématiques paraît pour le moins complexe.
L’équipe se propose alors d’utiliser une autre méthode: en s’appuyant sur la description de Newell, ils créent le premier systèmes d’experts à base de tableau noir (l’appellation apparaît en 1980 dans Hearsay II). L’idée est la suivante: des agents ayant un chacun un domaine d’expertise doivent coopérer pour résoudre un problème. Il est trop complexe de construire un unique agent capable de résoudre le problème dans son ensemble. L’idée est donc de faire coopérer les spécialistes de plusieurs domaines en partageant une structure de donnée où sont inscrits les problèmes à résoudre et le résultat de chaque problème résolu. Lorsqu’un agent inoccupé voit un problème non résolu et qu’il peut soit le diviser en sous-problèmes soit le résoudre, il met un marqueur indiquant qu’il travaille dessus. Une fois le problème résolu, il l’inscrit sur le tableau, ce qui permet à un autre agent d’utiliser ce résultat pour résoudre un autre sous-problème.
Le projet évolue. Une autre problématique apparaît: comment faire en sorte de faire communiquer ce genre de systèmes sur plusieurs machines ? La tableau noir est une instance centrale, qui doit être immédiatement accessible pour tos les agents. Une solution est trouvée par l’équipe dans laquelle travaille Victor Lesser (déjà premier auteur de l’article sur Hearsay II). La nouvelle architecture permet d’avoir plusieurs tableaux noirs qui communiquent entre eux. Ces tableaux permettent ainsi de travailler localement avec des agents, tout en participant à un projet plus large et distribué.
En parallèle naît l’un des protocoles de coordination multiagents les plus connus: le Contract Net (ou réseau contractuel) qui permet aux agents de découper des tâches et d’en déléguer la résolution à d’autres agents, sous la forme d’une enchère simplifiée. Le protocole reporte un grand succès, et est adopté pour un certain nombre de problèmes d’allocation de ressource en raison de sa nature naturellement distribuée. Les différents travaux qui se développent autour de ces applications vont aussi donner lieu à la création d’un élément qui va permettre de structurer la communauté et de tisser des liens entre ces différents travaux: en 1980, le premier Workshop on Distributed Artificial Intelligence a lieu. Il se poursuivra à partir de cette date tous les deux ans puis tous les ans jusqu’en 1996. En 1997, c’est la conférence Autonomous Agents and Multi Agent Systems (AAMAS) qui prendra le relais.
Voilà comment naît la recherche sur les systèmes multi-agents. L’histoire ne s’arrête pas là et il y a beaucoup à dire sur ce domaine, mais je vous raconterai cela dans un futur billet. D’ici là, renseignez-vous, réfléchissez et surtout n’oubliez pas de rêver !
Bibliographie
Newell, A. (1962). Some problems of basic organization in problem-solving programs (No. RAND/RM-3283-PR). Rand corp santa monica ca.
Rosenschein, J. S., & Genesereth, M. R. (1988). Deals among rational agents. In Readings in Distributed Artificial Intelligence(pp. 227-234).
Turing, A.M (1950).Computing Machinery and Intelligence. Mind 49: 433-460
Wooldridge, M. (2009). An introduction to multiagent systems. John Wiley & Sons.
“Métaphoriquement, on peut penser à un ensemble de travailleurs, qui regardent tous le même tableau noir: chacun est capable de lire tout ce qu’il y a dessus, et de juger lorsqu’il y a quelque chose qui vaut la peine d’y être ajouté. Cette conception correspond exactement au Pandemonium de Selfridge: un ensemble de démons, considérant tous la situation globale et hurlant en fonction de ce qu’ils voient et de leur nature.” L’architecture Pandemonium est une architecture permettant de faire de la reconnaissance visuelle à partir de stimuli visuels ↩
