COMMENT FAIRE COMMUNIQUER DES MACHINES AUTONOMES AVEC EFFICACITÉ ? DES CHERCHEURS ONT TROUVÉ LA SOLUTION

COMMENT FAIRE COMMUNIQUER DES MACHINES AUTONOMES AVEC EFFICACITÉ ? DES CHERCHEURS ONT TROUVÉ LA SOLUTION
© Delwin Steven Campbell

Les problèmes posés par la communication entre machines autonomes – des bases de données, des voitures sans chauffeur – sont un casse-tête… que des chercheurs ont réussi à résoudre.

Devinette : on est plusieurs amis à vouloir partir en vacances ensemble, et depuis longtemps on s’est mis d’accord sur deux dates possibles : soit le 13 juillet soit le 15 juillet. Question : combien de coups de fil au minimum doit-on se passer dans le groupe pour que tous connaissent les préférences de chacun ? La question semble dérisoire car avec les applications numériques actuelles – comme WhatsApp, Skype et autres – il suffit de créer un groupe de diffusion ou une discussion simultanée pour se mettre tous d’accord comme si l’on était dans la même pièce.

Pourtant, la réponse à ce type de question de partage des connaissances, dit problème du bavardage, est essentielle dans la gestion des informations entre « agents autonomes », par exemple entre bases de données indépendantes ou entre de futures voitures autonomes qui doivent entrer en communication à l’approche d’un carrefour (sans feux de signalisation), pour gérer au mieux leur priorité de passage sans créer de ralentissements.

Or la réponse est un casse-tête logique qui n’a rien d’évident… Du moins jusqu’aux travaux d’une équipe de chercheurs français dont les résultats ont été publiés à l’occasion de la 22e European Conference on Artificial Intelligence (du 29 août au 2 septembre dernier).

Le bavardage à quatre

Commençons par l’exemple. On est quatre amis, A, B, C et- D et l’on veut savoir quelle est la préférence de chacun (entre les options du 13 ou du 15 juillet). La solution la plus économique est la suivante : A appelle B pendant que C appelle D. Puis A appelle C pendant que B appelle D – ou alors, ce qui revient au même en nombre d’appels, A appelle C, puis C appelle à nouveau D pour lui dire la préférence de A. Il y a d’autres variantes, mais toutes donnent le même résultat : quatre appels est le nombre minimal pour que tous partagent l’information sur les préférences…

De manière générale, il a été démontré dans les années 1970 que pour N amis (ou « agents »), le partage des connaissances ne peut s’obtenir qu’avec un minimum de 2 x (N – 2) communications : si on est 5, cela donne 2 x (5 – 2) = 6 appels, etc. Néanmoins, cela ne fonctionne que si les N agents se sont mis d’accord à l’avance sur le schéma ou la succession des appels.

Comment je sais qu’il sait ?

En effet, dans le cas des quatre amis, avec quatre coups de fil A, B, C ou D connait les préférences des autres mais tous ne savent pas si les autres membres du groupe connaissent la sienne. Concrètement, dans le cas précédent, A ne peut pas savoir si D est au courant de sa préférence (et réciproquement), de même entre C et B, car ils ne se sont pas appelé. Reprenez à tête reposée, et vous verrez que c’est vrai…

Combien d’appels supplémentaires faudrait-il passer pour que cette lacune soit comblée, à savoir : que chaque membre du groupe connaisse les préférences des autres et qu’il soit sûr que tous les autres connaissent la sienne ? Dans ce cas concret, il faudrait deux appels supplémentaires, par exemple, entre A et D et entre B et C… On nomme cela une connaissance partagée d’ordre 2.

Comment je sais qu’il sait que je sais… ?

Mais voilà, avec ces 6 appels, je (A) sais maintenant que B, C et D connaissent bien ma préférence et je connais la leur (de même pour chacun des autres membres)… mais comment je peux être sûr que B sait que les deux autres sont au courant de sa préférence à lui ? Il faudrait alors que je passe un coup de fil à B pour lui demander : « Sais-tu si C et D sont au courant de ton choix ? »

Cette connaissance que j’ai (A) de la connaissance de l’autre (B) sur la connaissance des autres (C et D) concernant sa préférence (de B) est une connaissance partagée d’ordre 3. Combien d’appels supplémentaires de tous les membres du groupe pour que tous partagent ce 3e niveau de connaissance ?

Un casse-tête qui touche au Réseau

Et que dire de la question : est-ce que chacun des autres (B, C et D) sait que je (A) sais que chacun des autres sait la préférence des autres ? C’est un casse-tête « woody-allenesque »… d’ordre logique qui a une grande implication, par exemple quand des bases de données disséminées sur la Toile doivent partager des connaissances et certifier que celles-ci ont bien et totalement été partagées par les autres. Sauf à avoir un algorithme général gérant toutes les bases de données de la planète (ce qui est illusoire), il n’y a pas d’autre moyen que de communiquer ainsi deux à deux.

Et le défi se joue sur deux axes : d’une part réduire au minimum le nombre de communications entre serveurs – au risque de saturer le réseau (tout le monde appelle tout le monde plusieurs fois) – , d’autre part s’assurer qu’il n’y a pas de lacune dans le partage des informations (ce qui dans le cas de la lutte contre le terrorisme, par exemple, peut être dramatique).

La solution des Français

Les chercheurs français ont alors démontré la formule suivante : entre N agents autonomes, pour atteindre un degré de connaissance k (1, 2, 3…), le nombre minimal de communications est donné par la formule : (k+1) x (N-2). Une formule qui sera prise en compte dans la mise au point des protocoles de communication entre agents, en adaptant le degré d’exigence du partage des connaissances (la valeur de k) suivant le domaine concerné.

 

Roman Ikonicoff

Source: science&vie.com

Lamia Siffaoui
ADMINISTRATOR
PROFILE

Voir aussi

Laisser un commentaire

Votre adresse électronique ne sera pas publiée. Les champs Exigés sont marqués avec *

Cancel reply