Introduction aux systèmes multi-agents

Dans le monde mer­veilleux de l'intelligence arti­fi­cielle, il existe une caté­go­rie de sys­tèmes de simu­la­tion ins­pi­rés de la nature et par­ti­cu­liè­re­ment adap­tés à de nom­breuses pro­blé­ma­tiques en bio­lo­gie : les sys­tèmes mul­ti-agents. Ces sys­tèmes sont com­po­sés d'entités auto­nomes (les agents) qui inter­agissent entre elles et avec un envi­ron­ne­ment dans lequel elles évo­luent. Bien évi­dem­ment, l'inspiration "bio­lo­gique" pro­vient des insectes sociaux (four­mis, ter­mites, etc.) dont le com­por­te­ment indi­vi­duel et les inter­ac­tions mènent à l'apparition de phé­no­mènes ou de com­por­te­ments com­plexes. Ce phé­no­mène est appe­lé émer­gence et repré­sente une carac­té­ris­tique fon­da­men­tale de ces sys­tèmes.

Les sys­tèmes mul­ti-agents trouvent des appli­ca­tions dans de très nom­breux domaines : objets com­mu­ni­cants, sys­tèmes infor­ma­tiques dis­tri­bués, seg­men­ta­tion d'images, simu­la­tions de catas­trophes, d'interactions sociales, de réseau rou­tier,  de pro­pa­ga­tion d'épidémie, de réac­tion en chaîne, etc. En fait, toute situa­tion dans laquelle on peut iden­ti­fier des enti­tés pré­cises bien défi­nies et en inter­ac­tion. Mais, me direz-vous, cer­taines de ces situa­tions peuvent aus­si être simu­lées grâce aux mathé­ma­tiques, avec des sys­tèmes d'équations !? Oui, en effet, et on retrouve les mêmes résul­tats.

M'sieur l'agent ! Au loup !

Par exemple, le sys­tème proie-pré­da­teur bien connu. Deux popu­la­tions sont en inter­ac­tion : une de proies et une de pré­da­teurs. Les pré­da­teurs chassent les proies, se repro­duisent et meurent tan­dis que les proies ne font que se repro­duire et mou­rir. On cherche alors à connaître quelle est la dyna­mique de ce sys­tème, soit les effec­tifs des deux popu­la­tions au cours du temps. Dans sa forme la plus simple, la méthode mathé­ma­tique qui per­met de modé­li­ser ce sys­tème com­porte deux équa­tions : une pour l'effectif des proies et l'autre pour l'effectif des pré­da­teurs avec des taux de mortalité/​reproduction pour chaque popu­la­tion (détails ici). L'interaction entre les deux popu­la­tions se fait par deux rela­tions :

• La dépen­dance du taux de mor­ta­li­té des proies vis à vis du nombre de pré­da­teurs.
• La dépen­dance du taux de repro­duc­tion des pré­da­teurs vis à vis du nombre de proies.

Dans le cas de la simu­la­tion par sys­tème mul­ti-agents, on va défi­nir deux types d'agents : un agent proie et un agent pré­da­teur. Ici aus­si, on défi­ni­ra pour chaque type d'agent un taux de mor­ta­li­té et de repro­duc­tion. Mais, comme ce sys­tème sup­pose que proies et pré­da­teurs se déplacent dans l'environnement (sur une carte par exemple), on défi­ni­ra aus­si un mou­ve­ment pour chaque agent. La pré­da­tion en tant que telle est défi­nie par une action des agents pré­da­teurs : quand un pré­da­teur ren­contre une proie, il la mange. C'est à dire qu'on fait dis­pa­raître l'agent proie de la simu­la­tion. Voi­ci ce que peut don­ner une telle simu­la­tion en vidéo :

Comme vous pou­vez le voir sur la vidéo, les courbes tra­cées au fur et à mesure de la simu­la­tion ont la même allure que celles obte­nues avec le sys­tème d'équation. Un des avan­tages d'une simu­la­tion avec des agents est qu'on peut modi­fier les para­mètres du sys­tème en temps réel et ain­si voir immé­dia­te­ment la réponse. On a éga­le­ment une simu­la­tion située dans un envi­ron­ne­ment auquel on peut ajou­ter des contraintes (obs­tacles, zones sans nour­ri­ture, etc.). La diver­si­té des para­mètres peut être très impor­tante !

Lorsqu'on construit une simu­la­tion avec des agents, on rai­sonne en terme d'enti­tés, de com­por­te­ments et d'inter­ac­tion.

Fais commeuuh l'oiseau

Un autre sys­tème mul­ti-agents très connu est celui des boids. La ques­tion dans ce cas est de simu­ler un vol d'oiseaux à par­tir des oiseaux eux-mêmes. Un agent est donc un oiseau qui évo­lue dans un envi­ron­ne­ment en 3D selon 3 règles :

• évi­ter les col­li­sions (ne pas être trop proche des voi­sins),
• res­ter ali­gné sur ses voi­sins (le dépla­ce­ment se fait sui­vant une direc­tion don­née),
• res­ter proche du groupe (ne pas trop s'éloigner des voi­sins).

Je vous laisse appré­cier le résul­tat :

Le phé­no­mène qui émerge dans cette simu­la­tion est la for­ma­tion et le com­por­te­ment du vol d'oiseau : à aucun moment dans la défi­ni­tion des agents, on ne leur pré­cise de for­mer un vol. La seule per­cep­tion qu'ils ont et les règles de com­por­te­ment sont défi­nies par rap­port à leurs voi­sins les plus proches, donc une infor­ma­tion locale.

Je peux sentir leur présence …

La notion de per­cep­tion est fon­da­men­tale dans un sys­tème mul­ti-agents car elle per­met l'interaction agent/​agent et agent/​environnement. Ces inter­ac­tions peuvent être réa­li­sées de manière très dif­fé­rentes (trans­mis­sion de mes­sage, dépôt/​collecte d'information dans l'environnement, etc.) pour reflé­ter les méca­nismes réels qu'on sou­haite simu­ler. Quand il doit prendre une déci­sion, un agent fait appel à ses connais­sances et ses méca­nismes internes tout en éva­luant ce que sa per­cep­tion lui per­met de sen­tir (autres agents, obs­tacles, signaux divers).

Pour finir, les agents que j'ai pré­sen­té ici sont des agents réac­tifs et sont oppo­sés aux agents cog­ni­tifs. Les agents réac­tifs ne sont pas consi­dé­rés comme "intel­li­gents" car ils se contentent de répondre à des sti­mu­li. Les agents cog­ni­tifs, quant à eux, pos­sèdent des rai­son­ne­ments internes com­plexes, des buts à réa­li­ser et une cer­taine mémoire des évé­ne­ments pas­sés. Ces deux caté­go­ries d'agents per­mettent de répondre à un grand nombre de pro­blé­ma­tiques très variées. Je vous invite à aller voir les exemples de sys­tèmes mul­ti-agents four­nis par le logi­ciel Net­Lo­go pour vous rendre compte des pos­si­bi­li­tés.

Mer­ci aux agents relec­teurs : Clem, nal­lias, ZaZo0o

A voir :

Un ancêtre des sys­tèmes mul­ti-agents : le jeu de la vie

chaîne You­Tube de Pas­cal Bal­let avec des exemples variés de sys­tèmes mul­ti-agents

Page offi­cielle décri­vant le sys­tème des boids (en anglais)