CAGE
Cellular Automata General Environment
Alghero, Marzo 2003
Sommario

Automi Cellulari (AC)

Ambienti di simulazione e CAGE

Il modello di AC in CAGE

Caratteristiche dell’ambiente

Programmazione di AC in CAGE

Esempi di implementazione
Automi cellulari
Un Automa Cellulare è un sistema discreto dinamico composto da
un grande numero di celle in una griglia nello spazio (1-D, 2-D, o 3-D).
Ogni cella interagisce solo con le sue vicine ed esiste una regola di
evoluzione dell’automa cellulare che cambia lo stato di tutte le celle
simultaneamente ( in parallelo ) a passi discreti del tempo.
Automi Cellulari
Il comportamento globale del sistema è determinato dall’evoluzione degli
stati di tutte le celle come risultato di interazioni multiple tra le stesse.
Automi Cellulari
Griglie bidimensionali e vicinati classici
C
C
C
C
Automi Cellulari
Gli automi cellulari (AC) sono sistemi dinamici discreti ma risultano
spesso efficace alternativa alternativa ai sistemi di equazioni
differenziali per la simulazione di sistemi dinamici continui
In generale gli AC offrono un modello per studiare sistemi composti da
un gran numero di diverse parti (celle) in cui non si ha un controllo
centrale ma solo semplici interazioni locali
L’idea di base è di simulare il comportamento di un sistema
complesso dall’interazione di un grande numero di celle che
che seguono semplici regole, e non di descrivere il comportamento
globale mediante complesse equazioni
Automi Cellulari e calcolo parallelo
L’uso di computer paralleli risulta spesso inevitabile quale supporto
per la modellazione mediante AC di problemi reali
Gli AC rappresentano un modello di calcolo pararallelo che può
essere efficacemente implementato in architetture parallele in virtù delle
caratteristiche di parallelismo implicito e località
L’approccio naturale prevede la suddivisione delle celle tra i diversi
elementi di calcolo del computer parallelo (data parallelism)
In pratica nelle architetture a memoria distribuita (MIMD computer) il
parallelismo degli AC può essere implementato mediante l’approccio
SPMD (Single Program Multiple Data)
Ambienti di simulazione basati su AC
Esistono molti ambienti di modellazione e simulazione basati su AC
implementati sia in computer sequenziali (PCs, workstations) che
paralleli:
 CAPE
 PECANS
 CAMEL
 P-CAM
 StarLogo
 NEMO
 DEVS
 CELLULAR
 CAM-8 (hardware)
 ....
 CAGE:
Cellular Automata General Environment
Le potenziali aree di applicazione sono diverse: fisica, biologia,
genetica, chimica, pianificazione urbanistica, gestione ambientale, image
processing, economia.
Gli ambienti disponibili presentano diversi limiti (con particolare riferimento
alle applicazioni nel campo dell’urbanistica)
Alcuni limiti della formulazione classica e/o di molti ambienti ad AC
Stazionarietà spaziale e temporale degli intorni
In CAGE l’intorno può variare nel tempo ed è definito sulla base di relazioni, non
necessariamente geometriche, che intercorrono tra gli oggetti della realtà.
Regolarità della discretizzazione
In CAGE l’oggetto geometrico associato alle celle è considerato un attributo la cui
particolare occorrenza non è soggetta a vincoli di regolarità spaziale o temporale.
Stazionarietà ed omogeneità della funzione di transizione
In CAGE la funzione di transizione della cella è dipendente anche da parametri
variabili nel tempo, locali alla cella o globali.
Limitazione del numero di stati delle celle
In CAGE non esiste una limitazione a priori del numero degli stati e sono
disponibili diversi tipi di sottostati (intero, reale, carattere)
Alcuni limiti della formulazione classica e/o di molti ambienti ad AC
Chiusura rispetto ad eventi esterni
In CAGE è prevista la possibilità che fenomeni esterni influiscano, anche a livello
locale, sulla evoluzione della simulazione.
Località del controllo dell’evoluzione
In CAGE per consentire simulazioni realistiche esiste anche un meccanismo di
controllo globale (steering) dell’evoluzione del sistema
Difficoltà nell’importazione degli scenari da GIS
In CAGE è prevista l’implementazione di specifiche funzioni di importazione di dati
spaziali e alfanumerici da GIS esistenti
Ambienti utilizzabili solo da esperti programmatori
In CAGE il ciclo di modellazione-simulazione-analisi dei dati è semplificato da una
specifica interfaccia grafica comprensiva di funzionalità di modellazione semivisuale delle regole di evoluzione
Caratteristiche essenziali di CAGE
GUI amichevole per la modellazione dell automa cellulare in modo visuale
Applicazione cross-platform basata sulle librerie QT (Windows-Linux)
Rimozione di molte delle restrizioni tipiche degli ambienti ad AC
Strutturazione in layers dello scenario (nei diversi layers si svolgono,
parallelamente e secondo le regole assegnate, le simulazioni dei vari fenomeni di
interesse)
Funzioni di libreria predefinite e facilitazioni per la scrittura delle regole di
evoluzione
Funzioni di importazione/esportazione di dati grafici o tabellari
Esecuzione su elaboratore remoto mediante protocollo TCP
La GUI di CAGE
Finestre grafiche
Modellazione della struttura
Il modello di AC
L’automa cellulare AC è definito dalla tripla: AC
PG
 PG ,fG , L 
è l’insieme finito dei valori che assume il vettore g-dimensionale
dei parametri globali: PG  PG(1)  PG( 2)   PG( g )

fG  f G(1) , f G( 2 ) ,, f G( g )

è un vettore di funzioni di aggiornamento dei
parametri globali.
L  l1 , l2 ,, ln  è un insieme di n layer di celle.
Il layer
Un layer di celle è definito dalla tripla:
li  Ci , PLi , f Li 
Ci
è un insieme di celle
PLi
è l’insieme finito dei valori che assume il vettore r-dimensionale
dei parametri di layer.

f Li  f Li(1) , f Li( 2 ) ,, f Li( r )
parametri di layer

un vettore di funzioni di aggiornamento dei
La cella
La cella è definita dalla sestupla:
ci  Si , PCi , σi , fCi , i , Oi 
Si
è l’insieme finito dei valori che assume il vettore q-dimensionale
che definisce lo stato della cella
PCi
è l’insieme finito dei valori che assume il vettore r-dimensionale
dei parametri locali della cella
Oi è un insieme finito di oggetti geometrici, eventualmente
georeferenziati e caratterizzati da opportuna descrizione vettoriale.
ci  Si , PCi , σi , fCi , i , Oi 
La cella

σi   i , i ,, i
come:
(1)
( 2)
( n)

è un vettore di n funzioni di vicinato definite
 i( k ) :  Ci  Ck  C  PLi  PG  (Ck ), k  1..n
k
 i( j )con
 i(i )
Vicinato orizzontale
ji
Vicinato verticale
ci  Si , PCi , σi , fCi , i , Oi 
La cella
•

f Ci  f Ci(1) , f Ci( 2 ) , , f Ci( m )
è
un
vettore
di
funzioni
di
aggiornamento dei parametri locali con:
 n

(k )

fCi :  S k  i  PG  PLi  PCi   PCi
 k 1

 k  i

•
i è
la funzione di transizione della generica cella del layer, che
consente di aggiornare lo stato della cella ed è definita dalla:
i :  Si 
 i( i )
 PG  PLi  PCi
  Si
li  Ci , PLi , f Li 
Aggiornamento dei parametri di layer
Le funzioni di aggiornamento dei parametri di layer sono definite
dalla:
f Li :  Si 
Ci
 PLi
  PLi
I parametri di layer possono assumere valori dipendenti dalla
configurazione
attuale
dell’intero
layer,
offrendo
quindi
meccanismo di controllo globale dell’evoluzione del layer.
un
Aggiornamento dei parametri globali
AC  PG ,fG , L 
Il valore del parametro globale k-esimo può essere calcolato sulla base dei
valori assunti dagli altri parametri globali e da tutti i parametri di
layer:
fG( k )
 n

:  PLk  PG   PG( k )
 k 1



Il parametro globale può essere aggiornato, anche sulla base di variabili
esterne, da un generico modello di calcolo che si evolve parallelamente
all’automa cellulare
Architettura (futura) di CAGE
CA kernel
CA
CAkernel
kernel
C++
compiler
CAGE
server
PIPE
TCP
CAGE
client
CAGE
client
CAGE
client
Caratteristiche di CAGE: modellazione della struttura
nuovo layer
nuovo parametro
Rappresentazione del
flow-chart della
funzione
nuovo sottostato
Generazione funzione
Nuovo vicinato verticale
Rappresentazione ad
albero della struttura
Modifica attributi
dell’elemento
selezionato
Testo della funzione
Attributi dei layers
Per ogni layer è possibile specificare:
il nome;
il tipo di discretizzazione dello spazio:
regolare: una delle classiche discretizzazioni del piano in
celle esagonali, rettangolari, triangolari. La scelta della
discretizzazione regolare consente di scegliere anche tra uno
dei vicinati classici (Moore, Von Neumann, ecc);
non regolare: le celle sono costituite da oggetti grafici da
inserire con gli strumenti di editing disponibili in CAGE;
il tipo di contorno tra:
toroidale, limitato, inattivo (le celle di bordo vengono
impiegate nel vicinato delle celle interne ma i sottostati non
vengono aggiornati)
Parametri e sottostati
Per ogni parametro è possibile specificare:
il nome;
il tipo: tra intero, reale, carattere
il tipo di aggiornamento tra: costante o basato
su una funzione
Per ogni sottostato è possibile specificare le
seguenti proprietà:
il nome
il tipo: tra intero, reale, carattere
Vicinati
Per ogni vicinato orizzontale è possibile
specificare se è:
del tipo classico (Moore, Von Neumann ecc. ),
solo nel caso di discretizzazione regolare per
il layer
basato su una funzione (query) da fornire
Per ogni vicinato verticale si devono
specificare:
il layer a cui lo stesso si riferisce
la funzione di aggiornamento del vicinato
Funzioni
Per ogni funzione (aggiornamento dei
parametri, sottostati e vicinati) è
necessario specificare:
il nome
la frequenza di esecuzione
la probabilità di esecuzione
una condizione cui subordinare
l’esecuzione
Generazione di funzioni
Proprietà
del componente
Creazione del
diagramma
di flusso selezionato
Inserimento facilitato del codice (variabili e funzioni di libreria)
Componenti del diagramma della funzione
Flow-chart components
Blocco di istruzioni in formato libero: è necessario
rispettare la sintassi del linguaggio C
Salto condizionale
Salto condizionale secondo un valore di probabilità
Singolo statement
Uscita dalla funzione (corrisponde all’istruzione
return del C)
Condizioni logiche
Rappresentazione ad albero
Esempio: (a=1 AND b=2) OR (c=0)
OR
AND
a=1
b=2
c=0
Proposizioni logiche
Creazione di una proposizione logica composta
Funzioni di libreria
Funzioni geometriche
dist(obj1, obj2)
Restituisce la distanza tra i baricentri degli oggetti obj1 ed obj2
centroidX(obj)
Restituisce la coordinata X del baricentro dell’oggetto obj
centroidY(obj)
Restituisce la coordinata Y del baricentro dell’oggetto obj
area(obj)
Restituisce l’area dell’oggetto obj
perimeter(obj)
Restituisce il perimetro dell’oggetto obj
length(obj)
Restituisce la lunghezza dell’oggetto obj
Funzioni di libreria
Funzioni matematiche
abs(num)
Restituisce il valore assoluto di num
max(num1, num2)
Restituisce il massimo tra num1 e num2
min(num1, num2)
Restituisce il minimo tra num1 e num2
odd(num)
Restituisce true se num è dispari
even(num)
Restituisce true se num è pari
prob(num, over)
Restituisce true con una probabilità di num su over
Esempio: prob(10,100) restituisce true nel 10% dei casi
div(n1, n2)
Restituisce true se n1 è divisibile per n2
Funzioni di libreria
Funzioni di aggregazione su layer
Sum(var)
Restituisce la somma dei valori della variabile var sulle celle
Min(var)
Restituisce il minimo dei valori della variabile var sulle celle
Max(var)
Restituisce il massimo dei valori della variabile var sulle celle
Average(var)
Restituisce la media aritmetica dei valori della variabile var
sulle
NEqVal(var, val)
Restituisce il numero di celle per le quali la variabile var
assume il valore val
Funzioni di libreria
Funzioni di aggregazione su vicinato
NeighCell[lay].Sum(var)
Restituisce la somma dei valori della variabile var sulle celle
appartenenti al vicinato della cella corrente sul layer lay
NeighCell[lay].Min(var)
Restituisce il minimo dei valori della variabile var sulle celle
appartenenti al vicinato della cella corrente sul layer lay
NeighCell[lay].Max(var)
Restituisce il massimo dei valori della variabile var sulle
celle appartenenti al vicinato della cella corrente sul layer
lay
NeighCell[lay].Average(var)
Restituisce la media aritmetica dei valori della variabile var
sulle celle appartenenti al vicinato della cella corrente sul
layer lay
NeighCell[lay].NEqVal(var, val)
Restituisce il numero di celle appartenenti al vicinato della
cella corrente sul layer lay per le quali la variabile var
assume il valore val.
Aggiornamento di una variabile
 Per ogni variabile (parametro o sottostato) rappresentata
dall’identificatore [Name] è definita la variabile [NewName]

La funzione di aggiornamento della variabile deve contenere
Risultato:
almeno una istruzione di assegnazione del tipo:
if ( Attiva )
[NewName] = espressione
{ if ( ( NeighCell[Mondo].NEqVal(Attiva,1)!=2 ) && ( NeighCell[Mondo].NEqVal(Attiva,1)!=3 ) )

Esempio (life):
NewAttiva=0;
}
else if ( NeighCell[Mondo].NEqVal(Attiva, 1)==3 )
NewAttiva=1;
Aggiornamento di vicinato basato su funzione
(dist(Obj,Cell[Layer].Obj)<100) && (area(Cell[Layer].Obj) > 5000)
Cella
Vicinato generato al primo passo
(dist(Obj,Cell[Layer].Obj)<100) && (area(Cell[Layer].Obj) > 5000)
Vicinato
Query
di
orizzontale
aggiornamento
dist(Obj, Cell[Layer].Obj)<100
Frequenza
Probabilità
Condizione di
Condizione
inclusione
della cella
target
Attributi della query
Creazione di una discretizzazione non regolare
Strumenti di editing
Alcune altre funzioni utili
Creazione colormap
Controllo visualizzazione oggetti
Controllo visualizzazione
layersdelle variabili
Editing dei valori
Colormap
Alcune delle cose da fare (si accettano suggerimenti):
 Potenziamento del linguaggio di






programmazione delle regole (costrutti per
l’iterazione su insiemi di celle, ampliamento della
libreria di funzioni)
Gestione degli errori (messaggi di errore e di
avvertimento)
Potenziamento funzioni di editing/input/output
Help in linea
Versione parallela e architettura client-server
Porting in ambiente linux
…………………………..
GRAZIE !