Les Systèmes Multi-Agents

Abdelhafid Benaouda

22 octobre 2021

Table des matières

1 Introduction 2

2 Historique 2
Le modèle des acteurs : . . . . . . . . . . . . . . . . . . . . . 3
Le protocole Contract Net : . . . . . . . . . . . . . . . . . . . 3
Les premières applications : . . . . . . . . . . . . . . . . . . 4

3 Agent 5

4 Les Systèmes Multi-Agents 7

5 Travaux Pratiques : 11

6 Développement 12

Résumé

Ce cours non exhaustif, inspiré de [3] [4] [5] [1], présente les principaux éléments
d’explication et d’éclaircissement du paradigme des Systèmes Multi-Agents (SMA).
Il présente :
— Historique des SMA.
— Notion d’Agent, typologie d’agents.
— Les SMA.
— Domaines d’application des SMA.
— etc.

1
1 Introduction
Historiquement, entant que concepts, la notion d’agent logiciel et le pa-
radigme des Systèmes Multi-agents sont anciens. La démocratisation des ré-
seaux et de l’Internet ont contribué grandement à leurs mise-en-œuvre et
sont actuellement utilisés, dans différents domaines, pour la résolution des
problèmes complexes supportant un déploiement réparti.

2 Historique
En 1980, un groupe de chercheurs s’est réuni pour discuter des défis
concernant la résolution “intelligente” de problèmes dans un système com-
portant plusieurs résolveurs de problèmes. Lors de cette réunion, il a été dé-
cidé que l’intelligence artificielle distribuée n’axerait pas ses travaux sur les
détails de bas-niveau de la parallélisation ni sur comment paralléliser les al-
gorithmes centralisés mais plutôt sur le fait de savoir comment un groupe de
solutionneurs de problèmes pourrait coordonner ses efforts afin de résoudre
des problèmes de manière efficace.
On peut dire que les SMA ont vu le jour avec l’avènement de l’intelligence
artificielle distribuée (IAD). À ses début toutefois, l’IAD ne s’intéressait qu’à
la coopération entre résolveurs de problèmes afin de contribuer à résoudre
un but commun. Pour y parvenir, on divisait en général, un problème en
sous problèmes, et on allouait ces sous-problèmes à différents résolveurs qui
sont appelés à coopérer pour élaborer des solutions partielles. Celles-ci sont
finalement synthétiser en une réponse globale au problème de départ.
Ainsi donc, l’IAD au départ privilégiait le “problème à résoudre” tout en
mettant l’accent sur la résolution d’un tel problème par de multiple entités
intelligentes. Dans les SMA d’aujourd’hui, les agents sont (entre autres) auto-
nomes, possiblement préexistants et généralement hétérogènes. Dans ce cas,
l’accent est plutôt mis sur le fait de savoir comment les agents vont coordon-
ner leurs connaissances, buts et plans pour agir et résoudre des problèmes.
Parmi les systèmes développés tout au début, il y avaient :

2
 Fonction principale Emergence d’une
pré-determinée solution globale

Auto
Décomposition Organisation

Algorithmes,
Synchronisation, Réseau
planification

Exécution
distribution
parallèle d’algorithmes
des objectifs
complexes

F IGURE 1 – Résolution classique VS Emergence de résolution SMA [1]

Le modèle des acteurs : Un des premiers modèles proposé à l’époque

de l’IAD fut le modèle des Acteurs [2]. Les acteurs sont des composantes
autonomes d’un système qui communiquent par messages asynchrones. Ils
sont composés d’un ensemble de primitives, parmi lesquelles on retrouve :
— Create : créer un acteur à partir d’un ensemble de paramètres décrivant
son comportement ;
— Send : envoyer un message à un autre acteur ;
— Become : changer l’état local d’un acteur.
Les acteurs s’avèrent être un modèle assez naturel pour le calcul paral-
lèle. Cependant, les divers modèles d’acteurs, comme bien d’autres modèles
de l’intelligence artificielle distribuée font face à un problème de cohérence.
Leur granularité fine pose des problèmes de comportement dans des sys-
tèmes qui renferment plusieurs acteurs. Ils éprouvent également des difficul-
tés à atteindre des buts globaux avec seulement des connaissances locales.

Le protocole Contract Net : Le protocole du Contract Net fut une des

premières solutions au problème d’allocation de tâches auquel fait face gé-
néralement un ensemble de résolveurs de problèmes. Dans ce protocole, les
agents peuvent prendre deux rôles : gestionnaire ou contracteur. L’agent qui

3
 Acteur X
Boite à lettres

Spécifier un
Envoi de remplaçant
message N N+1

Création d’acteur

Comportement
Acteur Y

F IGURE 2 – La notion d’acteur [1]

doit exécuter une tâche donnée (le gestionnaire) commence tout d’abord par
décomposer cette tâche en plusieurs sous-tâches. Il doit ensuite annoncer les
différentes sous-tâches au reste des agents de l’environnement. Les agents
qui reçoivent une annonce de tâche à accomplir peuvent ensuite faire une
proposition devant refléter leur capacité à remplir cette tâche. Le gestion-
naire rassemble ensuite toutes les propositions qu’il a reçues et alloue la tâche
à l’agent ayant fait la meilleure proposition.

Les premières applications : Parmi les premières applications dévelop-

pées à l’aide de la technologie multiagents, on retrouve une application dans
le contrôle du trafic aérien et une autre dans la surveillance de véhicules mo-
torisés. Pour le contrôle de trafic aérien, Cammarata a étudié des stratégies
de coopération pour pouvoir résoudre les conflits entre les plans d’un groupe
d’agents. Ces stratégies ont pu être ensuite appliquées dans le cadre d’un
système de contrôle du trafic aérien. Dans ce système, chaque agent (repré-
sentant un avion) cherche à bâtir un plan de vol qui devrait le garder à une
distance sécuritaire de chaque autre agent. Dans le cas où des agents se re-

4
trouveraient dans une situation conflictuelle, ils doivent alors choisir parmi
eux, un agent apte à élaborer un nouveau plan de vol sans engendrer de
nouveaux conflits. Pour faire ce choix, Cammarata et ses collègues ont opté
pour deux stratégies qu’ils ont comparées entre elles. La première a consisté
à choisir l’agent le mieux informé ou l’agent le moins contraint pour jouer le
rôle de planificateur central et élaborer un nouveau plan de vol qui résou-
drait le conflit. La deuxième a consisté à faire le partage suivant : il revient
à l’agent le mieux informé d’élaborer un nouveau plan de vol et à l’agent le
moins contraint de l’exécuter.
La surveillance de véhicules motorisés tournait, quant à elle, autour du
système DVMT (Distributed Vehicle Monitoring Task). Ce système avait comme
tâche principale d’identifier quel type de véhicule circulait dans la zone où
étaient placés ses senseurs. À partir de ces interprétations, il devait tenter
d’établir une description des mouvements des véhicules dans la région qu’il
supervisait. Comme bien d’autres systèmes multiagents de l’époque, le sys-
tème DVMT utilisait un blackboard pour coordonner les efforts de ses dif-
férents agents. Rappelons qu’un blackboard est simplement une structure
de données partagées entre divers agents. Ces derniers peuvent la consulter
pour obtenir des informations sur l’état actuel du problème ou y écrire la
partie de la solution qu’ils ont obtenue.

3 Agent
Le concept d’agent a été l’objet d’études pour plusieurs décennies dans
différentes disciplines. Il a été non seulement utilisé dans les systèmes à base
de connaissances, la robotique, le langage naturel et d’autres domaines de
l’intelligence artificielle, mais aussi dans des disciplines comme la philoso-
phie et la psychologie. Aujourd’hui, avec l’avènement de nouvelles techno-
logies et l’expansion de l’Internet, ce concept est encore associé à plusieurs
nouvelles applications comme agent ressource, agent courtier, assistant per-
sonnel, agent interface, agent ontologique, etc.
Dans la littérature, on trouve une multitude de définitions d’agents. Elles
se ressemblent toutes, mais diffèrent selon le type d’application pour laquelle

5
est conçu l’agent. Des discussions ont été menées sur les différentes défini-
tions attribués aux agents ainsi que la différence entre un agent et un pro-
gramme classique. À titre d’exemple, voici l’une des premières définitions
de l’agent dûe à J. Ferber [4] :
Un agent est une entité autonome, réelle ou abstraite, qui est capable d’agir sur
elle-même et sur son environnement, qui, dans un univers multiagent, peut com-
muniquer avec d’autres agents, et dont le comportement est la conséquence de ses
observations, de ses connaissances et des interactions avec les autres agents.
Il ressort de cette définition des propriétés clés comme :
— l’autonomie,
— l’action,
— la perception
— et la communication.
D’autres propriétés peuvent être attribuées aux agents. Nous citons en parti-
culier :
— la réactivité,
— la rationalité,
— l’engagement,
— et l’intention.
Pour Wooldridge [5] qui représente une grande école de recherche dans
le domaine des SMA :
Un agent est un système informatique, situé dans un environnement, et qui agit
d’une façon autonome et flexible pour atteindre les objectifs pour lesquels il a été
conçu.
Il ressort de cette définition d’autres propriétés clés comme :
— situé,
— environnement,
— et flexible.
Ces termes peuvent être définis comme suit :
Situé : l’agent est capable d’agir sur son environnement à partir des en-
trées sensorielles qu’il reçoit de ce même environnement. Exemples : sys-
tèmes de contrôle de processus, systèmes embarqués, etc.
Autonome : l’agent est capable d’agir sans l’intervention d’un tiers (hu-

6
 main ou agent) et contrôle ses propres actions ainsi que son état interne.
Flexible : l’agent dans ce cas est :
* capable de répondre à temps : l’agent doit être capable de percevoir son
environnement et élaborer une réponse dans les temps requis ;
* proactif : l’agent doit exhiber un comportement proactif et opportu-
niste, tout en étant capable de prendre l’initiative au “bon” moment ;
* social : l’agent doit être capable d’interagir avec les autres agents (lo-
giciels et humains) quand la situation l’exige afin de compléter ses
tâches ou aider ces agents à accomplir les leurs.
Bien entendu, dépendement des applications, certaines propriétés sont
plus importantes que d’autres, il peut même s’avérer que pour certaines
types d’applications, des propriétés additionnelles soient requises. Il convient
cependant de souligner que la présence des propriétés qu’on vient de
voir comme l’autonomie, la flexibilité, la sociabilité, etc., donne naissance
au paradigme agent tout en le distinguant des systèmes conventionnels
comme les systèmes distribués, les systèmes orientés objets et les sys-
tèmes experts.

4 Les Systèmes Multi-Agents

Un système multiagent est un système distribué composé d’un ensemble
d’agents. Contrairement aux systèmes d’IA, qui simulent dans une certaine
mesure les capacités du raisonnement humain, les SMA sont conçus et im-
plantés idéalement comme un ensemble d’agents interagissants, le plus sou-
vent, selon des modes de coopération, de concurrence ou de coexistence.
Un SMA est généralement caractérisé par :

1. chaque agent a des informations ou des capacités de résolution de pro-

blèmes limitées, ainsi chaque agent a un point de vue partiel ;

2. il n’y a aucun contrôle global du système multiagent ;

3. les donnés sont décentralisées ;

4. le calcul est asynchrone.

Les SMA sont des systèmes idéaux pour représenter des problèmes pos-

7
sédant de multiples méthodes de résolution, de multiples perspectives et/ou
de multiples résolveurs. Ces systèmes possèdent les avantages traditionnels
de la résolution distribuée et concurrente de problèmes comme la modula-
rité, la vitesse (avec le parallélisme), et la fiabilité (dûe à la redondance). Ils
héritent aussi des bénéfices envisageable de l’Intelligence Artificielle comme
le traitement symbolique (au niveau des connaissances), la facilité de mainte-
nance, la réutilisation et la portabilité mais surtout, ils ont l’avantage de faire
intervenir des schémas d’interaction sophistiqués. Les types courants d’in-
teraction incluent la coopération (travailler ensemble à la résolution d’un but
commun) ; la coordination (organiser la résolution d’un problème de telle
sorte que les interactions nuisibles soient évitées ou que les interactions bé-
néfiques soient exploitées) ; et la négociation (parvenir à un accord acceptable
pour toutes les parties concernées).
Bien que les SMA offrent de nombreux avantages potentiels, ils doivent
aussi relever beaucoup de défis. Voici les problèmes inhérents à la conception
et à l’implémentation des SMA :

1. Comment formuler, décrire, décomposer, et allouer les problèmes et syn-

thétiser les résultats ?

2. Comment permettre aux agents de communiquer et d’interagir ? Quoi et

quand communiquer ?

3. Comment assurer que les agents agissent de manière cohérente

— en prenant leurs décisions ou actions,
— en gérant les effets non locaux de leurs décisions locales et
— en évitant les interactions nuisibles ?

4. Comment permettre aux agents individuels de représenter et raisonner

sur les actions, plans et connaissances des autres agents afin de se coor-
donner avec eux ? Comment raisonner sur l’état de leurs processus coor-
donnés (comme l’initialisation ou la terminaison) ?

5. Comment reconnaître et réconcilier les points de vue disparates et les in-

tentions conflictuelles dans un ensemble d’agents essayant de coordon-
ner leurs actions ?

6. Comment trouver le meilleur compromis entre le traitement local au ni-

8
 veau d’un seul agent et le traitement distribué entre plusieurs agents
(traitement distribuée qui induit la communication) ? Plus généralement,
comment gérer la répartition des ressources limitées ?

7. Comment éviter ou amoindrir un comportement nuisible du système

global, comme les comportements chaotiques ou oscillatoires ?

8. Comment concevoir les plates-formes technologiques et les méthodolo-

gies de développement pour les SMA ?

Les SMA sont à l’intersection de plusieurs domaines scientifiques : in-

formatique répartie et génie logiciel, intelligence artificielle, vie artificielle.
Ils s’inspirent également d’études issues d’autres disciplines connexes no-
tamment la sociologie, la psychologie sociale, les sciences cognitives et bien
d’autres. C’est ainsi qu’on les trouve parfois à la base des :
— systèmes distribués ;
— interface hommes-machines ;
— bases de données et bases de connaissances distribuées coopératives ;
— systèmes pour la compréhension du langage naturel ;
— protocoles de communication et réseaux de télécommunications ;
— programmation orientée agents et génie logiciel ;
— robotique cognitive et coopération entre robots ;
— applications distribuées comme le web, l’Internet, le contrôle de trafic
routier, le contrôle aérien, les réseaux d’énergie, etc.
Les recherches dans le domaine des systèmes multiagents poursuivent
deux objectifs majeurs :
— Le premier concerne l’analyse théorique et expérimentale des mécanismes
qui ont lieu lorsque plusieurs entités autonomes interagissent.
— Le second s’intéresse à la réalisation de programmes distribués capables
d’accomplir des tâches complexes via la coopération et l’interaction.
Leur position est donc double : d’un côté elles se placent au sein des sciences
cognitives, des sciences sociales et des sciences naturelles pour à la fois mo-
déliser, expliquer et simuler des phénomènes naturels, et susciter des mo-
dèles d’auto-organisation ; de l’autre côté, elles se présentent comme une pra-
tique, une technique qui vise la réalisation de systèmes informatiques com-
plexes à partir des concepts d’agent, de communication, de coopération et de

9
coordination d’actions.
Les agents autonomes et les systèmes multiagents représentent une nou-
velle approche pour l’analyse, la conception et l’implantation des systèmes
informatiques complexes. La vision basée sur l’entité agent offre un puissant
répertoire d’outils, de techniques, et de métaphores qui y ont le potentiel
d’améliorer considérablement les systèmes logiciels.
Il convient de ne pas confondre “agent” et “objet”. Tout d’abord, tout
comme les agents, les objets encapsulent leur état interne (leurs données). Ils
peuvent également poser des actions sur cet état par le biais de leurs mé-
thodes et ils communiquent en s’envoyant des messages. À ce niveau, ils
différent des agents par leur degré d’autonomie. En effet, une méthode doit
être invoquée par un autre objet pour pouvoir accomplir ses effets. Un agent,
quant à lui, recevra une requête et décidera de son propre gré s’il doit po-
ser ou non une action. Une seconde différence provient du caractère flexible
(réactif, pro-actif et social) du comportement d’un agent.
Bien que certains diront qu’il est possible de bâtir un programme orienté-
objet qui intègre ces caractéristique, on doit également voir que le modèle
standard d’un objet ne dit rien à propos de ces types de comportements. La
troisième et dernière différence provient du fait qu’on considère un agent
comme étant lui-même une source de contrôle au sein du système tandis que
dans un système orienté-objet, on n’a qu’une seule source de contrôle.

10
5 Travaux Pratiques :
Soient trois entités logicielles :

1. fibo (suite de Fibonacci),

f ibo : fn+2 = fn+1 + fn

avec : f0 = 0, f1 = f2 = 1

donc f ibo génère {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...}

2. carre : génère {0, 1, 4, 9, 16, 25, ...}

3. classeur : procède au classement des nombres envoyés, au fur et à me-

sure, c’est-à-dire en temps réel, des traitements réalisés par f ibo et carre.

Le résultat du traitement de classeur étant de classer les informations

reçues, en même temps et en temps réel par carre et fibo, ce qui produit, à
un instant t : {0, 1, 1, 1, 2, 3, 4, 5, 8, 9, ...}

Normalement, la boucle de traitement est infinie mais, comme la capacité

de nos machines est limitée, limitez-vous à un M ax.

TP1 : Les agents f ibo, carre et classeur sont forcément associés à des pro-
cessus (processus au sens Unix ou thread) et communiquent entre eux (en gé-
néral par tube). f ibo et carre envoient, chacun des nombres traités, en temps
réel, à classeur qui aussi, classe les nombres reçus, en temps réel, dès leurs
réceptions.

TP2 : Déploiement sur réseau, c’est-à-dire, chacun des agents f ibo, carre
et classeur est sur une machine sur réseau à part (host). La communication
doit se faire forcément par sockets.

TP3 : En utilisant l’API java le JMS (Java Messaging Service), où, chaque
agent envoie ses données aux autres via des messages JMS au lieu de le faire
par passage par arguments.

Dans vos rapports, tirez des conclusions sur les entités f ibo, carre et
classeur en considérant que :

11
— Chaque entité est autonome,
— la communication entre ces entités se fait par message,
— en supposant que chaque entité connaît ses interlocuteurs (environne-
ment), f ibo(classeur), carre(classeur) et classeur(f ibo, carre)
Peut-on parler, à votre avis, d’agents réactifs (fibo, carre et classeur) et de
SMA ?

6 Développement
Langage de Programmation : Java ou C ou C++ mais de préférence en
Java car les TP suivants seront réalisés dans ce langage.

Déploiement : L’exécution en mode console suffit (Pas besoin d’interface

graphique !).

OS utilisé : Linux est souhaité mais, pour le TP2, un des hosts doit être
un MSWindows, c’est-à-dire que le réseau doit être hétérogène.

Le responsable du module SMA

Abdelhafid Benaouda

12
Références
[1] Benaouda A. Contribution à la conception et à l’implémentation d’un langage
de spécification formelle dédié à la e-maintenance des systèmes de production par
l’approche des Systèmes Multi-Agents. Thèse de doctorat, Université Setif-1,
Département d’Informatique, Sétif, Algérie, 2006.

[2] G. Agha and C. Hewitt. Concurrent programming using actors. Object-

Oriented Concurrent Programming, Computer Systems Series, pages 37-
53, MIT Press,1988.

[3] I. Jarras et B. Moulin B. Chaib-draa. Agent et systèmes multiagents.

Hermes, 2001.

[4] Ferber J. Les Systèmes Multi-agents : Vers une intelligence collective. Inter-
Editions, Paris, 1995.

[5] Wooldrige M. Intelligent agents, a Modern Approach to Distributed Artficial

Intelligence. G. Weiss (Ed.), MIT Press, 2001.

13