Cellular automata (CA)

Navigation:  Geocomputational methods and modeling > Geosimulation >

Cellular automata (CA)

Previous pageReturn to chapter overviewNext page

Cellular Automata (CA) are a specific type of a more general class of entities known as automata. Essentially, automata process information input to them from their surroundings, and their characteristics are altered according to rules that govern their reaction to those inputs. Typically CA are modeled as a 1-dimensional string of cells or a 2-dimensional rectangular lattice of cells. Cells are typically square, although other forms (e.g. hexagonal, irregular) are permitted.

John Conway was the first to popularize the study of 2D CA in the early 1970s, when he introduced a model called the Game of Life. The Game of Life has only two states for each cell (alive or dead, or 1 or 0) and three simple state transition rules: (i) survival: if a cell is ‘alive’ (i.e. its state is ‘true’ or ‘1’, for instance) and it has two or three alive neighbors it remains alive; (ii) reproduction: if a cell is ‘dead’, but has three alive cells within its neighborhood its state becomes alive, and (iii) loneliness (less than 2 neighbors) or overcrowding (more than 3 neighbors): the cell dies. Despite these simple rules, the Game of Life can produce a range of complex behaviors from different initial conditions. A sample Game of Life simulation is shown in Figure 8‑1, generated using NetLogo, authored by Wilensky (1998). For ongoing discussions of the Game of Life see: http://conwaylife.com/

A more complex example, known as the ‘Heatbugs’ model, is illustrated in Figure 8‑2. This example has also been generated using NetLogo (Wilensky, 2004; full details of the parameter settings are provided on the referenced website). In this simulation ‘bugs’ move around on a grid of square ‘patches’.

Figure 8‑1 Game of Life Model

A. 35% cell occupancy, randomly assigned

B. 10% cell density after simulation run; still evolving

clip0392

clip0393

Figure 8‑2 Heatbugs Model

clip0394

Source (both the above figures): http://ccl.northwestern.edu/netlogo/models/

The rules applied are: a bug may not move to a patch that already has another bug on it; each bug radiates a small amount of heat; heat gradually diffuses through the world; some heat is lost to cooling; each bug has an ‘ideal’ temperature it wants to be (a state of high ‘happiness’); the bigger the difference between the temperature of the patch where the bug is and the bug's ideal temperature, the more ‘unhappy’ the bug is; when a bug is unhappy, it moves. If it is too hot, it moves to the coolest adjacent empty patch; conversely, if a bug is too cold, it moves to the warmest adjacent empty patch. Altering the model variables and parameters impacts the behavior of the ‘bugs’ to a greater or lesser degree, but in most instances as the simulation runs the unhappiness curve declines to a stable state. For some settings this is not the case, for example when the space is very over-crowded.

Wolfram (1983) reinvigorated interest in the field when he published a paper discussing a typology of CA consisting of four classes. These classes are based on the dynamic behavior of CA and the patterns they generate, referred to as elementary cellular automata. These include, for the Game of Life example: (i) static patterns; (ii) oscillators (or periodic patterns); (iii) spaceships (patterns that repeat themselves but translated in space); and (iv) patterns that increase in population size (a range of different patterns and behaviors). The unexpected complexity of the resulting behavior from the rules Wolfram identified, led him to believe that complexity in nature may be due to similar behavior.

Cellular automata, as applied in geospatial analysis, may be characterized by the following key attributes: State variables; spatial framework; neighborhood structures; transition rules; and time. Each is discussed briefly below.

State variables: these are a set of attributes for an automaton, where its ‘state’ describes the automaton at a particular point in time. State variables can consist of virtually any data type, but are commonly binary (e.g. 0 or 1, blue or green, dead or alive, true or false, etc.). In many geospatial problems such limited states are too restrictive, and more complex states (including continuous variables) have been utilized. Examples might be land-use classifications, demographic taxonomies or surface attributes. Although the values of state variables typically alter as the simulation proceeds, some cell locations or attribute values may be regarded as immutable or immune to change after pre-defined transitions, and if changed to that state, remain fixed thereafter (Figure 8‑1).

Spatial framework:  CA models operate over a lattice of cells, which can be specified in any number of dimensions ― typically 2D in the case of geospatial problems. A lattice can be designed using congruent cells (i.e. as a grid of cells), or any other regular shape (e.g. hexagons or triangles). However, irregular geometries such as Voronoi polygons and graphs can also be used. A lattice can be constrained to a certain size, although this size must be considered carefully as the transition rule of an automaton located adjacent to a boundary may affect the automaton’s neighborhood. To resolve this issue, a lattice can be extended infinitely (within the specified dimension). However, a common alternative is to ‘loop’ a one-dimensional lattice back round to the initial cell, or ‘wrap’ a two-dimensional lattice around on both sides of the lattice so they no longer have an edge(s). Geometrically the latter option is equivalent to treating the lattice as a two-dimensional projection of a torus (a doughnut-shaped surface).

Neighborhood structures are localized areas around each automaton, from which inputs are obtained. Neighborhoods in CA are generally identical for each automaton. In rectangular grids these neighborhoods are commonly characterized as either ‘Moore’ (the cell in questions plus its eight surrounding cells),  or ‘von Neumann’ (the cell in question and its four cardinal neighbors, or extensions of these as highlighted in Figure 8‑3, adapted from Torrens, 2006) .

However, a number of variations on the CA formalism have been developed. For instance: CA combined with map algebra (Geo-Algebra; Takeyama and Couclelis, 1997); irregular or graph based cell networks (O'Sullivan, 2001 and 2002); partitions based on geographical phenomena (e.g. roads; Semboloni, 2000); or Voronoi tessellations (Shi and Pang, 2000). There is no practical reason, other than computational efficiency, to limit the shape or size of a neighborhood surrounding an automaton, although variations will obviously affect the behavior of the model. It is possible to generalize the notion of neighborhoods, to facilitate first-order, second-order (lagged) neighbors, alternative weightings, concepts of ‘action at a distance’ etc

Figure 8‑3 Moore and von Neumann neighborhoods

clip0395.zoom56

Transition rules determine how the state of an automaton changes over time. Automata use transition rules to determine their state, and evaluate the state of their neighbors at a particular point in time. The states of neighboring automata determine the state of each automaton in the next time step. This can remain the same or change. Traditionally, very simple deterministic transition rules were applied. More recently, models have been developed that experiment with much more complex rules, including probabilistic functions, maximization of utility, and the incorporation of complex constraints and inertia factors.

Time is considered as being comprised of discrete steps. Transition rules take effect at each step or increment of a discrete time interval. CA models are parallel or synchronous processors rather than serial or asynchronous processors. In parallel processing, all cells change state simultaneously at each time-step of the model clock. By contrast, in serial processing, the state of one cell has to be computed before another can begin.

In relation to modeling geographical processes, Tobler (1979) was one of the first to suggest using CA. This was followed by GIS research applying CA to a number of research questions (Couclelis, 1985). More recently CA has been used to develop numerous models of geographical processes. A few examples include: studies of bushfires (Li and Magill, 2001); deforestation (Messina and Walsh, 2000); earthquakes (McGinnis, 2001); rainforest dynamics (Alonso and Sole, 2000); and urban systems (Candau, 2000; Torrens, 2000; Batty, 2005; Batty, 2007).

CA provides a very good medium for simulation, which has been reflected in the volume of their use. The popularity of using CA for modeling has increased considerably as the cost of computer power has decreased. Their adoption has been merited because CA provide many of the building blocks essential for modeling: cells serve as storage units, representing specific elements of the model system in discrete units; lattices serve as larger constructs of these units, where neighborhoods specify how these units network and relate to one another; state variables represent an infinite range of attributes for characterizing the systems conditions; and finally, transition rules represent processes or events that alter the system dynamically over time. Unfortunately, the inability of cells to move is a significant weakness of the CA framework. This is particularly important when trying to model mobile entities, for example pedestrians or vehicles. The inability of an automaton to move within a CA frame has catalyzed interest in Agent-Based Modeling (ABM), which is the focus of Section 8.2.3, Agents and agent-based models, et seq. While CA models can be developed with an ABM toolset, a toolset designed specifically for development of CA will have difficulty modeling the range of behaviors and dynamics necessary for ABM.