Système multi-agents

En informatique, un système multi-agent (SMA) est un système composé d'un ensemble d'agents (un processus, un robot, un être humain, une fourmi, etc.) actifs dans un certain environnement et interagissant selon certaines règles.

Un agent est une entité caractérisée par le fait qu'elle est, au moins partiellement, autonome, ce qui exclut un pilotage centralisé du système global.

Objet de recherche en intelligence artificielle distribuée, les systèmes multi-agents constituent une possibilité intéressante de modélisation de sociétés humaines et animales, et ont à ce titre des champs d'application larges, allant jusqu'aux sciences humaines.

Origine et aspects techniques

Origine

L'une des grandes sources d'inspiration pour les systèmes multi-agents a été l'étude des comportements sociaux de certaines familles d'insectes. Dans ce domaine, on se référera utilement aux articles Intelligence collective et Intelligence distribuée.

Les SMA peuvent être vus comme la rencontre de divers domaines :

• l'intelligence artificielle pour les aspects prise de décision de l'agent ;
• l'intelligence artificielle distribuée pour la distribution de l'exécution ;
• les systèmes distribués pour les interactions ;
• le génie logiciel pour l'approche agents et l'évolution vers des composants logiciels de plus en plus autonomes ;
• les objets communicants.

Un exemple pour comprendre : la métaphore des jeux vidéo

On peut représenter un SMA par une de ces communautés virtuelles que l'on trouve de plus en plus dans les jeux vidéo actuels.

Prenons l'exemple d'un jeu qui simulerait la vie d'une famille. Le SMA se décompose selon plusieurs dimensions. Tout d'abord, un environnement disposant d'une métrique. On peut considérer qu'il s'agit de la maison et du jardin où vit notre petite famille. Ensuite le SMA peut disposer d'un ensemble d'objets passifs sur lesquels peuvent intervenir nos agents. Il s'agira de tous les objets qui équipent la maison, mais également de la nourriture.

Un SMA se compose d'agents. Ceux-ci, actifs et autonomes, interagissent avec leur entourage (environnement, objets et autres agents).

Enfin, on intègre un ensemble d'opérateurs qui permettent aux agents d'agir sur les objets ou sur les autres agents (le fils peut manger un yaourt, promener son chien ou parler à sa sœur), et de capteurs qui permettent aux agents de connaître les changements de l'environnement et des autres agents (le yaourt est tombé par terre, papa m'a demandé de sortir le chien). Voici donc ce que l'on peut appeler un SMA.

En informatique, l'agent est un programme autonome possédant un ensemble de connaissances et agissant selon des règles qui lui sont propres.

Les cinq problématiques des SMA

On peut relever cinq problématiques principales lors de la création de systèmes multi-agents:

• D'abord, la problématique de l'action : comment un ensemble d'agents peut agir de manière simultanée dans un environnement partagé, et comment cet environnement interagit en retour avec les agents ? Les questions sous-jacentes sont entre autres celles de la représentation de l'environnement par les agents, de la collaboration entre agents, de la planification multi-agent.
• Ensuite la problématique de l'agent et de sa relation au monde, qui est représentée par le modèle cognitif dont dispose l'agent. L'individu d'une société multi-agent doit être capable de mettre en œuvre les actions qui répondent au mieux à ses objectifs. Cette capacité à la décision est liée à un "état mental" qui reflète les perceptions, les représentations, les croyances et un certain nombre de paramètres "psychiques" (désirs, tendances…) de l'agent. La problématique de l'individu et de sa relation au monde couvre aussi la notion d'engagement de l'agent vis-à-vis d'un agent tiers.
• Les systèmes multi-agents passent aussi par l'étude de la nature des interactions, comme source de possibilités d'une part et de contraintes d'autre part. La problématique de l'interaction s'intéresse aux moyens de l'interaction (quel langage ? quel support ?), et à l'analyse et la conception des formes d'interactions entre agents. Les notions de collaboration et coopération (en prenant coopération comme collaboration + coordination d'actions + résolution de conflits) sont ici centrales.
• On peut évoquer ensuite la problématique de l'adaptation en termes d'adaptation individuelle ou apprentissage d'une part et d'adaptation collective ou évolution d'autre part.
• Enfin, il reste la question de la réalisation effective et de l'implémentation des SMA, en structurant notamment les langages de programmation en plusieurs types allant du langage de type L5, ou langage de formalisation et de spécification, au langage de type L1 qui est le langage d'implémentation effective. Entre les deux, on retrouve le langage de communication entre agents, de description des lois de l'environnement et de représentation des connaissances.

Architecture des systèmes multi-agents

En reprenant les cinq problématiques précédentes, on peut décrire quelques éléments de l'architecture d'un système multi-agent.

• Les agents doivent être dotés de systèmes de décisions et de planification à plusieurs. Les théories de la décision sont un domaine à part entière d'étude à ce sujet. Dans la catégorie des interactions avec l'environnement, un autre problème récurrent des systèmes d'agents est celui du pathfinding (avec son algorithme le plus connu, l'algorithme A*).

• Les agents doivent être dotés d'un modèle cognitif : Là aussi, plusieurs modèles existent, l'un des plus classiques étant le modèle BDI (Beliefs-Desires-Intentions). Il considère d'une part l'ensemble de croyances (Beliefs) de l'agent sur son environnement, qui sont le résultat de ses connaissances et de ses perceptions, et d'autre part un ensemble d'objectifs (Desires). En croisant ces deux ensembles, on obtient un nouvel ensemble d'intentions (Intentions) qui peuvent ensuite se traduire directement en actions.

• Les agents doivent être dotés d'un système de communication. Plusieurs langages spécialisés ont vu le jour à cette fin : le Knowledge Query and Manipulation Language (KQML), et plus récemment, le standard FIPA-ACL (ACL pour Agent Communication Language) créé par la Foundation for Intelligent Physical Agents FIPA. Ce dernier standard repose en particulier sur la théorie des actes de langage, chère à John Searle.

• La problématique de l'adaptation est un sujet épineux, objet de recherches nombreuses à l'heure actuelle. On pourrait toutefois citer l'exemple de certains virus, aussi bien biologiques qu'informatiques, capables de s'adapter à leur environnement en mutant.

• Enfin, l'implémentation effective du système multi-agents, si elle ne fait pas à proprement parler partie de l'architecture du système, mérite d'être évoquée à travers l'exemple des nombreux langages de programmation qui ont été développés à des fins de recherche en intelligence artificielle. On citera en particulier le langage LISP.

Ces éléments d'architectures s'appliquent plutôt à un système composé d'agents cognitifs.

Des catégories ou modèles d'agents

Capture d'écran de SeSAm, qui permet de faire des simulations sociales à base de systèmes multi-agents.

On peut établir une classification des agents selon deux critères : agents cognitifs ou réactifs d'une part ; comportement téléonomique ou réflexe d'autre part.

La distinction que l'on peut faire entre cognitif et réactif tient essentiellement de la représentation du monde dont dispose l'agent. Si l'individu est doté d'une "représentation symbolique" du monde à partir de laquelle il est capable de formuler des raisonnements, on parlera d'agent cognitif tandis que s'il ne dispose que d'une "représentation sub-symbolique", c’est-à-dire limitée à ses perceptions, on parlera d'agent réactif. Cette distinction cognitif/réactif correspond à deux écoles de pensée des systèmes multi-agents. La première soutient une approche de famille d'agents "intelligents" devant collaborer, avec une perspective plus sociologique. La deuxième étudie la possibilité de l'émergence d'un comportement "intelligent" d'un ensemble d'agents non-intelligents (type fourmis).

La seconde distinction entre comportement téléonomique ou réflexe sépare les comportements intentionnels (poursuite de buts explicites) des comportements liés à des perceptions. Les tendances des agents peuvent ainsi être exprimées explicitement dans les agents ou au contraire provenir de l'environnement. On peut construire un tableau regroupant les différents types d'agents  :

Catégories d'agent

	Agents cognitifs	Agents réactifs
Comportement téléonomique	Agents intentionnels	Agents pulsionnels
Comportement réflexe	Agents "modules"	Agents tropiques

Les agents cognitifs sont la plupart du temps intentionnels, c'est-à-dire qu'ils ont des buts fixés qu'ils tentent d'accomplir. On peut cependant trouver parfois des agents dits modules qui, s'ils ont une représentation de leur univers, n'ont pas de buts précis. Ils pourraient servir par exemple à répondre à des interrogations d'autres agents sur l'univers. Les agents réactifs peuvent être séparés en agents pulsionnels et tropiques. Un agent pulsionnel aura une mission fixée (par exemple, s'assurer qu'un réservoir reste toujours suffisamment rempli) et déclenchera un comportement s'il perçoit que l'environnement ne répond plus au but qui lui était affecté (le niveau du réservoir est trop bas). L'agent tropique, lui, ne réagit qu'à l'état local de l'environnement (il y a de la lumière, je fuis). La source de motivation est dans un cas interne (agents pulsionnels qui ont une "mission"), dans l'autre cas liée uniquement à l'environnement.

Organisation des agents

Avec le développement des systèmes multi-agents, différents paradigmes organisationnels ont été développés. Ces organisations établissent un cadre pour les relations et interactions entre les agents. Nous allons présenter ici les principales :

• Hiérarchies : dans ce modèle, les agents sont hiérarchisés selon la structure d'un arbre, dans lequel chaque nœud représente un agent, et possède un lien d'autorité sur ses nœuds-fils. Ce modèle permet de décomposer la tâche globale du système.
• Holarchies : l'holarchie se rapproche de la hiérarchie, mais il existe quand même une différence majeure. En effet, il n'y a pas de relation d'autorité entre un agent et son sous-groupe, mais les agents du sous-groupe constituent "physiquement" leur sur-agent. Pour illustrer cette notion, on peut prendre l'exemple d'une ville, constituée de bâtiments. Les bâtiments sont des agents, et la ville est un agent constitué de ces agents bâtiments. On peut également avoir, à l'échelle supérieure, un agent région qui sera constitué d'agents villes. De même, un banc de poissons ressemble parfois à un poisson plus gros que les poissons qui le composent, le banc comme les poissons sont alors des agents, organisés en holarchie.
• Coalitions : une coalition est une alliance temporaire d'agents qui s'unissent et collaborent car leurs intérêts individuels se rencontrent. La valeur de la coalition doit être supérieure à la somme des valeurs individuelles des agents la composant. Pour illustrer cette notion, imaginons que nous ayons des agents qui ont chacun besoin d'un gâteau. Le gâteau individuel coûte 5 €, et le lot de 6 coûte 24 €. Si six agents forment une coalition pour acheter un lot, chacun pourra repartir avec son gâteau pour seulement 4 €. La coalition leur a donc permis d'optimiser leurs intérêts individuels.
• Équipes : les agents constituant l'équipe travaillent ensemble à la réalisation d'objectifs communs. À la différence des agents d'une coalition, les agents d'une équipe cherchent à maximiser les intérêts de l'équipe plutôt que leurs intérêts personnels.
• Congrégations : les congrégations sont assez similaires aux coalitions et aux équipes. Cependant, elles sont destinées à être permanentes et ont généralement plusieurs objectifs à réaliser. De plus, les agents peuvent entrer et sortir des congrégations, et appartenir à plusieurs congrégations en même temps.
• Sociétés : la société est un ensemble d'agents variés, qui interagissent et communiquent. Ils possèdent différents objectifs, n'ont pas le même niveau de rationalité, ni les mêmes capacités, mais sont tous soumis à des lois communes (normes).
• Fédérations : les agents d'une fédération cèdent une partie de leur autonomie au délégué de leur groupe. Les agents d'un groupe n'interagissent qu'avec leur délégué, qui lui-même interagit avec les délégués des autres groupes.
• Marchés : des agents vendeurs proposent des objets à la vente, sur lesquels des agents acheteurs peuvent enchérir. Ce genre d'organisation permet, par exemple, de simuler des marchés réels et/ou de comparer différentes stratégies de négociation.
• Matrices : les agents d'une organisation en matrices sont hiérarchisés. Cependant, à la différence de la hiérarchie présentée plus haut, où un agent n'était soumis qu'à l'autorité d'au plus un seul autre agent, les agents dans une organisation matricielle peuvent être soumis à plusieurs autres agents.
• Combinaisons : une organisation combinée mélange plusieurs des styles présentés ci-dessus (ou d'autres qui auraient été oubliés dans cette liste). Cela peut être, par exemple, une fédération de coalitions ou une hiérarchie d'équipes.

• 
  Organisation hiérarchique, les flèches indiquent les relations d'autorité. Les agents les plus hauts ont une vue plus globale que celle des plus bas.
• 
  Exemple d'holarchie: les villes sont constituées de bâtiments. Chaque bâtiment est un agent, chaque ville également.

Applications

Dans le monde de la recherche

On distingue généralement trois types d'utilisation : la simulation de phénomènes complexes, la résolution de problèmes et la conception de programmes.

Simulation de phénomènes complexes

On utilise les systèmes multi-agents pour simuler des interactions existant entre agents autonomes. On cherche à déterminer l'évolution de ce système afin de prévoir l'organisation qui en résulte. Par exemple, en sociologie, on peut paramétrer les différents agents composant une communauté. En ajoutant des contraintes, on peut essayer de comprendre quelle sera la composante la plus efficace pour parvenir à un résultat attendu (construction d'un pont). Ils permettent même d'expérimenter des scénarios qui ne seraient pas réalisables sur des populations réelles, que ce soit pour des raisons techniques ou éthiques. Ce qui importe c'est le comportement d'ensemble et non pas le comportement individuel. Des applications existent en physique des particules (agent = particule élémentaire), en chimie (agent = molécule), en robotique (agent = robot, dans le cas d'une implémentation sur robot réel, on parlera de système multi-robots), en biologie cellulaire (agent = cellule), en éthologie (agent = animal), en sociologie, en ethnologie (agent = être humain) et en économie (l'agent est un être humain dans un ménage faisant partie d'une population synthétique). L'autonomie permet ici de simuler le comportement exact d'une entité.

Comme exemples concrets, nous pouvons citer par exemple EpiSIM, logiciel qui permet de simuler la propagation de maladies dans un espace géographique paramétrable, ou encore DS, qui simule l'évolution de la population de l'île de La Réunion et permet d'anticiper son urbanisation. On trouve également des simulations de trafic routier ou d'évacuation de foule paniquée dans un bâtiment, qui permettent d'étudier l'origine des problèmes (embouteillages, bousculades…) afin de réfléchir à des solutions pour les restreindre.

Résolution de problèmes

L'intelligence artificielle distribuée est née pour résoudre les problèmes de complexité des gros programmes monolithiques de l'intelligence artificielle : l'exécution est alors distribuée, mais le contrôle reste centralisé. Au contraire, dans les SMA, chaque agent possède un contrôle total sur son comportement. Pour résoudre un problème complexe, il est en effet parfois plus simple de concevoir des programmes relativement petits (les agents) en interaction qu'un seul gros programme monolithique. L'autonomie permet au système de s'adapter dynamiquement aux changements imprévus qui interviennent dans l'environnement.

Conception de programmes

Dans le même temps, le génie logiciel a évolué vers des composants de plus en plus autonomes. Les SMA peuvent être vus comme la rencontre du génie logiciel et de l'intelligence artificielle distribuée, avec un apport très important des systèmes distribués. Par rapport à un objet, un agent peut prendre des initiatives, peut refuser d'obéir à une requête, peut se déplacer… L'autonomie permet au concepteur de se concentrer sur une partie humainement appréhendable du logiciel.

Dans l'industrie

Les utilisations de systèmes multi-agents dans l'industrie sont nombreuses et variées. On en trouve dans les jeux vidéo et dans l'animation, avec notamment le logiciel MASSIVE, permettant de simuler des foules, qui a été développé à l'occasion de la trilogie cinématographique du Seigneur des Anneaux. Ils peuvent également être utilisés par des entreprises pour, par exemple, suivre les comportements des clients naviguant sur un site web.

Dans la finance

Capture d'écran de la plateforme MetaTrader 4, qui permet de créer des agents pour faire du trading automatique.

Les systèmes multi-agents sont également utilisés dans le monde de la finance.

Plate-formes de développement de systèmes multi-agents

• AnyLogic - Logiciel de simulation multi-agents et multi-méthode
• CORMAS (COmmon Resources Multi-Agent System) est un framework de développement de systèmes multi-agents, open-source et basé sur le langage de programmation orientée objet SmallTalk. Spatialisé, il est centré sur des problématiques de recherche en sciences du développement et de négociation entre acteurs.
• DoMIS est un outil permettant la conception de Systèmes Multi-agents (orientés "pilotage opérationnel de systèmes complexes") et basé sur la méthode de conception B-ADSc (voir Analyse décisionnelle des systèmes complexes). Axé sur la conception, DoMIS permet l'établissement de spécifications utilisables par toute plateforme de développement capable de simuler, au mieux, le temps réel.
• JACK est un langage de programmation et un environnement de développement pour agents cognitifs, développé par la société Agent Oriented Software comme une extension orientée agent du langage Java.
• GAMA est une plateforme de simulation open-source (LGPL) proposant un environnement de modélisation à base d'agents spatialement explicites (Utilisation de données SIG pour la description des agents et de leur environnement) et un environnement de simulation particulièrement riche, permettant des visualisations complexes et des explorations intelligentes de l'espace des paramètres d'un modèle. Développée par l'IRD/SU au sein de l'unité mixte internationale UMMISCO.
• JADE (Java Agent DEvelopment) est un framework de développement de systèmes multi-agents, open-source et basé sur le langage Java. Il offre en particulier un support avancé de la norme FIPA-ACL, ainsi que des outils de validation syntaxique des messages entre agents basé sur les ontologies.
• Jadex, est une plate-forme agent développée en JAVA par l'université de Hambourg qui se veut modulaire, compatible avec de nombreux standards et capable de développer des agents suivant le modèle BDI.
• JAgent est un framework open source réalisé en Java dont l'objectif est de faciliter le développement et le test de systèmes multi-agents.
• Janus est une plateforme multi-agents modulaire écrite en Java. Elle permet de créer des systèmes multi-agents avec ou sans une approche organisationnelle basée sur le modèle (en) Capacité-Rôle-Interaction-Organisation (CRIO). Janus propose également un modèle de simulation de système holonique assimilant les agents à des holons (ou agents récursifs). Janus est extensible grâce à son utilisation de modules OSGi et propose le support réseau via la bibliothèque JXTA. Une méthodologie nommée (en) ASPECS peut être associée à Janus. Cette plateforme est développé conjointement par (en) ICAP-SeT-UTBM en France et le (es) CITAT en Argentine.
• Jason est un environnement open source de développement d'agents dans le formalisme AgentSpeak, et développé en Java par Jomi Fred Hübner et Rafael H. Bordini.
• MaDKit est une plate-forme multi-agents modulaire écrite en Java et construite autour du modèle organisationnel Agent/Groupe/Rôle. C'est une plate-forme libre basée sur la licence GPL/LGPL développée au sein du LIRMM.
• MAGIQUE est une plate-forme pour agents physiquement distribués écrite en Java et fournissant un modèle de communication original d'appel à la cantonade. Dans MAGIQUE, les compétences sont dissociées des agents. L'architecture des agents et les différentes compétences sont développées séparément. Les compétences sont ensuite greffées comme plugin dans les agents au gré du concepteur. Cette plate-forme est développée au sein du LIFL.
• OMAS, Open Multi-Agent Asynchronous Systems est une plate-forme de recherche développée par l'équipe d'intelligence artificielle de l'Université de technologie de Compiègne, sous la direction de Jean-Paul Barthès.
• SemanticAgent est basé sur JADE et permet le développement d'agents dont le comportement est représenté en SWRL. SemanticAgent est développé au sein du LIRIS, il est open-source et sous licence GPL V3.
• SPADE est un environnement de développement d'organisations multi-agents basé sur le protocole XMPP et est écrit en Python.
• MASSIVE (logiciel) est un logiciel pour la simulation de foule, basé multi-agents, qui a permis la création d'effets spéciaux dans un grand nombre de films, ayant été développé à l'origine pour les scènes de combat dans Le Seigneur des anneaux.
• Golaem Crowd est un plug-in pour Maya (logiciel) basé multi-agent et permettant d'effectuer des simulations de foule pour les effets spéciaux directement dans Maya.
• Simulate, plateforme de simulation de trafic multi-agent 3D temps réel, développée par Voxelia en partenariat avec le CITAT et ICAP-SeT-UTBM.
• NetBioDyn est un outil de simulation multi-agent à l'utilisation très simple destiné à l'éducation, développé à l'Université de Bretagne Occidentale.

Un comparatif des plates-formes et d'outils de modélisation orientés-agent est disponible : (en) Comparison of agent-based modeling software.

Aspects culturels

Systèmes multi-agents et fiction

Les concepts des systèmes multi-agents ont été repris dans différentes œuvres de fiction. Le plus souvent on retrouve la peur classique de l'invention qui échappe à son concepteur (référence à la notion d'émergence), mais le phénomène est amplifié par le nombre et l'intelligence collective des agents.

• Dans La Révolution des fourmis, de Bernard Werber les adolescents rebelles dans leur lycée créent sur ordinateur une société où les entités sont des humains qui finalement se rebellent.
• Dans La Proie de Michael Crichton où un essaim d'entités autonomes s'échappe d'un laboratoire.
• Les réplicateurs de la série Stargate SG-1 qui forment au départ de simples jouets et qui évoluent jusqu'à devenir une menace pour l'univers.
• Dans Code Lyoko, XANA est un programme multi-agents créé par Franz Hopper. Créé initialement pour contrer un projet militaire du nom de Carthage, il accède à la conscience et cherche à s’en prendre à l’humanité.
• Encore dans Code Lyoko, l'épisode "Marabounta" montre un autre programme multi-agents (appelé Marabounta) censé affaiblir les actions de XANA, mais le programme finit lui aussi hors de contrôle, XANA sera alors un allié temporaire face à ce nouvel ennemi.
• Toujours dans Code Lyoko, les derniers épisodes montrent un nouveau système multi-agents censé "tuer" XANA, programme encore en développement dans l'épisode 93 mais qui réussira tout de même à le ralentir les quelques minutes nécessaires. Dans l'épisode 94, sa version achevée neutralisera XANA en désactivant simultanément tous ses supers-calculateurs juste à temps.
• Dans Matrix, les programmes sont indépendants et hiérarchisés, on peut donc les qualifier d'agents. Dans la trilogie ce terme est utilisé pour nommer une partie d'entre eux, en fait les plus visibles. (Il était en effet invraisemblable que les machines aient évolué au point de simuler le comportement humain.) Néo est le premier à avoir découvert toute la complexité de la matrice, notamment lors de son combat avec Séraphin. Mais la confirmation ne viendra que dans Matrix Revolutions quand un "programme" lui parlera d'amour.

Voir aussi

Bibliographie

 : document utilisé comme source pour la rédaction de cet article.

• Jacques Ferber, Les Systèmes multi-agents : Vers une intelligence collective, InterEditions, 1995, 522 p. (ISBN 2-7296-0665-3)
• (en) Michael Wooldridge, An Introduction to MultiAgent Systems, Wiley and Sons, 2002, 348 p. [détail de l’édition] (ISBN 0-471-49691-X)
• (en) Gerhard Weiss, Multiagent Systems, A Modern Approach to Distributed Artificial Intelligence, Cambridge (Mass.)/London, MIT Press, 1999, 619 p. (ISBN 0-262-23203-0).

Articles connexes

• Intelligence artificielle distribuée
• Agent (informatique)
• Cerveau artificiel
• Analyse décisionnelle des systèmes complexes
• DisCSP
• Optimisation sous contraintes distribuée

Liens externes

• Cours Systèmes Multi-Agents du Mastère en Informatique de Paris XI
• Systèmes multi-agents : Approche décisionnelle des systèmes complexes B-ADSc