Cellular Automata

Cellular automata (CA) are systems consisting of the following:

• A cellular space or otherwise discrete division of the world into independent entities; usually in GIS, this is assumed to be the cells of a raster grid plus the properties of the boundaries of the space.
• An exhaustive set of states into which each of the cells falls, such as urban/nonurban, or land use classes.
• An initial or starting configuration of the states over the space, often a map of a spatial distribution at some initial time period.
• A neighborhood for a cell, most commonly the cell's immediate neighboring cells.
• A set of rules that determines how states behave during a single time step.

Time in the system then takes the form of an ongoing series of steps. The model begins with the initial configuration and enacts the rules independently at each cell, updating all cells synchronously at the passing of each time step.

The origins of cellular automaton theory lie at the roots of computer science. In the 1940s, Stanislaw Ulam, working at the Los Alamos National Laboratory (LANL), studied crystal growth on a lattice network. John von Neumann, also at LANL, was working on the problem of self-replicating systems. Ulam suggested that von Neumann develop his robotic self-replicating system as a mathematical abstraction. Using two-dimensional cellular automata that had large numbers of states, Von Neumann proved mathematically that a pattern could be devised that would make endless copies of itself within the given cellular universe.

In the 1970s, a two-state, two-dimensional CA called the “Game of Life” was invented by John Conway and popularized by Martin Gardner, writing in Scientific American. “Life” has only two states and three rules but is able to create an extraordinarily rich set of forms, including the glider, a shape that survives by continuous movement. Also evident was the fact that entire systems of cellular automata could grow, extinguish themselves, or hover between chaos and order. Using cellular automata like Life, it was shown that it was possible to create the abstract system design called a “universal Turing machine,” Alan Turing's 1937 theoretical structure around which gate-based computing was designed.

Other than work on Life, however, little research was conducted on CA until 1983, when Stephen Wolfram began an exhaustive systematic investigation of the behavior of one-dimensional CA, formalizing the types. The emergent complexity of the behavior led many to hypothesize that complexity in natural systems may be due to such simple mechanisms.

In geography, cellular automata were seized on early by Tobler and later by Couclelis as both a good theoretical foundation for spatial process modeling and a good match for data assembled in GIS. Interest in CA rose in the 1990s as scientific interest in complex systems became more widespread, and CA were probably the simplest way to model such systems within computers. Much of the research took place at the Santa Fe Institute and overlapped into the geographic information science community after the 1996 Santa Fe GIS and Environmental Modeling meeting.

Notable in CA model development in geographical disciplines were Michael Batty's research group at the Center for Advanced Spatial Analysis, University College, London; Roger White's research at the Research Institute for Knowledge Systems in Maastricht, The Netherlands; and research by Itzak Benenson and others at Tel Aviv's Environmental Simulation Laboratory, in Israel. In urban simulation, the SLEUTH model, developed by Keith Clarke at the University of California, Santa Barbara, has been widely researched and applied, but is just one of several CA-based models used in planning and urban research applications.

...