[News] Le bavardage comme problème de planification

Biologie, géologie, histoire naturelle, etc...

Modérateur : Modérateurs

Répondre
Isabelle
Messages : 11157
Inscription : 02/09/2004 - 10:49:47

[News] Le bavardage comme problème de planification

Message par Isabelle » 08/09/2016 - 12:00:27

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.

Image

Image
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

Source: CNRS-INS2I

Jack Teste-Sert

Re: [News] Le bavardage comme problème de planification

Message par Jack Teste-Sert » 08/09/2016 - 14:27:59

Absurde..., de croire que seuls les autistes peuvent communiquer par télépathie avec succès !

Une connexion quantique discriminante est possible à tout moment dès lors qu'on cible la personne que l'on veut joindre en la nommant (ou en y pensant). Dès lors, la connexion sort du "niveau planétaire quantique collectif" pour s'adresser sélectivement à la personne ciblée qui est immédiatement joignable.
Confirmation E.T. : http://www.ummo-sciences.org/fr/index-ordo.htm

Par contre, il reste à voir si cette communication télépathique est possible vers un groupe de personnes sélectionnées. Cela je ne l'ai pas testé !

Victor
Messages : 17133
Inscription : 05/06/2006 - 21:30:44
Activité : Retraité
Contact :

Re: [News] Le bavardage comme problème de planification

Message par Victor » 08/09/2016 - 14:40:49

Pour qu'un communication télépathique fonctionne
il faut surtout être émotionnellement accordé,
lorsqu'il y a un flots de discours c'est rare que cet accord soit fait,
En ce qui concerne la recherche en sciences, Je dirais : Cherche encore !

Avatar de l’utilisateur
QJ
Messages : 646
Inscription : 18/04/2007 - 9:47:23
Activité : Autre
Localisation : Belgique

Re: [News] Le bavardage comme problème de planification

Message par QJ » 08/09/2016 - 15:33:14

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.
Jack Teste-Sert a écrit :Absurde..., de croire que seuls les autistes peuvent communiquer par télépathie avec succès !
... Heu... Que dire...
:lol3:
L'esprit c'est comme un parachute: s'il reste fermé, on s'écrase. -Franck Vincent Zappa-

Avatar de l’utilisateur
cisou9
Messages : 10085
Inscription : 12/03/2006 - 15:43:01
Activité : Retraité
Localisation : Pertuis en Lubéron
Contact :

Re: [News] Le bavardage comme problème de planification

Message par cisou9 » 08/09/2016 - 15:49:33

___________ :_salut:
Rien; c'est de la science fiction !! :lol:
Un homme est heureux tant qu'il décide de l'être et nul ne peux l'en empêcher.
Alexandre Soljenitsyne.

Victor
Messages : 17133
Inscription : 05/06/2006 - 21:30:44
Activité : Retraité
Contact :

Re: [News] Le bavardage comme problème de planification

Message par Victor » 08/09/2016 - 16:47:16

C'est toi qui le dit !
En ce qui concerne la recherche en sciences, Je dirais : Cherche encore !

Pendesinialessandro
Messages : 229
Inscription : 04/08/2015 - 11:34:31
Activité : Enseignant ou Chercheur

Re: [News] Le bavardage comme problème de planification

Message par Pendesinialessandro » 08/09/2016 - 16:55:05

Absurde..., de croire que seuls les autistes peuvent communiquer par télépathie avec succès !
Jack Teste-Sert Dixit ! :yxt:

D’après un sondage Gallup USA 2001, je suis légèrement étonné ou déconcerté par une société dans laquelle 50% de la population adulte croit à la perception extrasensorielle, 42% aux maisons hantées, 41% à la possession du diable, 36% à la télépathie, 32% à la voyance, 28% à l’astrologie, 15% au channeling, et 45% à l’exactitude litterale du recit de la Création dans la Genèse.
Plus près de nous, les Français, la pensée scientifique et les parasciences :
-55% des français croient aux guérisons par magnétiseur, imposition des mains, ainsi que à la transmission de pensée ;
-46% aux explications des caractères par les signes astrologiques ;
-35% aux rêves qui prédisent l’avenir ;
-29% aux prédictions par les signes astrologiques, et horoscopes ;
-24% aux prédictions des voyantes ;
-23% à l’inscription de la destinée dans les lignes de la main ;
-19% aux envoûtements et sorcellerie ;
-18% aux passages sur Terre des extraterrestres ;
-16% aux tables tournantes ;
-11% aux fantômes, revenants…..
NB 58% de ces mêmes Français pensent que « l’astrologie est une science ». Ce qui prouve que nos contemporains ne savent plus très bien ce qu’est une science ou ce que science veut dire ! :pfff:

NB :-Les bonnes raisons de croire sont des raisons « épistémiques », c’est-à-dire les preuves, ou les données disponibles aux sujets, qui vont manifestement à l’encontre de ce qu’ils ont choisi de croire, en prenant leurs désirs pour des réalités, et c’est là un exemple typique de comportement irrationnel.

Victor
Messages : 17133
Inscription : 05/06/2006 - 21:30:44
Activité : Retraité
Contact :

Re: [News] Le bavardage comme problème de planification

Message par Victor » 08/09/2016 - 16:57:22

Perso c'est une partie de mon vécu, maintenant je n'explique rien de rien du tout
Je n''ai pas des voix comme dans le diagnostic que la schizophrènie mais des gens qui m'entendent
Je fais très bien la différence avec des boules Quiès
Ce n'est pas parce que vous niez ces phénomènes qu'ils n'existent pas
La psychologie et la psychiatrie, c'est un continent quasi vierge
En ce qui concerne la recherche en sciences, Je dirais : Cherche encore !

Pendesinialessandro
Messages : 229
Inscription : 04/08/2015 - 11:34:31
Activité : Enseignant ou Chercheur

Re: [News] Le bavardage comme problème de planification

Message par Pendesinialessandro » 08/09/2016 - 18:41:51

....Ce n'est pas parce que vous niez ces phénomènes qu'ils n'existent pas !.....
Victor DIXIT et nous tous devons le croire sur parole !
Cher Victor :
Vous semblez ignorer qu’il existe un critère pour vérifier si une opinion est raisonnable ou pas : toutes les opinions ne le sont pas ! Il suffit de démontrer rationnellement qu’elles le sont, au lieu de se limiter à le prétendre comme vous le faites ponctuellement !.. Le problème surgit quand une opinion considérée arbitrairement raisonnable, prétend irraisonnablement, sans la moindre preuve, d’être imposée à tout le monde !
Et c’est, en fait, ce que vous faites….
NB Dans le cas où je n’ai pas été assez clair, je reformule mon commentaire en disant que c’est à celui qui prétend l’existence des fantasmes, par exemple, d’en faire la démonstration rationnelle, et non à la science de prouver leur inexistence ! Vous saisissez la nuance ?
A ce jour personne n’a pu faire une démonstration rationnelle de l’existence ou véracité des croyances citées dans mon commentaire. PERSONNE ! Sauf -bien entendu-des pseudoscientifiques ou charlatans de tout horizon..... :non:
Prenez-en bonne note et évitez, dans la mesure du possible, et dans l’intérêt de tout le monde de diffuser des fausses symétries, ou visions phantasmatiques qui vous sont propres !.... Merci :bisou:

Victor
Messages : 17133
Inscription : 05/06/2006 - 21:30:44
Activité : Retraité
Contact :

Re: [News] Le bavardage comme problème de planification

Message par Victor » 08/09/2016 - 18:48:22

C'est mon vécu, vous croyez ce que vous voulez je m'en fous,
je vous sais carré, et super cartésien mais les réalités du psychisme vous échappe,
je me tais vous avez une croyance respectable et moi je sais tout mon vécu,
Malgré vous et les psy le phénomène, il existe et il n'est pas expliqué
Le phénomène qui me concerne n'est pas une opinion mais un vécu
Vous foutez dans la poubelle du scepticisme tous les phénomènes que vous ne comprenez pas
ça n'a rien de fantasmatique je vous dis, ça vous arrangerait ! Ben non et j'aimerais bien
En ce qui concerne la recherche en sciences, Je dirais : Cherche encore !

Avatar de l’utilisateur
cisou9
Messages : 10085
Inscription : 12/03/2006 - 15:43:01
Activité : Retraité
Localisation : Pertuis en Lubéron
Contact :

Re: [News] Le bavardage comme problème de planification

Message par cisou9 » 09/09/2016 - 9:28:43

___ :_salut:
Ben voyons !
Dans le système décimal.
_ 2 + 2 = 4
_ 2 x 2 = 4
C'est de la numérologie ? Non c'est de l'arithmétique..... :lol: ______ :lol2: _____
https://fr.wikipedia.org/wiki/Num%C3%A9rologie
Un homme est heureux tant qu'il décide de l'être et nul ne peux l'en empêcher.
Alexandre Soljenitsyne.

Répondre