Mosaïque avec des automates cellulaires coexistants

par Phileas Dazeley-Gaist
Article original

Introduction

Lors de l’école d’été de Wolfram en 2025, alors que je donnais des conseils sur un projet concernant la prise de décision collaborative à l’aide d’automates cellulaires (AC), j’ai passé un certain temps à réfléchir à différentes configurations possibles permettant aux règles des AC d’interagir entre elles et d’effectuer des « négociations ». Nous avons envisagé plusieurs configurations, notamment l’utilisation de cellules d’état pour les AC afin de représenter une répartition des opinions au sein d’une société, et nous avons essayé divers schémas dans le but de faire évoluer des règles qui produiraient de manière fiable des états de « consensus ».
Une approche que je n’ai pas eu le temps d’explorer en profondeur, mais qui s’est révélée prometteuse, consistait à représenter les agents comme des règles confinées à des régions spécifiques et strictement distinctes dans l’espace, tout en étant capables d’interagir entre elles là où leurs limites se touchent ou sont proches les unes des autres. Des configurations de ce type feront l’objet de ce court essai.
Voici un aperçu de ce vers quoi nous travaillons : des programmes qui opèrent sur des tableaux d’état d’automate cellulaire en appliquant une liste de règles d’automates cellulaires à une liste de régions non chevauchantes de l’état, de sorte que chaque région définie est soumise à sa propre dynamique, déterminée à la fois par la règle attribuée à la région et par la dynamique près de la limite de la région.
In[]:=
With​​(*Defineparams:*)​​{simDuration=100,​​rules=({#1,{2,1},{1,1}}&)/@{806,552,857},​​init=SparseArray[ConstantArray[0,{101,101}]],​​domainMasks=ArrayPad[DiskMatrix[20],30]+ArrayPad[DiskMatrix[30],20]+ArrayPad[DiskMatrix[40],10],​​cf=ColorData[10]},​​​​(*Preparethebackgroundandlegend:*)​​{background=Colorize[domainMasks,ColorRules->Prepend[Thread[#->cf/@#]&@Range[Length[rules]],0->LightGray](*ColorFunction->(cf[1+Length[rules]*#]&)*)],​​legend=SwatchLegend[cf/@Range[Length[rules]],rules]},​​​​(*Computetrajectory:*)​​traj=CoexistingCellularAutomata​​ (*Listofrules:*)rules,​​ (*Domainmasks:*)domainMasks,​​ (*Initialstate:*)init,​​ (*Numberofsteps:*)simDuration,​​ "GlobalMaskFunction"->(ArrayPad[DiskMatrix[40],10]&),​​ "GlobalMaskValueFunction"->(0&)​​,​​​​(*Animatetrajectoryframes:*)​​ListAnimate[Map[​​Labeled[Image[​​ImageCompose[​​background,​​{RemoveBackground[Image[1-#],White],.5}],​​ImageSize->Medium],​​legend,Right]&,traj]]​​
Out[]=

Automates cellulaires avec des conditions aux limites personnalisées

Nous progresserons jusqu’à des AC fonctionnant en parallèle sur des régions de l’espace qui ne se chevauchent pas. Mais d’abord, il sera utile de revoir certaines des bases.

AC unidimensionnels

Conditions aux limites des AC, prises en charge nativement

Dans Wolfram Language, les automates cellulaires ont par défaut des conditions aux limites périodiques.
Trajectoire d’automate cellulaire élémentaire avec conditions aux limites périodiques :
In[]:=
ArrayPlot[CellularAutomaton[28,ArrayPad[{1},50],100],ImageSize->Small]
Out[]=
Remarquez la cascade d’ondulations qui enveloppe l’espace horizontal lorsqu’elle sort par la droite et entre simultanément par la gauche.
Une autre prise en charge des conditions aux limites périodiques de manière native dans la fonction CellularAutomaton consiste à faire fonctionner des AC sur une toile infinie.
Trajectoire d’un automate cellulaire élémentaire sur une toile infinie :
In[]:=
ArrayPlot[CellularAutomaton[28,{{1},0},100],ImageSize->Small]
Out[]=
Ici, la largeur du tableau d’états n’est pas fixe. Dans ce cas, la cascade d’ondulations se propage simplement vers l’extérieur à l’infini, sans interruption.
Le système que nous envisageons exige que nous implémentions des conditions aux limites personnalisées, pour lesquelles il n’existe, à ma connaissance, aucune prise en charge intégrée pour le moment. Alors, comment pouvons-nous y parvenir ?

Confinement des AC à des régions de l’espace

Pour confiner une règle à une région spatiale au sein de l’état d’un AC, l’approche générale la plus simple à laquelle je puisse penser consiste à appliquer la règle à l’état complet, mais à rejeter toutes les modifications de l’état en dehors de la région attribuée à la règle au moyen d’un masque de région. Par exemple :

Suppression de la périodicité spatiale

AC bidimensionnels

◼
  • La région verte représente le domaine spatial de la règle de l’automate.
    • ◼
  • La limite est poreuse, de sorte que l’activité à proximité, à l’extérieur de la région verte, peut affecter la dynamique de la région verte.
    • ◼
  • Les conditions aux limites pour l’ensemble de l’espace de simulation sont toujours périodiques par défaut, mais peuvent être fixes ou contrôlées à l’aide des techniques de masquage que j’ai décrites pour les AC en 1D.
    • 4
    /
    4
    Cellular automaton dynamics with an isolated central region and a surrounding region subject to periodic boundary conditions.

    Trois dimensions et au-delà

    Bonus : divers exemples intéressants

    Mazes

    Autres formes complexes

    Révision

    ◼
  • Pour confiner une règle d’AC à une région spatiale spécifique, nous pouvons appliquer la règle à l’état complet, mais ignorer toutes les modifications en dehors de la région atribuée à la règle à l’aide d’un masque de région.
    • ◼
  • Pour supprimer les conditions aux limites périodiques de l’espace lui-même, nous pouvons compléter l’état initial avec suffisamment de zéros dans toutes les directions afin d’empêcher toute interaction périodique aux bords, calculer l’étape suivante et rogner le tableau obtenu pour revenir aux dimensions d’origine. Cela simule effectivement des conditions aux limites nulles constantes.
    • ◼
  • Nous pouvons également rendre les conditions aux limites de l’espace de simulation dynamiques et hétérogènes, par exemple en définissant un masque de limite global qui encadre la fenêtre de simulation, et en fixant les cellules situées à l’intérieur de la limite qu’il définit à des états aléatoires à chaque étape de la simulation. Tout AC dont le domaine spatial est suffisamment proche du masque de limite global verra sa dynamique affectée par les conditions aux limites globales aléatoires.
    • ◼
  • Ces techniques peuvent être appliquées aux AC en 1D et 2D, mais aussi aux AC dans des espaces de dimensions supérieures.

    • How does it work?

    1
    .
    Définir une liste de règles d’AC et un état initial pour l’ensemble de l’espace de simulation.
    2
    .
    Créer un tableau qui spécifie le domaine spatial pour chaque règle d’AC, où chaque cellule du tableau correspond à l’indice de la règle qui doit être appliquée dans cette région.
    3
    .
    Générer des masques binaires à partir du tableau des domaines spatiaux afin d’isoler les régions où chaque règle doit être appliquée.
    4
    .
    Définir les conditions aux limites pour l’espace de simulation global, qui peuvent être constantes ou dynamiques.
    5
    .
    Appliquer les règles d’AC à leurs domaines respectifs, tronquer les résultats selon les masques de domaine, faire la somme des tableaux d’état obtenus et appliquer les conditions aux limites globales.

    Calculez une seule étape d’une simulation d’AC coexistants

    Exécution d’une simulation complète d’AC coexistants

    Je définirai des conditions initiales constantes nulles sur l’ensemble de l’état initial.
    Preview the domain masks:

    Utilisation d’images en tant que masques de domaine d’AC coexistants

    et
    and
    et

    Code d’initialisation

    Implémentation : CoexistingCellularAutomata

    Examples with default global BCs (toroidal space)

    Exemples avec des CB globaux par défaut (espace toroïdal)

    Examples with custom global static BCs

    Exemples avec des CB statiques globaux personnalisés

    Exemples avec des CB dynamiques globaux personnalisés

    Implémentation : ruleSpaceSize

    Implémentation : generateVoronoiCASpatialDomains

    Exemples

    CITER CE NOTEBOOK