Noé Pion : Diffusion d'information sur un graphe

De Ensiwiki
Aller à : navigation, rechercher

Objectif du travail

Ce travail s'inscrit dans une collaboration entre Corinne Touati, chercheuse à l'INRIA, et Yann Blanchi, architecte et doctorante en architecture. Le but du projet est de construire une structure qui s'inscrit dans le courant de l'architecture adaptative, c'est à dire l'architecture qui s'adapte à son environnement. Ici, la structure en question sera une grille de structures gonflables, contrôlées par des arduinos. Ces structures pourront être touchées par des acteurs extérieurs dont les actions modifieront la structure. Concrètement, c'est un capteur de pression dans chacun des ballons gonflables qui composent la structure qui permettra de mesurer ces interactions.

Le but de notre travail a été de développer un simulateur de cette structure. Nous nous sommes ensuite intéressé au comportement de cette structure selon deux règles d'évolutions : le maximum et la moyenne des voisins. En particulier, une interprétation probabiliste est donnée à une implémentation de la moyenne.

Grid reel.jpg

Simulateur

Le simulateur a été réalisé en Scala, et à l'aide de Processing pour gérer le "Front-End". Scala est un langage fonctionnel et orienté objet qui est compilé en bytecode, interprétable par la JVM. Il bénéficie d'une forte inférence syntaxique qui permet d'écrire du code plus court que Java, C++ ... L'aspect fonctionnel permet aussi d'écrire un code assez "mathématique", en dépit de facilités de lecture pour un non-initié.

Nous avons, dans un premier temps, développé les grilles et les cellules en Scala pur, avec la possibilité de faire évoluer le système. Il est aussi possible d'obtenir des fichiers svg représentant l'évolution, pour potentiellement en faire des gifs après avec un outil externe, comme par exemple le gif suivant.

Exemple gif.gif


Finalement, Processing, qui est un framework développé pour Java, permet l'affichage et l'interaction avec notre structure. Plus précisément, Processing gère les évènements de clique de souris, sur lesquels nous rattrapons les coordonnées et en inférons les cellules cliquées.

Exemple processing.png

Transition entre les états

Chaque cellule possède, à chaque instant donné, un état $e$ représenté par un réel entre 0 et 1. Cet état est représenté en niveau de gris dans notre simulateur (0 = blanc, 1 = noir), mais correspond à un niveau de gonflement dans la réalisation finale. Une mise à jour est lancée à un pas de temps défini et modifiable dans le code. La mise à jour des états des cellules est dictée par un des deux règles suivantes, que nous étudions plus en détail dans le rapport.

Premièrement, on définit la notion de voisinage d'une cellule : c'est l'ensemble des cellules qui partagent une arrête commune avec lui. Cela donne donc, dans le cas où la grille est composée de grilles carrées, 4 voisins, sauf pour les bords, et pour un hexagone, 6 voisins sauf sur les bords. La cellule elle même n'est pas comprise dans son propre voisinage. Le cas des bords se relevant problématique pour une interprétation probabiliste du problème. Les deux règles de mise à jour étudiées sont les suivantes : - le maximum : à chaque pas, l'état d'une cellule est le maximum de ceux de ses voisins au pas précédent. - la moyenne : à chaque pas, l'état d'une cellule est la moyenne de ceux de ses voisins au pas précédent.


Résultats des simulations

Comme illustré dans les 2 gifs suivants, la grille carrée exhibe un comportement de "clignotement" alors que pour les hexagones, tout semble se passer comme prévu sauf à la première itération où la cellule "saute". Le clignotement est très problématique pour le problème final car il entraîne 2 problèmes. Déjà, si il y a clignotement, notre système ne converge sûrement jamais (c'est ce que nous montrerons plus tard), ce qui provoque une usure des pièces. En plus, les changements brusques d'états sont, en pratique, difficilement réalisables car les gonfleurs n'arrivent pas à gonfler assez vite les ballons. Cette raison nous force d'ailleurs à ne pas retenir le maximum comme règle implémentée, nous l'étudierons cependant car elle est assez simple et permet de se fixer les idées pour la moyenne.

Etude théorique

Nous modélisons notre problème comme un graphe où les sommets sont les cellules, et une arrête entre 2 sommets représente le fait qu'ils soient voisins.

Explications du problème des carrés

La clé pour comprendre le problème des carrés est de remarquer que le graphe est biparti. Ainsi, si on sépare nos sommets en deux ensembles B et N , alors on se rend compte que les états des sommets de B à t+1 ne dépendent que de ceux de E_a à t, et réciproquement. En particulier, comme on l'établit dans le rapport, pour une mise à jour effectuée avec le maximum, le maximum sur les sommets de B à t+1 est celui des sommets de N à t et réciproquement. Ce critère alterné possède aussi une telle règle, moins forte, pour la mise à jour, qui est établie dans le rapport.

Interprétation probabiliste de la règle de la moyenne

La règle de la moyenne est, en cette forme, presque une règle de Markov. En fait, on peut établir une matrice de passage A, indépendante de t, telle que si on note \epsilon_{t} le vecteur contenant les états de notre système au temps t, on a pour tout t, \epsilon_{t+1} = \epsilon_t A . La matrice A correspond à la matrice d'adjacence où chaque colonne est divisée par le nombre d'éléments non nuls de la colonne. Cette matrice devient stochastique si on impose que chaque sommet ait le même nombre de voisins, en reliant les extrémités par exemple. On a donc une matrice A de diagonale nulle, symétrique et dont tous les coefficients non nuls sont égaux.

En fait, on peut alors modéliser cette situation comme une situation où, à un état initial, on ait une certaine distribution de probabilité. En effet, si notre matrice de passage est stochastique, il y a conservation de la somme des états. Si elle est égale à 1, on peut l'interpréter comme une probabilité, par exemple de présence de particule. La règle de mise à jour s'interprète alors comme un choix d'une nouvelle position parmi les voisins avec équiprobabilité.

Alors, cette interprétation permet de mieux comprendre le "clignotement". Si une particule est sur une cellule de l'ensemble N initialement, alors elle sera sur une cellule de B à l'état suivant etc.

Pour ce qui est de la convergence, comme la matrice de passage pour les hexagones est apériodique, irréductible et récurrente positive, alors la chaîne de Markov converge vers un unique état stationnaire, sur lequel on montre qu'il est l'état où les états des cellules sont à 1/n où n est le nombre de sommets de notre graphe (c'est à dire le nombre de ballons gonflables). Il est particulièrement intéressant de remarquer que cet état correspond avec un maximum d'entropie, donc à une information minimale sur le système. Cela peut se résumer par : après un très long temps, nous n'avons aucune idée d'où est la particule.

Enfin, un dernier résultat d'importance concernant les matrices stochastiques est que si un des éléments de la diagonale est non nulle, alors la seule valeur propre de A de module 1 est 1, ce qui veut dire que notre matrice a bien un état stationnaire (cf. bibliographie). Nous utilisons ce résultat pour résoudre le problème posé par la moyenne sur une grille composée de carrés. En effet, si on passe de \epsilon_i^{t+1} = avg(voisin(i)) à \epsilon_i^{t+1} = e.avg(voisin(i)) + (1-e)\epsilon_i^{t+1} avec e dans ]0,1[, alors la nouvelle matrice de passage  = e*A + (1-e)*I_n reste stochastique. Elle est cependant maintenant de diagonale non nulle, donc la chaîne de Markov associée possède un état stationnaire, ce qui entraîne qu'on a éliminé les "clignotements" (cf. gif ci-dessous).

Non clignotement.gif


Conclusion

Dans ce travail de recherche, nous avons donc construit un simulateur, observé des comportements qui se révéleraient problématiques si ils étaient réalisés sur le projet réel, et cherché une explication ainsi qu'une solution. Une explication probabiliste a aussi été donnée pour donner un contexte à la formule de la mise à jour par moyenne.

De nombreuses autres formules de mise à jour peuvent être expérimentées, comme par exemple implémenter un jeu de la vie de Conway, ou chercher à modéliser des comportements de la théorie des jeux.

Bibliographie

Francinou-Gianella-Nicolas,Oraux X-ENS Algèbre 2, page 75, Cassini

J.Y. Ouvrard, Probabilités 2, Cassini

Rapport