GeoComputation using cellular automata

Michael Batty

Cellular automata as GeoComputation
Cellular automata (CA) are computable objects existing in time and space whose characteristics, usually called states, change discretely and uniformly as a function of the states of neighboring objects, i.e. those that are in their immediate vicinity. The objects are usually conceived as occupying spaces
which are called cells, with processes for changing the state of each cell through time and space usually articulated as simple rules which control the influence of the neighborhood on each cell. This formulation is quite general and many systems can be represented as CA but the essence of such modelling consists of ensuring that changes in space and time are always generated locally, by cells which are strictly adjacent to one another. From such representation comes the important notion that CA simulate processes where local action generates global order, where global or centralized order ‘emerges’ as a consequence of applying local or decentralized rules which in turn embody local processes. Systems which cannot be reduced to models of such local processes are therefore not likely to be candidates for CA, and although this might seem to exclude a vast array of geographical processes where change seems to be a function of actionata distance, this criterion is not so restrictive as might appear at first sight.

Formally, we can restate the principles of CA in terms of four elements. First there are cells, objects in any dimensional space but manifesting some adjacency or proximity to one another if they are to relate in the local manner prescribed by such a model. Second, each cell can take on only one state at any one time from a set of states which define the attributes of the system. Third, the state of any cell depends on the states and configurations of other cells in the neighborhood of that cell, the neighborhood being the immediately adjacent set of cells which are ‘next’ to the cell in question where ‘next’ is defined in some precise manner. Finally, there are transition rules which drive changes of state in each cell as some function of what exists or is happening in the cell’s neighborhood. There are further assumptions and conditions. It is assumed that the transition rules must be uniform, i.e. they must apply to every cell, state and neighborhood at all times, and that every change in state must be local, which in turn implies that there is no action-at-a-distance. There are conditions which specify the start and end points of the simulation in space and time which are called initial and boundary conditions respectively. Initial conditions apply to the spatial configuration of cells and their states which start the process, as well as the time at which the process begins. Boundary conditions refer to limits on the space or time over which the CA is allowed to operate.

To illustrate these principles, consider an elementary example. The most usual configuration of cells comprising a cellular automata is based on a regular twodimensional (2D) tessellation, such as a grid where the array of square cells are contiguous to one another. The simplest categorization of states is that each cell can be either alive or dead, active or inactive, occupied or empty, on or off, true or false, while the neighborhood within which any action changes the state of a cell is composed of the eight adjacent cells in the band around the cell in question, at the eight points of the compass. This is the so-called Moore neighborhood. A very basic rule for changes from cells which are ‘off’ to ‘on’ might be: if any cell in the neighborhood of any other cell in question is ‘on’, then that cell becomes ‘on’. In this way, cells which are off are turned ‘on’, those that are ‘on’ remain ‘on’. To show how this automata might change the state of an array of cells, we need an initial condition, a starting point for the configuration of cells, and also a stopping rule which in spatial terms is the boundary condition. We will assume that the temporal conditions are dictated by the spatial conditions in that once the process begins from time zero, it finishes when the spatial boundary is reached.
In this case, we fix the initial configuration as one active or live ‘on’ cell in
the center of a 100×100 square cellular array and start the process. Note how
easy and natural it is to represent this using pixels on a computer screen. In
Figure 5.1(a), we show a magnification of the grid of cells, a typical Moore
neighborhood around an arbitrarily chosen cell, and the central live cell which
starts the simulation. The process is particularly simple. At every time period,
each cell in the array is examined and if there is a live cell in its neighborhood,
then that cell is made live or switched on. Here, on the first time cycle, the cells
in the band around the center cell each have a live cell in their Moore
neighborhoods, and thus they are switched on. In the next iteration, the band
around this first band all have live cells in their neighborhoods and the same
occurs. A process of growth begins in regular bands around the initial seed site,
with the spatial diffusion that this growth implies clearly originating from the
operation of the rules on a system with a single seed site. In Figure 5.1(b), we
show this process of growth up to time t=40 when the 40th band around the seed
becomes live. We take this as the spatial boundary condition which in this case
is coincident with the temporal. Clearly the process could continue indefinitely
if the array of cells were infinite.
This kind of growth and diffusion is an analog to many systems. For example,
consider the cellular array as a grid of light bulbs all wired to those in their
immediate (Moore) neighborhood. The rule is that we switch one on when one
of those to which it has been wired has been switched on. If we begin by
switching the central bulb on, the process whereby all the bulbs are lit follows
the diffusion shown in Figure 5.1(b). If the central seed were a population which
grew in direct response to the immediate space around it, like a city, then the
process illustrated in Figure 5.1(b) might mirror urban development. These
kinds of example can be multiplied indefinitely for any simple growth process
from crystals to cancers. The morphology produced is very simple in that it is
one based on an entirely filled cluster whose form is dictated by the underlying
grid and by the influence of the neighborhood. We should also look at the
model’s dynamics. The number of cells occupied in this model can be predicted
either as a function of time or space. Calling the number of cells at the
horizontal or vertical distance r from the seed N(r), the cells occupied can be
predicted as N(r)=(2r+1)2. As r and time t are completely synchronized in this
automata, then N(i)=(2t+1)2. In Figure 5.1(c), we plot the number of cells which
are live at each distance and time, r=t=0, 1, 2, 3,…, which follows the
progression 1, 9, 25, 49,…, and so on.

This entry was posted in Articles, Gis-RS Books and tagged , . Bookmark the permalink.

Comments are closed.