Introduction aux systèmes multi-agents

Roger Nkambou

Plan

• Qu’est ce qu’un agent ?– Historique– Les propriétés des agents– Les applications des agents autonomes

• Les systèmes multi-agents– Propriétés d’un système multi-agent– Le cadre d’exécution – Historique

• Interaction dans les SMA

Qu’est-ce qu’un agent ?

• Définition de Ferber:

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 multi-agent, peut communiquer avec d’autres agents, et dont le comportement est une conséquence de ses observations, de ses connaissances et de ses interactions avec les autres agents.

Qu’est-ce qu’un agent ?

• Il ressort de cette définition des propriétés clés comme:– L’autonomie

– Le raisonnement et l’action

– La perception

– La communication avec l’extérieur.

• En plus, d’autres propriétés sont souvent associées au agents:– Réactivité, rationalité, engagement, intention etc.

Qu’est-ce qu’un agent ?

• Définition de Sycara et Wooldridge

Un agent est un système informatique, situé dans un environnement, et qui agit d’une façon autonome et flexible pour atteindre certains des objectifs pour lesquels il a été conçu.

Agent situé

• Un agent est dit situé s’il est capable d’agir sur son environnement à partir des entrées sensorielles qu’il reçoit de ce même environnement.

• Par exemple: systèmes de contrôle de processus, agent de supervision dans un laboratoire virtuel etc.

Agent autonome

• Un agent est dit autonome s’il est capable d’agir sans l’intervention d’un tiers (humain ou agent) et contrôle ses propres actions ainsi que son état interne.

• L’autonomie d’un agent est bien entendu limitée par son comportement dans une société d’agents.

Ce qu’un agent n’est pas

• Un agent n’est pas – Un objet

Agent flexible

La flexibilité d’un agent est liée à :• Sa capacité de répondre à temps (percevoir son

environnement et réagir à temps)• Sa proactivité (sa capacité à prendre l’initiative et

à être opportuniste au bon moment)• Sa capacité d’interagir avec les autres agents

quand la situation l’exige (pour compléter ses tâches ou coopérer avec eux) => aspects sociaux.

Contexte de la recherche sur les agents

Résolution

distribuée de pbs

Agents et

Systèmes Multi-agentIA Parallèle

IA distribuée

Motivations pour la recherche sur les agents

• Au départ, et du point de vue IA distribuée

modularité pour réduire la complexité

vitesse due au parallélisme

fiabilité due à la redondance

flexibilité nouvelles tâches peuvent être gérées plus facilement grâce à la modularité

Motivations (suite)

• Du point de vue IA

apport au langage naturel

applications proches de la réalité

Applications

• gestion des réseaux• contrôle de trafic

aérien• gestion des affaires• BD déductive• commande et contrôle• éducation

• trafic routier

• bibliothèques digitales• personal digital assistants

(PDA)• gestion des rendez-vous• filtrage du e-mail • gestion de l’information• data mining• Commerce électronique

Agents Logiciels (BT)

Proactifs

Ne nécessitent pas des instructions

Capables d ’agir seuls

Apprenants

Améliorent leur expertise (t)

Coopératifs

Partagent tâcheset informationsavec les autres

Attributs primaires

Coopération

Apprentissage

Autonomie

Topologie partielle des agents (BT)

Cooperate Learn

Autonomous

SmartAgents

CollaborativeAgents

CollaborativeLearning Agents

InterfaceAgents

Cooperate Learn

Autonomous

SmartAgents

CollaborativeAgents

CollaborativeLearning Agents

InterfaceAgents

Attributs secondaires (BT)

Attribute

versatility does the agent have many goals or can it engage in a varietyof tasks?

benevolence is the agent benevolent or non-helpful, antagonistic oraltruistic?

veracity does the agent lie knowingly or is it always truthful?

persistence is the agent temporally continuous?

emotionalattitudes

e.g. does the agent get ‘fed up’ being asked to do the samething time and time again?

mentalattitudes

does the agent have mentalistic attitudes such as beliefs,desires and intentions?

Topologie des agentsChart Title

AgentsCollaboratifs

Agentsd'interface

AgentsMobiles

Agentsd'information

AgentsRéactifs

AgentsHybrides

Systèmes d'agentsHétérogènes

AgentsSmarts

AgentsLogiciels

Agents collaboratifs

• Mettent l’accent sur l’autonomie et la coopération entre agents

• Ils opèrent presque tout le temps dans des environnements multiagents ouverts et contraints par le temps

• Ils négocient avec les autres agents en vue d’atteindre des ententes lors de la résolution distribuée de problèmes

• Capacités limitées en apprentissage

Agents collaboratifs: raison d’être

“to create a system that interconnects separately developed collaborative agents, thus enabling the ensemble to function beyond the capabilities of any of its members” (Huhns & Singh 1994)

Raisons d’être (suite)

• Résoudre des problèmes qui sont trop grands ou trop complexes pour un seul agent

• Permettre l’interconnectivité et l’interopérabilité des legacy systems

• Résoudre des problèmes «naturellement» distribués

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

EnvironnementAgent

Agent

Agent

Agent

Agent

Domaine

Utilisateur

CroyancesButs

Contenu d’un Agent

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

Environnement

EnvironnementAgent

Agent

Agent

Agent

Agent

Domaine

Utilisateur

CroyancesButs

ActionsRaisonnements

Contenu d’un Agent

7 - Architecture de INTERRaP (Muller 95)

• Trois niveaux d ’interaction et de contrôle (Muller, 95, Rao & Georgeff,1995)– comportement : niveau réactif et procédural– niveau de planification– niveau de coopération entre agents

• Agent décrit selon un ensemble – de croyances (état informationnel)– de situations (croyance des agents)– de buts que l ’agent peut avoir– d ’options (états de motivation de l ’agent) qui sont des buts selon les

situations– d ’intentions– de primitives opérationnelles

INTERRaP et Croyances

• Les croyances sont réparties en – modèle du monde (croyance sur l ’environnement)

– modèle mental (croyance de l ’agent sur lui-même)

– modèle social (croyance sur les autres agents)

• une croyance est une relation entre l ’état informationnel et l ’état de motivation

• le déclenchement d ’action est dû à une situation spécifique (sous ensemble de croyance d ’agent)

INTERRaP et Situations

• situations réparties selon trois classes– situations de comportement (SE du modèle du monde)– situations de planification locale (basés sur modèle du

monde et modèle mental)– situations de coopération

• buts répartis selon buts réactifs, locaux et coopératifs

• des primitives opérationnelles permettent aux agents de raisonner sur la façon de réaliser leur plan

Modèle conceptuel d ’agent

ACTION

Percep

tion

Buts

situations

croyances

options intentions

social

mental

monde

réactions

buts locaux

coopératifs

Primitivesopérationnelles

Planificationet échéancier

Exécution

Environnement

sélection

coopérative

Plan. locale

Habit./urgente

Activation de buts

Génération de croyances

Révision

États motivants

Raisonnement pour accomplir les planscomportements

Plans locaux

Plans joints

INTERRaP et fonctionnement• Génération de croyances et révision• Reconnaissance de situation• Activation de buts• Planification• Echelonnement• Exécution• Architecture qui définit l ’état interne d ’un agent

(perception, croyance, situations, buts, primitives opérationnelles et intentions) et les fonctions qui modifient les états mentaux (reconnaissance de situation, activation de buts, planification, échelonnement, exécution).

L ’architecture de l ’agent

Base de C. Unité de contrôle de l ’agent

Comportement

Planification loc

Planification coopRS

RS

RS PE

PE

PEModèlesocial

Modèlemental

Modèle dumonde

Senseurs Communication Acteurs

Environnement

RS: reconnaissance de situationPE: planification, exécution

L ’architecture SRK

Architecture basée sur trois niveaux

• Skill

• Rules

• Knowledge

Reconnaissance de la situation

Perception

Prise de décisions

Planification

Exécution

Environnement

Base de Données

Entrées prédites

Mise à jour

But ou tâche choisi

Actions

Situation familière

Situation non–familière

Situation reconnue en terme d’actions

Réflexe

Architecture SRK

Utilisation de l ’architecture SRK

Simulation et modélisation du trafic routierApplication au contrôle-commandePrise de décisions distribuéesInterfaces personnes-machines

Les agents collaboratifs : Défis• À Utiliser + dans les applications industriels

• À construire selon les méthodes issues du «génie» voire du génie logiciel

• Pousser encore plus loin la coordination, la communication et la négociation

• S’intéresser à la stabilité, à la scalabilité et aux problèmes de performance

• Introduire davantage d’apprentissage

• Trouver les «bonnes» méthodes d’évaluation

Agents interfaces

• Ils mettent l’accent sur l’autonomie et l’apprentissage en vue d'exécuter des tâches pour les utilisateurs

• Ils fournissent une assistance proactive à l ’utilisateur pour une application précise

• Leurs interactions avec les autres agents sont en général limitées

Agent interface = secrétaire

C’est un assistant personnel qui collabore avec l’utilisateur (un genre de secrétaire)

Agents interfaces :raisons d’être

• Moins de travail pour l ’utilisateur et le développeur

• L’agent peut s'adapter, à travers le temps, aux habitudes de l’utilisateur et à ses préférences

• Peuvent aider plusieurs utilisateurs à se partager leur savoir-faire

Comment ces agents fonctionnent

User

User'sAgent

OtherAgentAsking

Interacts with

Application

User feedback &programming by example

Observes &imitates

Communication

Interacts with

User

User'sAgent

OtherAgentAsking

Interacts with

Application

User feedback &programming by example

Observes &imitates

Communication

Interacts with

Agents interfaces: Défis

• Mener des expérimentations en vue de déterminer quelles sont les techniques d ’apprentissage qui sont préférables, pour quels domaines, et pourquoi

• Garantir la «vie privée» des utilisateurs

• Étendre si possible le champ d’application

Agents Mobiles

• Pièces logicielles qui peuvent :

migrer d’une machine à une autre

interagir avec différentes machines

exécuter des tâches pour les utilisateurs

retourner à leur ‘point de départ

Agents pour l’Internet

• L’explosion du web nécessite des outils performants pour rechercher, filtrer, extraire, etc. les informations dont on a besoin

• La solution passe par une architecture multiagent (avec des agents collabo-ratifs): NetSA en est une

BasedeDonnées

HTTP

HTTP

KQML

KQML

HTMLSQL

KQMLKQML KQML

KQML

KQML

Uni

té d

e C

omm

unic

atio

n av

ec

l’U

tili

sate

ur

Uni

téde

Tra

item

ent d

e l’

Info

rmat

ion

Uni

té

d’in

téro

gati

on e

t d’

extr

acti

on d

e l’

info

rmat

ion

Agent Utilisateur

Agent Superviseur

Agent Ressource

Agent Intermédiaire

Agent Ressource

Architecture NetSA

Agents pour l’internet : Défis

• Communication

• Sécurité

• Intégration de la planification de l’apprentissage et du data-mining

Agents réactifs

• Ils ne possèdent pas une modélisation symbolique interne de leur environnement

• Ils répondent par une réponse précompilée à tout état de l'environnent

Agents Réactifs:raisons d’être

• Robustesse et tolérance aux fautes

• Flexibilité

• Adaptabilité

• Rapides temps de réponses

Agents hybrides

• Ils combinent deux ou plusieurs philosophies– SRK combine Skill, Rules et Knowledge

• Ils couvrent les différentes facettes qu’on trouve habituellement aux niveaux des applications

Propriétés des agents

Propriétés des agents

L’environnementLe cadre d’exécution

L’agentLe système multi-agent

Propriétés extrinsèques

Propriétés intrinsèques

Propriétés intrinsèques des agentsPropriété 

Étendue des valeursDe À

 Durée de vie

 Transitoire Longue

Architecture 

 Réactive Délibérative

Construction Déclarative Procédurale

Mobilité 

Fixe Itinérante 

Adaptabilité Ajustée Autodidacte

Propriétés extrinsèques des agentsPropriété 

Étendue des valeursDe À

Endroit Local Distant

Autonomie sociale Indépendante Contrôlée

Sociabilité Autistique, conscient, responsable

Bienveillance Coopératif, compétitif, antagoniste

Interaction Logistique : -Directe ou via des intermédiairesSémantique : -Communication déclarative ou procédurale

Les systèmes multi-agents

• Un SMA est un ensemble d’agents qui interagissent en mode de coopération, de compétition et/ou de co-existence.

• Dans un SMA– Chaque agent a des informations ou des capacités de

résolution de limitées (ainsi, chaque agent a un point de vue partiel)

– Il n’y a aucun contrôle global du système multi-agent– Les données sont décentralisées– Le calcul est asynchrone.

Les défis à relever par les SMA

• Comment formuler, décrire, décomposer, allouer les problèmes et synthétiser les résultats ?

• Comment permettre aux agents de communiquer et d’interagir? Quoi dire et quand communiquer ?

• Comment assurer que les agents agissent de manière cohérenteo       En prenant leurs décisions ou actionso       En gérant les effets non locaux de leurs décisionso       Et en évitant les interactions nuisibles ?

• Comment permettre aux agents individuels de représenter les actions et raisonner sur elles, sur les plans et connaissances des autres agents afin de se coordonner avec eux ? Comment raisonner sur l’état de leurs processus coordonnés (comme l’initialisation ou la terminaison) ?

Les défis à relever par les SMA

• Comment reconnaître et réconcilier les points de vues disparates et les intentions conflictuelles dans un ensemble d’agents essayant de coordonner leurs actions ?

• Comment trouver le meilleur compromis entre le traitement local au niveau d’un seul agent et le traitement distribué entre plusieurs agents (traitement distribué qui induit la communication) ? Plus globalement, comment gérer la répartition des ressources limitées ?

• Comment éviter ou réduire un comportement nuisible du système global ?

• Comment concevoir les plates-formes technologiques et les méthodologies de développement pour les SMA ?

Disciplines des SMA

Les SMA sont à l’intersection de plusieurs disciplines-         Systèmes distribués- Interface personnes-machines- Bases de données et bases de connaissances

distribuées et coopératives- Compréhension du langage naturel- Réseaux et Protocoles de communication

- Programmation orientés agents et GL- Robotique cognitive et coopération entre robots- Applications distribuées (Web, Internet, Contrôle du

trafic routier, contrôle aérien, réseaux d’énergie,etc.)

Objectifs des recherches sur les SMA

2 objectifs majeurs :-      Analyse théorique et expérimentale des mécanismes qui ont lieu

lorsque plusieurs entités autonomes interagissent (Approche cognitive)

-      Réalisation des programmes distribuées capables d’accomplir des tâches complexes via la coopération et l’interaction (approche de ingénieur)

=> Une position double pour les SMA :-   - Au sein des sciences cognitives, sociales et naturelles pour à la fois modéliser,

expliquer et simuler les phénomènes naturels et susciter des modèles d’auto-organisation

- - Au sein des sciences de l’ingénieur en se présentant comme une pratique, une technique qui vise à réaliser des systèmes informatiques complexes à partir des concepts d’agent, de communication, de coopération et d coordination d’actions.

Propriété 

Étendue des valeursDe À

 Unicité

Homogène - Étendue

Granularité 

Fine - Grosse

Structure de contrôle Hiérarchique - Démocratique

Autonomie d’interface Communication :- vocabulaire spécifique, langage, protocoleHabileté : - buts, croyances, procédures, ontologies 

Autonomie d’exécution Indépendante - Contrôlée

Autonomie de conception Plate-forme / LangageArchitecture interne / Interaction

Infrastructure de communication -Mémoire partagée-Connexe ou non Connexe-Point à point, multi-destinataires ou diffusion-Synchrone ou asynchrone 

Protocole de communication -         KQML-         FIPA-         HTTP – HTML-         OLE, CORBA, DCOM, RMI

Sécurité Marqueurs, authentification

Propriétés des SMA

Caractéristiques de l’environnement

Connaissance Quelle est l'étendue de la connaissance de l’environnement ?

Prédiction À quelle étendue l'agent peut-il prédire son environnement ? 

Contrôle À quelle étendue l'agent peut-il modifier son environnement

Historique Les étais futurs dépendent-ils des anciens

Téléologie Peuplé ?

Stabilité Change ou non

Historique des SMA 1- Le modèle « Acteur »Les acteurs sont des composantes autonomes d’un système qui

comminiquent par messages asynchrones. Ils sont composées d’un ensemble de primitives, parmi lesquelles on trouve les suivantes :- Create : pour créer un acteur à partir d’un ensemble de paramètres décrivant sont

comportement;- Send : pour envoyer un message à un autre acteur;- Become : pour changer l’état local d’un acteur.

  Problèmes avec ce modèle : 

 - Difficultés dues principalement à des problèmes de cohérence quand il s’agit de gérer plusieurs « acteurs »;

- Difficultés à atteindre des buts globaux avec seulement des connaissances locales.

Historique des SMA

2. Le « contract-net »

- Un gestionnaire décompose une tâche et annonce les différentes sous-tâches;

- Les agents capables d’exécuter les différentes sous-tâches font des offres;

- Le gestionnaire évalue les offres et sélectionne celles qui lui paraissent convenir. Il alloue ensuite les sous-tâches aux contracteurs.

Environnements (outils) de construction de SMA

• ABE (Agent Building Environement) : un outil d'IBM, écrit en C++ et Java. Dans ABE, les agents sont capables de raisonner et d'accéder au web (HTTP), aux groupes de nouvelles (NNTP) et aux courriers électronique (SMTP).

• JAT (Java Agent Template) : un outil de Standford qui permet à des agents, développés en Java, de communiquer via KQML.

• JESS (Java Expert System Shell) : c'est du CLIPS en Java. Il permet la construction d'agents selon les techniques des systèmes à base de règles.

• Voyager : un outil crée par ObjectSpace qui traite de la mobilité des agents et qui offre un Object Request Broker pour des agents écrits en Java.

• ZEUS (British Telecom)

Interaction et coopération entre agents

• -         Interactions

• -         Coordination

• -         Négociation

• -         Communication entre agents

• - Méthode de conception de SMA

Topologie de interactions (Ferber)

• -         Agents indépendants• -         Collaboration simple entre agents• -         Encombrement• -         Collaboration coordonnée• -         Compétition individuelle pure• -         Compétition collective pure• -         Conflit individuel pour des ressources• - Conflit collectif pour des ressources

Indépendance entre agents

Il n’y a réellement pas d’interaction dans ce cas puisque :

-    les agents ont des buts compatibles (c-à-d qui ne sont pas en conflits)

-    les agents ont des ressources suffisantes

- les agents ont les capacités qu’il faut.

Collaboration simple

-         les agents ont des buts compatibles-         les agents ont des ressources suffisantes-         les agents ont des capacités insuffisanteso       => partage de tâcheso       => partage des informations-  Exemple : Collaboration de spécialistes pour la résolution

d’un problème pour lequel aucun n’a la capacité de le résoudre tout seul.

Encombrement

-         les agents ont des buts compatibles

-         les agents ont des capacités suffisantes

-         les agents ont des ressources insuffisantes

o       => conflit d’accès aux ressources

o       => les agents peuvent se gêner

-         Exemple

o       Trafic aérien

o       Gestion de stock etc.

Compétition individuelle pure

-         Les agents ont des capacités suffisantes-         Les agents ont des ressources suffisantes-         Les agents ont des buts incompatibles => ils doivent négocier (« lutter ») pour atteindre

leurs buts: - On dit qu’il y a compétition pure car l’accès aux ressources

n’est pas un enjeu - Il n’y a pas d’interaction en vue d’une coordination des

efforts

-      Exemple : Compétition sportive

Compétition collective pure

-         Les agents ont des ressources suffisantes-         Les agents ont des capacités insuffisantes-         Les agents ont des buts incompatibles

   ils doivent donc s’associer et se regrouper sous forme de « coalition » pour atteindre leurs buts

   On voit donc se former des grouper d’agents unis par le lien de collaboration coordonnée

   Les coalitions et groupes s’affrontent entre eux.

-      Exemple : Course de patin sur glace avec relais – 400 m relais …

Conflits individuels pour les ressources

-         Les agents ont des buts incompatibles.-         Les agents ont des capacités suffisantes.-         Les agents ont des ressources insuffisantes

(donc risques de conflits).  Exemples : -         compétition pour un poste dans une entreprise.-         compétition entre entreprises pour avoir une

position dominante sur le marché.

Conflits collectifs pour des ressources

-         Les agents ont des buts incompatibles.

-         Les agents ont des capacités insuffisantes.

-         Les agents ont des ressources insuffisantes.

o       => les agents doivent donc s'associer ou se regrouper pour acquérir des ressources

Ex : Affrontements en équipes (hockey, football, etc.)

Coopération entre agents

Durfee propose 4 buts génériques pour établir la coopération :

• - Augmenter le taux de finalisation des tâches grâce au parallélisme et aux interactions positives.

• - Augmenter le nombre de tâches réalisables grâce au partage de ressources (information, expertise, etc.).

• - Augmenter les chances de finaliser des tâches en les dupliquant et en utilisant éventuellement des modes de réalisation différents.

• - Diminuer les interférences entre tâches en évitant les interactions négatives.

Étendues de la coopération• - La coopération s'étend de la coopération totale à

l'antagonisme total.• - Les agents optant pour la coopération totale peuvent

délaisser leurs buts pour répondre aux besoins des autres agents afin d'assurer une meilleure coordination.– o     Cela risque de donner lieu a plus de communications

• - Les agents antagonistes ne vont pas coopérer et dans le cas leurs buts respectifs vont se trouver bloqués.– o     Dans de tels systèmes les communications sont minimaux.

• - Les systèmes réels se situent entre les deux extrêmes; coopération totale et antagonisme total.

• - La coopération totale est généralement mise en oeuvre dans la résolution distribuée de problèmes

Coopération totale et résolution distribuée de problèmes

-        Décomposition du problème en sous-problèmes

-         Attribution des sous-problèmes aux agents

-         Résolution des sous-problèmes

-         Intégration (Synthèse)

Solution globale

Coopération totale et résolution distribuée de problèmes (suite)

-         Les agents coopèrent pour résoudre des problèmes qu'ils ne peuvent pas résoudre individuellement.

-         Chaque agent utilise ses connaissances et ses ressources pour résoudre localement un ou plusieurs sous problèmes.

-         Les solutions partielles à tous les sous-problèmes sont par la suite intégrées.

Exemples : traitement de la parole, évaluation d'une situation distribuée, etc.

Interactions entre agents coopérants

-         On se doit de tenir compte des contraintes que les actions des autres agents placent sur le choix des actions de chaque agent.

-         Approche classique à la coordination : les agents doivent être en mesure de reconnaître les interactions entre les différents sous-buts pour pouvoir, soit les ignorer, soit les résoudre.

-         Coordination dynamique : dans le PGP (partial global planning), les agents interagissent en se communiquant leurs plans (partiels) et leurs buts selon un niveau d'abstraction approprié.o      Ces communications vont permettre à chacun d'anticiper quelles

seront les actions futures des uns et des autres, augmentant ainsi la cohérence de l'ensemble.

Comme les agents coopèrent, le receveur d'un message peut utiliser les informations reçues afin d'ajuster sa propre planification.

Interactions entre agents égo-centrés

-       Dans ce cas, les interactions se basent principalement sur La négociation :

o      La négociation est utilisée comme méthode de coordination et de résolution de conflits.

o      La négociation est également utilisée pour l'allocation de tâches et les changements de plans.