Automates de sable
Automates de sable
1. Introduction
Les automates de sable sont un système dynamique récent, introduit par Julien Cervelle et Enrico Formenti dans [4] en 2003, permettant notamment d'unifier tous les modèles de piles de sable connus (en particulier SPM [1, 2] et IPM(k) [3]). Ce modèle est relativement proche des automates cellulaires dans sa définition, au sens qu'il agit en parallèle sur plusieurs points, en fonction de données locales (la pente par exemple pour les tas de sable). Cependant un grand nombre de propriétés [5, 6, 8] montrent que ces modèles ne sont finalement pas si proches que cela, bien qu'ils puissent se simuler l'un et l'autre.
Ce site rassemblera les définitions nécessaires à la compréhension de ce modèle, quelques exemples simples d'utilisation de ces automates, avec un simulateur de ces exemples.
2. Définitions
Dans cette partie nous ferons un rappel rapide des notions de base à connaître, notamment ce qu'est une configuration, puis comment fonctionne un automate de sable. La plupart des définitions et résultats présentés ici sont tirés de [4] et [7], on pourra s'y reporter pour plus de détails.
2.1 Configurations
Une configuration représente un "état" sur lequel l'automate va travailler. C'est une grille de dimension d dans laquelle chaque case contient une colonne de grains, chaque colonne étant caractérisée par un entier indiquant le nombre de grains. On pourra également avoir les valeurs +∞ ou -∞ pour représenter une source ou un puits de grains.
Par exemple, en dimension 1, une configuration sera représentée par une droite sur laquelle en tout point de coordonnée entière il y aura un entier correspondant à une colonne :
Une configuration en dimension 1.
On dira qu'une configuration x est finie si elle a un nombre fini de colonnes non nulles, et (spatialement) périodique s'il existe d vecteurs p1, ..., pd tels que pour toute colonne d'indice i et pour tout entier 1 ≤ k ≤ d on ait xi = xi+pk.
On peut alors définir une topologie sur l'espace des configurations C, en introduisant une distance. Une première distance a été définie dans [4], puis raffinée dans [7]. Comme cette dernière permet d'obtenir une topologie compacte, c'est elle que nous définirons ici. On dira que 2 configurations x et y sont à distance 2-l, où l est le plus petit entier qui permet de différencier x et y. lreprésente en fait la taille de la plus petite boîte rectangulaire posée sur le sol, au niveau de la colonne centrale de chaque configuration, pour laquelle les observations à l'intérieur de la boîte diffèrent :
Calcul de la distance en dimension 1.
Ici, on a d(x,y) = 2-3 = 1/8. La topologie ainsi définie a pour ouverts de base les ensembles de configurations ayant des valeurs centrales "presque" identiques (à l près). L'espace des configurations muni de cette topologie a des propriétés importantes, rappelées ci-dessous.
Proposition 1 [7]. L'espace des configurations C est compact et donc complet.
2.2 Automates de sable
Un automate de sable est un système qui va transformer une configuration en une autre. Pour cela, l'automate va considérer simultanément chaque élément de la configuration, et y appliquer une modification déterminée par une règle locale f. f est une fonction prenant en argument un voisinage de l'élément considéré, qui renvoie la variation de la valeur en ce point.
La taille du voisinage ainsi que la borne de la variation sont déterminés par le rayon r de l'automate. Un automate de sable sera donc entièrement caractérisé par le triplet ‹d, r, f›. Par exemple sur la figure suivante, avec un rayon 2, f sera appelé pour le point en rouge avec les valeurs (-∞, 0, 1, 2). Il suffit alors d'aller chercher la valeur correspondant à cet appel pour trouver la variation de la colonne considérée.
Exemple d'appel de la règle locale f.
On peut alors à partir de la règle locale définir une règle globale F, qui représentera le fonctionnement de l'automate. F est définie par
| F(x)i | = xi + f(R(x,i,r)) | si |xi| ≠ ∞ , |
| = xi | sinon. |
On note ici R(x,i,r) le voisinage de xi de taille r. Pour finir, on dit qu'une fonction est invariante horizontalement (resp. verticalement) si elle commute avec les décalages horizontaux σk, 1 ≤ k ≤ d(resp. avec le décalage vertical ρ) définis par pour tout 1 ≤ k ≤ d, σk(x)i = x(i1, ..., ik+1, ... id) (resp. ρ(x)i = xi+1). Une fonction conserve les infinis si une colonne infinie reste infinie (et de même signe), et si une colonne finie reste finie. Il est maintenant possible de donner une caractérisation des automates de sable à l'aide de la fonction globale.
Théorème 2 [4, 7]. Une fonction F : C → C est la fonction globale d'un automate de sable si et seulement si
(i) F est continue ;
(ii) F est invariante horizontalement ;
(iii) F est invariante verticalement ;
(iv) F conserve les infinis.
Remarque [4, 6]. On peut simuler n'importe quel automate cellulaire avec un automate de sable, c'est donc un modèle universel.
3. Exemples d'automates
Nous allons maintenant citer certains exemples d'automates parmi les plus classiques. Il peut être plus facile de comprendre leur comportement à l'aide du simulateur.
3.1 Wave
Ce premier automate est très simple, mais également très intéressant. C'est un automate de dimension 1, de rayon 1, qui va regarder uniquement à gauche et aller dans la direction de son voisin de gauche.
| f(a, −) | = +1 | si a > 0 , |
| = -1 | si a < 0 , | |
| = 0 | sinon. |
3.2 SPM
Toujours en dimension 1, rayon 1, un des automates les plus utiles est celui qui simule SPM. On s'intéresse maintenant aux 2 voisins :
| f(a, b) | = +1 | si a = +∞ et b ≠ -∞ , |
| = -1 | si a ≠ +∞ et b = -∞ , | |
| = 0 | sinon. |
Avec cette définition, un grain tombe sur la colonne de droite dès que la différence de hauteur entre les 2 colonnes atteint ou dépasse 2 : on dira qu'il y a une falaise. De plus, la chute se propage lorsqu'il y a plusieurs falaises successives. Seule la première colonne perd un grain, et seule la dernière en gagne un.
Simulation de SPM.
3.3 Dunes 1
Cet automate modélise la formation et le déplacement de dunes, en simulant du vent de gauche à droite. C'est un automate de rayon 2 défini par les règles suivantes.
| f(−, a, b, −) | = +1 | si a ≥ 2 et b > -2 , |
| f(−, a, b, −) | = -1 | si a < 2 et b ≤ -2 , |
| f(a, 0, b, −) | = +1 | si a < 0 et b > -2 , |
| f(a, 1, b, −) | = +1 | si a ≤ 0 et b > -2 , |
| f(−, a, 0, −) | = -1 | si a < 0 , |
| f(−, a, -1, −) | = -1 | si a < 0 , |
| f(−, −, −, −) | = 0 | sinon. |
On retrouve la règle usuelle de SPM (2 premières lignes, et sur la figure, règle (a)). Mais on a aussi 2 règles moins classiques, qui déplacent les grains en fonction du "vent" : un grain se déplace lorsque la colonne de gauche est suffisamment basse pour ne pas bloquer le vent, et que celle de droite n'est pas trop haute (figures (b) et (c)).
Simulation de Dunes 1.
3.4 Dunes 2
Cet automate est une variante de Dunes 1, les règles ne sont que légèrement modifiées :
| f(−, a, b, −) | = +1 | si a ≥ 3 et b > -3 , |
| f(−, a, b, −) | = -1 | si a < 3 et b ≤ -3 , |
| f(a, 0, b, −) | = +1 | si a < 0 et b > -3 , |
| f(a, 1, b, −) | = +1 | si a ≤ 0 et b > -3 , |
| f(a, 2, b, −) | = +1 | si a ≤ 0 et b > -3 , |
| f(−, a, 0, −) | = -1 | si a < 0 , |
| f(−, a, -1, −) | = -1 | si a < 0 , |
| f(−, a, -2, −) | = -1 | si a < 0 , |
| f(−, −, −, −) | = 0 | sinon. |
Cela consiste à ne provoquer la chute des grains par SPM que lorsque la différence vaut 3 ou plus (règle (a) sur la figure précédente, représentant le comportement de Dunes1). On obtient alors des dunes plus réalistes, toujours relativement plates du côté venté, mais plus inclinées sur le versant opposé. La figure suivante permet de comparer les 2 phénomènes. Dans les deux cas on effectue 50 itérations de l'automate, à partir d'une seule colonne de hauteur 20. On voit clairement que l'automate Dunes2 crée des dunes beaucoup moins symétriques.
Simulations de dunes − comparatif.
Résultats obtenus à partir d'une seule colonne de hauteur 20, au bout de 50 itérations.
4. Simulateur
Le simulateur ci-dessous a été écrit par Julien Cervelle. Il permet d'étudier le comportement des automates les plus utilisés (la plupart vus dans les exemples) sur des configurations périodiques en dimension 1.
Note : ce simulateur est une applet java, si elle ne fonctionne pas c'est que vous n'avez probablement pas la bonne version du plugin. Elle nécessite le plugin java version 1.6 ou supérieure.
En cas de problème, vous pouvez consulter la page d'aide.
Bibliographie
| [1] | P. Bak, C. Tang et K. Wiesenfeld : Self-organized criticality. Physical Review A, 38(1):364−374, 1988. |
| [2] | E. Goles et M. A. Kiwi : Games on line graphs and sand piles. Theoretical Computer Science, 115(2):321−349, 1993. |
| [3] | E. Goles, M. Morvan et H. D. Phan : Sand piles and order structure of integer partitions. Discrete Applied Mathematics, 117:51−64, 2002. |
| [4] | J. Cervelle et E. Formenti : On sand automata. Dans STACS 2003, volume 2607 de Lecture Notes in Computer Science, pages 642−653, Springer-Verlag, 2003. |
| [5] | J. Cervelle, E. Formenti et B. Masson : Basic properties for sand automata. Dans MFCS 2005, volume 3618 de Lecture Notes in Computer Science, pages 192−211, Springer-Verlag, 2005. |
| [6] | J. Cervelle, E. Formenti et B. Masson : From sandpiles to sand automata. Theoretical Computer Science, 381:1−28, 2007. |
| [7] | A. Dennunzio, P. Guillon et B. Masson : Topological properties of sand automata as cellular automata. Dans JAC 2008, 2008. À paraître. |
| [8] | A. Dennunzio, P. Guillon et B. Masson : Stable dynamics of sand automata. Dans TCS 2008, 2008. À paraître. |