Interstices


  Découvrir

La force du collectif

En créant des entités informatiques capables de réagir à des événements imprévus, de dresser des plans et de travailler en équipe, les informaticiens simulent les comportements collectifs de groupes d’individus, d’animaux ou de molécules.

Illustration © Kirsty Pargeter – Fotolia

Illustration © Kirsty Pargeter – Fotolia.

Une première version de cet article est parue dans le dossier n°87 Les robots en quête d'humanité de la revue Pour la Science, numéro d'avril/juin 2015.

L'essentiel

  • L'approche centrée sur des individus aide à construire des modèles explicatifs de phénomènes complexes.
  • Un système multi-agents permet de construire des modes artificiels pour tester des hypothèses.
  • Tout peut être agent : un animal, un véhicule, un bâtiment, le feu...
  • La conception des comportements des agents repose sur les résultats de la recherche en intelligence artificielle.
  • Chaque agent agit selon le contexte et peut apprendre de ses expériences afin de mieux s'adapter.
  • Les interactions des agents entraînent l'émergence de phénomènes collectifs non définis a priori.

 

Sur un promontoire devant Erebor, Azog, le capitaine, lève un bras et pousse un cri. Ce sont alors des milliers d’orques qui se lancent à l’assaut de la Montagne Solitaire. Bientôt, elfes, nains et humains d’un côté, orques et gobelins de Gundabad de l’autre, s’affrontent dans une bataille gigantesque. Le fracas des combats résonne pendant plus d’une demi-heure sur les écrans, captivant les spectateurs de La Bataille des Cinq Armées, jusqu’à l’arrivée des aigles et la déroute des gobelins. Une fois encore, le réalisme des scènes du dernier volet de la trilogie adaptée de l’œuvre de Tolkien, Le Hobbit, impressionne.

Le nombre de figurants recrutés a dû être conséquent ! Non, en fait, très peu ont pris part à la mêlée, car la bataille est surtout réalisée en images de synthèse : elles mettent en scène une foule d’acteurs virtuels dirigés par des intelligences artificielles. Chacun des combattants est une entité informatique, un « agent », qui se comporte et « raisonne » de façon autonome selon son environnement et les objectifs qui lui ont été fixés. Le résultat, au niveau collectif, est un combat d’un réalisme saisissant.

Depuis la trilogie du Seigneur des Anneaux, récompensée par de nombreux Oscars, le logiciel Massive a été utilisé pour de nombreux films, jusqu’à ce dernier opus du Hobbit. Au cinéma, les scènes de groupe (batailles, panique, essaims, troupeaux...) sont de plus en plus confiées à l’ordinateur qui dirige des acteurs artificiels grâce à des algorithmes.

hobbit

La Bataille des Cinq Armées, (le troisième volet de la trilogie du Hobbit) met-elle en scène des milliers de figurants ? Non, des milliers d’entités informatiques autonomes, des agents animés par le logiciel Massive. Quelques règles simples de réaction aux événements qui surviennent dans leur entourage régissent leur comportement.
Image issue du film La Bataille des Cinq Armées réalisé par Peter Jackson - Distribution : Warner Bros France(2014) © Warner Bros.


En fait, l’attribution de règles de comportements et d’objectifs à une multitude d’entités informatiques autonomes s’applique à de nombreuses situations. Avec les mêmes principes, on simule des phénomènes naturels, on anime des mondes artificiels à des fins ludiques, on teste l’aménagement du territoire, on étudie des comportements sociaux. Ces diverses applications sont fondées sur un schéma commun : une modélisation centrée sur les individus via la simulation par agents.

Pour étudier un phénomène, les scientifiques en construisent une représentation simplifiée, un modèle. Les orbites elliptiques des planètes, introduites au XVIe siècle par Johannes Kepler, sont ainsi un modèle réaliste de leurs trajectoires autour du Soleil, même si l’interaction des planètes modifie légèrement les ellipses.

Cependant, on peut rarement confronter un modèle à la réalité par l’expérience, ou en tirer les conséquences logiques, tant les modèles que l’on peut analyser directement sont rares. Les scientifiques ont alors recours à des simulations. L’idée est de tester un modèle sur un substitut de la situation réelle, qui en reproduit fidèlement les caractéristiques essentielles. Aujourd’hui, la plupart des simulations consistent à résoudre de façon exacte ou approchée les équations qui sous-tendent les modèles physiques. Cette approche mathématique permet, par exemple, de modéliser la régulation génétique au sein d’une cellule.

Des modèles à agents comptant

Mais une nouvelle façon d’envisager la simulation a émergé, au carrefour des recherches sur la vie artificielle (quand on laisse des ensembles d’entités virtuelles se développer et s’auto-organiser) et des travaux sur la simulation des interactions d’individus. Le concept d’agents a repoussé les frontières de la modélisation au-delà des limites inhérentes à la seule mise en équations, notamment en fournissant des outils pour étudier les comportements en tant que tels.

L’une des faiblesses de l’approche mathématique de la simulation est son absence de portée explicative. On constate un comportement, telle une convergence vers un état, mais on ignore tout des mécanismes en jeu. Les équations régissant le modèle portent sur le comportement moyen des individus et négligent les variations de comportement d’une entité à une autre. Le devenir d’un individu particulier et sa contribution à l’ensemble du phénomène restent inconnus.

À l’inverse de la modélisation mathématique, les modélisations dites centrées sur des individus sont focalisées sur les moyens plutôt que sur les fins. Elles posent le problème à l’échelle de l’individu : étant donné les entités qui interviennent dans un phénomène, quel doit être leur comportement pour que ce phénomène se manifeste ? Cette modélisation centrée sur des individus, qui permet de passer d’une simulation macroscopique à une simulation microscopique, se décline principalement à travers deux paradigmes. Le premier est celui des automates cellulaires (le plus connu est le Jeu de la Vie), où l’on divise l’espace en cellules dotées d’un état, et qui en changent en fonction de l’état des cellules voisines, selon des règles identiques pour toutes. Le second rassemble les simulations multi-agents qui offrent d’emblée aux entités qui les composent des comportements diversifiés : c’est ce que nous abordons ici.

L’industrie des loisirs, notamment les jeux vidéo et le cinéma, constitue un débouché important pour ce type de simulations. Par exemple, dans le programme Massive qui est employé depuis le Seigneur des Anneaux, chaque « figurant » est un agent autonome à qui est attribuée une palette restreinte de règles de comportements, par exemple « Si je vois un ennemi, j’avance vers lui » ou « Si je suis attaqué sur le côté gauche, je pare avec mon bouclier ».

Chaque agent prend ses décisions en fonction du contexte et selon des paramètres qui lui sont propres, ce qui entraîne une variété comportementale. On regroupe alors ces agents et on les active afin qu’ils « jouent » une scène.

Dans le champ scientifique, les agents connaissent aussi un grand succès. En physique ou en chimie, les corps semblables sont interchangeables : c’est bien le cas des atomes et des molécules de même nature. En revanche, en éthologie, en sociologie ou en économie, les acteurs sont dotés d’une histoire propre, et leurs comportements individuels varient. Les agents sont particulièrement bien adaptés à la modélisation de phénomènes collectifs émergeant de l’action d’individus « simples ».

La structuration spatiale des groupes d’animaux tels que les nuées d’oiseaux ou les bancs de poissons s’explique aussi dans le cadre des systèmes multi-agents. On a longtemps supposé qu’un meneur coordonnait l’ensemble du groupe. Or Craig Reynolds, de la société Sony, a montré que pour reproduire des groupes réalistes, trois règles simples appliquées à chaque individu suffisent : la séparation tend à éloigner l’individu de ses congénères les plus proches ; l’alignement force l’animal à s’orienter dans la direction moyenne de ses voisins ; enfin, la cohésion le pousse vers leur position moyenne. Ce modèle, dit de « flocking », est désormais utilisé couramment dans les jeux d’armées de type Age Of Empire, Cossacks et Rome Total War.

Enfin, la simulation à visée ludique et celle qui fait office de « laboratoire virtuel » se rejoignent de plus en plus fréquemment, notamment à travers la montée en puissance des Serious Games, ces jeux dotés d’un objectif pédagogique. Plus le jeu fait appel à des situations jugées vraisemblables par le joueur, plus ce dernier s’y implique et en assimile les connaissances. L’utilisation d’agents autonomes dans ce contexte permet une construction modulaire, facilement extensible et capable de répondre à des objectifs pédagogiques variés. C’est par exemple le cas dans Format Store, un logiciel destiné à former des vendeurs à la gestion de la relation clientèle, où l’apprenant est immergé, via son avatar, dans un supermarché virtuel, entièrement peuplé d’agents : les clients, mais aussi les articles, qui peuvent changer d’état, les panneaux d’informations, les caisses...

De telles simulations logicielles permettent d’étudier les principes de modélisation et les outils logiciels nécessaires à la définition de divers comportements. Les résultats peuvent ensuite être utilisés et implantés dans des robots physiques afin qu’ils évoluent dans un environnement réel. En procédant de la sorte, on s’affranchit dans un premier temps des difficultés liées aux contraintes physiques des robots afin de se concentrer sur les aspects comportementaux. En ce sens, les simulations multi-agents deviennent des laboratoires virtuels d’expérimentation.

Par exemple, nous l’avons vu pour le « flocking », les simulations multi-agents ont montré comment des comportements collectifs complexes tels que la formation de structures géométriques ou la navigation en formation pouvaient résulter d’interactions simples des agents. Récemment, ces mêmes mécanismes ont été implantés par les chercheurs de Stanford dans des milliers de robots autonomes élémentaires et ont fait la démonstration de leur efficacité.

Construire des comportements adaptatifs

Ces illustrations masquent les difficultés que pose la plupart du temps la définition de règles de comportements adéquates en fonction du but fixé aux agents. On doit d’abord déterminer et reproduire les caractéristiques physiques de l’environnement qui sont pertinentes par rapport au phénomène étudié : structure spatiale, lois physiques, événements qui y surviennent. Par ailleurs, chaque agent doit répondre aux informations perçues dans son environnement par des actions judicieuses. Le lien entre la perception et l’action peut être rudimentaire ou bien être fondé sur des systèmes de planification ou de déduction. De surcroît, l’environnement où les agents évoluent est dynamique, car modifié sans cesse par les actions et les déplacements de ces agents. La complexité de la perception, combinée au nombre de règles à évaluer, peut donc entraîner un coût de calcul élevé pour la prise de décision. Le caractère local des perceptions est alors un des points essentiels pour réduire ce coût.

Placés dans un environnement changeant et complexe dont ils n’ont qu’un savoir partiel, les agents doivent ainsi gérer des connaissances incomplètes et potentiellement erronées lorsqu’ils décident de leurs actions. Lorsque ces dernières conduisent à des impasses, elles peuvent être surmontées grâce au caractère adaptatif des comportements dont les agents sont dotés.

Pour ce faire, deux grandes approches du comportement individuel sont mises en oeuvre. Les agents dits « réactifs » sont construits à l’aide d’instructions simples qui dictent la réponse à apporter en présence d’événements prédéfinis. Ils sont très dépendants de leur contexte et sont incapables d’envisager un objectif à long terme, par exemple « gagner la bataille ». Leurs capacités individuelles d’adaptation et d’autonomie sont donc limitées.

De plus, les règles comportementales peuvent être interdépendantes, si bien que l’ajout de nouvelles compétences demande une révision de l’ensemble des règles. Grâce à des mécanismes d’apprentissage, l’agent peut disposer de comportements qui vont s’adapter aux situations rencontrées de façon à y répondre plus efficacement, mais cela ne résout pas la gestion des situations imprévues. Néanmoins, le modèle réactif est aujourd’hui le plus utilisé pour la modélisation de comportements dans les jeux vidéo, en raison d’abord de sa simplicité de conception et de programmation et de son faible coût de calcul. En outre, il est parfaitement approprié à la modélisation d’entités physico-chimiques et fait fréquemment apparaître des comportements collectifs efficaces.

Cependant, simuler des comportements intelligents proches de ceux des êtres humains, prenant en compte la réflexion, l’opportunisme ou l’esprit d’équipe, l’adaptation et l’indépendance, est de plus en plus souhaité. Ces compétences sont réservées à des agents plus évolués, les agents dits « cognitifs ». Alors que le comportement des agents réactifs dépend des événements qui surviennent dans leur contexte immédiat, la prise de décision des agents cognitifs s’appuie sur un raisonnement qui prend en compte les diverses possibilités d’action. Ils construisent ainsi des plans d’action afin de satisfaire des objectifs parfois lointains et abstraits, et sont capables d’adapter leurs plans à l’évolution du contexte.

Les agents cognitifs

Pour atteindre les buts qui leur sont fixés, les agents cognitifs élaborent et évaluent plusieurs plans d’action. Le principe le plus répandu est le chaînage arrière. L’agent cherche parmi les actions qu’il sait exécuter celle qui l’aiderait à atteindre le but fixé. Une fois une telle action déterminée, il étudie ses conditions d’application. Celles qui ne sont pas vérifiées deviennent des nouveaux buts, ou sous-buts, à satisfaire. La résolution suit ce principe de fonctionnement en cascade jusqu’à ce que l’agent arrive à une action dont toutes les conditions sont satisfaites. La plupart des agents cognitifs raisonnent ainsi en remontant de l’aboutissement des actions vers les conditions autorisant leur réalisation.

La tâche reste complexe, mais on peut utiliser les algorithmes conçus par les spécialistes en intelligence artificielle pour aborder ces problèmes. Les résultats sur la planification aident chaque agent à établir l’ensemble des possibilités qui s’offrent à lui à chaque instant. Elles se traduisent par autant d’actions exécutables par l’agent dans le contexte actuel. Des mécanismes de sélection d’action sélectionnent ensuite l’action qui sera retenue. Les mêmes algorithmes génériques peuvent ainsi être utilisés par tous les agents au sein d’une simulation.

Les agents peuvent néanmoins être pourvus de capacités différentes. Ils sont ainsi construits à partir de briques élémentaires qui décrivent ce que les agents peuvent faire au sein de la simulation et comment ils le font. Les variations dans les comportements obtenus résultent donc, d’une part, des contextes locaux distincts pour chaque agent et, d’autre part, des différences de compétences entre agents. On peut ainsi distinguer les agents par les capacités qu’on leur affecte. En attribuant une compétence « soigner » et aucune compétence de combat à un agent dans une bataille, le calcul de ses plans d’action en fera un infirmier et non un combattant. On peut aussi influer sur le comportement de l’agent en lui faisant préférer l’emploi d’une compétence à une autre. En variant ces préférences entre les agents, même dotés de compétences identiques, on obtient une diversité de comportements. Ces possibilités facilitent la mise en place des simulations et contribuent à construire des « personnalités » différentes d’un agent à l’autre.

La modélisation par des agents a un autre avantage. Dans les exemples précédents, les agents remplacent des « individus », des êtres vivants. Toutefois, en pratique, un agent peut représenter n’importe quelle entité susceptible d’interagir avec d’autres. Cela revient parfois à introduire dans la simulation un nombre d’agents considérable, mais les moteurs de simulation actuels, dotés de mécanismes d’optimisation, calculent efficacement les interactions de toutes ces entités. On dispose ainsi de modèles où les objets d’étude sont traités de façon uniforme.

Prenons un exemple, celui de l’élaboration de « smart cities », un enjeu important consistant à doter « d’intelligence » des bâtiments, des routes, des dispositifs urbains, des véhicules, afin d’optimiser les futurs réseaux de ressources, d’énergie, de transport... La simulation peut, en amont de la réalisation technique in situ, apporter une aide dans la prise de décision en offrant des outils pour tester diverses hypothèses et comparer des scénarios. Pour ce faire, on doit modéliser comme agents les divers artefacts et acteurs du système. Les réseaux de transport (électricité, gaz, eau, routes...) peuvent être coupés en tronçons qui sont autant d’agents.

Sur ces réseaux peuvent circuler les habitants (piétons, véhicules, transports collectifs), mais aussi les ressources, telle l’eau, dont la qualité peut être modifiée en retour par les autres activités urbaines. Les bâtiments deviennent aussi des agents qui prélèvent une part des ressources, des individus, des véhicules selon leur nature et leurs objectifs.

campus-osm-final2

TRAFFICGEN est un simulateur multi-agents de trafic routier. Dans un modèle de réseau calqué
sur la réalité, on peut introduire des véhicules ainsi que des perturbations pour en étudier les effets
et contribuer à l’aménagement routier. © SMAC - Trafficgen.


C’est ce genre de modélisation qui a été retenu par les concepteurs du jeu SimCity 2013 pour leur nouveau moteur GlassBox développé par la société Maxis (voir l’encadré). La particularité du moteur est d’être complètement fondé sur les principes de la simulation multi-agents, la logique y étant poussée très loin puisque tout élément qui a une influence sur le jeu est un agent doté d’un comportement. Ce n’est pas surprenant pour les Sim (les habitants d’une Simcity) qui ont par exemple pour objectif de trouver un emploi, mais c’est plus étonnant pour les voitures, les bâtiments et même les tuyaux qui transportent les ressources.

simcity1simcity2simcity3a

Dans SimCity 2013, tous les éléments du jeu sont des agents qui se propagent et influent sur le déroulement du jeu : les voitures, l’eau, le feu...

Vers une plus grande échelle

Cette nouvelle illustration du lien entre jeux vidéo et études scientifiques montre en outre que cette approche « tout-agent » peut supporter une montée d’échelle à la fois en nombre total d’agents mais aussi en nombre de « familles » différentes d’agents. Elle offre également une grande souplesse et de nombreuses possibilités dans la réalisation de simulations. En unifiant les principes qui dirigent l’ensemble des entités impliquées dans la simulation, il devient plus facile d’y ajouter des nouveaux éléments et de les faire agir et interagir afin d’enrichir la simulation et de multiplier les phénomènes qu’elle met en évidence. Néanmoins, l’apparition dans la dernière décennie de systèmes à très large échelle soulève de nouvelles problématiques sur lesquelles se focalisent les travaux de recherche actuels dans notre domaine.

Le déploiement à grande échelle des simulations par agents est l’un des autres enjeux majeurs des recherches actuelles. L’application Massive, qui anime jusqu’à plusieurs dizaines de milliers de combattants, est l’un des exemples les plus impressionnants de gestion simultanée d’un grand nombre d’agents. Certes, la plupart des simulations ne mettent en œuvre que quelques centaines d’agents, ce qui est suffisant pour l’étude de systèmes clos et limités en taille ou pour celle de groupes imposants considérés sous un angle précis, par exemple les nourrices dans une colonie de fourmis, une équipe de robots ou un groupe d’amis sur un campus universitaire. Toutefois, des simulations à plus vaste échelle, mettant en jeu des millions d’agents extrêmement diversifiés, sont nécessaires pour l’étude de certains phénomènes, tels la propagation d’une maladie, un comportement économique global, la diffusion dans les réseaux sociaux...

Le premier problème est celui du temps de calcul. La progression de la puissance des machines promet des simulations de plus en plus rapides, mais il s’agit surtout de programmer des modèles de comportements et des architectures d’agents avec des algorithmes concis et efficaces.

Un bon paquet d’agents

Traiter un grand nombre d’entités soulève aussi une question méthodologique : à quel niveau de détail doit-on placer les agents ? Prenons un exemple en biologie moléculaire, un des domaines les mieux adaptés à l’élaboration d’architectures et de modèles d’agents pour des applications à vaste échelle. Une bactérie renferme environ 4 000 types de molécules dont les trois quarts assurent des fonctions cellulaires. Ne sachant pas toujours lesquelles sont pertinentes dans un mécanisme donné, on doit en simuler un très grand nombre. Si l’on se place à un niveau d’analyse plus fin, on atteint des populations de 1010 molécules dans la cellule ! Il est impossible de modéliser chacune d’elles. Doit-on alors créer un agent par espèce moléculaire ou pour un nombre fixé de molécules ? Comment faire le lien entre ces agents arbitraires et les concentrations ? Comment représenter les situations où quelques centaines d’agents molécules seulement sont impliquées ?

Un changement d’échelle de représentation devient intéressant. On regroupe des paquets d’agents en agents de plus haut niveau pour économiser du temps de calcul ; c’est aussi indispensable pour se placer à un niveau donné et faciliter l’identification du niveau adéquat (molécules, groupes de molécules, cellules...).

La simulation par agents est ainsi un outil pratique pour formuler des hypothèses en biologie moléculaire et les tester à faible coût. Dans cette situation, on est conduit à développer des simulations multi-agents « multiniveaux ». Les recherches dans ce domaine visent à automatiser le passage d’un niveau à l’autre, c’est-à-dire à détecter des groupes d’agents qui peuvent être remplacés par un agent macroscopique, et inversement. Enfin, la révolution du « Big Data » n’est pas sans conséquence sur la conception de simulations multiagents : la disponibilité croissante de grandes masses de données concernant des systèmes complexes ne les rend pas plus faciles à analyser. Toutefois, elles sont utiles pour paramétrer avec plus de réalisme les propriétés et les comportements des agents. De plus, les techniques de recherche d’information qui sont employées pour traiter les données réelles peuvent être employées de la même façon sur les données produites par les simulations, ce qui offre de nouveaux outils de comparaison et de validation.

L’agent fait le bonheur

Les modèles multi-agents, où des entités informatiques autonomes communiquent, interagissent, s’adaptent, voire se coordonnent et planifient leurs actions, autorisent la mise à l’épreuve des hypothèses de fonctionnement d’un système. On peut aussi comprendre l’apparition de caractères globaux et de structures macroscopiques à partir d’entités individuelles. Les modèles multi-agents sont ainsi un cadre naturel pour étudier des phénomènes complexes ou les comportements collectifs d’envergure.

Les outils nécessaires à ces simulations sont semblables quelle que soit la finalité de la simulation. L’expansion du domaine des jeux vidéo, qui fournissent un banc d’expérimentation remarquable, laisse espérer le développement de techniques informatiques puissantes et génériques applicables à des domaines tels que la sociologie ou la biologie. De surcroît, la capacité de ces techniques à déborder du champ de la simulation pour fournir des outils de contrôle en temps réel d’objets physiques communicants (robots, véhicules intelligents, réseaux de distribution, smartphones ou tablettes tactiles) permet d’envisager dans un avenir proche leur généralisation en tant qu’outils d’aide à la décision, dans de nombreux secteurs d’activité.

Bibliographie