Plan Les systèmes multi-agents De la conception à la

1

Les systèmes multi-agentsDe la conception à la programmation

Laboratoire IBISC & Départ. GEIIUniversité & IUT d’Evry

[email protected]

Plan

• Définitions du terme « agent »• Conception et implémentation de sma

– Des acteurs aux agents– Programmation orientée agents (AOP)– Plate-formes de développement de systèmes multi-agents

(S.M.A)• IAD

– Raisonnement distribué– Intégration de connaissances hétérogènes– Notion d’ontologies

Intelligence Artificielle Distribuée (I.A.D)

• Les problèmes sont physiquement distribués• Les problèmes sont fonctionnellement distribués

– multi savoir‐faire /multi expertises– Hétérogénéïté des savoirs

• Les réseaux de communication imposent une vision distribuée– Internet, Bases de données mondiales, Web Sémantique– Penser global agir local

• La complexité impose une vision locale• Nécessité dʼadaptation (locale)

– Changer un central téléphonique ne met pas en péril le réseaumondial

Comment gérer les distribution ?

1. Les tableau noirs (blackboards)• Contrôle centralisé• Partage d’information

2. Les acteurs• Contrôle décentralisé• Envoi de messages

2

«un ensemble d’agents qui interagissent dansun environnement commun et quiparticipent à une dynamiqued’organisation » ([Demazeau Ferber 98])

Définitions du terme agent

Un agent établit un ensemble de conditions sur les relations entredes objets et des processus.

(1) Un processus (ou un processeur) est associé à chaque objet pourle rendre actif (et/ou proactif). Exemples :

Dans les systèmes basés sur les acteurs([Hewitt 77], [Briot 89]), ceprocessus exécute le comportement de l'objet.

Dans les règles de production, les processus correspondent auxdiverses règles que l’objet doit activer [Barthelemy & al. 88].

(2) Tout objet est doté d'une architecture lui permettant de modéliserdes connaissances dans son domaine de compétence ainsi que desconnaissances lui permettant d’interagir avec d’autres objets etson environnement.

(3) Chaque objet doit prendre ses décisions localement, c’est-à-dire,sans l’intervention d’un objet centralisateur (proacivité).

Définitions du terme agent (suite)

Définition de système Multi-Agents

Systèmes dans lesquels des agentsartificiels opèrentcollectivement et de façondécentralisée pour accomplirune tâche

• Agent = entité autonome,proactive, réactive, sociale

• SMA = système hétérogène,ouvert, dynamique, (auto)-organisé

• Notions importantes =concurrence, coopération,communication, coordination,collaboration, interaction

Organisation

Agents

Systèmesd’interaction

Emergence defonctionnalités Contraintes et

objectifs sociaux

Programmation concurrente basée sur les acteurs (1)

• Un objet (passif) envoie un message et attend laréponse pour entamer une autre tâche, alors qu’unacteur envoi un message et continue son activité,qui peut être, par exemple, envoyer un autremessage.

• Un acteur est un objet actif qui communique avecles autres acteurs (ses accointances) par envoi demessage asynchrone.

3

• Destinés aux machines parallèles.• Il existe plusieurs modèles (comportements)

d’acteurs : ABCL, Agha• De nombreux langages :

Plasma (Hewitt 77)Act1(Lieberman 81)Act2 (Theriault 81)Pract/Acore (Manning 87)

Programmation concurrente basée sur les acteurs (2) Modèle d’acteurs

Comportement de base d’un acteur :

1. Lire un message2. Exécuter le comportement associé au message3. Aller en 1.

Le système Actalk (Briot 89)

• Les acteurs sont des instances de la classe Actorqui permet l’encapsulation d’objets standardssmalltalk 80.

• Un acteur est caractérisé par un comportementet une boîte à lettres. Le comportement estexécuté par l’objet standard qui est encapsulé.

Actalk (suite)

Actor {mailBox, behavior} ActorBehavior {aself}

ObjectMinimalObject

ABCLActor ExtendedActorExtendedActorBehavior

ABCLActorBehavior

4

Actalk (suite)

mailBox

behavior replacementBehavior

Concept de comportement de remplacement

ABCLActor

Actor {mailBox, behavior} ActorBehavior {aself}

ObjectMinimalObject

ExtendedActor ExtendedActorBehaviorABCLActorBehavior

A counter Behavior

Counter {contents}

Instance de

Sous classe de

Exemple : un compteur acteur

Plate formes basées sur les acteursAgents dérivés d’acteurs

• Extension d’acteurs pour implémenter des agents• Un agent=un acteur• Spécification du comportement de l’acteur pour

l’adapter au comportement souhaité pour un agent

Exemple : le système Mocah

Actor ActorBehaviour Classes de Actalk

ActeurAgent AgentBehaviour Classes de Mocah

Hérite deHérite de

Les classes de Mocah à partir des classes d’Actalk.

5

Programmation orientée agentsProgrammation de systèmes multi-agents

Langages d’agents

1) D’exécution des agents en mode concurrent (asynchrone)2) Permettant l’envoie de messages entre les agents3) Architecture et/ou comportements génériques des agents4) Protocoles de communication (différents moyens de

considérer la communication)5) Interface de visualisation de l’exécution et/ou de déploiement6) Méthodologie de conception

• Une méthode simple pour l’implémentation d’unsma est par exemple : MAGE. Simuler unscheduler d’agents. Maintenir une liste d’agents etdonner la main aux agents tour à tour en leurpermettant d’exécuter un cycle. La granulation ducycle /et/ou le nombre de cycles est à définir.Dans le cas de MAGE, un agent déclenche unerègle de production à chaque fois qu’il a la main.Pas debuggage, ni de conception globale du sma.L’utilisateur est totalement libre

• Shoam est le premier à parler de la nécessitéd’avoir des langages de programmationspécifiques pour les agents, avec Agent0, donnerdétails, sur le langage, au tableau

AgentTool• Basé sur une méthodologie MaSE

1) Identifier les buts2) Appliquer les cas d’utilisation3) Raffiner les buts4) Créer les classes d’agents5) Construire les conversations6) Assembler les classes d’agents7) Implémenter effectivement les méthodes

• Déploiement des agents au sein de l’environnement• Génération automatique du code des conversations

Quelques plate-formes multi-agents célèbres

6

AgentBuilder : environnement de programmation complet• Modélisation OMT• Identification d’ontologie avec OMT• Modèle BDI pour modéliser le comportement des agents• Langage AGENT0 pour coder le comportement des agents• Langage de communication : KQML• Exécution des agents à partir du système• Possibilité de générer des .class

Quelques plate-formes multi-agents célèbres (suite)

DECAF : environnement de développement de plans• Pas de méthodologie pour la conception• Utilitaires pour décrire des plans• Mécanismes de coordination de tâches• Application d’heuristiques pour ordonnancer les tâches• Les heuristiques sont construite via une interface• Éditeur d’agents pour le « débuggage »


Jack• Éditeur gestionnaire de projet• Langage de programmation (JAL)• Un compilateur• Agents basés sur le modèle BDI• Pas de déploiement


JAFMAS :• un ensemble de protocoles de communication et

d’interaction entre agents• Méthodes de coordination et de vérification de

cohérence• Méthodologie en cinq phases :

1) Identifier les agents2) Identifier les conversations3) Identifier les règles de conversation4) Analyse le modèle des conversations5) Implémentation.


7

Jive :• Éditeur graphique• Possibilité de travail en groupe sur un même projet• Création des conversations avec les réseaux de Pétri et le

langage COOLMadKit :• Éditeur pour le déploiement et la gestion de plusieurs

S.M.A• Utilitaire pour simulations


Zeus• Trois couches :1) Agent=entité

autonome+raisonnement+croyances+ressources+préférences.

2) Organisation : relations entre les agents3) Modes de communication, protocoles, coordination• Plusieurs éditeurs : ontologies, description des

tâches, organisation, définition des agents,coordination, faits et variables.


Jade : propriétés• Répond aux norme FIPA97• Pas de méthodologie spécifiée• Classes génériques pour manipulation d’ontologies• Possible mobilité des agents (migration des agents)


Jade : description et utilisation

•Lancement d’un agent avec la méthode (setUp ())

•Un agent peut contenir un ou plusieurs comportements

•Un comportement peut être :

–Un lancement du moteur d’inférence (JESS)

–Toute autre méthode Java•Interface graphique pour l’enregistrement et la gestion des agents•Possibilité de visualiser les conversations•Communication par le langage ACL (FIPA)


8

• Jade : architecture globale

1. AMS : Agent Management System2. ACC: Agent Communication Chanel3. DF : director facilitator (service pages jaunes)

Sites web des plate formes

AgentBuilder http://www.agentBuilder.com/AgentTool http://en.afit.af.mil/ai/agentool.htm.Brainstorm/J http://www.exa.unicen.edu.ar/~azunino/brainstormj.htmDECAF http://www.eecis.udel.edu/~decaf/Jack http://www.agentsoftware.com.au/shared/products/index.htmlJade http://sharon.cselt.it/project/jade/JAFMAS http://www.eces.uc.edu/~abaker/JAFMAS/Home.htmlJiVE http://www. eces.uc.edu/~abaker/JiVE/index.htmlMadKit http://www.madkit.orgZeus http://www.labs.bt.com/projects/agents/zeus/

Méthodologies de développement de SMA

• On initialise les accointances des acteurs• Dans le cas d’acteurs, on spécifie les

différents comportements associés auxmessages échangés

Phases concernées par la méthodologie :– Analyse– Développement– Implémentation– Déploiement

Méthodologies de développement de SMA (suite)

9

• Différentes phases de développement d’un s.m.a.• MaSE• Aalaadin ou AGR• RETSINA• Dmars• OAA• DESIRE• Gaia• Tropos• Kaos• Cassiopé

Méthodologies de développement de SMA (suite) Modes de raisonnement en Intelligence Artificielle

Un raisonnement est souvent un entrelacement de plusieurs types de raisonnement connus

Raisonnement plausible

Raisonnement non monotone

Raisonnement par défautRaisonnement qualitatif

Systèmes experts

Modus Ponens etModus Tollens

La coopération dans les SMA

La communication et la coopérationsont étroitement liées, l’envoi demessages étant le résultat dedécisions de coopération

• Coopérer, c’est adopter une attitude (Cesta and Miceli)

Etat interne

Niveau d’énergie

danger Faim Normal

0

Seuilinférieur

20 60 100

SeuilSupérieur

Relation entre niveau d’énergie et états internes des agents.

Solitaire : les agents s’ignorent.Parasite : l’unique but est de chercher de la nourriture ou de manger la nourriture envoyée par les autres agents.Egoïste : demande de l’aide ou recherche de la nourriture.Social : plusieurs types de buts en fonction de leur état interne, rechercher de la nourriture, fournir de l’aide ou demande de l’aide).

10

• Coopérer, cʼest conceptualiser (Gasser,Adler et Simoudis )– concepts manipulés :

• engagements,• les intentions et les buts

– Instanciation des concepts en fonction delʼapplication envisagée

• Coopérer c’est s’engager (« commitment »)– Qui fait quoi– Liens d’autorité entre les agents

L’engagement revêt différentes formes– L’engagement interne : une relation entre un agent et une action

(Bouron, Cohen & Levesque)– L’engagement collectif : engagement interne d’un groupe

d’agents– L’engagement social : « un agent x possède un engagement

social envers un agent y s’il s’engage à réaliser une action a(engagement interne) et si y est intéressé par l’action a. Lerésultat de a est un but pour l’agent y ; c’est pour cela que ypossède également comme but que l’agent x doit effectuer a.L’agent y possède alors des droits de regards sur l’agent x, ilpeut vérifier s’il a bien effectué a, exiger sa réalisation,protester s’il n’est pas satisfait…

• Coopérer, cʼest partager des résultats etdes tâches (Davis et Smith, Rochowiak)

• Deux modes de coopération– Partage de tâche : problème à traiter est

décomposable en sous tâches pouvant être réalisées defaçon indépendante

– Partage de résultats : doter chaque agent demoyen(s) lui permettant de partager des résultats.

• Coopérer, cʼest calculer (Sunju Park,Levi, Stirling)– Définition de montants de rétribution pour

la réalisation de tâches– Maximisation de profits individuels– Définition de niveaux de satisfaction

locaux (solution obtenue dés que tous lesniveaux sont atteints)

– Utilité épistémique : valeur de fausseté etde vérité de chaque proposition cognitive

11

• Coopérer, cʼest coordonner des plans,plan partiel global : PGP (Durfee, Lesser)

– Définition dʼun plan global et de plans locaux– Échange de plans partiels entre agents– Les agents ajustent leurs activités en

fonctions des plans des autres, et proposentdes modifications des plans

– Possibilité dʼinférer les buts des autres àpartir de leurs actions en vue dʼaméliorer lacoordination globale (réseau probabiliste dereconnaissance de plans)

Le protocole réseau contractuel

• Le protocole réseau contractuel ("ContractNet" en anglais) a été une des premièresapproches utilisées dans les systèmes multi-agents pour résoudre le problème d'allocationdes tâches (Davis et Smith, 1983).

• deux rôles: gestionnaire et contractant• Décomposition des tâches en sous-tâches

Le protocole réseau contractuel (suite)

12

Applications des SMA

• Intelligence ambiante• Simulation de systèmes complexes• Résolution de problèmes distribués• Commerce électronique• Modélisation biologique• Web services• Diagnostic de pannes• Travail collaboratif• Apprentissage collectif

Résolution de problèmes et s.m.a

problème

Analyse etconception

Algorithme derésolution du problème

domaine

Modélisationagents

•Agents et,•intéractions entre les agents

Instance duproblème

Données

Résolution

exécution

Approche classique Approche à base de s.m.a

Solution(s)

Types d’agents/types d’applications?

• Deux types d’architecture d’agents– Agents réactifs– Agents cognitifs

Types d’agents/types d’applications? (suite)

• Agents réactifs– un agent ne possède pas de représentation explicite (ni

d'eux-mêmes, ni des autres, ni de leur environnement)– un agent n’effectue pas de raisonnement abstrait (nécessite

des représentations)– l’intelligence (l'organisation) est une propriété émergente;

l'organisation des agents entre eux n’est qu’un effet induitde leur activité et de leurs interactions : elle n’est explicitéeà aucun niveau dans le système, ce n’est pas une donnée duproblème

13


Ethologie• Insectes sociaux, autres animaux sociaux

– fourmis, termites, abeilles, guêpes– loups, rats, primates, oiseaux, poissons

• Exemple : les fonctions collectives des fourmis LasiusNiger– régulation de la température du nid– formation collective de ponts par les ouvrières– construction et protection des nids– tri du couvain et des items de nourriture– coopération dans le transport d'objets trop lourds– choix des chemins les plus courts entre nid et sources de nourriture– choix des sources de nourriture les plus riches au détriment des autres

Types d’agents/types d’applications? (suite)Exemples de fonctions collectives

Types d’agents/types d’applications? (suite)Le fourragement Collectif

• "Benchmark" très populaireen IAD et Vie Artificielle

• Exploration et exploitationcollective d'unenvironnement inconnu etdynamique, par des robotsou agents simulés

• Beaucoup de techniquesenvisageables (inspirées laplupart du temps desfourmis)

Les robots fourrageurs

Robots

Base

Minerai

Pb = Collecte d'échantillonsde minerai dans unenvironnement inconnu

2. Ramassage 3. Retour

4. Recherche aléatoire 1. Recherche aléatoire

Les robots les plussimples


14

Questions conceptuelles

• Nombre et densité d'agents– Certains phénomènes ne surviennent qu'en

présence d'un nombre ou densité d'agents donné :effet de "seuil" ou "masse critique"

• Exemples– construction des arches par les termites– ponts chez les fourmis– choix du plus court chemin

Questions conceptuelles (2)

• Choisir un modèle de communication– propagation par l'environnement

• champs de potentiel• communication non-intentionnelle• instantanée ou non• pérenne ou non

– message point à point– message "broadcasté"

Questions conceptuelles (3)

• Choisir un modèle de comportement– Pourquoi un comportement se déclenche

• Perceptions ? Buts externes ?• Buts internes ? Motivations ?• Combinaison des deux ?

– Comment un comportement se déclenche• Interactions entre perceptions et motivations (activation,

planification)• Interactions entre comportements (sélection)• Inné ? Acquis ?

Modèles : Architecture de Subsumption

• Brooks 86 - Behavior Language 90• Modèle semi-hiérarchique de sélection

d'actions

Niveau 0Déplacement aléatoire

Niveau 1Construction de carte

Niveau 2Exploration

Niveau 3Evitement obstacles

Capteurs EffecteursNiveau 0

Actionner pince

15

Modèles : Architecture de Subsumption

évitement d’obstacles

suivi de piste

mouvement exploratoire

mouvement de retour

mouvement aléatoire

Agents cognitifsExemple architecture BDI

Le contrôle BDI (Michael Wooldrige)

Algorithme de contrôle d'agent BDI//B0, D0 et I0 les croyances, désirs et intentions initiales de l'agent1 B =B02 D =D03 I = I04 répéter 4.1 obtenir nouvelles perceptions p 4.2 B = revc(B, p) 4.3 I = options(D, I) 4.4 D = des(B, D ,I) 4.5 I = filtre(B, D, I) 4.6 PE = plan(B, I) 4.7 exécuter(PE) jusqu'à ce que l'agent soit arrêté

Notion d’engagement (commitment) d'un agent envers une intention

Algorithme de contrôle d'agent BDI avec obligation limitée

1 B = B02 D = D03 I = I04 répéter 4.1 obtenir nouvelles perceptions p 4.2 B = revc(B, p) 4.3 I = options(D, I) 4.4 D = des(B, D ,I) 4.5 I = filtre(B, D, I) 4.6 PE = plan(B, I) 4.7 tant que (PE<>{} et nonaccompli’I,B) et possible(I,B)) répéter

- x =exécuter(x); PE = reste(PE) - obtenir nouvelles perceptions p - B = revc(B, p) fin tant que jusqu'à ce que l'agent soit arrêtéfin

16

Algorithme de contrôle d'agent BDI avec obligation ouverte1 // initialisations4 répéter 4.1 obtenir nouvelles perceptions p 4.2 B = revc(B, p) 4.3 I = options(D, I) 4.4 D = des(B, D ,I) 4.5 I = filtre(B, D, I) 4.6 PE =plan(B, I) 4.7 tant que (PE<>{} et nonaccompli(I, B) et possible(I, B)) répéter - x = première(PE); exécuter(x); PE = reste(PE) - obtenir nouvelles perceptions p - B = revc(B, p) - D = des(B, D ,I) - I = filtre(B, D, I) - PE = plan(B, I) fin tant que jusqu'à ce que l'agent soit arrêté

Approches d’intégration de méthodes hétérogènes

• Minsky et Papert ([Minsky & Papert 74])« L’évolution des stratégies d'utilisation des

connaissances est fortement corrélée à labonne exploitation de la diversité des moyensd'expression, d'identification et d'utilisationdes connaissances. »

Approches d’intégration de méthodes hétérogènes (suite)

• Le cadre proposé :" doit permettre une interaction entre ces

différents types de connaissances de façon àavoir une compréhension complète dudomaine à résoudre..." de manière qu'ilpuisse "contrôler le choix de segments deconnaissances pertinents..." ou "déciderquand une approche particulière doit êtreinterrompue en faveur d'une autre..." ([Bublin& Kashyap 88] pages 18-25).

Objectif

• Conception d’un système permettant decombiner plusieurs modes de raisonnementlors de la résolution d’un problème

• Ce système doit être capable d’adapterdynamiquement sa manière d’intégrer lesmodes de raisonnement en fonction de soncontexte d’utilisation

17

Raisonnement multi-modèles

Systèmes Multi-Agents

C.B.R Amdec Comport ...

Mocah : Modélisation de lacoopération entre agents

hétérogènes

Intégrationcentralisée

Intégration distribuée

Jacquard

MDX2 Dynamis...

Modèles de raisonnement

Modèles de raisonnement pour le diagnostic

ExhaustivitéRéduit le risque d'explosioncombinatoireManque de rapiditéManque de fiabilité

Une Amdec(cause)

Raisonnement basé sur lesmodes de défaillance, deleur effet et criticité(Amdec)

RapiditéDiversité des problèmes traitésManque de fiabilité

Bibliothèque deCas

Raisonnement basé sur lescas (CBR)

Fiabilité de ses solutionsRisque d'une explosioncombinatoireManque d'exhaustivité

Comportementsdes composants(suspect)

Raisonnementcomportemental(Comport)

Caractéristiques desméthodes

Connaissancesmanipulées

Modèle de raisonnement

Agents coopératifs

Raisonnementà partir de cas

RaisonnementComportemental

Connaissancesde coopération

Raisonnement basésur les Amdec



Agent Comport

Agent CBRAgent Amdec

Caractéristiques de Mocah

• Identification de concepts communs• Modélisation de l’expertise à un niveau

conceptuel• Modélisation homogène du domaine et de la

coopération

18

Une identification de concepts communs

réalisé

e pa

r

génè

re

Méthode Données

Tâche

rend utilisable

utilise

rend candidate

modifie

Décomposition des connaissances selon trois dimensions

Exemples de tâches de diagnostic Exemples de tâches de coopération

19

NiveauSuperviseur

Connaissances sursoi

Connaissancessur

Les autres

MoteurTâches du domaine

Tâches de coopération

Agenda

Architecture interne d'un agent coopératif

Raisonnementcomportemental Raisonnement à

partir de cas

Raisonnement à partird'Amdec

Diagnostic de pannes de l'essuie-vitre

Initialisation d'un problème à résoudre

diagnostiquerdiagnostiquerdiagnostiquer

Enoncé global à résoudre

nonOk lave-vitretype Vehicule R19

Rapidité=2Fiabilité=7

Représentationslocales

Agendas

Boîtes à lettres

CBR Amdec Comport

nonOk lave-vitreCmd M145 ontype Vehicule R19Nbr d'apparitions 4Rapidité 2Fiabilité 7

nonOk lave-vitretype Vehicule R19Nbr d'apparitions 4

Rapidité=2Fiabilité=7

nonOk lave-vitretype Vehicule R19

Cmd M145 onRapidité=2Fiabilité=7

Extraits d'un scénario de coopération

CBR

Amdec

Comport

diagnostiquergénererHyp


diagnostiquerDemandeInfo



diagnostiquer

DemandeInfo

Demande

diagnostiquergénererHypdiscriminerinformerAccoint

integreMess


diagnostiquerintegrerMess

Demande

DemandeInfo

diagnostiquergénererHypvérifierHyp

DemandeInfoInformation

diagnostiquervérifierHypintegreMess

diagnostiquervérifierHypdiscriminer

DemandeInfo

informAccoint

Information

Demande

T1 T2 T3 T4 T5 T15 T16 T25

diagnostiquer diagnostiquerdiagnostiquergénererHyp

Résultat

Solution

pompe H.Sréservoir d'eau vide

Information

20

Résultats et observations

• Amélioration des caractéristiquesindividuelles des modèles de raisonnement

• Organisation dynamique de la résolution• Apparition d'un agent Pivot

• Observation de la coopération entre agents• Évaluation de la résolution collective = évaluation de l'activité

de coopération• Expérimentation de stratégies de coopération et de modèles de

raisonnement• Une modélisation d'expertises de coopération• Un environnement de programmation agent

Problématiques

Ontolgies

• Définitions• Application/intérêts

– Classification/web/langage naturel– intégration de modèles de raisonnement

• Ontologies et SMA

Définitions

An ontology is an explicit specification of aconceptualization. Ontologies definedomain concepts, their properties and therelationships between them, and thusprovide a domain language that ismeaningful to both humans and machines.They are formal theories supportingknowledge sharing and reuse.

21

Définitions (suite)

• En philosophie, l'ontologie (du grec oν, oντος,participe présent du verbe être) est l'étude de l'êtreen tant qu'être, c'est-à-dire l'étude des propriétésgénérales de ce qui existe.

• La scolastique considéra cette étude comme unepartie de la métaphysique, en tant qu'elle définitles transcendentia, les déterminations communesà tous les êtres (ce qu'on appellera plus tardmétaphysique générale, par opposition à lathéologie, dite métaphysique spéciale).

Wikipédia

• En informatique, une ontologie est un ensemblestructuré de concepts. Les concepts sont organisésdans un graphe dont les relations peuvent être :– des relations sémantiques ;– des relations de composition et d'héritage (au

sens objet)• L'objectif premier d'une ontologie est de modéliser

un ensemble de connaissances dans un domainedonné.

Conclusion

• L’I.A.D est un domaine de recherche récent• De nombreux axes non encore explorés• Plate formes explorent souvent un aspect de

l’IAD

Sources

• http://turing.cs.pub.ro/auf2/html/chapters/chapters.html (accédée le 18 janvier 2010)

• Cours Guillaume Hutzler

Documents

Plan Les systèmes multi-agents De la conception à la