Les applications pratiques des SMA révèlent une amélioration significative des performances des robots autonomes dans des environnements inconnus. En s’inspirant des comportements naturels, cette recherche propose une approche innovante qui transforme notre compréhension de la coordination multi-agent, avec des implications cruciales pour l’intelligence artificielle.
Les mécanismes de coordination multi-agent
Le mécanisme spécifique de coordination qui est actif dans un SMA détermine sa dynamique interne, i.e. les interactions entre les agents ainsi que les propriétés externes de la société d’agents. Les mécanismes de coordination varient avec les domaines dans lesquels ils sont utilisés et en fonction de la propension des agents à coopérer, de l’environnement et de son degré de stabilité et de prédictibilité, ainsi que des tâches à réaliser.
Pourquoi coordonner ?
Appliquer la définition de la coordination au cadre des SMA amène à dire que la coordination est la gestion des dépendances qui existent entre les activités des agents. Or, dans un SMA, les activités des agents sont souvent incomplètement spécifiées car il est impossible d’avoir des agents omniscients disposant d’informations complètes et à jour sur l’état complet du système dont ils font partie. Dans ce contexte, la coordination correspond avant tout aux différents processus ou actions que les agents doivent engager afin de réaliser leurs actes sociaux de manière cohérente : l’unité globale du système issue des comportements locaux des agents doit être préservée. Sans coordination, un système est voué au désordre.
Comment coordonner ?
Au niveau d’un SMA, la coordination nécessite de déterminer l’existence de situations d’interaction, d’identifier ces situations d’interactions et de les gérer.
La question est de savoir comment mettre en œuvre une coordination au niveau du système. De nombreuses questions de recherches se posent alors :
- Les mécanismes de coordination doivent-ils être implémentés au sein des agents, entre les agents, au travers de l’environnement, au travers de l’organisation, au travers des échanges ?
- Si l’on décide d’associer un mécanisme au niveau des agents, doit-on diminuer les interactions entre les agents en les spécialisant, en réduisant leurs interdépendances ou augmenter les capacités locales afin de prendre des décisions localement plus adaptées ?
- Si l’on décide d’associer un mécanisme au niveau des organisations : doit-on spécialiser les agents et former des structures organisationnelles centralisées, hiérarchiques, de marchés ou de communautés ?
- Si l’on décide d’associer un mécanisme au niveau des interactions : doit-on faire échanger des informations afin d’augmenter les connaissances sur le système (représentation des autres, méta-information, abstractions) et gérer les communications (mesure d’intérêts, de temps de réponse…) ? [Champion ,03]
Toutes ces possibilités de mise en œuvre de mécanismes de coordination sont envisageables et peuvent être combinées pour donner naissance à d’autres mécanismes [Bond et al, 88]. Les mécanismes multi-agents les plus courants et occupant une place privilégiée dans la littérature sont présentés par la Figure 1.7. Ces mécanismes multi-agents sont issus des réflexions menées sur la classification (selon le type des dépendances à gérer) des mécanismes théoriques de coordination et appliquées au contexte des systèmes multi-agents.
[4_applications-pratiques-des-systemes-multi-agents_5]
Figure 1.7 : Principaux mécanismes de coordination multi-agent.
Ces mécanismes sont maintenant exposés un à un dans les parties suivantes. Il s’agit de la structuration organisationnelle, de l’allocation (de ressources ou de tâches), de la planification, de la négociation et de la coordination réactive.
Structuration organisationnelle
L’organisation définit implicitement les responsabilités, les capacités et le rapport à l’environnement des agents. La structuration organisationnelle exploite cette structure organisationnelle prédéfinie du SMA qui fournit un cadre pour les activités et les interactions à travers la définition des rôles, des moyens de communication et des relations d’autorité. Dans un SMA, l’organisation est habituellement vue comme l’ensemble des relations à long terme entre agents. Quand les agents jouent certains rôles dans une organisation, ils agissent suivant le comportement que ces rôles et leurs relations impliquent. [Champion ,03]
Il existe deux configurations extrêmes de ce type d’organisation. Dans une organisation hiérarchique, chaque tâche est contrôlée par un agent gestionnaire qui coordonne son processus de réalisation [Durfee et al , 89]. A l’opposé, dans une organisation latérale, il n’existe pas de gestionnaire unique et chaque tâche est réalisée de manière coopérative. La configuration intermédiaire et la plus courante d’organisation est la structure informelle dans laquelle cohabitent une certaine hiérarchie induite par des relations d’autorité, des contacts en diagonale et des contacts horizontaux directs entre les agents (Figure 1.8).
[4_applications-pratiques-des-systemes-multi-agents_6]
Figure 1.8 : Exemples de structures organisationnelles (d’après [Ossowski 98])
- Allocation
La résolution de problèmes s’effectue généralement en quatre phases : la décomposition des tâches (et/ou des ressources), l’allocation des tâches (et/ou des ressources), l’exécution des tâches (et/ou des ressources) et la synthèse des résultats de l’exécution. Dans ce contexte, l’allocation essaie de répondre à la question : qui doit faire quoi et comment, en fonction des
buts, des compétences des agents et des contraintes contextuelles, sachant que les agents impliqués pouvant être différents les uns des autres
[4_applications-pratiques-des-systemes-multi-agents_7]
Figure 1.9: Résolution d’un problème par un SMA.
Concernant l’allocation de tâches, celle-ci peut s’effectuer de deux manières selon qu’elle dépende d’un ou de plusieurs agents. D’une part, si un seul agent décompose un problème en sous-problèmes et répartit les tâches entre les autres agents, l’allocation est centralisée. D’autre part, si chaque agent est capable de décomposer son problème en sous problèmes et de répartir les tâches associées, l’allocation est distribuée.
La méthode d’allocation de tâches la plus étudiée est probablement le réseau contractuel Il s’agit d’une allocation distribuée et L’allocation de ressources répond à une problématique similaire à celle de l’allocation de tâches et celles-ci sont souvent liées. Les mécanismes employés pour l’allocation de ressources sont souvent fondés sur des systèmes issus de l’économie tels que le contrôle de marché ou les enchères.
Planification
La planification multi-agent tente de coordonner les actions de plusieurs agents de manière à ce qu’un but commun soit atteint (exemples classiques : la construction d’une maison, l’assemblage de composants…) [Hendler, 90]. Du fait que les agents établissent des plans qui spécifient leurs actions et interactions futures en fonction d’un certain objectif, tous les agents impliqués dans la planification s’entendent pour se comporter suivant ces plans.
La planification dans un SMA peut se décomposer en trois étapes : la construction de plans, la synchronisation de plans (coordination) et l’exécution de plans. Comme il est possible d’utiliser un ou plusieurs agents à chacune de ces étapes, il est possible d’obtenir un grand nombre d’organisations différentes. Un système de planification est alors composé d’un
ensemble d’agents pouvant planifier, synchroniser ou exécuter des plans, un même agent pouvant accomplir une seule ou plusieurs de ces tâches
[4_applications-pratiques-des-systemes-multi-agents_8]
Figure 1.10 : Système de planification multi-agent (exemple).
- Négociation
Une part importante du travail effectué sur la coordination multi-agent concerne la négociation car la majorité des mécanismes de coordination peut entraîner un processus de négociation. La négociation peut sembler être la solution ultime pour la résolution de conflit et la littérature est prolixe concernant tout ce qui s’y rapporte.
Pour définir la négociation, il est possible de dire qu’il s’agit d’un processus par lequel une décision conjointe est prise par deux ou plusieurs parties.
La négociation comporte quatre aspects : la décision, le langage, l’objet de la négociation et le processus [Müller, 96] :
- La décision : Il s’agit de la dimension intra-agent, elle est relative à la modélisation du raisonnement du négociateur. Pour prendre une décision quant au déroulement d’une négociation, l’agent peut avoir recours à des fonctions d’utilité (utilisation de la théorie des jeux, par exemple), à des fonctions de comparaison et de corrélation, à des préférences et à des stratégies de négociation. La stratégie de négociation occupe une place prépondérante dans le développement d’un processus de négociation. Une stratégie détermine quelle option, parmi celles permises, un agent décide de choisir. Une stratégie peut relever d’un comportement purement égoïste ou, plus rarement, altruiste de la part du négociateur. Elle est, dans tous les cas, basée sur des critères locaux, non contraints par des conventions externes.
- L’objet de la négociation : Le point central d’un modèle de négociation est de représenter le sujet pour lequel il existe un différent parmi les agents. L’objet de la négociation est fortement dépendant du contexte et peut être de nature diverse (tâches, intervalles de temps, ressources, plans, etc.).
- Le langage : Il s’agit de la dimension inter-agent, elle est relative à la communication
(explicite ou implicite) entre les agents. Comme il n’est pas toujours suffisant de communiquer l’objet de la négociation, un agent à besoin d’exprimer comment l’autre partie devrait interpréter un message. Pour répondre à cette problématique, des travaux ont été réalisés à partir de la théorie des actes de langage et ont mené à l’élaboration de primitives de négociation. Enfin, un protocole de négociation doit être défini afin de déterminer la séquence des messages. Le protocole est généralement une convention acceptée et utilisée par toutes les parties impliquées dans le processus, il s’agit d’une connaissance commune. Le protocole fait référence aux primitives et contraint l’objet de la négociation.
[4_applications-pratiques-des-systemes-multi-agents_9]
Figure 1.11 : Exemple de protocole de négociation entre deux agents.
- Le processus : Il s’agit de la dimension globale, elle est relative au comportement du système. Le processus est fonction des modèles de négociation mis en œuvre et des comportements des participants. Il peut prendre plusieurs formes. Lorsqu’il est question d’une négociation par compromis, chacune des parties relâche les contraintes les moins importantes et l’accord est établi lorsque toutes les contraintes sont satisfaites. Lorsqu’il est question d’une négociation intégrante, les agents cherchent à identifier les buts profonds et à trouver une solution qui satisfait complètement ces buts. [Champion, 03]
Coordination réactive
La coordination réactive s’intéresse essentiellement, comme son nom l’indique, à la coordination des agents réactifs. Ceux-ci étant très simples de par leur structure interne et possédant une représentation très limitée de leur environnement, des mécanismes de
coordination dédiés ont du être mis en œuvre. Plusieurs cas sont possibles.
Si les agents ont des buts indépendants, les seuls problèmes qu’ils peuvent rencontrer viennent des conflits éventuels d’accès à des ressources communes. Il est alors possible de distinguer
deux grandes catégories de situations. Les premières ont trait à l’accès d’une même portion d’espace par un ensemble d’agents. Il s’agit alors pour eux d’accomplir leurs buts tout en s’évitant. Les techniques utilisées sont alors des techniques définissant des comportements répulsifs et attractifs tels que le comportement de meute [Reynolds, 87] (pour constituer des meutes de robots [Mataric, 92]) ou le comportement de bancs de poissons. Une des techniques les plus abouties est celle dite des champs de vecteurs, utilisée pour la résolution de conflits relatifs aux trajectoires de vol des avions [Zeghal, 93]. Les secondes catégories de situations portent sur l’utilisation d’une ressource ponctuelle, telle un outil commun. Il est alors possible d’utiliser des mécanismes de synchronisation.
Si les agents ont des buts dépendants et que les actions des uns peuvent améliorer celles des autres et donc augmenter les performances du système dans son entier, le principe général consiste à utiliser les capacités des agents réactifs à réagir aux modifications de l’environnement et souvent à marquer cet environnement pour coordonner les actions des agents entre eux. Les exemples classiques sont la récupération de minerais par des robots explorateurs et la résolution de problèmes par création de « chemins d’odeur », métaphore faisant référence aux fourmis et aux phéromones qu’elles laissent sur leur passage [Drogoul, 93].
________________________
2 Définition donnée par l’article 62 de la loi sur les nouvelles régulations économiques (NRE) du 15 mai 2001. ↑
3 Auchan Les 4 Temps, La Défense. ↑
Questions Fréquemment Posées
Quels sont les mécanismes de coordination dans les systèmes multi-agents ?
Les mécanismes de coordination dans les systèmes multi-agents incluent la structuration organisationnelle, l’allocation de ressources ou de tâches, la planification, la négociation et la coordination réactive.
Pourquoi est-il important de coordonner les agents dans un système multi-agent ?
La coordination est importante car elle permet de gérer les dépendances entre les activités des agents, préservant ainsi l’unité globale du système issue des comportements locaux des agents.
Comment peut-on mettre en œuvre la coordination dans un système multi-agent ?
La coordination peut être mise en œuvre en déterminant l’existence de situations d’interaction, en identifiant ces situations et en les gérant, que ce soit au niveau des agents, de l’organisation ou des interactions.