Introduction Aux Systèmes multi-agents
Contents
1. Protocole formalisme R seau de P tri Une conversation est une suite d tats li s par des transitions Places 2 Etat interne de l agent 4 Message en cours d acheminement Transitions 4 Synchronisation due a la r ception de messages 4 Conditions d application des actions Pl 0 a R seau de Petri Exemple Agent A A veut faire P A ne peut pas faire P attente de r ponse messages en cours d acheminement Interaction Formalisme AUML Semantique un protocole est un ensemble de messages chang s entre des r les Notation 4 Une dimension verticale qui represente le temps 4 Une dimension horizontale qui repr sente les diff rents roles www auml org auml projects main shtml Jh Protocole r le Exemple R les tudiant enseignant Agents Anne Bob Charles Anne gt tudiant Bob gt tudiant enseignant Hit d interaction gt partir des r les interactions Ga Protocole message Performatif Performatif Contenu distribuer sujet inform sujet s1 lt Arit Condition LA i distribuer sujet ken rendre sujet n timeout Y Il y a k r ponses envoy es avant le timeout avec ksn Y Protocole messages Agencements distribuer sujet re D gt rendre sujet lt _ Si enseignant envoie un distribuer sujet alors recevra un rendre sujet Atten2. query if request i querylf j p i request j j InformIf i p gt demande j de lui donner la valeur de p Preconditions induites D i croit j peut le faire gt donc B Bif p d apr s les pr conds de inform croit que j n a pas d j l intention de le faire Remarques Performatif request L agent i ne peut pas faire a B Agent i a ou il n en a pas l intention D Done lt i a gt ou il est incapable d atteindre les preconditions gt Pas d finies dans FIPA R ponse request protocoles agree refuse inform done Performatifs FIPA ACL 6 Quelle heure est il gt Impossible avec un Query if Query ref lt i query ref j Ref x x gt X expression en x Ref 1 all any Jota description des propri t s All tous les x possibles Any n importe lequel gt Donne moi le x qui v rifie cette propri t Performatifs FIPA ACL 7 Exemples lt i query ref j all x pull violet x gt gt Dis moi qui sont les tudiants qui portent un pull violet lt i query ref j any x pull violet x gt gt Donne moi n importe quel tudiant qui porte un pull violet lt i query ref j iota x pull violet x gt Qui est cet tudiant qui porte un pull violet Inform ref lt i inform ref j Ref x x r gt r est la r ponse Ex lt i inform ref j any x pull violet x bill gt Differences entre ACL et KQML Sy
3. ex h te port num ro gt service de num rotation AMS Communiquer gt adresse de l agent Broadcast tous les agents sur une PF Connue R ponse un message Fournie par l environnement ferm couplage fort Environnement ouvert 16 Service de pages jaunes DF enregistrer nom AID rechercher nom gt AID Architecture Transport du message Impossible d utiliser de l invocation interblocage gt boites aux lettres asynchrones construction consulte D du message C lt p j inl transport Plateforme Fonctionnement Action exog ne envoyer asynchrone T agent gt 1 BAL actions de consultation Peut tre vue comme des actions exog nes Filtrage des messages emetteur performatif Boucle proc durale consulter agir gt message precondition a Structure d un message Enveloppe metteur AID Destinataire AID De A Pour B C Demande fA il_pleut 4 _ Langage ontologie KR Identification du message message ID conversation ID Contenu Performatif force Contenu proposition Ja FIPA ACL Repr sentation formelle lt snd performatif dest contenu gt Exemple Agent m t o action r pondre Precondition lt snd demande self c gt Effet si c il pleut temps pluie Regu lt 0u ou c il fait beau temps soleil Envoyer ou a aa alors lt
4. par son adresse Interaction dirig e par l metteur Modalit s 4 Point point diffusion diffusion restreinte Probl matique 4 Prise en compte du temps a Probl me de connexion Q Interpretation Interaction directe Qui Probl me de connexion Probl matique Avec quel agent interagir pour obtenir un service une ressource Solutions 4 Gestion des connaissances sociales 2 Protocoles 4 Service offert par la plateforme Interaction directe Diffusion Principe les messages sont envoy s a tous les agents Avantages 4 simplicit 4 prise en compte des besoins de l metteur et du recepteur 4 gestion de l ouverture Limites 4 Cout bande passante 2 Co t traitement 4 Prise en compte du contexte Interaction directe Accointances Principe Les connaissances sociales d un agent repr sentent ses accointances avec les autres agents du systeme D QD QD Oe QD OO Re ob OY of Fe ek OP lle z Avantages a Simplicit a Limitation a priori du co t de communication et de traitement Limites 2 Gestion de louverture 4 Espace de recherche r duit 4 Prise en compte du contexte Middle Agent Sycara 00 Requ te de service D l gation de service Demandeur Matchmaker pr f rences Descriptions non tri es s Demandeur Broker de Pi Pa a Fh s SO R sultats du service Publication des ka D l gation de gt Capacit s S Publicat
5. Introduction Aux Systemes multi agents Syma cursus SCIA Julien Saunier julien saunier ifsttar fr IFSTTAR D TETE Ressources Multiagent Systems A Modern Approach to Distributed Artificial Intelligence Edited by Gerhard Weiss MIT Press emmanuel adam free fr site IMG pdf poa_introP pdf www limsi fr jps enseignement www emse fr boissier www ecs soton ac uk about pdfs AgentLink_Fifty_Facts pdf www agentlink org roadmap al3rm pdf www lirmm fr ferber Cours librement inspire de ceux de Flavien Balbo et Nicolas Sabouret Les Systemes Multi Agents Mod les d interaction Cours 2 Plan Rappels Interactions indirectes La m taphore du tableau noir Les evolutions Les communications directes Agent Communication Languages Protocoles d interaction Les communications multi parties D finitions Interaction Generale Morin 77 4 Les interactions sont des actions r ciproques modifiant le comportement ou la nature des l ments corps objets ph nom nes en pr sence ou en influence Multi Agent 4 Mise en relation dynamique de deux ou plusieurs agents par le biais d actions reciproques D finitions Quatre fa ons d interagir entre agents Werner89 E Pas de communication pas d interaction les agents ne communiquent pas soit ils interagissent par perception de l environnement soit ils peuvent atteindre leur objectif sans aide ext rieure L envoi de signaux
6. Tuple spaces amp Artefacts gt Artefact objet dynamique avec interface mi agent mi environnement stigmergie Interaction indirecte Principe Approche proposant d ajouter au niveau de l infrastructure un environnement logique pour faciliter les changes d information Interaction dirig e par le r cepteur Modalit a Stigmergie 4 Espace partag Blackboard espace de tuples Probl matique 4 Prise en compte du temps Q Gestion de l ouverture Probleme de connexion a Interpretation Interaction indirecte Li Blackboard Principe Engelmore 88 Le tableau noir est un espace de recherche partag ou s inscrivent les r sultats obtenus par les sources de connaissances KS Agent L acc s au tableau noir peut tre en lecture et ou criture Central At mA Blackboard te 1 re ae eee ee ee ee eee eee a federated syste ee ae a Central Blackboard Distributed Blackboard Architecture Architecture Interaction indirecte Espace des tuples Origine Syst me distribu Principe Carriero 86 Le mod le Linda propose une m moire partag e nomm e espace de tuples ainsi qu un m canisme de r cup ration des donn es utilisant leurs signatures Mise en uvre sal tuple est d fini comme une suite ordonn e d l ments yp s 2 Un motif template est un tuple particulier dans lequel les champs sont typ s mais peuvent ne pas avoir de valeur d fi
7. d B pA B Bif pV Uif p Effet B p avec Bif p B bV B A et Uif b U bVU no Performatif Inform if D finition d ordre syntaxique i informIf j p Si inform j p V i inform j p Pr cond B p B Bif pV Uif p Effet B p idit j si p est vrai ou faux i connait la valeur de v rit de p ou de p ne croit pas que j la connait Performatifs FIPA ACL 3 Performatif Query if Message Agt gt Agt query if p i demande j si p est vrai i ne connait pas la valeur de v rit de p gt ne croit pas p et i ne croit pas p i croit que j peut lui donner cette valeur Pr cond Bif p As Uif p N A B I Done j informIf i p _ Effet Done lt j informlf i p L i querylf j p lt Exemple lt Descartes query ii Hegels holds fourchette Platon gt Performatifs FIPA ACL 4 Performatif Request _ Message Agt Agt request p demande de faire X croit que lt i X gt est possible i e l ensemble des pr conditions est satisfaite croit que j peut faire X croit que j n a pas d j l intention de faire X Effet X a t effectu e Exemple Descartes request Platon lacher fourchette Platon gt Performatifs FIPA ACL 5 Formellement E Pr cond P a p B Agent j a 7B I Done a avec P a pr conditions de a Effet Done a et P a y lpEP a tq B p Remarque
8. ion des ation w SEFE s a ms param tres D l gation R sultats a R sultats ene de service du service t param ttes 1 gt du service 8 Fournisseur Fournisseur n Fournisseur 1 al Fournisseur n Principe stocker la connaissance sur les comp tences dans des agents sp cialis s Mod le de coordination fond sur les comp tences capability based coordination Quoi Theorie des actes de langage Pr ambule niveaux de communication Chez les tres vivants Couche physique son pheromone Couche syntaxique agencement des sons grammaire Couche semantique abeilles sens des mots Couche pragmatique effet r el r le social Dans les syst mes informatiques yy Transport niveau reseau Niveau syntaxique langages de KR Niveau connaissances ontologie Niveau message langage de communication ACL Niveau communication protocoles Theorie des Actes de Langage suite Austin 62 Searle 69 Vanderveken 88 Parler communiquer c est modifier l tat mental de ses interlocuteurs donc c est agir Trois aspects ou actes d un nonc Locutoire l action de dire llocutoire l action que souhaite l auteur Perlocutoire ce que comprends l interlocuteur Th des Actes de Langage Cinq cat gories d actes de langage Searle Assertifs Directifs Promissifs Expressifs D claratifs faits conna
9. issances pere pierre marie ordres faire action engagements ok action conversation m ta bien_recu la s ance est ouverte Approche cognitiviste Sperber amp Wilson 3 actes Dire que Dire de assertions promesses pr dictions imp rative ordres conseils Demander Si interrogative demande d information Theorie AL et SMA Mod les fond s sur Searle Sperber amp Wilson Demande d information Affirmation Ordres Engagements M ta D claratif Aspect illocutoire _Locutoire Support de la communication couches syntaxe et connaissance Communication r ussie Le destinataire interpr te mon message correctement gt Perlocutoire Illocutoire A Notion de performatif Contenu illocutoire Force Proposition Force illocutoire ou performatif Contenu propositionnel Exemples affirme il_ pleut demande il_ pleut Dans les SMA Performatifs issus directement des cat gories d actes de langage Interrogatif Assertif x Exercitif Promissifs Expressifs amp Chez Ferber expressifs competences croyances Message Performatif Proposition A Interactions directes Message SMA Un metteur et des destinataires Un performatif contenu propositionnel Gestion des messages Identifiants Niveau connaissance gt mod le KR Agent Communication Language Structure des messages D finition des performatifs Et surtout de leur s mantique La
10. les agents se synchronisent par l envoi de messages cod s L envoi de plans le transfert d informations concerne les t ches et les croyances des agents L envoi de messages ce mode de communication le plus usit dans la communaut SMA permet aux agents d changer leurs intentions et leurs besoins Communication Probl matique Shannon 48 LS a D 2 Message Agent A Agent B Message Definition La communication est l change volontaire d informations provoque par la production et la perception de symboles tir s d un systeme partage de symboles conventionnels Russel et Norvig 03 Resume interactions M A Avec l environnement Synchrone et bloquant gt invocations i Avec les autres agents Via l environnement interaction indirecte modifie consulte Gi O env Mod le blackboard R parti interface artefacts Ricci amp Omicini Par envoi de message gt interaction directe e p o env Support environnement Interactions indirectes M moire partag e blackboard gt acces concurrent bloquant N emp che ni l autonomie ni les croyances Simple impl menter pas de pb de concurrence Ressource critique centralis e amp bloquante Stigmergie blackboard N variables perception locale r duit blocage dynamique diffusion simulation fourmis
11. matif 2 Pr conditions Pre indiquent les tats n cessaires _ dans les agents pour que le message puisse tre cr 4 Postconditions Post d crivent les tats des agents apr s le traitement du message 2 Completion d crit le r sultat attendu du message Exemple 3 Tell A B X Tell A B X Pre A bel A X know A want B know B bel A X vknow B bel A X Pre B intend B know B bel A X vknow B bel A X Post A know A know B bel A X Post B know B bel A X Completion know B bel A X KQML Discussion Avantages a Premier standard de communication a Beaucoup d applications supportent KQML 4 Langage extensible n Cr ation de nouvelles performatives r ation de nouveaux param tres m Cr ation de nouvelles ontologies Limites 4 Des performatifs non conformes la th orie des actes du langage a Ambiguite et impr cision a Ne prend pas en compte les conversations 4 Classes de performatives absentes car il n y a pas d expressifs et de d claratifs FIPA ACL Introduction FIPA Fondation for Intelligent Physical Agents Elle a b n fici des r sultats de la recherche sur KQML M me syntaxe que KQML Protocoles explicites pour les changes de messages FIPA ACL Adressage des agents M canisme de transport Structure d un message Performatifs pr d finis Adressage Agent IDentity AID Identifiant unique de l agent Multi plateforme
12. ngage de communication agent KQML m Knowledge Query and Manipulation language Leprincipe est de s parer la tt ag es haka li e P protocole de communication np E du domaine de l application de celle li e au contenu des messages d pendante de l application Historique a 1993 du consortium DARPA KSE knowledge sharing effort 4 Con u pour changer des informations et des connaissances entre agents 2 But d velopper des outils g n riques pour favoriser l interop rabilit des agents heterogenes KQML Syntaxe KQML performative language lt texte gt ontology lt texte gt sender lt texte gt receiver lt texte gt Niveau message Niveau communication content lt expression gt Niveau contenu KQML performatives Cat gorie Demande simple Demande de r ponses multiples R ponse Information g n rique G n rateur D finition de Comp tences Gestion de r seau Nom evaluate ask if ask about ask one ask all stream about stream all eos reply sorry tell achieve cancel untell unachieve Standby ready next rest discard generator advertise subscribe monitor import export register unregister broadcast route forward KQML Exemple ask one sender joe content PRICE IBM price receiver stock server reply with ibm stock language LPROLOG ontology NYSE TICKS KQML S mantique Pour chaque perfor
13. nie a Trois op rateurs out t ajout du tuple t in m lecture d un tuple correspondant au motif m et retrait de ce tuple read m lecture d un tuple correspondant au motif m pas de modification de l espace de tuples Agents amp Artefacts Environnement ensemble d artefacts Artefact Etat observable Op rations lecture criture non blocantes Op rateurs internes environnement actif Mode d emploi Description du service Description des op rations interface Outil de coordination Implementation mod le CARTAGO Ricci A amp A suite Construction _CcreateArtifact Name Type Conf Description getArtifactIbD Name Description AID gt disposeArtifact AID Utilisation USe AID Op Name Params SID sense SID Filter Timeout Perception timeout gt L artefact informe l agent du r sultat focusS AID SID unfocus J gt L agent surveille une donn e SID getOI AID OI SoS L agent demande le mode d emploi Conclusion sur les interactions indirectes Question du r le de l environnement environnement agent Direct vs indirect gt compl mentaire Attention aux interblocages Interactions directes Qui Quoi Comment e Theorie des actes de langage e Mod le FIPA e AUML Interaction directe Principe Approche classique de communication adress e un metteur envoie un message un r cepteur localis
14. ntaxe identique sauf pour les primitives ex tell pour KQML inform pour ACL diff rence dans les descriptions s mantiques Q D finition des primitives diff rentes pr conditions et les post conditions pour KQML Faisabilit et effet pour ACL Q Utilise un langage diff rent pour d crire les tats mentaux des agents Mais les deux consid rent des agents coop ratifs locutoire illocutoi ACL est un standard de la FIPA Evolution plus lente que KQML ACL est plus portable support par quelques plateformes e g JADE Autonomie d interaction Interactions directes gt Non pr dictibilit de la reponse La s mantique de l interaction ne d crit pas la r ponse seulement les conditions et effets du point de vue de l agent metteur L agent peut r pondre ce qu il veut gt d finition de protocoles en particulier SMA faiblement coupl s L agent peut ne pas r pondre gt attente et timeout en particulier SMA ouverts Protocole Introduction Probl matique 4 int gration de schemas typiques structurant les changes 2 Permettre aux agents de savoir comment utiliser les ACL D finition 4 Un protocole pr cise qui peut dire quoi qui et les reactions possibles a ce qui est dit Consequences 4 Une restriction de l utilisation des actes 4 Ing nierie des protocoles Protocoles pr d finies Formalisme de d finition des protocoles M thodologie de d finition de protocoles
15. s Un r le peut tre pris par plusieurs agents Un agent peut prendre plusieurs r les Deadlines gt Locales temps propre Ex CNP gt participant value temps de reponse et respect de la deadline Vision locale d un probl me gt 1 SMA plusieurs protocoles Ex annuler un request cancel avec reponse inform ou failure gt pas d crit dans FIPA request Book Order I I l Request Book l te mach ea Price availability _ Ltn l I l I l I I I I response i i _ l I l I I I response Mg l Delivery Options Delivery info Delivery info l 1 Delivery Choice _ Payment details Lg I I I I Not understood I l l T No approved 1 l l
16. self oui snd gt sinon lt self non snd gt Agent parisien action demander Precondition decid attente Effet lt self demander il_pleut meteo gt attente Performatifs FIPA ACL Interrogatif Query If Query Ref Subscribe _Assertif Inform Inform If Inform Ref Exercitif Request Request When Request Whenever Propagate Proxy Promissifs Agree _ Expressifs Cancel Failure Not Understood Sp cifiques au CNP Call for Proposal Propose Accept Proposal Confirm Disconfirm Refuse Reject Proposal 22 performatifs de base Semantique Mod lisation BDI syst me KD45 Modalit s B U tout est croyance Bf l agent i croit que f est vrai Les connaissances de l agent locales Uf l agent i croit f plus probable que f Les propositions probables f l agent i veut que f soit vraie Les proposition que l agent souhaite vraies Pr dicat s d action action ou lt agent action gt Ex Done lt agent action gt precond GQ Performatifs FIPA ACL 1 Performatif Inform Message Agt gt Agt inform p A C idit j que p est vrai icroit que p est vrai agent non byzantin ine croit pas que j connait d j p _ _ Effet j croit que p est vrai NB p peut tre n gative Exemple la lt Descartes inform Hegels not holds fourchette Platon gt Performatifs FIPA ACL 2 Formellement i inform j p Pr con
17. tion rappel i Ce sont des r les pas des agents gt Les agents qui prennent un r le s engagent interagir conform ment au protocole Protocoles blocs LOOP R p ter une interaction n distribuer sujet 4 rendre sujet lt lt m timeout Apres un message rendre sujet on peut avoir une infinit de rappels suivis de declare fin rendre sujet p gt 5 0 Or P Protocoles blocs OPT Bescanes optionnels distribuer sujet p rendre sujet 4 gt sur cet exemple il y a au plus un seul change i pd Protocoles blocs imbriqu s distribuer sujet question lt reponse p rendre sujet vu question lt r ponse Protocoles blocs ALT ternatives distribuer sujet no Enseignant distribue le sujet puis soit les studiants posent une question soit ils rendent le Protocoles etiquettes Macros dans le protocole gt Distribution distribuer sujet al Distribution p Protocole FIPA request FIPA N 26 2002 request e protocole Contract Net CNP FIPA aa 2002 deadline m nbr de participants n nombre de reponses i nombre de refuse j nombre de propose k nombre de reject nombre de accept deadline date limite de reponse Protocoles Remarque
Download Pdf Manuals
Related Search