SWEN90004
Modelling Complex Software Systems
Lecture Cx.05
Cellular Automata I: 1D and 2D CAs
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
SLIDE 1
Objectives
understand the limits of mathematical models
introduce cellular automata – a bottom-up approach to modelling complex systems explore the behaviour of 1- and 2-dimensional CAs.
SLIDE 2
Motivation
SLIDE 3
From macro to micro. . .
Complex systems are systems whose behaviour emerges from interactions between many individual parts:
Lotka-Volterra model–
parts = animals (predator and prey)
interaction = predation (eating of prey by predator)
SIR disease model–
parts = people (susceptible, infectious and recovered)
interaction = disease transmission (from infectious to susceptible people)
SLIDE 4
From macro to micro. . .
The ODE models of these systems required us to represent their state in terms of global (or macro) variables, and to define update rules in terms of how these global variables changed over time:
Lotka-Volterra model:–
variables = predator/prey population size
update = in terms of rates of birth, death and predation
SIR disease model:–
variables = proportion of the population in each disease state update = in terms of rates of infection and recovery
SLIDE 5
From macro to micro. . .
However, in order to build these ODE models, we had to make assumptions about our systems. Both models required us to assume that all individuals in our subpopulations (eg, predators, or susceptibles) were identical, and that all individuals in our population had an equal chance of interacting with each other.
SLIDE 6
From macro to micro. . .
In discussing possible problems with these models, these assumptions kept coming up as limitations:
Lotka-Volterra model:–
some predators/prey might be stronger/weaker than others
some predators/prey might be faster/slower than others
predaotrs/prey populations might have non-uniform spatial distribution
SIR disease model:–
some age groups (eg, children) might be more susceptible/infectious
populations might have non-uniform spatial distribution (eg, 90% of our population
might be vaccinated, but if the 10% who are not all live in the same suburb, that is a high-risk subpopulation)
We could extend our ODE models to reflect this heterogeneity (variation between individuals), but the number of equations and parameters required would explode rapidly.
SLIDE 7
From macro to micro. . .
For the next few weeks, we are going to explore approaches to modelling that are capable of representing this heterogeneity in populations:
cellular automata models agent based models
network models
These models will be computational rather than mathematical
SLIDE 8
Implementing a spatial model
Consider an SIR model, in which each person in our population has a fixed location on a square lattice (grid):
what is the most appropriate data structure?
how could you represent states?
how do you determine who interacts with who? how are states updated?
SLIDE 9
1D Cellular Automata
SLIDE 10
Cellular Automata
Cellular Automata (CA) are a type of discrete dynamical system that exhibit complex behaviour based on simple, local rules.
Developed in the 1940s by John von Neumann and Stanisłav Ulam at Los Alamos National Laboratory, who were interested in self-replicating robots (von Neumann) and crystal growth (Ulam).
FigureJohn von Neumann, Richard Feynmann & Stanisłav Ulam, Los Alamos, 1940s
SLIDE 11
Consider the patterns in Conway’s game of life: https://www.youtube.com/watch?v=C2vgICfQawE
If we equate a ‘robot’ with a pattern of active cells on a grid, then we can see the analogy with self-replicating robots: a particular pattern of active cells that, when updated according to the rules of dynamical system, is able to create a copy of itself. (The rules for this game are below, towards the end of this lecture).
Cellular Automata
automaton: a theoretical machine that updates its internal state based on external inputs and its own previous state
Figure
cellular automaton: an array of automata (cells), where the inputs to one cell are the current states of nearby cells
Figure
SLIDE 12
The bottom figure represents one possible neighbourhood that could be used to define interactions. See below for alternatives.
Cellular Automata
InaCA:
time is discrete (like the logistic map)
space is discrete: typically a 1D or 2D grid (3D also possible)
system state is discrete: each component of a system is in one of a finite set of states
(eg, ON or OFF); therefore the entire system has a finite, countable number of states
update rules are defined in terms of local interactions between components
SLIDE 13
Cellular Automata – applications
SLIDE 14
• simulation of physical systems:
– fluid and gas dynamics—each component is a particle with a particular velocity, whose future state depends on its interactions with adjacent molecules
– earthquakes—each component is a small *cell* of the Earth’s crust, which interact with neighbouring cells via tectonic forces
– bushfires—each component is region of bushland, interactions are fire spreading • simulation of biological and social systems:
– artificial life—investigations of self-replicating behaviour
– pattern formation—each component is a part of an organism, interacting via chemical
signals
– social simulation—(many examples in NetLogo)
• computing:
– theory—CAs with universal computing properties
– graphics and image processing—simulation of textures and surface effects – games—procedural level generation and emergent game play
1D Cellular Automata—the simplest case!
Figurespace: a one-dimensional grid of cells
Figurestate: each cell takes one of two states
Figureneighbourhood: the cell itself and its two adjacent neighbours (K = 3)
SLIDE 15
NB: These figures are from the book (available online) The Nature of Code, by Daniel Shiffman (Chapter 7: http://natureofcode.com/book/chapter-7-cellular-automata/)
Although the examples are written in the language Processing, the book does an excellent job of addressing issues around the implementation of complex systems models—I recommend using it as a resource if you need ideas for Assignment 1!
A 1D cellular automata is the simplest type of cellular automata.
Cells are arranged in a line (1D grid).
Each cell can take on a finite number of states (here, 2), has a finite number of possible inputs (each possible combination of states of cells in its neighbourhood)
Time is discrete (ie, the system updates in distinct steps, or generations).
The system has an update rule that defines the next state of each cell in terms of its input.
1D Cellular Automata—the simplest case!
Figuretime: discrete generations (time steps)
Figureupdate: use the state of the neighbourhood in the previous generation
SLIDE 16
1D Cellular Automata—the simplest case!
Figurethere are 2K possible combinations of neighbourhood states
Figureeach of these combinations determines the state of the target (centre) cell in the next generation
SLIDE 17
1D Cellular Automata—the simplest case!
Figurewe have a lookup table to determine the next state of each of the cells
What about the edges?
SLIDE 18
As noted, this particular cellular automata (1D, 2 states, adjacent neighbours) is quite minimal, yet
it results in 23 possible input combinations (neighbourhood states) for each cell, and 223 possible update rules, and is capable of a wide range of behaviours.
Imagine a 2D cellular automata (ie, on a two-dimensional grid, rather than a one-dimensional line), where each cell can take one of 8 states (rather than 2) and the neighbourhood consists of 5 cells (itself, and the four neighbours above, below, left and right of it).
Now we have 85 = 32768 possible input combinations. For each of these input combinations, there is a choice of 8 possible output states, so there are 885 possible update rules.
1D Cellular Automata—behaviour
We will use NetLogo to explore the behaviour of some different rules
SLIDE 19
You should investigate the dynamic behaviour of a range of different 1D CA rules using either the Matlab code provided, the NetLogo platform (there are CA models in the Model Library under ‘Computer Science’) or any of the wide range of CA platforms available online.
Observe that many rule sets produce similar behaviour; they may be trivially equivalent to each other under simple transformations of their underlying geometry such as:
• mirror: reflection about the vertical axis
• complement: exchange 0 for 1 and 1 for 0 in the definition
More formally
Each finite automata consists of a finite set of cell states Σ, a finite input alphabet α and a transition function ∆, which is a mapping from the set of neighbourhood states to the set of cell states:
∆ = ΣN → N
The state of a neighbourhood is a function (eg. cross product) of the states of the automata covered by the neighbourhood template. Thus, the input alphabet α for each automaton consists of the set of possible neighbourhood states.
Let K =| Σ | (the number of cell states).
The size of α is equal to the number of possible neighbourhood states:
|α| = |∆| = |ΣN| =KN
SLIDE 20
More formally
To define a transfer function ∆, a unique next state in Σ must be associated with a possible neighbourhood state.
Since there are K =| Σ | choices of states to assign as the next state for each of the | ΣN | possible neighbour states, there are KKN possible transitions functions ∆ that
can be defined.
DNK is the set of all possible transitions functions ∆ which can be defined using N neighbours and K states.
SLIDE 21
More formally
For example
Consider a 2-dimensional cellular automata using 8 states per cell; a regular lattice with a five cell local neighbourhood (north, south, east, west).
Here, K =8 and N =5, so there are:
| ∆ |= KN = 85 = 32768 possible neighbourhood states.
For all of these neighbouhood states, there is a choice of 8 different states for the next cell state under ∆, so there are:
DNK = KKN = 885 ≈ 1030000 possible transitions functions.
SLIDE 22
Naming CA rules
There are KKN = 223 possible rules for updating the canonical 1D CA (K = 2; N = 3).
We can interpret the sequence of 8 output values as base-2 number:
0×27 +1×26 +0×25 +1×24 +1×23 +0×22 +1×21 +0×20 =90 ie, this is Rule 90
SLIDE 23
Exploring CA rules
Many of the 256 rules are trivially equivalent to each other: simple transformation of the underlying geometry:
complement: exchange the roles of 0 and 1 in the definition
Some of the 256 elementary rules are identical – simply by renaming the states or reversing right and left – so the number of essentially different elementary rules is smaller (only 88).
mirror: reflection through a vertical axis.
SLIDE 24
Rule 30
Rule 30 displays aperiodic, chaotic behaviour. . .
Figure
SLIDE 25
While Wolfram initially described the behaviour of Rule 30 as chaotic based on its appearance, it has since been shown to meet the criteria of a chaotic system, inclding displaying a sensitive dependence on initial conditions (similar starting states of cell activation result in very different dynamic trajectories).
Rule 30
. . . that bears similarity to patterns found in nature
FigureA Textile Cone Snail (Conus textile), Cod Hole, Great Barrier Reef, Australia
Photographer: Richard Ling richard@research.canon.com.au
SLIDE 26
Rule 110
Rule 110 is Turing complete; ie, capable of universal computation
Figure
http://nicolas.brodu.net/en/programmation/mesincom/index.html
SLIDE 27
Discrete time dynamics
Many of our concepts from last week’s ODE models also apply here. . .
We are interested in the long term behaviour of the system: what happens as
t → ∞?
Our state space (the set of all possible states in the system) is discrete and finite,
and our trajectories are sequences of states
We can observe transients, fixed point and limit cycle attractors
the states that lead to each attractor constitute its basin of attraction
Figure
SLIDE 28
In this figure, a ‘dot’ represents a state of the system (ie, the pattern of activation of all of the cells), and an ‘arrow’ represents the transition from one state to the next when we apply the update rule (similar to how we used the ‘cobweb diagram’ to show how the state of the logistic map changed over time).
In this representation:
(a) shows a fixed point attractor—from this state, the next state that results from applying the update rule is itsemf, so the system behaviour does not change over time.
(b) shows a limit cycle attractor—this is a seqence of states that lead from one to the next and back to the initial state, so the system will oscillate between these states over time.
(c) and (d) show state-spaces that will eventually become fixed or oscillating, once the transient dynamics of the system have passed.
Wolfram classes
“. . . many (perhaps all) CA fall into four basic behaviour classes”
Stephen Wolfram, 1984
Figure
SLIDE 29
Class I: evolve to a fixed homogeneous state—the system freezes into a fixed state after a short time. eg, rule 160
Class II: evolve to a fixed inhomogeneous state—the system develops periodic, or limit cycle, behaviour. eg, rule 108
Class III: evolve to a chaotic or aperiodic behaviour—the system continuously changes in unpredictable ways and, in some cases, sensitive dependence on initial conditions. eg, rule 126
Class IV: evolve to complex localised structures—the system can develop in highly patterned but unstable ways, with complex interactions between local structures. eg, rule 110
Class IV in particular has been the focus of much study for its computational properties.
2D Cellular Automata
SLIDE 30
2D Cellular Automata
A 2D CA is similar to a 1D CA, except that we have to choose how to define our neighbourhood and our update rules.
Two common neighbourhoods are:
the Von Neumann neighbourhood (left): {(0, 0), (±1, 0), (0, ±1)} the Moore neighbourhood (right): {−1, 0, 1} × {−1, 0, 1}
Figure
SLIDE 31
Conway’s Game of Life
Invented by British mathematician, John Conway in 1970, inspired von Neumann’s earlier attempts to construct a self-replicating machine
Like Rule 110, the Game of Life is Turing complete
SLIDE 32
Conway’s Game of Life
The rules of Life:
each cell can be alive (black) or dead (white)
if an alive cell has fewer than 2 living neighbours, it dies—loneliness
if an alive cell has more than 3 living neighbours, it dies—overcrowding
if an alive cell has either 2 or 3 living neighbours, it stays alive—survival
if a dead cell has exactly 3 living neighbours, it comes alive—reproduction The initial pattern of living cells constitutes the first generation of the system. The
rules are then applied simultaneously to every cell in the system to produce the second generation, and so on.
What is the long term behaviour of the system?
SLIDE 33
The rules of Life
Loneliness
If an alive cell has fewer than 2 living neighbours, it dies
SLIDE 34
In this and the following figures, we are focusing on what happens to the central cell in the 5×5 grid. A black cell is ‘alive’, a white cell is ‘dead’ and grey cells could be any combination of dead or alive.
The rules of Life
Overcrowding
If an alive cell has more than 3 living neighbours, it dies
SLIDE 35
The rules of Life
Survival
If an alive cell has either 2 or 3 living neighbours, it stays alive
SLIDE 36
The rules of Life
Reproduction
If a dead cell has exactly 3 living neighbours, it comes alive
SLIDE 37
Conway’s Game of Life
We will use NetLogo to explore the behaviour of some different initial conditions
SLIDE 38
Conway’s Game of Life
over time, organised patterns emerge:
Figure
SLIDE 39
Conway’s Game of Life
can be used to implement information-carrying signals and logical operations on those signals
Figure
SLIDE 40
Conway’s Game of Life
The Game of Life (and CA more generally) is a ‘classic’ example of a complex system:
many components
local interactions
decentralised control
parallel processing
emergent global behaviour self-organisation
They still make some strong assumptions that may limit their applicability as models of real systems however. . .
all updates happen synchronously all updates are deterministic
Next lecture we will discuss how we could create CA models of more realistic scenarios: predator-prey interactions and the spread of an infectious disease.
SLIDE 41
Additional references
Gardner, M (1970) Mathematical Games—The fantastic combinations of John Conway’s new solitaire game “life”. Scientific American 223:120–123.
Wolfram, S (1984) Computation theory of cellular automata. Communications in Mathematical Physics 96:15–57
Langton, C (1986) Studying artificial life with cellular automata. Physica D 22:120–149
Flake, GW (1998) The Computational Beauty of Nature. MIT Press, Cambridge MA (chapter 15)
Wolfram, S (2002) A New Kind of Science. Wolfram Media, Champaign IL
Schiff, JL (2008) Cellular Automata: A Discrete View of the World. Wiley-Interscience, Hoboken NJ
Shiffman, D (2012) The Nature of Code. http://natureofcode.com/ (chapter 7)
SLIDE 42