Recherche
Thèse
Resumé de la thèse
Titre: Formation de coalition dans les systèmes multi-agents rationnels
Introduction
Dans les Systèmes Multi-Agents (SMA) utilisés dans un contexte de commerce électronique, il faut concevoir des protocoles particuliers qui prennent en compte les particularités des agents.
Dans un contexte dynamique, la formation de coalitions permet de coordonner efficacement les agents.
L'objectif de la thèse est alors de concevoir dans ce contexte des protocoles qui permettent aux agents d'atteindre un consensus sur la structure de coalition à appliquer.
Les agents
Dans le contexte de commerce électronique, les agents peuvent représenter des personnes. Il est donc nécessaire de les considérer comme fortement autonomes.
Les stratégies sont potentiellement complexes, car basées sur le court, le moyen ou le long terme, limitées par une rationalité bornée, ... Il est donc difficile de décider si un comportement est rationnel ou pas. On ne peut donc pas faire d'hypothéses sur la rationalité des agents, car celle-ci n'est pas observable.
Du fait de la décentralisation de la conception dans l'espace et dans le temps, les agents sont fortement hétérogènes et il serait très réducteur d'imposer une architecture particulière.
Les agents sont donc fortement autonomes, faiblement rationnels et hétérogènes.
Les coalitions
Comme le montrent les théories organisationnelles, il n'existe pas de structure optimale ; dans un environnement qui se modifie rapidement, les organisations doivent donc s'adapter dynamiquement aux changements. Les coalitions, groupes créés ponctuellement en réponse à une demande, permettent de coordonner les agents de manière efficace.
Les protocoles
Pour répondre aux particularités des agents, il faut concevoir des protocoles particuliers.
Du fait des stratégies potentiellement complexes, on ne peut pas a priori connaître les meilleures solutions du point de vue des agents. Il faut donc concevoir des protocoles universels, i.e. indépendants de toute stratégie.
Dans le contexte de e-commerce, le protocole doit être accepté par toutes les parties. Il
doit donc notamment être égalitaire, c'est-à-dire ne favoriser personne.
Les agents sont fortement autonomes ; tout comportement est donc possible, même celui de tricheur. Les protocoles doivent donc empêcher toute triche, ou au moins pouvoir la détecter. Les règles du protocole doivent donc toutes s'appliquer à des données observables.
Les agents étant très hétérogènes, il paraît plus simple d'utiliser un langage de communication de bas niveau, suffisament riche pour permettre la négociation, mais sans que cela ne nécessite de traitements complexes.
Le protocole proposé
Le protocole que nous proposons est basé sur un échange de préférences (respect de l'hétérogénéité), avec un contrôle total des règles (contrôle de la triche) et indépendant de toute stratégie (respect de l'autonomie).
Les agents s'échangent leurs préférence en utilisant une diffusion parallèle, font éventuellement évoluer leur préférences jusqu'au consensus. En cas de blocage, une procédure de formation d'alliances permet de retourner dans une phase évolutive.
Habituellement, les préférences sont modélisées à partir d'une hypothèse de transitivité, plus ou moins forte. Au contraire, nous montrons qu'une préférence est une comparaison locale entre deux possibilitiés, et que donc la transitivité n'est pas requise. Sans cette hypothèse, nous avons pu proposer un nouveau formalisme et défini de façon naturelle un opérateur d'agrégation de préférences. Cependant, mais l'opérateur de choix (ou d'élection) reste difficile à déterminer de façon univoque.
Expérimentations
J'ai développé une plateforme de test rapide de protocoles utilisant les réseaux de Petri afin de tester les caractéristiques de notre protocole, puis de proposer des stratégies efficaces.
Conclusion
Nous avons proposé un protocole de formation de coalition dans des systèmes multi-agents dans un contexte de commerce électronique. Il est basé sur un échange de préférences et respecte l'autonomie des agents. Puis nous avons validé et testé ce protocole.