

Cellular Automata "MiniModels":
Emergent Spatial Structure in Vegetation Succession
By: David
E. Atkinson, Mike
C. Sawada and Konrad
Gajewski
Paper presented at the Canadian Association of Geographers
annual meeting,
Ottawa 1998
Introduction
Slide 1
The purpose of the talk we present today is to demonstrate the use of
a modeling methodology termed "cellular automata". I will first
review the morphology and dynamical aspects of CA and then proceed into
a brief history, leading towards some of the uses to which CA has been
put in geography, ecology and other disciplines.
Mike will then review the technical aspects of our model operation and
the results of experiments conducted to examine the influence of various
adjustable parameters on the evolution of spatial structure in the model
environments.
The model we present here is the essence of the model Mike and I and
Konrad Gajewski will use to examine the response of the boreal treeline
of northern Québec to various environmental forcing factors, such
as climate amelioration in the postglacial period.
Description
A cellular automata model can be characterized by making reference to
its physical layout, its rules of transition and the discrete nature of
space, time and interaction within its world.
The spatial realm, or "universe", of any CA consists of a one,
two or three dimensional space that has been divided into discrete units,
or "cells", that completely fill the universe.
Each cell in a CA is irreducible, or discrete, in nature and thus is
capable of taking only one value, or "state", selected from
a finite set of states. The cell forms the lowest limit of spatial resolution
in a CA, much like a single pixel in a raster image from a GIS or satellite
image.
Slide 2
Here is the layout of the grid. Because interactions in a CA are local
scale, the frame of reference changes continually with each cell considered.
Thus, at this point the white cell in the middle is the cell under consideration
and the cells surrounding the middle cell form "the neighborhood".
The dark blue cells represent a "von Neumann" neighborhood structure
and the dark blue and red cells taken together constitute a "Moore"
neighborhood structure.
Usually, a CA structure is a square grid, although triangular and hexagonal
cell spaces have been used.
Slide 3
Other characteristics of Cellular Automata include such things as:
 The fate of any cell is governed by localscale interactions with
its neighbors, or what are termed "transition rules".
 The transition rules reflect system dynamical agents as applied
at the localscale . These govern things such as interspecies competition,
reproduction, death due to overcrowding.
 Transition rules are either deterministic or stochastic
(i.e. probabilistic)
.
 Time steps are discrete and indivisible within the model.
It is the set of simple, localscale rules that, when applied over thousands
of neighbor interactions over scores or hundreds of time steps, determines
the spatial structure for the entire universe under consideration.
Slide 4
Here is a generalized transition rule expressed in formalized notation
for a von Neumann neighborhood.
Briefly, the state any cell a will take at the next time step
is a function f of its own state at time t and the
state of its neighbors at time t . The function f represents
the transition rule set.
Slide 5
Here we can follow through the application of a simple transition rule.
The cell under consideration possesses state zero. There is a transition
rule that specifies when a cell will take state one and when it will take
state zero. In this case, a cell will take state one if exactly three
of its neighbors possess state one. Application is a simple matter of
polling the neighborhood and comparing against the transition rule. In
this case, three neighbors possess state one. Thus, the state of the cell
under consideration is set to 1, to be implemented at the next time step.
Focus then shifts to the next cell down (or to the right) and the application
of the transition rule is repeated.
History
Slide 6
I will now briefly review the history of Cellular Automata.
The earliest work on CA began in the 1950s by John von Neumann, one of
the main workers on the ENIAC project. He was interested in the concept
of "machine selfreplication", and after a suggestion by Stanislow
Ulam, began to use CA to create machines that could control information
and processes to reproduce themselves or to construct other entities.
These early CA are very similar in form and function to CA models used
today: they possessed grids made up of discrete elements, discrete states
and time steps, and transition rules that governed the evolution of a
cell.
In general, CA from the pre1970s were confined to computer science and
digital electronics. Its spread into other research fields was limited
by a lack of computer availability and power.
Slide 7
Much theoretical work was laid out by the early workers in CA, including:
 2 and 3dimensional structures
 transition rules that are not stationary, meaning the transition rules
can change according to some function that is time, space or neighborhood
dependent
 deterministic and stochastic rules
 cell age limits, an important consideration for ecological/biological
applications
 neighborhoods of 4 (von Neumann) and 8 (Moore) square elements
 universe constructed of various geometric elements (square, triangle,
hexagon)
Slide 8
In 1970 an article appeared in Scientific American describing a CA model
that, although small and not particularly complex, was very important
in raising awareness of Cellular Automata. This was an article by Gardner
detailing a "mathematical recreation" devised by the Cambridge
mathematician Conway, called the Game of Life. It is a simple example
of a CA that uses a deterministic, completely stationary transition rule
set on cells that can possess one of only two states. Its significance
lay more with the fact that it brought the concept to many people. It
is one of the most frequently cited CA references.
Throughout the 1970s the concept began to permeate into other disciplines.
That plus an increase in availability and power of computers meant that
CA models were more frequently actually implemented on computer and were
being applied to model problems and systems in nature.
Slide 9
In the 1980s the dominant force in CA modeling was Stephen Wolfram. He
published papers formalizing aspects of the mathematics and statistical
mechanics of CA and demonstrating the application of CA in such fields
as artificial life, fluid dynamics and cryptology. He initiated the modern
study of the "Science of Complexity", which is tasked with investigating
the ability of simple structures with simple, local scale transition rules
to generate largescale patterns possessing great complexity.
Also in the 1980s University of Ottawa professor Michel Phipps devised
the "neighborhood coherency principle", an important early contribution
to CA modeling as applied to ecology.
Now, before describing our CA model, I will detail recent applications
of CA in ecology.
Ecology Applications
Slide 11
Since 1990 CA has been applied to various questions in ecological research,
including:
 effect of spatial pattern form on species coexistence or diversity
 succession modeling
 disturbance modeling
 environmental gradient forcing
 effect of different plant strategies on community structure
 wave regeneration of trees
 hostparasitoid relationships
 predatorprey relationships
Our model
Slide 12
The van der Laan model is a threestate probabilistic CA. It considers
state zero also called the dead state, state one also called species A
and state two also called species B. Three types of competition between
cell states can be modeled:
 Coexistence, where the probability of a cell in state 1 or 2 becoming
state 0, or dead, is greater if its neighborhood contains states of
its own kind. Here we do not expect large tessarae of any cell to develop.
 Contingent competition, where the probability of a cell dying is greater
if its neighborhood contains more cells of a different state. Here we
expect large tessarae of each cell to develop.
 Dominance, under dominance a species in any situation is more robust
than another species. In our model this is represented as a gradient
across the cellular space, such that, in the left side of the universe
one species dominates over another and vice versa on the other side.
Slide 13
The following schematic outlines the operation of our model.
Boxes in yellow correspond to the basic van der Laan model and blue boxes
represent our extensions upon this basic model:
 We initialize three twodimensional arrays, one contains the states
of cells at time t, the second the states at time t+1 and the third
contains the age of each cell at time t.
 At this point a random age structure can be introduced to the cells
which eventually determines their probability of undergoing competition.
 After initialization looping begins, one loop for the number of generations
and one for each cell in the cellular universe which also applies the
rule sets for each cell.
 The edge structure is determined as is the neighborhood of influence
for each cell, a Moor Neighborhood in our case.
 A dead cell, state 0, chooses a random neighbor. If this takes place
then the loop is exited and the next cell is considered.
 If a cell is in state 1 or 2 then it has a probability of dying.
 If it does not die then a rule set specific to the state of the cell
being considered is applied. These rules are based on the competition
types previously noted and determine the state of a cell in the next
generation as a function of its current state and that of its 8 nearest
neighbors.
 This loop is repeated for every cell in the universe and new states
are updated each time in the second array.
 Once the states in the generation are determined then the current
cellular universe and its corresponding cells are sent to analysis modules
which determine, amongst others, the average patch sizes, area, perimeter,
and fractal dimension for each generation.
 Then the states at t+1 are updated as the states for time t.
 If a disturbance has been specified it is now applied and can take
the form of either a symmetrical species unspecific, patch specific
or species patch specific disturbance.
 The loop is repeated for each generation.
Slide 14
The model parameters can be specified by the user in this form according
to the specific goal of the simulation.
 Our simulations used 200x50 cell universes with an island structure.
 All the simulations have the same parameters of Beta = 5% (the probability
of a cell dying due to neighbors of its own kind) and Lambda 2.5 to
7.5% (the probability of a cell dying due to neighbors of another kind)
with Omega = 0 (the probability of a cell dying for some other reason).
Note however, these values are used differently in each type of competition
modeled.
 Our first set of runs introduce the van der Laan model which contains
a gradient from coexistence to contingent competition, followed a run
with dominance and then these runs with an age structure and disturbance
regime.
Results
Slide 15 (for discussion slide click
here)
 Here is a pair of runs to demonstrate the basic functioning of the
van der Laan model without our extensions.
 This simulation has two different starting densities but the same
rule sets.
 There is a gradient, such that, coexistence is modeled on the left
side of the universe and grades into contingent competition on the right
side of the universe. In other words, the probability of a cell dying
due to neighbors of its own state is greater on the left side of the
universe than on the right side of the universe.
 First, on the left is competition modeled with an initial 100% density
of states 1 and 2 and second with an initial 1% density of 1 and 2 states.
 Both show smaller patches and more fragmentation on the left side
and larger patches or tessarae on the right side of the universe.
 However, the initial density has effects on the patch size at generation
500, such that, with a low initial density the tessarae are much larger.
 In terms of average patch size, with a 1% density, both species increase
rapidly initially creating large patches. At which point the average
patch size slowly decreases as competition leads to fragmentation of
the larger patches at the edges.
 This, note, is reflected in the Fractal Dimension which indicates
that patches are more complex in the high density run.
 Also of interest, is the implicit development of feedback in the system.
At the left side of the universe there is implicit negative feedback,
such that, large tessarae are discouraged from developing. On the right
side of the universe there is positive feedback which encourages the
development of large tessarae, but only to a point. Once two large tessarae
develop they have a negative feedback relation due to contingent competition
at their edges.
Slide 16 (for discussion slide click
here)
 This run has the same parameters as the previous but models dominance
from two different initial conditions.
 The Average Patch Size results are similar with the qualification
that the average patch size under the random start becomes larger for
both species.
 However the fractal dimension is more difficult to interpret at this
time.
 Also, at the 500th generation we find with the low density initial
conditions, remnant patches of both species outside of their optimal
range, this is due to the dynamics of the initial increase in patch
sizes, such that, large patches which developed outside of their optimal
ranges persist for longer due to initial large tessarae
Slide 17 (for discussion slide click
here)
 This run illustrates the previous Coexistence to Contingent Competition
run but with our extension of the model with an age structure.
 Here, the maximum ages for each species in terms of generations are
assigned to each state at the beginning of the simulation, creating
a uniform age structure for each species.
 The probability of a given cell undergoing competition effects is
directly proportional to its age. The younger the cell, the more susceptible
it is to death due to competition. A cell, which reaches its maximum
allotted life span, must of course die.
 We have three runs where species A the red cells are assigned an age
of 40 generations and we vary the age of species B each run by decrementing
its maximum age by 5 generations.
 We do this to determine whether the longer lived species has a competitive
advantage with all other things being. Furthermore, we want to see how
initial mass deaths lead to large dieoffs of one species, which as
a historical factor may be important in the evolution of the end spatial
structure.
 In the first graph, we see that each species begins with initial average
patch sizes which are nearly identical, that is, until the initial dieoff
begins between 30 and 40 generations. At this point the average patch
sizes for each species within a given run rapidly diverge. The species
which died first ends up being excluded from many areas. The exception
is when the maximum age of both species is the same.
 This illustrates how the present spatial structure is influenced by
historical events long after they have occurred even when no present
trace of these events remains.
 The Fractal Dimension indicates that patches are most complex under
an equal age structure. Fractal dimensions become less complex as the
age difference increases. This is largely due to the fact that the species
with a longer lifespan becomes more dominant and creates larger homogeneous
patches which percolate, that is, decrease the perimeter/area ratio.
 Finally, we can see the degree to which age structure is important
in the competitive dynamics by looking at this figure. This figure illustrates
the number of dead cells each generation. It shows that the dieoffs
of fully mature cells oscillate with a dampened amplitude. At approximately
generation 200 a random age structure has developed and the number of
dead cells each generation cannot be distinguished from a run with the
same parameters but no age structure. However, this is not to say that
the field at 500 generations is identical since the initial age structure
has significant effects on the end structure.
Slide 18 (for discussion slide click
here)
 This run is similar to the previous but with dominance.
 The major difference is in the average patch size trend of the species
with the shorter lifespan. This graph shows that, although there is
a divergence after the initial die off, because species B the blue species
is dominant on the left side of the universe it continues to grow. Under
the previous model, species B trended toward smaller and smaller patches
to eventual extinction with a large age difference in some simulations.
 The fractal dimension is again like the previous dominance run and
is difficult to interpret at this time.
Slide 19 (for discussion slide click
here)
 This run represents coexistence to contingent competition under three
different disturbance regimes. In each case, the chance that a disturbance
will occur in any generation is 15 percent.
 Run A shows a disturbance that produces square blocks occupying 5
percent of the universe. These disturbances are species independent.
 Run B shows a disturbance that affects patches. Either species can
be affected, but a given disturbance is limited to one species and one
patch.
 Run C shows a patchspecific disturbance regime that is limited to
one species, species A.
Where disturbance regimes are concerned, I would like to draw your attention
to this graph which illustrates the number of cells of each species in
each generation.
With square symmetrical disturbances under the coexistence to contingent
competition model, the species dynamics follow more closely a model run
with the same parameters but without any disturbance regime. Chance, in
this case, determines the advantages one species will gain over another.
With patch specific disturbances that can take place in patches of either
species under some empirical or probability density function, the divergence
of the dominance of each species takes place quite early, indicated by
the black (purple) lines. Since the disturbance regime is patch specific
but species unspecific, competitive advantages between the species can
rapidly change depending on the disturbance and its magnitude. Note the
two change overs in the dark lines. Here species A begins the run by increasing
its dominance over species B. Suddenly a disturbance takes place in a
large patch of Species A and the relation immediately shifts. Then, for
sometime, species B dominates, and at approximately generation 370 a massive
low frequency high magnitude disturbance destroys a lot of Species B and
quickly Species A begins to take over. At the end of the run, species
A largely dominates the space as seen in the second figure.
Similarly, and not unexpected, with the same disturbance frequency but
specific to patches containing Species A, by the end of the run Species
B dominates the field.
Conclusions
In our current model, the rules by which cells change states are not
spacetime stationary. In order to incorporate environmental gradients
that influence state changes in different areas of space we have introduced
gradients which influence how the rules are applied for each cell. Furthermore,
in order to introduce an age structure to the model we found it necessary
to break the time stationarity rule as well, such that the probability
of a certain rule being applied changes according to the age of each cell.
Although we base our model nomenclature upon the van der Laan model of
competition, we could have called the model "state succession across
environmental gradients". This is because the essence of cellular
automata deals with state changes as a function of local neighborhood
interactions. In this sense, our competition gradients represent environmental
gradients which affect the probability of a given cell adopting a given
state in the next generation.
In general, it is apparent that the system portrayed here is sensitive
to a number of parameters. Further work with this model will include analyses
to better quantify the observed sensitivities, in order to determine critical
or "threshold" values.
As geographers, we are fundamentally interested in spatial relations
and the processes which give rise to spatial structure in the landscape
which surrounds us. From this perspective, our current model is generic
and applies to no specific 'realworld' situation. However, from this
we find that cellular automata may be a unique tool that will allow us
to understand and generalize the processes which give rise to 'realworld'
spatial structure.


