Embed Size (px)
Citation preview
Organisation des SystèmesMulti-AgentsJoël Quinqueton
LIRMMMontpellier, France
Joël Quinqueton 2
Rappels du cours précédent1. Motivations: distribution2. Origines
1. Tableaux Noirs2. Acteur
3. Problématique: agent + organisation4. Agents
1. Situés ou communicants2. Cognitifs ou réactifs
Joël Quinqueton 3
Plan du Cours1. Sociétés & Organisations 4
1. Modes d'Organisation 72. Communication 103. Interaction et coopération 224. Allocation de Tâches 335. Coordination 38
2. Développement à base d’agents 48
Joël Quinqueton 4
Sociétés & Organisations• Système Multi-Agent: système composé de:
– un environnement (espace disposant ou non d'une métrique)– un ensemble d'objets situés (il est possible, à un moment donné, de
leur associer une position dans l'environnement). Ils sont passifs etpeuvent être perçus, créés, détruits et modifiés par les agents
– un ensemble d'agents capables de percevoir, produire, consommer,transformer et manipuler les objets de l'environnement
– un ensemble de relations (communications) unissant les agents– un administrateur chargé de contrôler l'activation des agents
Joël Quinqueton 5
5. Sociétés & Organisations
Caractéristiques d’un SMA• vision locale et décentralisée
– locale : chaque agent est responsable de sesconnaissances (encapsulation) et de ses actions(autonomie), mais également de l'organisation qu'ilmet en place avec d'autres agents. Aucun agent n'ade vue globale du SMA tout entier.
– décentralisée : on s'efforce d'éliminer tout contrôlecentral. Les tâches à réaliser et les compétencespour le faire sont distribuées sur les agents.
Joël Quinqueton 6
Caractéristiques d’un SMA
• Un SMA peut-être :– ouvert : les agents y entrent et en sortent
librement (ex: un café)– fermé : l'ensemble d'agents reste le même (ex:
un match de football)– homogène : tous les agents sont construits sur
le même modèle (ex: une colonie de fourmis)– hétérogène : des agents de modèles différents,
de granularité différentes (ex: l'organisationhospitalière)
Joël Quinqueton 7
Modes d'Organisations
• Organisation:• Façon dont le groupe est constitué pour pouvoir travailler (pas
de définition unifiée)– Décrit
• l'ensemble des composants, leur nature, leurs responsabilités,leurs besoins en ressource (processeurs) et leurs liens decommunication ou d'arrangement
• un ensemble de données à traiter (l'environnement)• un ensemble de tâches à réaliser
– Propriétés• définit un cadre pour l'interaction• produite par l'interaction entre les agents• peut être statique ou dynamique
Joël Quinqueton 8
Visions d’une organisation– Point de vue physique vs logique
• distribution géographique des agents au sein d'unenvironnement
• description d’une société d’agents et des activitésqui y prennent part en termes de rôles, d’assignationde tâches, de comportements, de relations d’autorité
– Environnement physique vs social• respecte un certain nombre de lois, peut être muni
d’une métrique• autres agents, organisation
Joël Quinqueton 9
Axes de Distribution1. centrés sur les données (eg leur géographie, leur origine)2. centrés sur les buts, rôles (eg leur type)3. centrés sur le niveau de résultat atteint (eg le niveau d'abstraction)4. centrés sur les ressources (eg ressources matérielles)
Joël Quinqueton 10
Le besoin de communication
• Le dilemme du prisonnier– chaque prisonnier peut avouer ou non– si aucun n’avoue : 2 ans– si les 2 avouent: 4 ans– si un seul avoue: il est libre et l’autre a 5 ans
• Stratégies sur des longues suites:– populations de stratégies– génération proportionnelle au score de la génération
précédente– stratégie “donnant donnant” dominante
Joël Quinqueton 11
Modes de Communication (1)• La communication peut être définie par :
– le contenu des messages• échange de signaux, de requêtes, de plans, d’offres, de connaissances,
d'arguments• contenu figé ou dynamique…
– leur type et leur canal• direct par envoi de messages• indirect par l’environnement)
– leur forme: protocole de communication utilisé, destinataires– ce qui la provoque ou la motive
• engagement a priori à communiquer, intentionnalité explicite• interaction suscitée de manière dynamique par une perception de
dépendance, par exemple
Joël Quinqueton 12
Modes de communication (2)
• La communication peut être caractérisée par:– ce qu’elle induit
• Directement: modification des croyances, apparition deconflits, problèmes de cohérence)
• Indirectement: réaction à une perception au travers del'environnement
– les agents qu'elle implique: humains ou artificiels.– son mode : direct ou indirect
Joël Quinqueton 13
Modes de Communication (3)• Communications directes (ou explicites) :
– l'échange direct est réalisé volontairement en directiond'un individu ou groupe d'individus
– communication par partage d'informations:• les agents lisent et déposent une information sur une
zone de données commune (eg tableau noir, forums)– communication par envoi de messages
• communication point à point (téléphone, mél)• communication par diffusion (broadcast)
Joël Quinqueton 14
Modes de communication (4)
• Communications indirectes (ou implicites) :– les agents laissent des traces (signaux) de leur présence
ou de leur action• qui sont perçues par d'autres agents
– l’environnement propage (et éventuellement déforme)les signaux déclenchés par la réalisation d’une action
– entraîne des types d'échanges limités– permet de ne pas avoir à déterminer précisément le rôle
de chaque agent dans le traitement collectif• les objets dans l'environnement émettent des signaux ou des
champs de potentiels guidant les agents
Joël Quinqueton 15
Théorie de la Communication• Le modèle classique
– une transmission d'informations d'un émetteur vers unrécepteur (ou destinataire)
– l'information est codée à l'aide d'un langage et décodée àl'arrivée par le destinataire
– elle est transmise pas un canal (ou médium) detransmission qui peut être bruité
– le contexte est la situation dans laquelle les interlocuteurssont placés (lui-même décomposé en contexte de l'émetteuret du destinataire)
• Notion d'actes de langage et de structureconversationnelle
Joël Quinqueton 16
Message
Medium/Canal
Code
Emetteur Destinataire
Théorie de la Communication
Joël Quinqueton 17
Les actes de langage
• La communication : une actionintentionnelle caractérisée par un type etplusieurs composantes (Austin 62 et Searle69):
• Type: Assertif, directif, interrogatif,exercitif, promissif, expressif
• Composantes: locutoire, illocutoire etperlocutoire
Joël Quinqueton 18
Les types d’actes de langage• assertifs: affirmer quelque chose sur le monde (Jean a 2
ans)• directifs: donner des directives au destinataire• interrogatifs: poser une question (quelle heure est-il?)• exercitifs: demander d'accomplir une action (pousse-toi!)• promissifs: s'engager à accomplir certains actes dans
l'avenir (je passerai demain)• expressifs: donner des indications concernant son propre
état mental (je suis heureux)
Joël Quinqueton 19
Les Composantes des actes
• composante locutoire (l'énoncé)• illocutoire (force associée au message par
l'émetteur)• perlocutoire (effet sur le destinataire e.g.
persuader)• « pouvez vous me passer le sel? »
Joël Quinqueton 20
1 2
3
4
5
6
A:B << DemanderFaire(P)
A:B << DemanderFaire(P) : A demande à B de faire P
B:A << AccepterFaire(P)
B:A << NotificationFinAction(P)
B:A << RefuserFaire(P)
B:A << EchecFaire(P)
Automates à états finis
Protocoles conversationnels– automates à états finis (Winograd & Florès 86)– réseaux de Pétri
Joël Quinqueton 21
Réseaux de Petri
DemanderFaire(P)
RefuserFaire(P)
AccepterFaire(P)
DA
FB
Réseaux de PétriAgent A
Agent B
EchecFaire(P)
NotificationFinAction(P)
AR1
FA1
FA2
AR2
DB
BR
B ne veut pas faire P
B veut bien faire P
Succès
Echec
Satisfaction
RéussiteEchec
Joël Quinqueton 22
Interaction: Définition
Joël Quinqueton 22
Interaction: Définition• Mise en relation dynamique de 2 ou plusieurs agents par le biais d’un
ensemble d’actions réciproques
Joël Quinqueton 22
Interaction: Définition• Mise en relation dynamique de 2 ou plusieurs agents par le biais d’un
ensemble d’actions réciproques– c’est un élément nécessaire à la constitution d’organisations.
Joël Quinqueton 22
Interaction: Définition• Mise en relation dynamique de 2 ou plusieurs agents par le biais d’un
ensemble d’actions réciproques– c’est un élément nécessaire à la constitution d’organisations.
• “On appellera situation d’interaction un ensemble de comportementsrésultant du regroupement d’agents possédant des compétencesparticulières et qui doivent agir pour satisfaire leurs objectifs entenant compte des contraintes provenant des ressources plus ou moinslimitées dont ils disposent.” (Erceau)
Joël Quinqueton 22
Interaction: Définition• Mise en relation dynamique de 2 ou plusieurs agents par le biais d’un
ensemble d’actions réciproques– c’est un élément nécessaire à la constitution d’organisations.
• “On appellera situation d’interaction un ensemble de comportementsrésultant du regroupement d’agents possédant des compétencesparticulières et qui doivent agir pour satisfaire leurs objectifs entenant compte des contraintes provenant des ressources plus ou moinslimitées dont ils disposent.” (Erceau)
• “C’est parce qu’ils coopèrent que les agents peuvent accomplir plusque la somme de leurs actions, mais c’est aussi à cause de leurmultitude qu’ils doivent coordonner leurs actions et résoudre desconflits.” (Ferber)
Joël Quinqueton 23
Types d’Interaction
• Relation aux buts : compatibles ou incompatibles --> collaboration, compétition ou conflit
• Relation aux ressources : conflictuelle ou nonconflictuelle --> coordination (anticiper lesproblèmes), résolution de conflits, négotiation
• Relation capacité des agents / tâches : suffisantesou non --> dépendance ou non
Joël Quinqueton 24
Situations d’interactionButs Ressources Compétences Types de situation Catégorie
Compatibles Suffisantes Suffisantes Indépendance Indifférence
Compatibles Insuffisantes Suffisantes Coordinationd'accès
Coordination
Compatibles Suffisantes Insuffisantes Collaboration simple
Compatibles Insuffisantes Insuffisantes Collaborationcoordonnée
Collaboration
Incompatibles Suffisantes Suffisantes Compétitionindividuelle pure
CompétitionIncompatibles Suffisantes Insuffisantes Compétition collective
pure
Incompatibles Insuffisantes Suffisantes Conflits individuelspour des ressources
ConflitIncompatibles Insuffisantes Insuffisantes Conflits collectifs
pour des ressources
Joël Quinqueton 25
La Coopération• Deux agents sont en situation de coopération
aux deux conditions minimales suivantes [Hoc99] :– ils poursuivent chacun des buts qui peuvent entrer
en interférence, soit au niveau des résultats, soit auniveau des procédures
– ils font en sorte de traiter ces interférences pourque les activités de chacun soient réalisées defaçon à faciliter la réalisation de celles de l'autre oula réalisation de la tâche commune (si elle existe)
Joël Quinqueton 26
Interférence en Coopération
• Interférence:– Les effets des actions d'un agent sont
pertinents pour les buts de l'autre– 2 sens:
• soit ils favorisent les buts de l'autre:interférence positive
• soit ils les gênent: interférence négative
Joël Quinqueton 27
Formes de Coopération• Trois formes de coopération peuvent être distinguées [Hoc
96]:– la coopération confrontative, selon laquelle une tâche est exécutée
par plusieurs agents de spécialités différentes oeuvrant de manièreconcurrente sur le même ensemble de données, le résultat étantobtenu par "fusion";
– la coopération augmentative, selon laquelle une tâche est répartiesur une collection d'agents similaires, oeuvrant de manièreconcurrente sur des sous-ensembles disjoints de données, lasolution étant obtenue sous la forme d'un ensemble de solutionslocales;
– la coopération intégrative, selon laquelle une tâche est décomposéeen sous-tâches accomplies par des agents de spécialités différenteset oeuvrant de manière coordonnée, la solution étant obtenue auterme de leur exécution.
Joël Quinqueton 28
Exemple
Coopérationconfrontative
Coopérationaugmentative
Coopérationintégrative
Joël Quinqueton 29
Activités Coopératives
Coopération dans l'action
Création localed'interférences
Détection localed'interférences
Résolution locale d'interférence
Identification de butset de sous-buts
Elaboration d'un objectifou d'un but commun
Coopération dans la planification
Elaborationd'un plan commun
Répartitiondes rôles
Autres élaborationsportant sur le référentiel
commun
Méta-Coopération
Elaboration d'un code de communication
commun
Elaboration de représentations
compatibles
Elaboration d'un modèle de soi-même
et du partenaire
Niveaux d'abstraction• Trois niveaux d'abstraction peuvent être distingués
dans l'activité coopérative [Hoc 99]:
Joël Quinqueton 30
5.3 Modes d'Interaction
Raisons de Coopérer (1)
• attitude intentionnelle (eg intégrative)• résultat d’une dépendance (eg intégrative)• résolution de conflits (eg augmentative ou
confrontative)
Joël Quinqueton 31
5.3 Modes d'Interaction
Raisons de Coopérer (2)
• résultat d’une dépendance (eg intégrative)– un agent peut dépendre d'un autre pour atteindre un but
;– R-dépendance : les agents dépendent de ressources
(R=ressources); il s’agit d’une dépendance physique,ou dépendance à l’environnement ;
– A-dépendance : les agents dépendent d’autres agents (A= agent) ; il s’agit d’une dépendance fonctionnelle ousociale ;
Joël Quinqueton 32
Raisons de Coopérer (3)
• résolution de conflits (eg augmentative ouconfrontative)– situations qui résultent d’un problème d’accès à
une ressource limitée, ou d'une compétition decompétences
– techniques de négociation, d’arbitrage,d’utilisation d’un règlement, de recours à lacompétition ou à la force
Joël Quinqueton 33
Allocation de Tâches (1)
• Objectifs– décomposer le problème en sous-problèmes– répartir les tâches selon les compétences des agents– ré-organiser si nécessaire
• Méthode– statique : chaque agent sait qui sait faire quoi– dynamique : mise en oeuvre d'une interaction entre
agents (eg contract net)– mixte : remise à jour périodique des connaissances sur
les autres
Joël Quinqueton 34
Allocation de Tâches (2)
• Allocation centralisée– un seul agent décompose un problème en sous-
problèmes et répartit les tâches entre les autres agents• plus grande cohérence, problème de fiabilité et d'extensibilité
• Allocation distribuée– chaque agent est capable de décomposer son problème
en sous-problèmes et de répartir les tâches associées• meilleure fiabilité et extensibilité, problème de cohérence
Joël Quinqueton 35
Exemples
Faire x Faire z
Faire y
Faire x
Faire y
Faire z
Allocation centralisée Allocation distribuée
Problème
Solution
Décomposition
Tâches
Synthèse
Joël Quinqueton 36
Le Réseau Contractuel (1)
• Allocation distribuée et dynamique des tâches parappel d'offre
• Fonctionne en 4 étapes:– annonce par l'offrant– proposition par les contractants– annonce d'un gagnant– établissement du contrat
Joël Quinqueton 37
Le Réseau Contractuel (2)Who can ?
I can I can I can 0.95 0.85 0.45
You realize
I realize I realize0.75 0.55
Give me
There it is
Annonce
Proposition
Annonce d'un gagnant& établissement
du contrat
Joël Quinqueton 38
La coordination
• Définition de la coordination [Malone 1987]– traitement additionnel de l’information– quand des agents connectés poursuivent des
buts– un agent seul poursuivant les mêmes buts n’en
aurait pas besoin
Joël Quinqueton 39
Coordination & Conflits (1)
• Comment planifier et coordonner les actionsde plusieurs agents de manière à ce qu'unbut commun soit atteint ?
• Deux modes:– planification centralisée– planification distribuée
Joël Quinqueton 40
Coordination & Conflits (2)
• planification centralisée– existence d'un organe centralisateur qui réalise
les plans et gère les conflits– peut s'exprimer de manière récursive– hyp: connaissance des compétences et
contraintes des autres agents + capacité àdécomposer
– facilite le maintien de la cohérence, demeureproche d'un problème classique de planification
Joël Quinqueton 41
Coordination & Conflits (3)
• planification distribuée– pas d'organe centralisateur, chaque agent
produit des plans partiels qui peuvent êtrecoordonnés par un coordonnateur
– hyp: capacité à communiquer les buts, actions& contraintes individuelles
– forte charge de comunication, forte complexité- problème non complètement résolu
Joël Quinqueton 42
Coordination Distribuée (1)
• Chaque agent produit un plan partiel– existence de conflits possibles entre plans partiels
• Quelques solutions:– un agent reçoit tous les plans partiels– tous les agents envoient tous leurs plans partiels– on exécute les plans partiels, et lors de l'exécution les
points de conflits sont reconnus et gérés
Joël Quinqueton 43
Coordination Distribuée (2)• un agent reçoit tous les plans partiels
– centralisation des plans, fusion et utilisation de techniques desynchronisation
• tous les agents envoient tous leurs plans partiels– chaque agent peut analyser les conflits potentiels et reconnaitre les
points de conflits avec ses propres plans• on exécute les plans partiels, et lors de l'exécution les
points de conflits sont reconnus et gérés– impose de pouvoir replanifier de manière dynamique
Joël Quinqueton 44
5.5 Coordination & Conflits
Résolution de Conflit
• Plusieurs solutions– Solution a priori
• Usage de la force, d'une autorité, d'un poids supérieur(ascendant d'un agent sur un autre)
– Arbitrage• existence d'un agent arbitre ou médiateur qui dispose des
différents points de vue et tente de résoudre le conflit– Négociation
• les agents en conflit entrent dans une série de tractations,d'échanges et de compromis de manière à parvenir à un accord,c'est-à-dire une solution qui satisfasse toutes les parties
Joël Quinqueton 45
5.5 Coordination & Conflits
Négociation (1)• Structure d'une négociation entre deux agents
A & B1.A fait une proposition2. B évalue sa proposition, détermine la satisfaction
qui en résulte3. si B est satisfait, on s'arrête là,
sinon B élabore une contre-proposition en fonctionde ses propres buts et de ses contraintes
4. on va en 2 en échangeant les rôles de A & B
Joël Quinqueton 46
Négociation (2)
• Deux grandes catégories de négociation– Négociation par compromis
• Chacune des parties relache les contraintes lesmoins importantes
• Il y a accord lorsque toutes les contraintes sontsatisfaites
– Négociation intégrante• Cherche à identifier les buts profonds (changement
de but)• Trouver une solution qui satisfasse complètement
ces buts et non les propositions de "surface"
Joël Quinqueton 47
Développement centré agent
• Accélérer le développement et diminuer l’effort deprogrammation
• Abstraire les mécanismes– de communication– d’interaction– de coordination
• Implémenter des systèmes complexes• Bonne extensibilité du code• Support pour le déploiement
Joël Quinqueton 48
Évaluation comparative d’outilset environnements
• Tony Garneau & Sylvain Delisle,Département de mathématiques etd’informatiqueUniversité du Québec à Trois-Rivières
• Présenté à JFIADSMA’2002, Lille• Prochain et dernier cours de TC
Joël Quinqueton 49
Plan de la présentation• Introduction• Évaluation
– Objectifs et choix des outils– Critères d’évaluation
• Résultats– Résultats par outil– Classement global
• Conclusion
