Projects & Achievements

Simulation de systèmes électroniques grâce aux automates cellulaires

Presenting » Videos » Pictures

Télécharger la présentation PDF (Beamer/LaTex)   

Un automate cellulaire est un algorithme évoluant généralement sur une grille à maillage carré bien qu'il arrive de travailler avec des grilles hexagonales. Chaque case est appelée cellule et chaque cellule peut adopter différents états suivant des règles simples. L'état de toutes les cellules dépend uniquement des règles de transition et de l'état de ces cellules aux dates antérieures. L'état d'une cellule particulière dépend uniquement de l'état de ses cellules voisines à  la date précédente. À noter qu'il existe plusieurs types de voisinage, comme le voisinage de Moore (8 voisins) ou le voisinage de Von Neumann (4 voisins).

Bien que les règles de transitions des automates cellulaires soient simples, ils permettent de modéliser un grand nombre de phénomènes physiques, biologiques voir sociaux, complexes tels que les feux de forêts, les épidémies, les avalanches, les déplacements de fluides ou encore les mouvements tectoniques.

Les automates cellulaires permettent donc de décrire des phénomènes mathématiquement prédictibles de façon relativement simple.

La simulation du mouvement des électrons dans un circuit électronique constitue une branche à part entière du domaine des automates cellulaires appelée WireWorld. J'ai choisi de réaliser un automate cellulaire capable de simuler un circuit électronique complexe.

Il m'a semblé difficile de réaliser ex nihilo un automate cellulaire de type WireWorld. J'ai donc choisi de commencer par programmer des automates cellulaires simples tels que la croissance d'une structure fractale ou le Jeu de la Vie de John Conway. Ces automates sont dits « automates totalistiques » c'est-à-dire que l'évolution d'une cellule ne dépend que de la somme de ses voisines actives. La simplicité des algorithmes m'a permis de me concentrer sur la programmation du cadre d'évolution des grilles sans me soucier des règles de transition.

J'ai hésité sur le choix du langage de programmation pour ce projet. D'abord attiré par Python et sa syntaxe minimale faisant de lui un langage rapide dans l'écriture, j'ai finalement décidé d'utiliser le langage C. En effet, le langage Python est un langage interprété ce qui le rend extrêmement lent dans le calcul des images. À l'inverse, le langage C, langage compilé, est extrêmement rapide et permet d'obtenir des simulations en un temps minimal. La bibliothèque OpenCV fournie par la société Intel permet de travailler rapidement sur des matrices, des images, ce qui en fait un outil de choix pour l'aspect graphique de l'automate cellulaire.

Programme 1 - Croissance d'une structure fractale

Le premier programme développe une figure à partir d'un point, « façon fractale ».
On définit un réseau à deux dimensions en ne s'intéressant qu'aux premiers et seconds voisins de chaque cellule (environnement de Moore). Chaque cellule a deux états : 0 ou 1. La règle d'évolution est définie ainsi : une cellule dont l'état est 0 passe à 1 si, et seulement si, une seule de ses voisines est également à l'état 1. Sinon, la cellule reste à l'état 0. À l'état initial, une seule cellule de la grille est à l'état 1. Ainsi, on obtient :

Le programme parcourt la grille (un tableau d'entiers à deux dimensions) à  la recherche d'une cellule à l'état 0 dont une seule de ses voisines serait à l'état 1. Lorsque c'est le cas, il passe la cellule à l'état 1. Le programme ne modifie pas le tableau en cours de lecture mais une réplique de ce tableau. Ce n'est que lorsque la grille a entièrement été parcourue que le tableau original est remplacé par sa réplique modifiée. C'est la technique du double buffering notament utilisée dans le domaine de l'affichage vidéo pour le rendre plus fluide. Ici, cela permet de bien dissocier la lecture et l'écriture et d'éviter les erreurs.
Voici le résultat de l'algorithme aux étapes 88 et 122 dans une grille de 640 000 cellules (800 x 800) :

Programme 2 - Le jeu de la vie de John Conway

Le Jeu de la Vie est certainement l'automate cellulaire le plus célèbre. C'est le mathématicien John Conway qui, s'interessant aux travaux de John von Neumann (1940), met au point un algorithme décrivant une machine capable de s'auto-reproduire.

Voici les règles du Jeu de la Vie :

• Naissance : cellule '0' passe à '1' si exactement 3 voisins sont à '1' ;
• Survie : cellule '1' reste à '1' si 2 ou 3 voisins sont à '1' ;
• Mort : cellule '1' passe à '0' dans les autres cas.

Voici l'évolution d'une grille de 64 cellules à  partir d'un placement aléatoire de cellules vivantes et suivant les règles précédentes :

Au bout d'un certain nombre d'itérations - nombre plus ou moins grand suivant la taille de la grille - on arrive à  un ensemble de figure dites «stables». Les structures stables sont des ensembles de cellules qui n'évoluent plus. La plupart de ces structures sont connues. Parmi elles :

Il existe également des structures qui répètent le même motif à intervalles réguliers, les oscillateurs. Voici un oscillateur d'une période de deux itérations :

Enfin, les « planeurs » sont des oscillateurs qui se déplacent sur la grille. On trouve même certains motifs qui produisent des planeurs de façon cyclique.

La simulation d'un Jeu de la Vie sur une grille de 160 000 cellules dont les états sont initialement choisis au hasard permet de constater qu'au bout d'un certain nombre d'itérations les cellules évoluent jusqu'à  former plusieurs structures stables ou des oscillateurs. Voici une capture du programme à l'itération 1430 :

On observe encore quelques zones actives mais l'ensemble du système tend à l'immobilité.

Le graphe m'a permis de constater que ni le nombre de cellules actives à  l'initialisation, ni la taille de la grille n'avaient d'influence sur l'allure de la courbe de décroissance du nombre de cellule actives. Elle semble suivre une loi exponentielle et tend vers une asymptote horizontale proportionelle au nombre de cellules actives à  l'initialisation. J'en déduis que le nombre de cellules actives minimum à l'issue de la simulation est prédictible et envisage de le mettre en équation.

Programme 3 - Le WireWorld

Un WireWorld est un automate cellulaire inventé par Brian Silverman en 1984. Il permet de représenter le mouvement des électrons sur les pistes d'un circuit électronique. À la différence des automates présentés ci-dessus, le WireWorld n'est pas seulement totalistique : la variable décrivant une cellule n'est plus booléenne et elle dépend de l'état des voisines à la date précédente et non plus seulement de leur présence.

Une cellule a donc quatre états possibles : vide, cuivre, tête d'électron, queue d'électron. Elles évoluent comme suit :

• Une cellule vide reste toujours vide ;
• Une tête d'électron devient toujours une queue d'électron ;
• Une queue d'électron devient toujours une cellule « cuivre » ;
• Une cellule « cuivre » reste toujours une cellule cuivre sauf si une ou deux de ses voisines sont des têtes d'électron. Elle devient alors une tête d'électron au pas suivant.

Voici le WireWorld de deux diodes, l'une passante, l'autre bloquante :

Grâce à la représentation de composants, de portes logiques et d'horloges, le WireWorld peut simuler des systèmes complexes tels que des chronomètres, des réveils ou encore des calculatrices.

Cependant, le WireWorld est plus un outil pédagogique que scientifique. En effet, il existe un grand nombres d'algorithmes destinés à ce type de simulation, plus performants.

Le modèle d’automate cellulaire que présente le WireWorld peut être adapté dans un tout autre domaine : la résolution de labyrinthes. L’application des automates cellulaires au pathfinding serait une nouvelle méthode de résolution graphique de labyrinthes. On peut imaginer une cellule aux caractéristiques semblables à celle de « l'électron » du WireWorld mais en plus doté d'une mémoire. Elle se multiplierait à chaque fourche du labyrinthe et en emprunterait ainsi tous les couloirs. La première d'entre elle qui atteindrait la sortie du labyrinthe aurait forcément emprunté le chemin le plus court, temporellement parlant du moins, et il suffirait de lire sa mémoire pour obtenir la solution du labyrinthe la plus rapide.

Videos

Pictures