Modèle en étoile
Communication
Certaines approches prennent en compte les difficultés liées aux communications, toutefois le plus souvent, ce problème est abordé d’un point de vue utilitariste (voir par exemple [Xuan et al., 2001]). Ces approches reconnaissent qu’il est parfois problématique pour des agents de communiquer mais réduisent cette difficulté par un coût associé à l’action de communication, ce coût est intégré aux processus de décision de l’agent, ce qui lui permet de décider s’il est « rentable » de communiquer. Néanmoins, ces approches ne considèrent pas les cas dans lesquels la communication est impossible (à moins d’y associer un coût infini) et il n’est pas toujours facile de savoir comment les agents obtiennent les valeurs des coûts associés aux communications et connaissent leurs éventuelles évolutions1 . 5.2.1 Socially attentive monitoring Ainsi dans STEAM [Tambe, 1996a] (et plus particulièrement dans SAM (Socially Attentive Monitoring) [Tambe et Kaminka, 2000], voir section 4.5.2 et annexe A) les membres de l’équipe n’émettent effectivement qu’une partie des messages que le modèle des intentions communes — qui est à la base de STEAM — leur impose d’émettre. Pour ce faire, SAM permet aux membres de l’équipe d’estimer de manière probabiliste l’état de l’équipe (sa position dans sa hiérarchie d’activités, voir section 4.5.2) en fonction d’observations et des messages reçus (qui peuvent ne représenter qu’une partie des messages émis). Sachant que les autres membres utilisent SAM, connaissant des informations relatives au domaine (telles que des probabilités d’observations de certains faits ou encore d’émission de messages selon l’activité courante de l’équipe) et disposant d’une fonction d’utilité, un agent peut déterminer s’il doit ou non émettre un message en comparant ce que lui coûte l’émission et le coût estimé pour l’équipe si ce message n’est pas émis. Cette approche est une des rares qui permette à une équipe de collaborer malgré des communications non fiables (et elle permet de plus aux agents d’en profiter pour se passer d’émettre certains messages), toutefois elle repose sur une grande quantité d’informations liées au domaine, dont l’obtention n’est pas triviale et dont l’existence repose sur des hypothèses fortes (les probabilités, les fonctions d’utilité, le coût des communications).
Routage
La solution la plus couramment utilisée (souvent implicitement d’ailleurs) pour faire face au fait que deux agents n’ont pas directement la possibilité communiquer est d’utiliser des techniques de routage provenant du domaine des réseaux afin de faire transiter les messages d’agent en agent.
Écoute flottante
Comme nous venons de le voir, les systèmes de communication classiques hérités des réseaux et de l’informatique, qui donnent aux agents une interface de communication abstraite, ne nous satisfont pas dans le cas général. En effet, en occultant le support de communication « physique » ils empêchent les agents de tirer parti de certaines de ses propriétés. La plupart des supports de communication ne sont pas dyadiques par nature, par exemple nous avons déjà vu (chapitre 4) que la communication orale entre humains ne l’est pas : même lors d’une conversation entre deux personnes, un tiers est susceptible d’entendre ce qui se dit et même d’intervenir. Il est vrai que les systèmes multiagents artificiels dans lesquels la communication se fait oralement sont plutôt rares, mais les mêmes propriétés se retrouvent en fait dans presque tous les supports : les communications par radio sont par nature émises « à la cantonnade » et susceptibles d’être interceptées par plusieurs agents présents dans le système. Même sur un réseau local ethernet classique cette propriété se retrouve : tous les messages (à vrai dire les trames IP) « passent devant » tous les agents présents sur le réseau, on a l’impression contraire uniquement parce que les agents autres que le destinataire s’interdisent de lire ce qui ne les concerne pas (par souci de confidentialité, mais aussi d’économie de ressources de calcul). Cette propriété des supports de communication permet naturellement d’appliquer les principes de l’écoute flottante aux SMA. Plutôt que de tenter de transformer un support de communication non fiable pour fournir une interface standard de communication dyadique à des agents qui ont souvent besoin de communications de groupe, nous estimons qu’il est préférable de « rester proche » du support et de laisser les agents eux-mêmes tenir compte des propriétés du support de communication. Ainsi, nous prenons le parti que seuls les agents pouvant directement communiquer le peuvent. Par exemple, si un agent doit transmettre une information à un agent avec lequel il ne peut directement communiquer, il ne peut compter sur une « couche » spécifique du système pour le faire mais doit par exemple faire explicitement appel à un autre agent pour l’y aider, ou bien les agents doivent avoir été conçus pour naturellement faire circuler les informations pertinentes dans le système. Plutôt que de « router » les messages entre les agents, nous estimons qu’il est parfois plus pertinent de « router » l’information. L’avantage est alors qu’aucune ressource n’est utilisée pour tenter de maintenir l’illusion d’un système de communication fiable et reliant tous les agents alors que les possibilités de communication entre les agents sont par nature partielles et dynamiques. En utilisant les principes de l’écoute flottante les agents peuvent, en plus des communications « normales », suivre l’évolution de l’activité du système les environnant, détecter la présence de nouveaux membres du système, estimer les croyances des autres membres ou encore leur proposer spontanément de nouvelles informations.
Groupes locaux
Nous avons vu au chapitre 2 que la plupart des structures de coopération nécessitent pour les agents de pouvoir communiquer. Or, nous avons décidé de nous passer des systèmes classiques de communication qui auraient pu nous assurer des possibilités de communication à travers tout le système, et nous nous plaçons même dans des cas où les communications sont si problématiques que de tels systèmes ne sont pas applicables. Une solution est que les agents se regroupent entre agents pouvant plus facilement communiquer afin de coopérer malgré tout. 5.3.1 Groupes La définition la moins restrictive que l’on peut donner d’un groupe d’agents est : un sous-ensemble de l’ensemble des agents d’un SMA. Un tel sous-ensemble peut se définir en intension ou en extension. Une définition en intension définit les membres d’un groupe par certaines propriétés, par exemple « les habitants de Toulouse », tandis qu’une définition en extension définit le groupe par l’énumération de ses membres. Les deux formes sont a priori nécessaires pour la manipulation de la notion de groupe par les agents. D’une part, il semble naturel de penser que pour que deux agents puissent coopérer ils doivent se connaître. Ceci fait que les membres d’un groupe doivent se connaître les uns les autres au moins dans une certaine mesure, ce qui justifie la définition des groupes en extension. Mais d’autre part, ces groupes ne se forment pas de manière totalement aléatoire ou arbitraire, mais obéissent à certaines règles, car sinon ces groupes n’auraient aucune signification. Les aspects intensifs et extensifs peuvent en fait se conjuguer : les règles afférentes aux groupes peuvent être utilisées par un agent afin de déterminer quels sont les membres d’un groupe, mais aussi pour déterminer si un groupe potentiel est valide ou non. Une des contraintes (ou règles) les plus couramment utilisées concernant les groupes, et que nous reprenons dans notre modèle, est qu’un agent 80 Chapitre 5. Modèle en étoile ne peut être membre que d’un seul groupe à la fois. Cette contrainte peut ne s’appliquer qu’à certains niveaux du système, par exemple un agent qui fait partie du groupe « les habitants de Toulouse » ne peut appartenir à « les habitants de Paris », mais peut appartenir au groupe « les moustachus ». On retrouve cette propriété par exemple dans [Tidhar et al., 1998], où les groupes forment une hiérarchie, deux groupes du même niveau ont une intersection nulle, mais leurs membres peuvent faire partie d’un même groupe de niveau supérieur. 5.3.2 Localité Créer des groupes se justifie par une hypothèse sur les propriétés des possibilités de communication entre agents. Nous désignons cette hypothèse comme l’hypothèse de localité des communications en référence à l’exemple typique de limitation de portée des communications, illustré sur la figure 5.3. Dans le cas où c’est leur portée qui limite la communication entre les agents, il est raisonnable pour eux d’estimer que s’ils peuvent communiquer à un instant t ils le pourront encore dans les instants qui suivent, et il est donc raisonnable pour eux de se regrouper (au moins temporairement) pour coopérer. Dans cet exemple les possibilités de communication sont directement liées aux distances entre les agents, d’où la notion de localité. La définition suivante généralise le concept de communication locale : DÉF. 5.1 – Communications locales. Nous définissons les possibilités de communication entre agents d’un SMA comme locales si pour tout instant t il existe une durée δt telle que les conditions de communication restent identiques durant l’intervalle de temps [t, t + δt]. COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE COMMENTAIRE L’alternative à une situation de communications locales est par exemple un mode de communication dans lequel les messages émis ont une probabilité fixe de réception. Dans ce cas, le fait de pouvoir communiquer avec un possibilités de communication avec cet agent. Si les communications sont locales, il est alors raisonnable pour les agents de former des groupes pouvant coopérer localement en tirant parti des bonnes conditions de communication entre les membres. L’idée de créer des groupes pour faciliter la coopération n’est pas nouvelle, on peut 5.3. Groupes locaux par exemple citer les travaux de Matari´c qui dans [Matari´c, 1998] utilise des communications locales pour l’apprentissage avec des agents qui se regroupent pour des périodes de temps pendant lesquelles ils interagissent fortement. Le même principe peut être également appliqué dans des systèmes de grande taille afin cette fois de structurer les communications [Hyuckchul et Tambe, 2003]. Au sein de ces groupes il est possible d’utiliser une grande variété de structures de coopération (voir chapitre 2). Toutefois il faut noter que ces structures doivent être capables de s’adapter dynamiquement à des effectifs variables dans le groupe ou bien être capables de s’initialiser rapidement. En effet, si les conditions de communication changent rapidement, les groupes formés ne peuvent rester stables très longtemps, et ils peuvent même avoir des durées de vie très courtes