Cellular automaton (pl. cellular automata, abbrev.

CA)
http://en.wikipedia.org/wiki/Cellular_automata
Discrete model: regular grid of cells (in N dimensions), each in one of a finite number of states, such as "On" and "Off" (in contrast to a coupled map lattice, i.e. logistic mapping). For each cell, define a neighborhood (usually including the cell itself). For example, the neighborhood of a cell might be defined as the set of cells a distance of 2 or less from the cell. Discrete time. An initial state (time t=0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed local rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. For example, the rule might be that the cell is "On" in the next generation if exactly two of the cells in the neighborhood are "On" in the current generation, otherwise the cell is "Off" in the next generation. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously, though exceptions are known.

Some relevant historic landmarks for CA

1940s: von Neumann's cellular automata (inspired by Stan Ulam, both at LANL). Two-dimensional, self-replicating universal copier and constructor. Neighborhood : only those orthogonal cells that touch are neighbors; and with 29 states per cell. Design known as the tessellation model, and called a von Neumann universal constructor.

1970s: Game of Life . Two-state, two-dimensional cellular automaton. Invented by John Conway, popularized by Martin Gardner ( Scientific American). Rules for cells: 2 black neighbors stays the same; 3 black neighbors it becomes black; all other situations it becomes white. Diversity of behavior, fluctuating between apparent randomness and order. Frequent occurrence of gliders (cells that move themselves across the grid). It can be arranged that the gliders interact to perform computations: the Game of Life can emulate a universal Turing machine. 1983: Stephen Wolfram published the first of a series of papers systematically investigating a very basic but essentially unknown class of cellular automata, which he terms elementary cellular automata. Wolfram suspects that complexity in nature may be due to similar mechanisms, and formulated the concepts of intrinsic randomness and computational irreducibility, suggesting that rule 110 may be universalproved by Matthew Cook in the 1990s. 2002: Wolfram published A New Kind of Science, arguing that the discoveries about cellular automata are not isolated facts but are robust and have significance for all disciplines of science.

Elementary cellular automata

Simplest nontrivial CA: 1D, two possible states per cell, cell's neighbors: adjacent cells. Neighborhood of 3 cells 23=8 possible patterns for a neighborhood. 28=256 rules. Standard

Rule for each pattern: whether the cell will be a 1 or a 0 in the next generation naming convention for 256 CAs: Wolfram code, a number from 0 to 255.

Wolframs classification
Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears Point attractors. Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local Limit cycles. Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely Chaotic. (but finite CA has to repeat itself eventually) Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways. Structured. Class 2 type stable or oscillating structures may be the eventual outcome, but the number of steps required to reach this state may be very large, even when the initial pattern is relatively simple. Local changes to the initial pattern may spread indefinitely. Wolfram has conjectured that many, if not all class 4 cellular automata are capable of universal computation. This has been proven for Rule 110, and Conway's game of Life.

Rule 90

http://mathworld.wolfram.com/ElementaryCellularAutomaton.html

Rule 30 cellular automaton

Rule 110 cellular automaton

Starting configuration consists of a 1 (at the top of each image) surrounded by 0's. Each row of pixels represents a generation in the history of the automaton, with t=0 being the top row. Each pixel is colored white for 0 and black for 1.

current pattern new state for center cell

111 110 101 100 011 010 001 000

current pattern new state for center cell

111

110 101 100 011 010 001 000

Rule 30: class 3 behavior: simple input patterns can lead to chaotic, seemingly random histories. Rule 110: class 4 behavior, which is neither completely random nor completely repetitive. It presents universality. Localized structures appear and interact in various complicated-looking ways. It has been the basis over which some of the smallest universal Turing machines have been built, inspired on the breakthrough concepts that the development of the proof of rule 110 universality produced.

Neighborhoods for 2D CA

Von Neumanns neighborhoods

Moores neighborhoods

Game of Life: black=alive, white=dead

Moores neighborhood. www.math.com/students/wonders/life/life.html
If an alive cell has fewer than 2 alive neighbors, it dies (loneliness) If an alive cell has more than 3 alive neighbors, it dies (overcrowding) If an alive cell has either 2 or 3 alive neighbors, it goes on living (happiness) If a dead cell has exactly 3 alive neighbors, it comes alive (reproduction). Otherwise it stays dead.

A puffer-type breeder (red) that leaves glider guns (green) in its wake, which in turn create gliders (blue) Emergent behavior?

Some CA applications: CA are easy to parallelize Biology

large grids possible

Patterns of some seashells, like the ones in Conus and Cymbiola genus, are generated by natural CA.

Plants regulate their intake and loss of gases via a CA mechanism. Each stoma on the leaf acts as a cell. Moving wave patterns on the skin of cephalopods can be simulated with a two-state, two-dimensional cellular automata, each state corresponding to either an expanded or retracted chromatophore. Threshold automata have been invented to simulate neurons, and complex behaviors such as recognition and learning can be simulated. Fibroblasts bear similarities to cellular automata, as each fibroblast only interacts with its neighbors.

Chemistry
The BelousovZhabotinsky reaction is a spatio-temporal chemical oscillator displaying geometric patterns such as concentric circles and spirals which can be simulated by means of a cellular automaton (Gerhardt & Schuster)

Computer processors
CA processors are physical (not computer simulated) implementations of CA concepts, which can process information computationally. Cell states are determined only by interactions with adjacent neighbor cells. No means exists to communicate directly with cells farther away. One such CA processor array configuration is the systolic array. Cell interaction can be via electric charge, magnetism, vibration (phonons at quantum scales), or any other physically useful means.

Miscellanea
Fire propagation, crowd behavior, (Printista et al., UNSL) etc.

Generalizations of the CA concept.

Use Genetic Algorithms to find rules which can lead to certain computations (see work by M. Mitchell et al., on emergent computation). Use grids other than rectangular/cubic: triangular, hexagonal, etc. They are still space oriented, not agentbased Rules can be probabilistic rather than deterministic. A probabilistic rule gives, for each pattern at time t, the probabilities that the central cell will transition to each possible state at time t+1. Sometimes a simpler rule is used; for example: "The rule is the Game of Life, but on each time step there is a 0.001% probability that each cell will transition to the opposite color. The neighborhood or rules could change over time or space. For example, initially the new state of a cell could be determined by the horizontally adjacent cells, but for the next generation the vertical cells would be used. The grid can be finite, so that patterns can "fall off" the edge of the universe. In CA, the new state of a cell is not affected by the new state of other cells. This could be changed so that, for instance, a 2 by 2 block of cells can be determined by itself and the cells adjacent to itself. Continuous automata. Instead of the rule and states being discrete (e.g. a table, using states {0,1,2}), continuous functions are used, and the states become continuous (usually values in [0,1]). The state of a location is a finite number of real numbers. Certain CA can yield diffusion in liquid patterns in this way. Continuous spatial automata have a continuum of locations. The state of a location is a finite number of real numbers. Time is also continuous, and the state evolves according to differential equations. One important example is reaction-diffusion textures, differential equations proposed by Alan Turing to explain how chemical reactions could create the stripes on zebras and spots on leopards. When these are approximated by CA, such CAs often yield similar patterns. There are known examples of continuous spatial automata which exhibit propagating phenomena analogous to gliders in the Game of Life.

Agent-Based Modeling (ABM)

http://en.wikipedia.org/wiki/Agent-based_model
What is an agent? A discrete entity with its own goals and behaviors, i.e. certain characteristics and attributes. Autonomous, with a capability to adapt and modify its behaviors Assumptions Some key aspect of behaviors and interactions can be described by a set of rules. These agents need not be rational (letters, many car drivers), but need to have some explicit set of actions which will follow (perhaps according to some probability distribution) from their current state (environment) and the state of other agents Complex social processes and a system can be built from the bottom up. Examples People, groups, organizations Animal or plants - Social insects, swarms Robots, systems of collaborating robots - Cars or airplanes. Agents are diverse and heterogeneous Rich behavior!
Grimm et al.,Pattern-oriented modeling of agent-based complex systems. Science 310, 987 (2005).

Agent-Based Modeling (ABM)

Off-shoot of complexity theory which explores complex systems; the whole is greater than the sum of the parts Agent-based simulation can capture "real life" economic/business systems on a computer by replicating the behaviors of heterogeneous participants and modeling the interactions between them. By simulating the nature of the interactions between the agents in a system, ABMs can become a learning tool for understanding a system under a variety of conditions. They are particularly useful for evolving/dynamic systems. Like other types of simulation techniques, they are meant to complement and enhance rather supplant traditional approaches

Spatially explicit model of animal behaviour

Sibly, R.M., Akakaya, H.R., Topping, C.J., O'Connor, R.J. (2005) Population-level assessment of risks of pesticides to birds and mammals in the UK. Ecotoxicology, 14, 863-876.
F M c) BEHAVIORAL STATE FM = FINDING MATE

Population dynamics emerge as result of local interactions, including pesticides. Dynamic landscape with crop rotation and weather-dependent plant growth

D Y YES Is it past breeding date (June 19th)? NO Is it past covey hopping time (June 1st)? NO Are you in a new covey now? NO

YES

NO Are you visiting some other covey?

Are coveys within 500m of you? NO

YES Jump to a new covey

YES Leave the covey

FL

YES Revoke visitors pass NO Join this covey Did you find mate in new covey?

Fly to a new area YES

Find Mate in area (500 m2)

Make your covey Does your mate have a territory? YES Did you find mate in your search area? NO

FM

G M

YES

NO

FO M

Adoption of Innovations: CA meets ABM

http://ccl.northwestern.edu/netlogo/models/community/

Parity Model There is only one rule, which all the adopters follow. The rule is that each cell looks at its four neighbours (the ones immediately to its left, right, above and below) if an odd number (that is, 1 or 3) have adopted, it adopts or turns 'on'. if an even number have adopted (2 or 4), the agent does not adopt or is off

Nigel Gilbert (2002 )

Software
(http://en.wikipedia.org/wiki/Comparison_of_agent-based_modeling_software)

Ascape (Java) www.brook.edu/dybdocroot/es/dynamics/models/ascape Netlogo

http://ccl.northwestern.edu/netlogo/models/community/ GIS compatible

RePast/Sugarscape REcursive Porous Agent Simulation Toolkit. GIS compatible

http://repast.sourceforge.net/ http://sugarscape.sourceforge.net/

SWARM www.swarm.org/

Sugarscape Was the First Comprehensive Computational Study of Artificial Societies

Sugarscape
Agents Have
Life, Death, Disease Trade: Sugar, Spice Wealth Sex, Reproduction Culture Conflict, War Externalities: Pollution

The Puebloan Agent Model Traces Household Movements As They Seek The Best Plots for Growing Maize
Researchers constructed the model by entering environmental data precipitation, water-table fluctuations etc. on a digitized map of the valley.
COPYRIGHT 2005 SCIENTIFIC AMERICAN, INC.

By A.D. 1170, the simulation shows the population clustering along the valleys northwestern margin, matching the actual pattern found by archaeologists. Although the simulated settlements are more aggregated than the real ones, the location of the largest settlement in the simulation is within 100 meters of the valleys biggest ruin, the Long House.

Kohler, Timothy A., George J. Gumerman and Robert G. Reynolds, Simulating Ancient Societies, Scientific American, July 2005.

Flexible Agent Based Simulation for Pedestrian Modeling on GPU Hardware (Paul Richmond)

www.dcs.shef.ac.uk/~paul
Richmond Paul, Coakley Simon, Romano Daniela (2009), "Cellular Level Agent Based Modelling on the Graphics Processing Unit", Proc. of HiBi09 - High Performance Computational Systems Biology, 14-16 October 2009, Trento, Italy