La simulation est utilisée dans divers domaines scientifiques quand la réalisation de l’ensemble des expériences concrètes nécessaires à la validation ou l’infirmation d’une théorie prendrait un temps trop grand ou demanderait des moyens dont on ne disposerait pas. Grâce aux résultats de la simulation, on peut ensuite orienter le choix des expérimentations à réaliser pour tendre vers les résultats désirés.
La modélisation est un processus particulier de simulation. Il consiste à donner une représentation simplifiée (parce que non complète) d’un objet, phénomène ou personne à modéliser, afin d’essayer de reproduire son comportement en simulation. Dans le meilleur des cas, le modèle permettra aussi de prédire certains comportements que le sujet modélisé pourrait adopter dans le cadre d’une simulation. Cette capacité prédictive, qualité indispensable d’une modélisation, peut avoir un caractère qualitatif ou quantitatif, selon que le modèle se contente de prévoir un certain comportement ou qu'il permette de prédire la valeur de telle ou telle grandeur mesurable.
Un modèle informatique (on parle aussi de modèle numérique) est l'implémentation d'un modèle sur un ordinateur. Il permet de simuler un phénomène en utilisant les capacités de calcul de l’ordinateur.
Parmi les modèles informatiques, on trouve les modèles à base de système multi-agents (SMA). Dans une modélisation par SMA, le phénomène est décrit de la perspective de ses constituants (approche bottom-up). On cherche ainsi à décrire des comportements globaux en ayant une représentation des agissements d’un ensemble d’entités autonomes et actives nommées agents que Ferber [1] définit comme étant :
« Une entité réelle ou virtuelle, évoluant dans un environnement, capable de percevoir et d’agir dessus, qui peut communiquer avec d’autres agents, qui exhibe un comportement autonome, lequel peut être vu comme la conséquence de ses connaissances, de ses interactions avec d’autres agents et les buts qu’il poursuit. »
Grâce à ces SMA, on peut modéliser des systèmes réels dans lesquels des comportements très complexes émergent d’interactions relativement simples et locales entre de nombreux individus différents. De nombreux systèmes naturels ou créés par l’homme sont complexes en ce sens – depuis l’économie, les sociétés, les normes culturelles et les embouteillages, jusqu’aux écosystèmes, conditions météorologiques, systèmes immunitaires et évolution – et les dynamiques non linéaires de ces systèmes sont difficiles à étudier en utilisant des modèles traditionnels.
Les systèmes multi-agents utilisent la puissance des ordinateurs pour explorer les dynamiques de ces systèmes. Au niveau le plus simple, un SMA consiste en un ensemble d’agents et de règles d’interaction entre eux. Chaque agent est capable d’évaluer individuellement sa situation et de prendre des décisions à partir d’un ensemble de règles. Il peut exécuter divers comportements relatifs au système représenté, par exemple produire, consommer, vendre… Les agents peuvent ensuite être capables d’évoluer, permettant à des comportements non anticipés d’apparaître. Des SMA sophistiqués utilisent parfois des réseaux de neurones, des algorithmes évolutionnaires, ou d’autres techniques d’apprentissage, afin de permettre un apprentissage et une adaptation réaliste.
Après avoir rappelé l’historique de l’apparition de la modélisation par système multi-agents, nous présenterons les différents cadres d’applications de cette méthode, ses intérêts et ses limitations, ainsi que les perspectives de recherche qui lui sont associées.
Les machines de von Neumann sont certes à l’origine des systèmes multi-agents, mais elles ne sont pas des modèles à base d’agents – ni même, en fait, des modèles. Ce sont des constructions théoriques, mais d’un genre novateur à l’époque, qui ouvrent la voie de l’étude et de la construction de la vie artificielle, et plus tard, de sa modélisation numérique.
A la fin des années 1940, le mathématicien John von Neumann suggéra la réalisation d’une machine capable de reproduction. Le système qu’il proposait pourrait suivre avec exactitude des instructions détaillées pour réaliser une copie de lui-même. Ce système créerait donc sa copie, avec une copie des instructions, et générerait donc une progéniture fertile. Construire réellement une machine de von Neumann aurait été une tâche impossible. Mais un ami de von Neumann, Stanislaw Ulam, également mathématicien, qui réfléchissait au problème en parallèle, suggéra de construire la machine sur papier, comme un ensemble de cellules sur une grille. L’idée intrigua von Neumann, qui la dessina, créant ainsi le premier des systèmes appelés plus tard automate cellulaire.
Bien que von Neumann n’ait jamais terminé sa preuve mathématique, les implications étaient claires : la base de la vie était l’information.
Le concept définissant l’existence de la vie en tant qu’information amena de fascinants thèmes de recherche. L’un d’eux étaient le Jeu de la Vie de John Horton Conway. A la différence de la machine de von Neumann, le Jeu de la Vie fonctionne à partir de règles très simples : la vie apparaît sur un échiquier virtuel, et chaque cellule naît, vit et meure selon les règles définies.
Conway et son équipe jouèrent de multiples parties, effectuant chaque altération de chaque cellule à la main, étudiant quantités de configurations. Plus tard, Conway ouvrit le jeu à la compétition, offrant un prix à qui prouverait que le Jeu de la Vie était capable de générer une population infinie à partir d’une configuration finie donnée. L’équipe gagnante programma le jeu sur un ordinateur : c’était la première utilisation connue d’un ordinateur pour créer la vie artificielle.
De nos jours, le Jeu de la Vie a toujours ses adeptes, avec un grand nombre de pages web qui lui sont consacrées[i]. Il est le point de départ des systèmes de simulation informatique, et a posé de nombreuses questions qui ont largement influencé la recherche sur la modélisation par systèmes multi-agents.
Le Jeu de la Vie sur l’échiquier de Conway était pure information, les règles étant extrêmement simples, mais les implications très complexes. Mais si de tels mouvements complexes peuvent résulter de règles aussi simples, les comportements réels ne pourraient-ils pas eux aussi être le résultat de comportements très simples ?
De cette question est venue l’idée de l’utilisation de la vie artificielle pour créer des modèles du monde réel à partir des unités à la base des phénomènes. L’étude des configurations groupées des oiseaux en vol (« boids », pour « birdoids ») de Craig Reynolds en est un exemple[iv]. Pour l’observateur humain, les oiseaux en vol paraissent suivre un contrôle centralisé selon la taille du groupe et la complexité du vol. Reynolds suspecta que le vol en bande était une activité décentralisée, et créa un modèle informatique pour étudier cette théorie. Ses agents, qu’il appela « boids », suivaient chacun des directives simples ; le comportement qui émergea était très proche du vol en bande dans la nature. Si proche, en fait, que les « boids » furent utilisés comme un point de départ à des animateurs graphiques qui avaient besoin d’animer des vols en bande pour les films d’Hollywood notamment pour les dessins animés tels qu’un envol de chauves-souris pour Batman Returns (1992), un troupeau de gnous pour The Lion King (1994), une foule nombreuse dans The Hunchback of Notre Dame (1996)…
Les intérêts des SMA comparés à d’autres techniques de modélisation peuvent être résumés en trois points principaux :
Les phénomènes émergents résultent de l’interaction entre entités individuelles. Par définition, ils ne peuvent pas être réduits aux parties du systèmes : le tout est plus important que la somme de ses parties (théorie de la Gestalt), à cause de l’interaction entre ces parties. Un phénomène émergent peut avoir des propriétés multiples issues des propriétés des parties. Par exemple, un embouteillage, qui résulte du comportement et des interactions entre conducteurs, peut se déplacer dans la direction inverse de celle des voitures qui l’ont effectivement déclenché. Cette caractéristique des phénomènes émergents les rend difficiles à comprendre et à prédire : ils peuvent en effet être contre-intuitifs.
Modéliser un phénomène à l’aide d’un système multi-agents devient donc particulièrement intéressant lorsqu’il y a potentiellement des phénomènes émergents, par exemple lorsqu’un comportement individuel, au lieu d’être linéaire, peut être caractérisé par des règles de type si - alors ; ou bien lorsque les agents doivent disposer d’une mémoire, que l’on veuille modéliser des phénomènes d’apprentissage ou d’adaptation ; lorsque les interactions entre agents sont hétérogènes ; ou bien encore lorsque l’utilisation d’une moyenne fausserait les résultats, car le système pourrait être sensible à certaines perturbations.
Dans de nombreux cas, un système multi-agents est plus naturel pour décrire et simuler un système composé d’entités « comportementales ». Lorsqu’on essaie de décrire un embouteillage, les cours de la bourse, des votants, ou comment fonctionne une entreprise, les SMA permettent au modèle de paraître plus proche de la réalité. Par exemple, il est plus naturel de décrire comment les clients se déplacent dans un supermarché que de créer les équations différentielles qui régissent la dynamique de la densité des clients. Puisque les équations de densités résultent du comportement des clients, une approche basée sur les SMA pourra également permettre à l’utilisateur d’étudier les propriétés globales.
On peut donc mettre en valeur une nouvelle utilisation intéressante d’un système multi-agents : il sera particulièrement bien adapté à la description d’un système du point de vue de l’activité de ses constituants, c'est-à-dire lorsque le comportement des individus n’est pas résumable à une transition globale, ou bien lorsque celui-ci est complexe (et donc difficile à décrire avec des équations) ou parfois irrationnel. De plus, la modélisation est plus facilement interprétable par un observateur humain, car la description par un SMA est plus naturelle que par de simples processus ; la validation par un expert en sera donc facilitée, car il pourra facilement se rapporter au monde réel.
La flexibilité des SMA peut être observée sur de multiples dimensions. Par exemple, il est simple d’ajouter plus d’agents à une simulation multi-agents. Les SMA fournissent également un cadre naturel pour adapter la complexité des agents : on peut jouer sur les règles de comportement, le degré de rationalité, la capacité à apprendre et à évoluer, ou bien encore les règles d’interaction.
Une autre dimension de flexibilité est la capacité à modifier les niveaux de description et d’agrégation : on peut facilement travailler avec des groupes d’agents, des sous-groupes, des agents isolés, avec différents niveaux de description co-existants dans un modèle donné. On peut vouloir utiliser un SMA lorsque ce niveau de description ou de complexité n’est pas connu au cours du temps, ce qui nécessite un aspect flexible de la modélisation.
On doit cependant reconnaître certaines limitations aux systèmes multi-agents : bien que ce type de modélisation présente de grandes qualités, il existe assez peu d’applications industrielles, sans doute à cause de la nature particulière des variables et de la difficulté à mesurer les paramètres. La simulation sociale en milieu industriel n’a pas encore eu beaucoup de succès, car l’accent a été mis sur sa capacité prédictive plutôt que comme un moyen d’enseignement. Par exemple, le patron d’une entreprise peut mieux comprendre sa place sur le marché en observant un modèle multi-agents de sa situation ; cependant, quantifier les bénéfices tangibles de quelque chose d’intangible est difficile, et il ne pourra pas annoncer avoir gagné X millions de dollars en jouant avec une simulation de ses clients.
Pour être utilisable, un SMA doit présenter plusieurs caractéristiques essentielles et parfois difficiles à réunir : tout d’abord, un modèle doit avoir un objectif précis, car un modèle avec un but trop général ne peut pas fonctionner. Il doit être construit au bon niveau de description, avec la quantité exacte de détails servant ce but, ce qui peut se révéler assez délicat.
D’autre part, les phénomènes modélisés impliquent souvent des agents humains, avec un comportement potentiellement irrationnel, des choix subjectifs, et une psychologie complexe – en d’autres mots, des facteurs difficiles à quantifier, calibrer, et même parfois difficiles à justifier. On ne peut donc pas prendre de décisions sur la base de la conclusion d’une simulation : à cause de la variabilité des donnés d’entrée du modèle, la nature des sorties est similairement variable, et peuvent aller de ce qui relève d’intuitions purement qualitatives jusqu’à ce qui peut devenir des résultats quantitatifs utilisables pour la prise de décision.
Enfin, simuler le comportement de toutes les unités constituant un système multi-agents peut être extrêmement gourmand en ressource informatique, et donc en temps. Bien que la puissance informatique augmente à une vitesse exponentielle, les hauts besoins computationnels d’un SMA restent un problème lorsqu’il s’agit de modéliser de grands systèmes.
Les applications existent pourtant. Farrel et son équipe ont développé un monde virtuel peuplé d’agents servant à prédire quand et comment un succès cinématographique a lieu. Travaillant pour la Twentieth Century Fox, ils ont modélisé comment des films tels que Titanic ou Le Projet Blair Witch ont pu devenir des succès, mais leur modèle n’était pas très fiable. Prédire un succès est probablement la chose la plus difficile à faire ; comprendre comment un succès arrive est une meilleure utilisation du modèle.
Les champs d’application sont nombreux, en particulier dans les sciences sociales, politiques ou économiques, dans lesquelles les exemples de phénomènes émergents abondent : on citera par exemple la modélisation des flux (évacuation, trafic, gestion de flux de consommateurs, migration intra-urbaines (IRD)), celle des marchés (la bourse, simulation stratégique), ou bien encore des entreprises (risque, organisation de la société). Les applications existent aussi dans des domaines plus différents comme en météorologie, l’écologie (Cycle du Carbone (IRD), Contrôle et modélisation de ressources renouvelables (COMORE à l’INRIA)), ou même le sport (STAPS Marseille).
Nous développerons dans les pages suivantes différents aspects de l’utilisation des systèmes multi-agents, dans les thèmes suivants :
Sociologie : étude de la modelisation de communautés de développeurs open source,
Socio-ethnologie : modélisation de la coopération entre êtres humains au sein d’un groupe, des dynamiques d’opinion, et de déplacements de populations en réponse à des modifications de l’environnement ou des règles sociales,
Biologie : Simulation de différents aspects du système immunitaire, cancérologie, croissance de bactéries,
Economie : Micro/Macro économie, flux monétaires,
Physique : modélisation d'écoulement,
Ethologie : animaux sociaux, relations entre espèces (compétition, sélection parallèle, migrations, etc).
Lorsque l’on parle de modélisation mathématique complexe, les modèles analytiques paraissent à l’heure actuelle plus fiables que ceux à base d’agents. Mais il faut considérer la modélisation à base d’agents comme un exemple de sciences expérimentales, et donc ne pas attendre la rigueur mathématique que peut avoir un modèle analytique. Ainsi les phénomènes d’émergence qui peuvent être observés à l’aide des modèles à base d’agents ne doivent pas être relégués à la fonction de démonstration de phénomènes. L’émergence est un concept qui, s’il était décrit plus rigoureusement, pourrait justifier l’utilité des modèles à base d’agents, ce qui servirait grandement tous les domaines de la science qui utilisent ces modèles. Les travaux effectués sur les systèmes complexes adaptatifs peuvent servir de piste [5-6].
De nombreuses autres questions restent en suspens, plus particulièrement liées aux systèmes multi-agents :
Comment concevoir les agents afin qu'ils puissent décomposer leurs buts et tâches, allouer à d'autres agents des sous-buts et sous-tâches, ou encore synthétiser des résultats partiels et des solutions ?
Comment intégrer les autres agents dans les connaissances internes de l'agent afin d'en tenir compte dans ses propres raisonnements ?
Comment gérer des points de vues différents et des conflits ?
Comment réaliser des SMA dont on maîtrise les comportements ? Sur quelles plateformes et avec quelles méthodologies de conception ?
Comment éviter des comportements globaux non désirés (oscillation, non convergence ...) ?
Comment faire négocier des agents ? Sur quelle base contractuelle ?
Comment réaliser des processus sophistiqués comme la résolution de problème, l'apprentissage, la planification ou encore la prise de décision dans un contexte multi-agents ?
Comment un agent peut-il décrire et surtout valider le comportement qu'il prétend avoir ?
Toutes ces questions restent à l’étude dans de nombreux laboratoires de recherche, qui travaillent sur la conception d’agents évolutifs et temps réel, le raisonnement avec et dans le temps sous contraintes des ressources limitées, la décision dans des environnements stochastique, ou bien encore les capacités d’apprentissage et d’adaptation de l’agent ou du groupe d’agents.
Références :
Articles et livres :
[1]Ferber, J. 1995. Les systèmes multi-agents. Vers une intelligence collective. InterEditions, Paris.
[2]von Neumann, J., 1966, Theory of Self-Reproducing Automata (Edited and completed by A. W. Burks), Urbana, IL: University of Illinois Press
[3]Levy, S. Artificial Life; Pantheon: New York, NY, 1992. p 44
[4]Gardner, M. 1970. "The Fantastic Combinations of John Conway's New Solitaire Game Life." Scientific American, (223). pp.120-123.
[5]Holland, J., (1997) Emergence: From Chaos to Order (Addison–Wesley, Reading, MA).
[6]Epstein, J. M. (1998) Complexity 4, 36-48.[CrossRef]
[7]Epstein, J. M. & Axtell, R. L., (1996) Growing Artificial Societies: Social Science from the Bottom Up (MIT Press, Cambridge, MA).
[8]Eric Bonabeau, Agent-based modeling: Methods and techniques for simulating human systems, PNAS 2002; 99: 7280-7287.In PNAS (http://www.pnas.org/cgi/content/full/99/suppl_3/7280#SEC4)
[9]Steven C. Bankes, Agent-based modeling: A revolution?, PNAS 2002 99: 7199-7200 In PNAS (http://www.pnas.org/cgi/content/full/99/suppl_3/7199 )
Sites :
[i]Cours « Systèmes multi-agents » proposé par François BOURDON. http://www.iutc3.unicaen.fr/~bourdf/cours/CNAM_AgMob/SMA-CNAM-AM-p1-t.pdf
[ii]Les systèmes multi-agents : Présentation générale In « Cormas : Ressources naturelles et simulation multi-agents ». http://cormas.cirad.fr/fr/demarch/sma.htm
[iii]Jeu de la vie de Conway : http://www.univ-lemans.fr/enseignements/physique/02/divers/conway.html
http://www.radicaleye.com/lifepage/patterns/contents.html
http://wwwhomes.uni-bielefeld.de/achim/gol.html
[iv]Simulation de Boïds : http://www.red3d.com/cwr/boids/
[v]Historique des modèles à base d’agents : In the Brookings Institution : http://www.brook.edu/ES/dynamics/models/history.htm
[vi]Simulation à base d’agents et Sciences sociales : [vii] Présentation des activités de l’équipe MAD (Modèles, Agents et Décision). http://users.info.unicaen.fr/~fbourdon/TalkEvalCNRS.pdf
[viii]Numéro spécial online PNAS (May 2002) Adaptive Agents, Intelligence, and Emergent Human Organization: Capturing Complexity through Agent-Based Modeling : http://www.pnas.org/content/vol99/suppl_3/