IV.2.4. Agent médiateur
· Son utilité principale est dans le processus de
planification dont il joue le rôle d'un coordinateur entre les
différents agents services. Il sert à chercher un plan solution
au problème de l'utilisateur en planifiant l'ensemble d'actions
retournées par les agents service et en résolvant les
différents conflits pouvant exister entre eux.
· C'est au niveau du quel donc, qu'un planificateur
existe.
1. Architecture interne
Cet agent est un agent cognitif. Au niveau duquel le
raisonnement principal de notre modèle est réalisé ; c'est
la planification proprement dite.
Afin de bien comprendre son architecture interne, il est
essentiel avant de l'aborder, d'expliquer les grandes lignes du
déroulement de la planification au niveau de cet agent.
En effet, le modèle de planification utilisé
est distribué, le domaine de planification est réparti sur
l'ensemble des agents service. Chaque agent service est capable de
réaliser un certain nombre d'actions : ses compétences. C'est la
mise en commun et l'ordonnancement des compétences de chaque agent, dans
le but de résoudre un problème donné, qui va permettre de
faire émerger un plan solution.
Cette mise en commun et ordonnancement sont assurés
par le module de planification de cet agent médiateur ; le
planificateur.
Le planificateur utilisé dans notre modèle
repose sur la recherche de la solution dans un espace d'états (chapitre
1 § I.2.3.1), exploite le principe du chaînage arrière et
communique avec les différents agents service pour collecter l'ensemble
d'opérateurs lui permettant la poursuite du processus de
planification.
Pour raisonner, ce planificateur a besoin donc d'une
structure de données lui facilitant la construction du graphe
d'états et son parcours et d'un module de communication lui facilitant
l'intégration des compétences des agents service.
Un planificateur, une structure de données
représentant le graphe d'états et un module de communication sont
donc les composants de notre agent médiateur. Ils sont
représentés dans la figure « figure 4.14 » suivante
:
Agent service1
Agent service2
Agent serviceN
Agent utilisateur
Problème
Plan
Planificateur
Agent médiateur
Graphe
d'états construit
Module de
communication
Figure 4.15 : Architecture interne de «
l'agent médiateur »
· Le graphe d'états construit :
c'est une structure de données qui sert de support au
raisonnement du planificateur. Elle représente un graphe d'états
orienté construit dynamiquement au cours du processus de planification
dont, les noeuds sont les différents états atteints par le
planificateur et les arcs représentent les différents
opérateurs (actions) venants des agents service qui permettent de passer
d'un état à un autre. Le noeud principal du graphe
représente le but de l'utilisateur à atteindre.
But
Sous_but1 Sous_but2 Sous_butn
Sous_sous_but1 Sous_sous_but2
Chaque noeud du graphe représente :
1. les préconditions de l'opérateur venant de l'un
des agents service et permettant de passer de son noeud père à
lui ; et
2. les effets des opérateurs venants des agents service
et permettant de passer de lui à ses noeuds fils.
Lorsque le planificateur arrive à construire un chemin
dans ce graphe permettant d'aller du noeud principal (le but) à un noeud
satisfaisant l'état initial alors, le problème est résolu
et le plan solution sera donc l'inverse de la séquence
d'opérateurs allant du but à l'état initial.
· Le planificateur : l'agent
médiateur lorsqu'il reçoit un problème (état
initial et but) de l'agent utilisateur, il exploite les opérateurs
(compétences) des différents agents service dans un algorithme de
planification pour le résoudre. Ce module de l'agent sert à
implémenter un tel algorithme.
Planificateur
Plan solution
Ensemble d'actions de planification
venants des agents
service
|
|
|
Description de l'état initial
Description du but
Rappelons (comme déjà vu dans le chapitre1
§ I.2.3) qu'un nombre important d'algorithmes existe pour faire la
planification. Le planificateur de notre système exploite le
mécanisme de la recherche d'une solution dans un espace d'états
ainsi que le principe du chaînage arrière.
Ce planificateur est considéré
régressif, puisqu'il se déplace vers l'arrière.
Il consiste à construire le graphe de recherche du problème, non
pas en partant de l'état initial, mais en partant du but et en
appliquant l'inverse des opérateurs de planification (venant des agents
service) pour produire des sous-buts jusqu'à arriver à
l'état initial. Si l'algorithme permet de remonter à cet
état initial, alors il retourne le plan solution trouvé.
· L'algorithme de planification :
Avant d'aborder l'algorithme, il convient de montrer
premièrement son principe. Principe :
- L'algorithme est récursif, il exploite le graphe
d'états pour résoudre le problème soumis par
l'utilisateur.
- Il diffuse le but de l'utilisateur avec son état initial
vers tous les agents service comme un premier problème à
résoudre (première itération de l'algorithme).
- Chaque fois que le planificateur reçoit toutes les
réponses des agents service à un nouveau sous-problème, il
dispose d'un mécanisme lui permettant de vérifier l'existence
d'un plan solution au but de l'utilisateur (un chemin dans le graphe
d'états allant du but à l'état initial de
l'utilisateur).
- Si ce n'est pas le cas (l'itération essayée ne
convient pas à résoudre le but de l'utilisateur), et tant qu'il
n'a pas trouvé de solution satisfaisante, le planificateur met
éventuellement à jour le graphe d'états et le parcourt
d'abord pour choisir un nouveau sous-but non résolu encore et il le
diffuse avec l'état initial de l'utilisateur à tous les agents
service comme un nouveau sous-problème à résoudre
(nouvelle itération).
- L'algorithme s'itère alors jusqu'à arriver
à construire dans le graphe d'états, un chemin allant du but de
l'utilisateur à son état initial.
|
Algorithme 4.2 : algorithme de planification
1. mettre le but de l'utilisateur le noeud principal du
graphe d'états ;
2. soit path la séquence
d'opérateurs (actions), permettant de passer du noeud principal du
graphe d'états à un autre noeud du graphe (un sous-but).
3. initialisation :
· path ? ø ;
· nouveau_but ? but_utilisateur ;
· solution_trouvée ? false ;
· non_solution_trouvée ? false ;
4. Tant que
(non(solution_trouvée)et(non(non_solution trouvée)))
faire
· Diffuser (nouveau_but, état initial) aux
différents agents service ;
· Attendre toutes les réponses des agents
service ;
· Si (l'un des agents service
retourne un opérateur « op » dont les effets
correspondent
au « nouveau_but » et les préconditions
correspondent à l'état initial ) alors
solution ? inverse de (path.op) ; solution_trouvée ?
true ;
· Si (toutes les
réponses sont négatives et il n'y a pas encore de noeuds à
visiter dans le graphe d'états) alors
solution ? pas de solution ; non_solution_trouvée ?
true ;
|
|
Algorithme 4.2 : algorithme de planification
(suite)
· Si (toutes les
réponses sont négatives, mais il y'a de noeuds pas encore
traités) alors
nouveau_but ? choisir noeud pas encore traité du
graphe d'états ;
path ? séquence d'opérateurs permettant de
passer du but principal à ce noeud ;
· Si (un ensemble d'agents
service retournent un ensemble d'opérateurs dont les Effets
correspondent à « nouveau_but » mais les préconditions
ne correspondent pas à l'état initial)
alors
Mettre à jour le graphe d'états (ajouter les
préconditions des opérateurs retournés comme des sous-but
fils de « nouveau_but ») ;
nouveau_but ? choisir noeud pas encore traité du
graphe d'états ; path ? séquence d'opérateurs permettant
de passer du but principal à ce noeud ;
5. Fin tant que
6. Retourner (solution) à l'agent utilisateur
;
|
Exemple illustratif :
Afin d'illustrer le fonctionnement de cet algorithme,
introduisons l'exemple suivant :
Notre utilisateur est à Paris le Dimanche et veut se
rendre à New York le Mardi. Il veut organiser son voyage par Internet.
Pour le faire supposons que deux services sont déjà
sélectionnés : un service de réservation de vols
aériens et un autre de réservation de trains.
Dans notre système ces deux services sont
représentés par les deux agents : Agent_S_V et Agent_S_T.
· L'agent Agent_S_V extrait de la description du service
qu'il représente l'opérateur suivant :
Reserver_Vol(Nom_utilisateur Ville_depart Ville_Arrivee
Date_Depart Date_Arrivee) Precond : (À Nom_utilisateur Ville_Depart
Date_Depart)
Effet : (À Nom_utilisateur Ville_Arrivee
Date_Arrivee)
Et a comme base de connaissances :
(Exist_trajet Paris Madrid Dimanche Dimanche)
(Exist_trajet London Moscou Samedi Dimanche) (Exist_trajet London New York
Lundi Mardi)
· L'agent Agent_S_V extrait de la description du service
qu'il représente l'opérateur suivant :
Reserver_Train(Nom_utilisateur Ville_depart Ville_Arrivee
Date_Depart Date_Arrivee) Precond : (À Nom_utilisateur Ville_Depart
Date_Depart)
Effet : (À Nom_utilisateur Ville_Arrivee
Date_Arrivee)
Et a comme base de connaissances :
(Exist_trajet Roma Paris Mercredi Jeudi) (Exist_trajet Alger
Paris Samedi Dimanche) (Exist_trajet Madrid London Dimanche Lundi)
De la requête de l'utilisateur l'agent utilisateur extrait
le problème de planification suivant et l'envoie à l'agent
médiateur :
Etat initial : (A utilisateur Paris Dimanche)
Etat but : (A utilisateur New York Mardi)
Après la réception de ce problème par
l'agent médiateur, l'algorithme se déroule comme suit :
1. Initialisation Le graphe d'état est le suivant :
(A utilisateur New York Mardi)
nouveau_but ? (A utilisateur New York Mardi) path ?
ø
2. L'agent médiateur diffuse le problème
((A utilisateur New York Mardi) , (A utilisateur Paris Dimanche)) aux
deux agents Agent_S_V et Agent_S_T puis, il attend jusqu'à recevoir
leurs réponses.
3. Les deux agents service suite à la réception
de ce problème, cherchent en exploitant leurs bases de connaissances
dans leurs actions celles dont les préconditions correspondent à
l'état initial du problème et les effets correspondent au but.
Agent_S_V ne trouve pas cette correspondance, mais il trouve
une action (Reserver_Vol(utilisateur London New York Lundi Mardi))
dont les effets correspondent au but et dont la précondition ne
correspond pas à l'état initial, cet agent envoie donc cette
précondition ((A utilisateur London Lundi)) comme un nouveau
but à résoudre à l'agent médiateur.
Agent_S_T ne trouve aucune correspondance, il envoie donc une
réponse négative.
4. maintenant, l'agent médiateur dispose des
réponses des deux agents service, il va procéder comme suit :
Il met à jour le graphe d'états, ce dernier sera
donc le suivant :
(A utilisateur New York Mardi)
(A utilisateur London Lundi)
nouveau_but ? (A utilisateur London Lundi)
path ? ( Reserver_Vol(utilisateur London New York Lundi
Mardi))
5. L'agent médiateur diffuse le nouveau
problème ((A utilisateur London Lundi) , (A utilisateur Paris
Dimanche)) aux deux agents Agent_S_V et Agent_S_T puis, il attend
jusqu'à recevoir leurs réponses.
6. Agent_S_V lui renvoie une réponse négative
et Agent_S_T lui renvoie l'opérateur (Reserver_Train(utilisateur
Madrid London Dimanche Lundi)) et comme un nouveau but à
résoudre la précondition de cet opérateur (A
utilisateur Madrid Dimanche).
7. Suite à la réception de ces réponses,
l'agent médiateur : Met à jour le graphe d'états, il sera
le suivant :
(A utilisateur New York Mardi)
(A utilisateur London Lundi)
(A utilisateur Madrid
Dimanche)
nouveau_but ? (A utilisateur Madrid Dimanche)
path ? ( Reserver_Vol(utilisateur London New York Lundi
Mardi) , Reserver_Train(utilisateur Madrid London Dimanche Lundi) )
8. L'agent médiateur diffuse le nouveau
problème ((A utilisateur Madrid Dimanche) , (A utilisateur Paris
Dimanche)) aux deux agents Agent_S_V et Agent_S_T puis, il attend
jusqu'à recevoir leurs réponses.
9. Agent_S_T lui renvoie une réponse négative
et Agent_S_V lui renvoie l'opérateur (Reserver_Vol(utilisateur Paris
Madrid Dimanche Dimanche)) et un message lui indiquant que cet
opérateur permet de résoudre le nouveau problème
reçu directement.
10. Suite à la réception de ces réponses,
l'agent médiateur va mettre à jour les deux variables : solution
et solution_trouvée comme suit :
solution_trouvee ? true
solution ? ( Reserver_Vol(utilisateur Paris Madrid Dimanche
Dimanche) Reserver_Train(utilisateur Madrid London Dimanche Lundi)
Reserver_Vol(utilisateur London New York Lundi Mardi) )
11. De cette façon, l'algorithme sort de la boucle «
tant que » et retourne à l'agent utilisateur le
plan solution (contenu de la variable « solution »).
2. Fonctionnement
Perception :
- Réception d'un message de l'agent administrateur,
contenant la liste des identificateurs des agents services.
- Réception d'un message de l'agent utilisateur, contenant
la description du problème à résoudre.
- Réception d'un message de l'agent utilisateur,
contenant une demande
d'annulation d'une demande de composition en cours de
résolution.
- Réception d'un message de l'agent service, contenant une
solution directe à un problème.
- Réception d'un message de l'agent service, contenant une
liste d'actions possibles.
- Réception d'un message de l'agent service, indiquant
l'absence d'une solution au niveau de cet agent.
Raisonnement : le raisonnement
effectué par cet agent est au niveau de la planification. Après
que l'agent soit doté de la description du problème (état
initial et but) d'après l'agent utilisateur, il exécute
l'algorithme de planification afin de le résoudre.
Action : selon le diagramme d'activités
suivant :
Attente
Recevoir message (problème) d'un agent utilisateur
Recevoir message (annulation) d'un agent utilisateur
Interroger les agents service
Diffuser message
(annulation) vers
les agents service
Planifier
Autre
Solution trouvée
Non solution trouvée
Envoyer message (solution) à l'agent utilisateur
Envoyer message (pas de solution) à l'agent
utilisateur
Figure 4.16 : Diagramme d'activités pour
le fonctionnement de l'agent médiateur IV.3. interactions entre
les agents du système
Dans la partie précédente, nous avons
présentées l'architecture et le fonctionnement de chaque agent du
système à part. cependant, dans le modèle proposé
aucun des agents ne peut résoudre le problème de l'utilisateur
tout seul. C'est la coopération entre les agents qui le permet.
Cette coopération nécessite en effet, des
différentes interactions entre les agents. Ces dernières sont
directes par envoie de messages.
L'envoie de messages entre les agents nécessite un
langage commun compréhensible par tous les agents du système.
Dans notre travail nous avons choisies le langage FIPA-ACL (il sera
détaillé dans l'annexe).
Pour modéliser les interactions entre les agents, les
concepteurs des systèmes multi-agents peuvent utilisés
différents moyens : les diagrammes de séquence UML peuvent
être utilisés, ils sont simples et intelligibles, mais ils ne
fournissent pas aucun flux de contrôle.
Dans notre travail nous avons exploitées une autre
alternative: l'utilisation des diagrammes de protocole
d'interaction d'AUML utilisés par la FIPA. Ces diagrammes sont
en effet une extension des diagrammes de séquence d'UML, mais qui sont
plus puissants dans leur expressivité. Ils les étendent par
l'ajout d'un nombre d'éléments de flux de contrôles et
utilisent les actes communicatifs d'ACL pour les messages
échangés (voir l'annexe).
Les interactions pouvant existés dans notre système
sont :
· interactions agent administrateur - agent utilisateur
· interactions agent administrateur - agent
médiateur
· interactions agent utilisateur - agent
médiateur
· interactions agent médiateur - agent service
Dans ce qui suit nous détaillerons chaque type
d'interaction à part par une modélisation à travers les
diagrammes de protocole d'interaction AUML.
| 
