Le bavardage comme problème de planification

ECAI est la conférence européenne de référence sur l'intelligence artificielle. L'opportunité de découvrir quelques aspects de ce vaste domaine de recherche. Dans ce deuxième focus, nous découvrons le problème du bavardage (gossip problem) et du niveau de connaissances partagées à travers le casse-tête d'un groupe d'amis essayant d'organiser leurs prochaines vacances. Des chercheurs de l'IRIT viennent de proposer une nouvelle solution à ce problème, qui généralise les résultats antérieurs et ouvre de nombreuses perspectives d'application.

Un groupe d'amis s'est rencontré au mois d'août au camping. Ils ont échangé leurs numéros de téléphone, et quelques mois après ils se concertent pour convenir d'un rendez-vous pour l'été prochain, soit le 22 juillet, soit le 5 août. Supposons qu'ils peuvent seulement communiquer par appels téléphoniques (ce n'est certes pas très réaliste à l'époque de Facebook et Whatsapp, mais supposons). Combien de coups de fil faut-il passer pour que chacun sache les préférences de tous les autres ? Ce casse-tête est appelé le problème du bavardage (gossip problem).

Si le groupe ne comporte que deux amis, c'est très simple: un appel suffit pour qu'il y ait connaissance partagée: l'appelant et l'appelé connaissent les dates où cela leur est possible. Mieux, après cet appel, il y a connaissance partagée d'ordre 2: le premier ami sait que le second sait ses dates et inversement. L'ordre 1 correspondrait au fait qu'un ami connaisse les dates de l'autre ami, l'ordre 2 ajoute un niveau de connaissance (l'un sait que l'autre sait). Mieux encore, les dates deviennent connaissance commune: après un appel elles deviennent connaissance partagée de n'importe quel ordre k, c'est-à-dire pour n'importe quel chiffre, n'importe quel "niveau". Un nouvel appel apporte habituellement un niveau supérieur de connaissance (k+1), mais comme ils ne sont que deux amis à s'appeler, ils restent tous les deux au même niveau de connaissance: le premier sait que le second sait que le premier sait, ainsi de suite, pour n'importe quel enchâssement.

Si le groupe consiste en trois amis, il faut trois appels pour arriver à la connaissance partagée d'ordre 1. Par exemple, Anne appelle Béa, puis Béa appelle Chloé, et finalement Anne appelle Chloé (notons en passant que l'initiateur de l'appel n'a pas d'importance). Il est impossible d'arriver à la connaissance partagée d'ordre 1 avec moins d'appels. Le protocole à trois appels est donc optimal. Cependant, à la fin il n'y a pas connaissance partagée d'ordre 2: Béa ne sait pas qu'Anne a appelé Chloé, et ignore donc si Anne connaît les dates de Chloé. En effet, nous supposons que lors d'un appel les amis ne se communiquent que leurs dates. Il faut un quatrième appel entre soit Béa et Anne, soit Béa et Chloé. Cependant, il vaut mieux que les amis ne se communiquent pas simplement des dates: il peuvent par exemple communiquer également des connaissances à propos des dates. Ainsi, lors du quatrième appel, disons entre Béa et Anne, Anne peut dire à Béa que Chloé connaît les dates d'Anne ; autrement il faudrait un cinquième appel entre Béa et Chloé. Cependant et à la différence du cas de deux amis, pour trois ou plus il est impossible d'atteindre la connaissance commune. En effet, à plus de deux, cette connaissance commune ne pourrait être possible que s'il y avait une communication simultanée entre les amis, comme s'ils étaient autour d'une table, ou alors s'ils connaissaient l'ordre des appels et les informations demandées à chaque fois.

Quel protocole pour quatre amis ? Le cas de trois amis suggère un protocole à six appels: tout le monde appelle tout le monde. Cela donnerait ainsi pour n agents, n(n-1)/2 appels car les appels se font entre des "couples" d'amis. Mais on peut faire bien mieux: quatre appels peuvent suffire. D'abord Anne et Béa s'appellent pendant que Chloé et Diane s'appellent ; ensuite Anne et Chloé d'un côté et Béa et Diane de l'autre. Ce protocole pour atteindre la connaissance partagée d'ordre 2 peut être généralisé avec 2(n-2) appels. Ce sont des mathématiciens qui ont montré dans les années 70 que ces protocoles sont optimaux: il est impossible d'obtenir la connaissance partagée en moins d'appels.

Dans leur article à la European Conference on Artificial Intelligence (ECAI 2016), Martin C. Cooper, Andreas Herzig, Faustine Maffre, Frédéric Maris et Pierre Régnier de l'Institut de recherche en informatique de Toulouse (IRIT - CNRS/Université Toulouse 1/Université Toulouse - Jean Jaurès/Université Paul Sabatier/INP Toulouse) ont généralisé ce résultat: ils ont proposé un protocole qui produit la connaissance partagée d'ordre k en (k+1)(n-2) appels et ils ont montré que ce protocole est optimal. C'est une avancée par rapport aux résultats précédents car ce protocole permet d'atteindre la connaissance partagée d'ordre k+1, donc pour tous les "niveaux".

Au-delà d'un casse-tête amusant, le problème du bavardage est important en théorie des réseaux et en bases de données réparties: par quels mécanismes peut-on assurer qu'une information est partagée par une base de données répartie ou par un ensemble d'agents ? Le bavardage est également pertinent pour toute sorte de scenario impliquant des agents et leurs connaissances incomplètes. On peut s'imaginer des situations comme, par exemple, un groupe d'amis essayant de savoir si tout le monde va bien après une catastrophe ou un attentat. Il est alors tout à fait réaliste qu'un ami ne se contente pas de savoir que tout le monde va bien: il aimerait aussi rassurer les autres et aimerait donc qu'il y ait connaissance partagée d'ordre 2 ; voire d'ordre 3 ou au-delà. Il a été montré en psychologie sociale que de tels raisonnements sur les connaissances d'ordre supérieur sont fondamentaux pour l'interaction entre agents: l'absence d'une telle théorie de l'esprit (qui est communément supposée chez les autistes) rend la communication et la compréhension mutuelle difficile.

Le bavardage peut être vu comme un problème de planification multi-agents. Avant d'être un problème de calcul, il s'agit d'un problème conceptuel: comment modéliser les agents et leurs connaissances ? Les chercheurs de l'IRIT ont adopté un outil bien connu en intelligence artificielle: la logique épistémique. Des formules logiques comme KA KB p expriment que l'agent A sait que l'agent B sait que p est vrai, et la formule KA (¬KB p & ¬KB ¬p) exprime que A sait que B ignore si p est vrai ou non. Jusqu'à maintenant les chercheurs en planification classique se sont bornés à la communication de faits (à travers des formules booléennes), ce qui excluait la communication de connaissances. Les chercheurs de l'IRIT ont réussi à trouver une approche plus générale qui permet de communiquer des connaissances d'ordre supérieur (c'est-à-dire des connaissances communes ou des connaissances d'ordre partagée), ce qui dans le cas du problème du bavardage permet d'atteindre la connaissance partagée d'ordre supérieur, à défaut de connaissance commune. Ils ont également montré que leur résultat était optimisé.

Les chercheurs ont obtenu d'autres résultats pour des variantes du problème du bavardage: avec des graphes de communication non complets (où tous les amis n'ont pas tous les numéros de téléphone), avec des buts d'ignorance (où certains amis ne doivent pas apprendre certaines informations), etc. La simplicité et la flexibilité du problème du bavardage font ainsi de lui un problème paradigmatique pour la planification multi-agents. Jusqu'à maintenant les travaux en planification se sont concentrés sur des solutions centralisées (avec un ordonnanceur central qui détermine l'ordre des appels). Les chercheurs vont élargir leurs recherches à des variantes distribuées, mais aussi d'autres modes de communication, comme par exemple quand l'émetteur envoie un message à un groupe d'agents au lieu d'un seul.

Publication:A simple account of multi-agent epistemic planning de Martin C. Cooper, Andreas Herzig, Faustine Maffre, Frédéric Maris et Pierre Régnier