Descriptif
Introduction
Un système multi-agent est constitué d’un grand nombre d’entités autonomes, appelées agents, ayant généralement un objectif individuel à atteindre, en interaction entre elles au sein d’un même environnement. Dans tous les SMA, une fonction globale est attendue à partir de la spécification au niveau local de chacune des entités. Ce phénomène global est émergent lorsque la manière d'atteindre cette propriété du niveau global n’est pas programmée dans les agents et n’existe que par leurs comportements et interactions conduisant à une activité permanente d’adaptation collective. L'étude de ce phénomène d’émergence, et ce dans de nombreuses disciplines scientifiques, tente de décrire et d’expliquer les formes, les motifs et les comportements survenant au sein d’un système dans son environnement sans organisateur (contrôle) extérieur à celui-ci. Elle correspond à l’apparition spontanée d’une cohérence globale à partir uniquement des interactions locales au micro-niveau d’entités initialement indépendantes et où les règles d’interaction du micro-niveau sont exécutées sans aucune référence à la fonction globale.
L’objectif de ce projet, côté multi-agent, est d’établir un modèle général de système multi-agent et environnement puis de le particulariser afin d’étudier des propriétés de ceux qui sont à fonctionnalité émergente fondée sur l’auto-organisation coopérative. Les deux questions de base qui se posent sont :
- Est-il possible de définir les propriétés que les agents doivent posséder pour que le système multi-agent satisfasse une propriété globale particulière ?
- Si les agents satisfont une certaine propriété, que peut-on en déduire au niveau global ?
Modèle général à agents explicites
La grande variété des systèmes dits multi-agents est a priori couverte par une grande variété de modèles: Algèbres de processus, automates cellulaires ou communicants, synchrones ou asynchrones, systèmes de réétiquetage ou de réécriture de graphes, programmation par contraintes distribuées, etc.
Nous proposons de rechercher un modèle assez général pour modéliser les différents types de systèmes multi-agents, qui puisse s’instancier en chacun des principaux types de ces systèmes, afin de les classer, les caractériser et les comparer. Outre le fait qu’un tel modèle met en évidence différentes formes de communication et de synchronisation, un des objectifs est également de mettre en évidence et comparer différentes formes des concepts d’émergence, de coopération et de non-coopération etc.
Pour déterminer les propriétés de tels systèmes, il faut un modèle défini à partir du comportement de chaque agent, de ses interactions avec les autres agents et avec l’environnement. Il ne faut pas qu'il soit directement défini comme une boîte noire (système de transition global). Il faut donc pouvoir expliciter un certain nombre d’éléments et de concepts, notamment :
- Chaque action du MAS doit être assignée à un agent (ou plusieurs);
- Il faut pouvoir exprimer l’action simultanée/combinée de plusieurs agents;
- Un agent peut lui-même être un MAS;
- Il faut pouvoir reconnaître l’état d’un groupe d’agents (pouvant être le collectif complet);
- Il faut exprimer le couplage par feed-back entre les états du système et ceux de son environnement;
- Il faut définir les notions de système coopératif, d’agent coopératif, d’état coopératif (local et global);
- Il faut définir un phénomène émergent.
Problématique multi-agent - enrichissement théorique
Les problématiques multi-agent et les modèles distribués s’enrichissent mutuellement. Un exemple de cet enrichissement est le croisement entre les algèbres de processus et la programmation par contraintes.
Un croisement auquel nous nous intéressons est celui entre les produits d’automates (ou algèbres de processus) et les topologies de réseau d’interconnexion. On considère un ensemble d’automates dont les composants s’exécutent sur les sommets d’un graphe d’interconnexion, et auquel on ajoute la contrainte que les synchronisations entre automates s’exécutent sur des sous-graphes particuliers. Par exemple, les synchronisations binaires s'exécutent sur des paires de sommets voisins, les synchronisations multiples sur des cliques ou des étoiles, etc. Dans ce cas un blocage local peut être causé par une topologie particulière interdisant à une synchronisation de s’effectuer.Cette situation peut être vue comme un état non coopératif, et l’action correctrice consiste à modifier localement la topologie du graphe sous-jacent afin de permettre cette synchronisation. Pour chaque graphe sous-jacent on a un système de transition modélisant le comportement du système pour ce graphe particulier. Les actions correctrices font passer d’une topologie à une autre comme le montre le schéma suivant:
Apport des laboratoires
IRIT
Les
membres de l’équipe SMAC apporteront leur
connaissance des systèmes multi-agents et plus
particulièrement sur ceux basés sur
l’auto-organisation par coopération. En effet,
l'équipe SMAC de l’IRIT s'intéresse
à la conception d'applications ouvertes, complexes, dont les
environnements sont dynamiques et pour lesquelles il n'y a pas de
solution algorithmique connue (par exemple, la prévision de
crues, la synthèse de mécanismes, la
programmation émergente, le commerce
électronique, la robotique collective...).
Nos travaux s’articulent autour de la théorie AMAS
qui oriente la conception de systèmes multi-agents
adaptatifs à fonctionnalité émergente.
Dans ce cadre les notions de systèmes adaptatifs,
d’apprentissage, d’auto-organisation et
d’émergence sont étudiées.
Conformément à la théorie des AMAS,
nous avons pu vérifier expérimentalement que
lorsque les agents coopèrent réellement,
l'activité collective est optimale. La
coopération est ainsi un critère local de
réorganisation interne du système lorsqu'il est
plongé dans un environnement dynamique. Nous apportons ainsi
notre expérience concernant le développement de
systèmes multi-agents.
LAAS
Le LAAS apporte sa connaissance
sur la modélisation, la
spécification et la vérification des
systèmes distribués complexes à
communication synchrone ou asynchrones. La théorie des
ordres partiels, des automates communicants, des
réseaux de Pétri, des algèbres de
processus sont des outils fondamentaux pour
l’étude de ces systèmes, et le LAAS en
a développé de nombreuses applications aux
systèmes coopératifs, aux protocoles de
communication, etc.
Divers travaux ont donné naissance à des
modèles spécifiquement adaptés
à des problématiques particulières,
tels que des algèbres de processus
dynamiques et des algèbres de processus
localisés sur des graphes d’interconnection. Ces
travaux nous semblent particulièrement adaptés
aux systèmes multi-agents.
De plus le LAAS est actif dans le domaine de la vérification
des systèmes distribués, d’un point de
vue théorique mais également pratique par la
conception d’outils performants dont l’adaptation
aux systèmes multi-agents produira un
bénéfice mutuel.