N.Kabachi1
PLAN GENERAL
BibiliographieHistoriqueDe l’IA à l’IADThèmes de recherche de l’IADProblèmes de base en IADSociété d’Agents (SMA)
• Concept d’Agent• Communication• Organisation• Coopération• Résolution de conflits
Exemple d’application
N.Kabachi2
Organisation (1)
un construit politique et culturel, un moyen dont les acteurs sociaux se dotent pour régler leurs interactions afin d’obtenir le minimum de coopération nécessaire pour atteindre des objectifs collectifs. [Crozier & Friedberg, 77]
une structure décrivant comment les membres sont en relation et interagissent afin d’atteindre un but commun. [Fox, 81]
la somme totale des moyens employés pour diviser le travail en tâches distinctes et pour ensuite assurer la coordination nécessaire entre ces tâches. [Mintzberg, 79]
liée à la division de travail, répartition des rôles, des tâches et de responsabilités entre les membres d’un groupe
N.Kabachi3
Organisation (2)
Deux Approches pour la conception des organisations[Sichman, 95]
l’approche statique : les liens d’autorité et de communicationentre des agents sont complètement définis pendant la phase deconception du système.
l’approche dynamique : les liens d’autorité et de communicationne sont pas pré-établis entre les agents, ils sont créés de façondynamique ( "émergence").
Exemple en Éthologie : société de fourmis, de termites, etc...
N.Kabachi4
Organisation (3)
Typologie des organisations [Gasser, 92]
centralisée (hiérarchie uniforme) : correspond au mode d’adaptation fixe, avec des liens de subordination de type maître/esclave. Exemple : l’armée.
de marché : correspond aux organisations basées sur le principe de contrat.Un mécanisme d’allocation de tâches régi par le protocole d’appel d’offres. Exemple : l’univers économique
de communauté pluraliste : correspond aux organisations variablesémergentes. Exemple : la communauté scientifique
de communauté à règles de comportements : des organisations variables prédéfinies avec interactions selon des protocoles explicités. Exemple : les systèmes multi-experts.
N.Kabachi5
Organisation (4) : Exemple
Niveau Opérationnel
Niveau Tactique
Niveau Stratégique
AC1,2AC1,1
AC0,1
AC0,2
AC0,3
AC0,5 AC0,6
AC2,1
AC0,4
Niveau méta
: lien de dépendance : lien de hiérarchie : effet de groupe
N.Kabachi6
La coopération peut signifier :
partage d'information
détection et résolution de conflits
réalisation de tâches en commun
résolution d'un problème à plusieurs
Coopération (1)
N.Kabachi7
Coopération (2)
Les être humains coopèrent à cause de leurs capacités limitées[Schmidt, 91] : Point de vue de la sociologie
Quatre buts génériques de coopération [Durfee et al., 91] :
Augmenter la vitesse de résolution des tâches par leur parallélisation
Augmenter le nombre ou la portée des tâches réalisables par le partage de ressources
Augmenter la probabilité d’achever des tâches par leur duplication et si possible par l’utilisation de méthodes différentes pour les réaliser
Diminuer l’interférence entre tâches en évitant les interactions négatives.
N.Kabachi8
Modèles de coopération
Un agent peut coopérer suivant les modèles suivant :
Coopération par partage de tâches et de résultats : Ce type de coopération est adapté pour les domaines où il existe une hiérarchie de tâchesou de niveaux d’abstraction. Dans le cas contraire il faut procéder par partage de résultats.
Commande : un agent supérieur décompose le problème en sous-problèmes qu’il répartit entre les autres agents, ceux-ci le résolvent et renvoient les solutions partielles à l’agent supérieur.
Coopération (3)
N.Kabachi9
Appel d’offre : un agent supérieur décompose le problème en sous-problèmes dont il diffuse la liste. Chaque agent qui le souhaite envoie une offre ; l’agent supérieur choisit parmi celles-ci et distribue les sous-problèmes. Le système travaille ensuite en mode commande.
Compétition : l’agent supérieur décompose et diffuse la liste des sous problèmes comme dans le mode appel d’offre, chaque agent résout un ou plusieurs sous-problèmes et envoie les résultats correspondants à l’agent supérieur qui à son tour fait le tri.
Coopération (4)
N.Kabachi10
Contrôle (2) : point de vue de l’IA, l’IAD
Système : artefact-artefact, artefact-humain: IHM
Contrôle:1. Interaction (véhicule du contrôle)
• langage d'interaction (actes de langage)2. Contrôle de la coopération: a. Protocoles d'interaction (Y. Demazeau) b. Agents spécialisés dans la gestion des interactions
- broker, coordinateur ( A. Slodzian)- gestionnaire (J.L. Soubie)
N.Kabachi11
Contrôle (3) : point de vue de l’Éthologie
Système: société animale, insectes.
Contrôle:1. environnement : Lorsque les seules
interactions entres individus surviennent au travers des modifications de l'environnement
(Wilson E.O.).2. Stigmergie : L'insecte ne dirige pas son travail,
mais il est guidé par lui.(Grassé P.P. )
N.Kabachi12
Résolution de conflits (1)
Les agents coopératifs ont besoin d’éviter les situations conflictuelles pour résoudre un problème
• Coordination de leurs activités• Négociation de leurs actions
Une solution possible
N.Kabachi13
Résolution de conflits (2)
CoordinationLa coordination des actions (dans le cadre de la coopération) est l’articulation des actions individuelles accomplies par chacun des agents de manière à ce que l’ensemble aboutisseà un tout cohérent et performant.
Exemple : - deux véhicules qui se croisent dans un carrefour, - un trapéziste qui doit agripper les poignets de son partenaire - les avions de la patrouille de France - les musiciens dans un orchestre
La coordination des actions est liée à la planification et à la résolution de conflits.
N.Kabachi14
Résolution de conflits (3)
NégociationLes activités des agents sont souvent interdépendantes et entraînent des conflits. Pour les résoudre, il faut considérer lespoints de vue des agents, les négocier et utiliser des mécanismesde décision concernant les buts du système.
La négociation est caractérisée par :
• un nombre faible d’agents impliqués dans le processus• un protocole minimal d’actions : proposer, évaluer, modifier et accepter ou refuser une solution.
N.Kabachi15
Résolution de conflits (4)
Structure de négociation entre deux agents A et B
1. A fait une proposition;2. B l’évalue et détermine la satisfaction qui en résulte;3. Si B est satisfait alors arrêt, sinon B élabore une contre-proposition et donne des arguments;4. Si A considère les argument de B alors reprendre ce schéma en inter-changeant A et B, sinon faire intervenir un troisième agent.
N.Kabachi16
- Automates à états finis (Winograd & Florès 86)- Réseaux de Pétri
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
N.Kabachi17
Processus Physique
Projet Production
Chaîne d’Activités 2
AgentUsinage
Centre Activité Fraisage
Centre Activité Usinage
AgentCdB
Centre Activité CdB
Centre Activité Ordo.
FraisageAgent
AgentOrdo.
PAgent
Agent
Processus Adm. Chaîne d’activités 1
Chaîne d’activités 2
fraisage
Flux Informationnels
Flux Matières
Modèle d’une entreprise
A
N.Kabachi18
Situation réelle de négociation et de conflitAgent "A"
L'agent A fixe "La Taille de Lot (TL) de production à 35 pièces".
- Rationalité évaluative: retards de livraison aux clients (Re) avec un Taux de satisfaction de Y jours de retards - Intentions : respecter la Re - Connaissances: une petite TL permet de diminuer les retards.
-Rationalité évaluative: sur le rendement physique (Re) avec un Taux de satisfaction de X% de rendement.-Intentions : respecter la Re.-Connaissances: pour améliorer le rendement, il faut limiter les changements d'outils donc augmenter la TL.
Agent "Ordo" Agent "fraisage"
SITUATIONS
Négociation Conflit
N.Kabachi19
0
2
4
6
8
54 55 56 57 58
Rendement physique(%)
Retards de livraison
(jours)
35
4045
50 55
60
65
70
(Taille des lots)
Résultats de la Négociation
L'observation des résultats indique une convergence vers une taille "optimale"de 50 pièces par lot
N.Kabachi20
Modèle de compréhension d’une entreprise
D D
D
Centre de Décision
Chaîne d’Activités
Centre deDécision
CentreActivités
Re/Rs
Centre deDécision
CentreActivitésProcessus
Opérationnel D
Re/Rs
Processus Stratégique
D D
D
Centre de Décision
Chaîne d’Activités
Centre deDécision
CentreActivités
Re/Rs
Centre deDécision
CentreActivitésProcessus
Opérationnel
Centre de Décision
Rationalité issues duniveau sup
Intentions
SystèmeInférent
Infos. Perçues
Connai-ssances
Décisions
Rationalités
Centre de Décision
N.Kabachi21
Agents Cognitifs : Diagramme d'États
AccointancesCentre
ActivitésPercevoir
du CA
Raisonner
RécupérationMessage
Contrôle
AgentMéta
Niveau
Rationalités, Décisions
Requêtes informations
Requêtes, Infos, ...
Agent Cognitif
Environnement
Création/EnvoiMessages
Signaux
Décisions
Percevoirde l’Env.Informations
N.Kabachi22
Modèle Fonctionnel d’un Agent Cognitif
Perception
Capacité d’exécution(Contrôle)
Informations
Met à Jour
Capacités de Raisonnement
Connaissances
Raisonne sur Active leraisonnement
Communications
Messages
Contrôle
Interprète
Décisions
Système d’information
Autres Agents Centres d’Activités
: Environnement : Fonctionnalités
N.Kabachi23
Conclusion : Construction d’un SMA (1)
Problème : la poursuite
Ce problème vient d’un jeu lui-même tiré d’une histoire, Octobre Rouge, dans laquelle un sous-marin Soviétique (proies) doit essayer d’échapper à des torpilleurs américains (prédateurs).
Le but de ce jeu est de parvenir à ce que les prédateurs capturent les proies en l’entourant (Cf. diapo suivante).
Construire un Système Multi-Agents
N.Kabachi24
Conclusion : Construction d’un SMA (2)
Proie capturéepar des prédateurs
Prédateurs
Proieslibres