WAI

Automaty komórkowe

1

wprowadzenie

W. Kosiński, Piotr Prokopowicz, Marcin Burzyński

Historia

Janos von Neumann pod koniec lat 40 XX wieku zajmował się
modelem tzw. „pierwotnej zupy” (cieczy, z której miało powstać
ż

ycie). Inspirowany przez lwowskiego matematyka Stanisława

Ulama wprowadził do swego modelu dyskretną przestrzeń i czas.

Najsłynniejszym automatem komórkowym jest tzw. „gra life”

2/20

Najsłynniejszym automatem komórkowym jest tzw. „gra life”
Johna H. Conwaya (1970), która swego czasu miała nawet swój
fanklub.

W latach 80-tych intensywną popularyzacją i praktycznym
zastosowaniem automatów komórkowych zajmował się Stephen
Wolfram znany skądinąd jako twórca pakietu Mathematica.

Co to jest automat komórkowy?

Automat komórkowy (ang. Cellular Automata skrót CA)
składa się z:
- zbiór komórek K (sieć komórek) przestrzeni D-
wymiarowej k

i

∈

K

- zbiór stanów S pojedynczej komórki – z reguły ten sam
dla wszystkich komórek s

i

∈

S

3/20

dla wszystkich komórek s

i

∈

S

- reguła R pozwalająca na podstawie aktualnego stanu
komórki i jej otoczenia określić jej stan w kolejnym
kroku. Funkcja przejścia. Ewolucja układu komórek.

By dopełnić opis CA należy zdefiniować jeszcze
warunki brzegowe.

CELLULAR AUTOMATA - DEFINITION

•Regular lattice of cell in n-dimensional
space

•Set of states of single cell, usually the
same for all cells

•Set of local transition rules which define
next state of cell as a function of cell and

next state of cell as a function of cell and
neighborhood previous states.

CELLS

STATES

RULES

BYDGOSZCZ UNIVERSITY

Institute of Environmental Mechanics and Applied Computer Science

4/12

Oznaczenia

Jednym ze sposobów klasyfikowania CA jest podanie pary liczb

(D, r) – gdzie D jest wymiarem automatu a r jest promieniem
otoczenia.

Wymiar D tylko dla jednowymiarowej przestrzeni wyznacza
jednoznacznie siatkę automatu komórkowego.

Różne rodzaje sieci komórek:

5/12

Różne rodzaje siatek cd.

6/12

Rodzaje siatek cd.

7/12

Sąsiedztwo

W realizacji CA istnieją różne warianty branego pod uwagę otoczenia
nazywane sąsiedztwem.

Sąsiedztwo von Neumanna

Sąsiedztwo Moora

8/12

Sąsiedztwa cd

Sąsiedztwo von Nemanna dla r=2

9/12

Sąsiedztwo Wolframa (dla D=1)

Sąsiedztwa cd

Nietypowe sąsiedztwa

10/12

skierowane

rozpatrywana jest para

komórek

przypadkowe

NEIGHBOURHOODS

Von Neumann
neighborhood
of R=1

Wolfram neighborhood of R=1

Moore
neighborhood
of R=1

R=2

R=2

BYDGOSZCZ UNIVERSITY

Institute of Environmental Mechanics and Applied Computer Science

11/12

Warunki brzegowe

Torus

periodyczne

12/12

NEIGHBOURHOOD

At most, the the first and the last cells are
connected each other:

Then one obtains periodic boundary
condition:

BYDGOSZCZ UNIVERSITY

Institute of Environmental Mechanics and Applied Computer Science

13/12

Inne warunki brzegowe:

- zamknięte pochłaniające

- zamknięte odbijające

Poza warunkami brzegowymi CA mogą różnić się
sposobem aktualizacji stanów komórek:

14/12

sposobem aktualizacji stanów komórek:

- wszystkie naraz - gra Life

- tylko wybrane (deterministycznie, bądź losowo) –
mrówka Langtona

Przykład

gra life

Symulacja zachowania się kolonii bakterii jednokomórkowych.

Sieć komórek – prostokątna (kwadratowa)

W jednej komórce może przebywać w danej chwili tylko jedna bakteria.

Czyli komórka może przyjmować stan „1” lub „0” (jest bakteria lub jej
brak)

15/12

Wykorzystywane jest sąsiedztwo Moore’a.

Reguły przejścia:

-

Bakteria umiera w następnym kroku, jeśli ma sąsiadów więcej niż 3 lub
mniej niż 2.

-

Bakteria urodzi się w pustej komórce, która ma w sąsiedztwie 3
bakterie.

Klasyfikacja Wolframa automatów binarnych, 1D z

sąsiedztwem R=1

• Zapiszmy na trzech bitach liczby od zera do 7 w kolumnie,

gdzie na najniższym poziomie będzie zero, tzn.

• 0 0 0, a na najwyższym 1 1 1.

• Ta kolumna reprezentuje wszystkie osiem możliwych stanów

sąsiedztw środkowej komórki i jej stanu.

sąsiedztw środkowej komórki i jej stanu.

•

Jeśli teraz wypiszemy kolejne liczby naturalne od zera do

255 binarnie i ustawimy każdą ósemkę w pionie obok tej
kolumny, skonstruowanej w pierwszym kroku, zapisanych
kolejnych liczbach naturalnych od zera do 7, to otrzymamy
256 różnych praw transformacji automatu binarnego 1D z
sąsiedztwem Wolframa R=1. (

poz. załączny plik Zad_AG.pdf, jego strone 2, gdzie

mamy automat Nr.90

)

16/12

Przykład

ruch drogowy

Model Kai Nagela i Michaela Schreckenberga z 1990r.
Sieć komórek – liniowa.
Komórka może być pusta lub zawierać samochód z przypisaną jedną z
prędkości.
Samochody poruszają się od lewej do prawej.
Reguły uwzględniają cztery elementy:
-przyspieszanie (do maksymalnej prędkości)

17/12

-przyspieszanie (do maksymalnej prędkości)
-bezpieczeństwo (redukcja prędkości)
-elementy losowe (nieprzewidziane zdarzenia na drodze – zwalnianie)
- ruch

2 3

1

0

0 2

0

1

TRAFFIC FLOW SIMULATION

•One dimensional synchronous linear cellular

automata
•Boundary condition - periodic
•asymmetric neighborhood
•deterministic rules and fuzzy rules

BYDGOSZCZ UNIVERSITY

Institute of Environmental Mechanics and Applied Computer Science

18/12

TRAFFIC

FLOW

SIMULATION

-

NEW

CONCEPT OF RULE

Fuzzy rule based on fuzzy controlling:

BYDGOSZCZ UNIVERSITY

Institute of Environmental Mechanics and Applied Computer Science

19/12

TRAFFIC FLOW SIMULATION - RESULTS
OF SIMULATIONS

Real

observations

Cellular

Automata

simulations

BYDGOSZCZ UNIVERSITY

Institute of Environmental Mechanics and Applied Computer Science

20/12

Literatura

[1] Krzysztof Kułakowski - "Automaty komórkowe", Ośrodek Edukacji

Niestacjonarnej Akademii Górniczo-Hutniczej im. St. Stasica w Krakowie;
Kraków 2000.

21/20

Niestacjonarnej Akademii Górniczo-Hutniczej im. St. Stasica w Krakowie;
Kraków 2000.

[2] Mateusz Miracki, Andrzej Dworak - "Modele komórkowe ruchu

drogowego" Wydział Fizyki i Informatyki Stosowanej, Akademii Górniczo-
Hutniczej, Kraków