Sujet 2 : la coordination dans un automate cellulaire

Encadrant

Objectif

Dans un certain type d'automate cellulaire (maillage carré dans un hyper-tore du plan, voisinage de Moore, ou 8-voisinage - cf annexe), nous représentons différents mondes artificiels ; le TER consiste à définir l'ensemble des états cellulaires et la fonction de transition de l'automate afin de satisfaire les contraintes imposées sur chacun de ces mondes.

Développer un petit simulateur afin d'illustrer les choix effectués.

Monde des balles ponctuelles

Dans ce monde, chaque cellule de l'automate cellulaire définit au choix :

la présence d'un obstacle
la présence d'une balle se déplaçant
le vide

La configuration initiale de l'automate définit un paysage d'obstacles avec des balles prêtes à se déplacer.

La fonction de transition doit garantir que :

si une balle se déplace vers une cellule vide, elle s'y déplace effectivement
si une balle se déplace vers une cellule non vide (occupée soit par un obstacle, soit par une autre balle), elle change de direction (direction opposée)
un obstacle ne bouge pas
une cellule ne contient qu'une balle à la fois

Monde des balles étendues

Même monde que précédemment, excepté qu'une balle occupe plusieurs cellules adjacentes, par exemple (la balle occupe 5 cellules adjacentes) :


	o
o	o	o
	o

La fonction de transition doit garantir que la cohérence de la balle est conservée, i.e. elle est toujours composée du même nombre de cellules, et maintient globalement sa forme (donc, localement, la forme peut être différente).

Monde des balles dispersées

Même monde que précédemment, excepté qu'une balle peut occuper des cellules disjointes, par exemple (la balle occupe 16 cellules) :


o	o	o	o
o	o	o	o

o	o	o	o
o	o	o	o

La fonction de transition doit, là aussi, garantir que la cohérence de la balle est conservée, i.e. elle est toujours composée du même nombre de cellules, et maintient globalement sa forme.

Annexe : les automates cellulaires

Un automate cellulaire est défini par :

un ensemble dénombrable C de cellules
un ensemble fini E d'états
une fonction d'observation O qui, à tout instant t (un entier naturel), permet de connaître l'état e = O(t, c) d'une cellule c :

O : N x C -> E

une fonction de transition T qui, à un n-uplet d'états, associe un état e = T(e₁, e₂, ..., e_n) :

T : Eⁿ -> E

une fonction de voisinage V qui, à toute cellule c, lui associe son voisinage, i.e. un n-uplet de cellules (c₁, c₂, ..., c_n) = V(c)

V : C -> Cⁿ

Si nous construisons la fonction K : N x Cⁿ -> Eⁿ telle que K(t, (c₁, c₂, ..., c_n)) = (O(t, c₁), O(t, c₂), ..., O(t, c_n)), i.e. la fonction qui associe à un n-uplet de cellules le n-uplet de leurs états respectifs à l'instant t, alors l'automate cellulaire doit toujours satisfaire la propriété suivante :

quel que soit t > 0, O(t+1, c) = T( K(t, V(c) ) )

Autrement dit, l'état d'une cellule à un instant t+1 ne dépend que de l'état de ses cellules voisines à l'instant t ; la fonction de transition traduit cette dépendance. A l'instant initial t=0, l'état des cellules doit être donné.

Pour le TER, l'espace des cellules est un simple tableau de cellules, du style :

Sur ce schéma est représenté le voisinage de Moore de la cellule 'c' : ce sont toutes les cellules marquées d'un 'x', cellule 'c' comprise (il y a donc 9 cellules voisines) ; cet espace est un hyper-tore du plan si le bord horizontal en haut est supposé connecté au bord horizontal en bas, et que le bord vertical gauche est connecté au bord vertical droit. Dans ce cas, les cellules voisines au sens de Moore de la cellule 'a' sont, en plus d'elle-même, les cellules marquées d'un 'y'.