Corrélation, interaction, systèmes multiagents et coordination

Corrélation

 Il est possible de déterminer de manière empirique si des agents « font quelque chose ensemble » en mesurant leur entropie mutuelle [Adami, 1998]. Sans avoir accès à la structure interne des agents ni au système dans son ensemble, on peut calculer si les actions des agents sont statistiquement liées les unes aux autres. Si c’est le cas, on parle alors de corrélation entre les agents. Toutefois la notion de corrélation n’est pas liée à l’interaction ; en effet imaginons un ensemble d’agents parfaitement identiques plongés dans le même environnement mais incapables d’interagir : étant identiques et confrontés au même environnement, les agents ont des comportements très semblables, voire identiques s’ils sont entièrement déterministes, et donc on observe une très forte corrélation malgré une absence totale d’interaction. Mais dans un tel cas l’activité globale n’est que la juxtaposition des activités individuelles. 

 Interaction L’environnement d’un agent

 A peut contenir d’autres agents qui sont susceptibles d’agir sur cet environnement. Or A Dans [Van Dyke Parunak et al., 2002], les auteurs parlent plutôt de coordination et définissent la communication comme tout flux d’information entre l’agent et son environnement (qui inclut les autres agents). Le terme interaction nous semble plus approprié pour couvrir la diversité des flux d’information entre un agent et son environnement. Prenons par exemple un cas de ressources partagées entre agents, le dîner des philosophes orientaux (dû à Dijkstra) : « Cinq philosophes orientaux partagent leur temps entre l’étude et la venue au réfectoire pour manger un bol de riz. La salle affectée à la sustentation des philosophes ne comprend qu’une seule table ronde 8 Chapitre 1. Agents et SMA FIG. 1.1 – la table des philosophes. sur laquelle sont disposés un grand plat de riz (toujours plein), cinq bols et cinq baguettes. » patientent et la baguette 2 est inutilisée. Comme on le voit sur la figure 1.1, un philosophe qui prend les deux baguettes autour de son bol empêche ses voisins d’en faire autant. Dès qu’il dépose l’une de ses baguettes, son voisin, affamé, peut s’en emparer. Le cas échéant, ce dernier devra attendre que l’autre baguette soit disponible. Les baguettes sont ici les ressources partagées et les agents interagissent par leur intermédiaire. Il y a interaction entre les agents mais pas de véritable communication2 , à moins que nos philosophes ne se soient mis d’accord sur un protocole d’utilisation des baguettes. Pour nous, il y a interaction entre un agent A et un agent B, si le choix des actions de A peut être influencé par B (et inversement). Il faut donc que : (1) A puisse percevoir une partie des actions de B (ou du moins leurs conséquences sur l’environnement) et que (2) A tienne compte de ces perceptions pour choisir ses actions. DÉF. 1.2 – Interaction. Soit un environnement E comprenant un ensemble d’agents Γ = {A, B, C…}. Nous dirons que les agents de Γ interagissent si et seulement si pour tout agent x de Γ, il existe un autre agent y de Γ qui, plongé dans E \ {x} a une séquence d’actions différente de celle qu’il a dans E, toutes choses étant égales par ailleurs. À présent que nous avons défini la notion d’interaction, nous pouvons définir ce que nous entendons par système multiagent : DÉF. 1.3 – Système multiagent. Un système multiagent (SMA) est un environnement qui contient un ensemble d’agents qui interagissent. 1.2.3 Coordination Nous avons vu dans la section précédente qu’une des notions fondamentales des SMA est l’interaction entre agents. Toutefois, cette notion 2Pour une discussion plus approfondie à propos de cette distinction, se référer au chapitre 3. 10 Chapitre 1. Agents et SMA n’est pas suffisante, en effet dans la plupart des cas les interactions entre agents sont plus élaborées que le simple partage de ressources de l’exemple des philosophes. Nous parlerons alors de coordination. DÉF. 1.4 – Coordination. Nous parlerons de coordination dans un ensemble d’agents si et seulement si (1) ces agents interagissent et (2) une partie au moins de ces interactions prend la forme de transmission d’information par un langage articulé ou par d’autres codes. Il va de soit, d’après cette définition, que coordination implique interaction, mais il peut être difficile de différencier une simple interaction d’un code ou même d’éléments d’un langage articulé. Par exemple, les abeilles utilisent les mouvements de leur corps afin d’indiquer à leurs congénères la position de sources de nourriture. Il a fallu beaucoup de temps avant qu’on ne se rende compte que ces étranges « danses » constituent un véritable langage [Von Frisch, 1993]. Il serait tentant de définir la coordination comme de l’interaction associée à de la communication, cependant nous n’aborderons pas le problème de la communication dans ce chapitre et nous ne la définirons qu’au chapitre 3. La coordination est donc une notion liée aux capacités « cognitives » des agents. Un transfert d’information ne se différencie d’une simple suite d’actions3 que par la capacité des agents à le décoder. On peut dire que pour que des agents soient capables de coordination, ils doivent avoir été conçus pour cela, tandis que deux agents quelconques peuvent très bien interagir, par exemple en se gênant mutuellement. 

Architecture réactive et coordination 

Architecture réactive

 Nous avons vu que la rationalité d’un agent se juge à la manière dont il associe ses actions à ses perceptions. La manière la plus simple de concevoir un agent rationnel (on parlera d’architecture) est donc de le doter d’un 3 Il peut même s’agir simplement de certaines propriétés de l’agent, comme les couleurs vives de certains animaux (par exemple certaines grenouilles d’Amazonie) qui signifient « poison » aux éventuels prédateurs. Et il s’agit bien là uniquement d’un transfert d’information, car certains animaux arborent ces mêmes couleurs sans pour autant être toxiques, ce qui leur assure pourtant une certaine tranquillité. L’ensemble de règles stimulus-réponse qui décrira entièrement son comportement. On parlera alors d’agent réflexe ou encore d’approche comportementale (behavior-based). L’approche comportementale pour la conception d’agents rationnels artificiels est principalement due à Brooks du MIT4 avec son architecture de subsomption [Brooks, 1986]. Dans deux manifestes maintenant célèbres [Brooks, 1991a ; Brooks, 1991b] il définit son projet : concevoir des robots « intelligents » (des agents rationnels) de manière incrémentale, en partant de comportements très simples et en les combinant pour en obtenir de plus élaborés, jusqu’à l’« intelligence ». Dans ce projet, Brooks prend le contre-pied de l’approche utilisée jusque-là en intelligence artificielle (IA) et qui consistait à prendre le problème « par le haut » en commençant par le raisonnement de haut niveau (voir section 1.5.1) et en postulant que les tâches en apparence plus simples telles que la perception et l’action se résoudraient facilement. Cette approche classique, que Brooks désigne par le sobriquet GOFAI (Good Old-Fashioned Artificial Intelligence) a donné des systèmes capables de résoudre des problèmes complexes et même de prouver des théorèmes mathématiques par exemple, mais incapables ne serait-ce que de se déplacer dans un laboratoire en évitant quelques obstacles (tâche qui semble pourtant bien simple). Au contraire, Brooks commence par traiter les problèmes tels que la locomotion, et réalise des robots capables de se déplacer même dans des environnements très accidentés (voir figure 1.2). La différence fondamentale entre l’approche classique et l’approche comportementale tient aux symboles. L’approche classique donne une représentation symbolique de son environnement à l’agent. Cette représentation est une abstraction des sorties des capteurs de l’agent, l’agent manipule ensuite ces symboles en interne grâce à un « modèle du monde » et décide de ses actions. Dans l’approche comportementale, on considère que « le monde est son meilleur modèle ». Dans sa version la plus simple (figure 1.3), cette approche ne comporte pas d’état interne, les sorties des capteurs sont directement traitées par de simples circuits électriques qui calculent en continu le signal à envoyer aux effecteurs. Règles Perception Action FIG. 1.3 – Architecture réactive. Comme illustré figure 1.4, il est possible d’adjoindre des états internes à un agent réactif afin de rendre son comportement plus « intelligent ». En effet, imaginons un agent réactif A poursuivant une cible B. Son principe de fonctionnement est on ne peut plus simple : toujours avancer vers B. Mais si à un moment donné A ne perçoit plus B (à cause d’un obstacle par exemple) il risque fort de s’arrêter sur place alors que si A continue à se déplacer, B finirait par reparaître. En dotant A d’un seul état interne du type « dernière position connue de B » on peut rendre son comportement plus robuste. Tant que le nombre de ces états internes reste limité, il est possible de parler d’architecture réactive (voir section 1.5.1). 

Coordination entre agents réactifs

 Malgré leur simplicité de principe, des agents réactifs en groupe peuvent montrer une grande richesse de comportements collectifs. Nous en présentons ici quelques exemples.Émergence, éthologie Il est possible de modéliser le comportement de sociétés animales ou même des phénomènes de foule par des SMA composés d’agents réactifs simples. Notamment en éthologie, il a été possible de simuler de manière très fidèle des comportements tels que le fourragement chez les fourmis ([Topin et al., 1999] ou le projet Manta [Drogoul et Ferber, 1994], figure 1.5) ou encore la construction de nids chez certaines espèces de guêpes [Bonabeau et al., 2000]. Ces simulations aident à étudier l’influence des variations de divers paramètres de l’environnement sur le comportement de la société. portement individuel et collectif. De l’interaction entre les membres d’un SMA, émerge le comportement global du système. Ainsi, des termites individuellement très simples sont capables en groupe de construire une structure aussi complexe qu’une termitière, avec ses loges, galeries et cheminées d’aération. Travaux de Matari´c Dans la lignée des travaux de Brooks, Matari´c [Matari´c, 1994 ; Matari´c, 1995 ; Matari´c, 1998] propose une architecture comportementale pour la synthèse de comportements collectifs comme le déplacement en groupe, le fourragement (figure 1.6) ou l’accostage, à partir de comportements individuels de base comme le déplacement avec évitement d’obstacles, la poursuite, l’agrégation ou encore la dispersion.