Paper 28 HOW CELLULAR MODELS OF URBAN SYSTEMS WORK. (1. T H E O RY) Paul M. Torrens

Centre for Advanced Spatial Analysis University College London 1-19 Torrington Place Gower Street London WC1E 6BT Tel: +44 (0) 20 7679 1782 Fax: +44 (0) 20 7813 2843 Email: [email protected] http://www.casa.ucl.ac.uk http://www.casa.ucl.ac.uk/working_papers.htm Date: November 2000 ISSN: 1467-1298 © Copyright CASA, UCL. 2

Table of Contents

1

Introduction

2

Complexity

2.1 Emergence and complex adaptive systems

2.2 Artificial Life

2.3 Reductionism versus synthetics

2.4 Why treat cities as complex systems?

2.5 Criticisms of complexity

3 Basic cellular automata

3.1 Cellular automata, computers, and Turing Machines

3.2 One-dimensional cellular automata

3.2.1 Wolfram's cellular automata classes

3.3 Two-dimensional cellular automata

3.3.1 The Game of Life

3.3.2 Specifying CA as urban systems

3.4 The complex characteristics of cellular automata

3.4.1 Rank-size rules and power laws

3.4.2 Self-organization

3.4.3 Self-similarity and fractal dimension

4 Cellular automata for urban simulation

4.1 Advantages of using cellular automata for urban simulation

4.1.1 Weaknesses of traditional models

6SDWLDOLW\ 4.1.3 Decentralized approach 3

4.1.4 Affinity with geographic information systems and remote sensing 4.1.5 Attention to detail 4.1.6 Function and form 4.1.7 Dynamics 4.1.8 Infusion of complexity theory 4.1.9 Simplicity 4.1.10 Linking macro- to micro-approaches 4.1.11 Visualization 4.2 Modifying CA for urban applications 4.2.1 Cell-states 4.2.2 Lattices 4.2.3 Neighborhoods 4.2.4 Time 7UDQVLWLRQ UXOHV 4.3 Moving forward with cellular urban models 4.3.1 A taxonomy for cellular urban models 4.3.2 Explorations in spatial complexity 4.3.3 Dimensionality 4.3.4 Infusing theory 4.3.5 The meaning of rules 4.3.6 Generating new urban forms 4.3.7 Education and outreach 4.3.8 Hybrid models 4.3.9 Validating cellular urban models 4

5

Conclusions

References

5

1 Introduction Cellular automata (CA) models have been applied to urban systems with a recent fervor and have used to explore research questions in applications from location to urban morphology. This paper (part 1 of a two-part series) is intended to serve as an introduction to how cellular models of urban system actually work, on a theoretical level. Part 2 focuses on how to build urban CA models in a practical context. This paper begins by tracing the intellectual roots of urban CA in complexity (section 2) and computer science (section 3). In section 4, the paper begins to discuss urban CA. Section 4.1 outlines the advantages of using CA in urban studies. Section 4.2 describes how CA must be modified for urban applications. Section 4.3 then discusses some likely avenues for future development in the field. The paper concludes in section 5 with a discussion on where research at the Centre for Advanced Spatial Analysis at University College London is moving in the direction of agent-based and urban CA models.

2 Complexity 2.1 Emergence and complex adaptive systems The idea of complexity hinges on the notion of emergence. 1 In emergent systems, a small number of rules or laws, applied at a local level and among many objects or agents, are capable of generating surprising complexity in aggregate form. These patterns manifest themselves in such a way that the actions of the parts do not simply sum to the activity of the whole (Holland 1998). Essentially, this means that there is more going on in the dynamics of the system than simply aggregating little pieces into larger units. Although often ordered in their structure, the complex systems that are generated are not always just random or chaotic; recognizable and ordered features usually emerge. Additionally, these systems are dynamic and change over time and the dynamics often operate without the direction of a centralized executive. Examples of emergent systems abound. For

VFLHQFH RI HPHUJHQFH 7KLV LV WR VXFK DQ H[WHQW WKDW FRPSOH[LW\ VWXGLHV KDV EHHQ WHUPHG DV WKH

.UXJPDQ

6

example, the liquidity of water is more than a simple extrapolation of characteristics that can be attributed to individual water molecules, which have no liquid quality of their own (Krugman 1996). Similarly, in economics, the activity of individual market participants, trading without centralized control, often leads to aggregate outcomes that are relatively efficient, as efficient as if they were controlled. 2.2 Artificial Life The field of artificial life (or A-life) is concerned with human-made systems that exhibit life-like characteristics and behaviors. As well as exploring the possibility of creating artificial life, the field is focused on understanding natural life by attempting to abstract the fundamental dynamical principles that underpin biological phenomena--in short, this is a search for the rules that make life possible. A-life has close parallels with complexity studies. Life and living organisms represent some of the best examples of complex adaptive systems. Very simple genetic rules applied across many cells spawn advanced biological structures and organisms. The quest for artificial life is being pursued by replicating the complex dynamics of living systems in other physical media that make them accessible to new kinds of experimentation and testing (Sipper 1997). In this sense, it is hoped that some of the principles that govern real life can be uncovered in the process. An obvious candidate for such a laboratory is the computer. "The stuff of this life is non-organic matter, and its essence is information: computers are the kilns from which these new organisms emerge. Just as medical scientists have managed to tinker with life's mechanisms in vitro, the biologists and computer scientists of a-life hope to create life in silico." (Levy 1992, p.5) 2.3 Reductionism versus synthetics This detailed, bottom up approach to complexity is, in some senses, a relatively new way of approaching scientific inquiry. Much research in the social sciences, and particularly in geography, is challenged by a dichotomy between the individual (the household, a 7

person, and independent objects) and the aggregate (populations, collectives, and regions). In a spatial sense, researchers have been confronted with the dilemma of reconciling patterns and processes that operate and manifest at local scales with those at larger scales. This can be considered as a problem of ecological fallacy. An ecological fallacy occurs when it is inferred that results based on aggregate data cannot be applied to the individuals who form the aggregated group. A related problem in geography is the Modifiable Areal Unit Problem (Openshaw 1983). Of course, there are many examples in which aggregate forms may be extrapolated from the individual. However, reconciling the two often poses a challenge, particularly when processes that operate at the local level are interdependent, i.e., the actions of one individual depend on the actions of another individual. In these cases, an understanding of the processes that generate macro-scale patterns may not be easily gleaned by simply aggregating up from the individual; what is needed instead is an understanding of the interactive dynamics that link local-scale and larger-scale phenomena. 7KLV LV DQ DUJXPHQW RI UHGXFWLRQLVP YHUVXV V\QWKHWLFV 7KH UHGXFWLRQLVW DSSURDFK DQDO\]HV SUREOHPV E\ EUHDNLQJ WKHP GRZQ WR WKHLU FRQVWLWXHQW FRPSRQHQWV UHGXFLQJ WKHP WR PDQDJHDEOH SLHFHV DQG JDLQLQJ DQ XQGHUVWDQGLQJ RI WKHP LQ WKH SURFHVV ,Q VRPH FDVHV WKLV DSSURDFK ZRUNV TXLWH ZHOO DQG IRU PDQ\ SKHQRPHQD WKH WHFKQLTXH LV ZKROO\ DSSURSULDWH SDUWLFXODUO\ LQ VLWXDWLRQV ZKHUH WKH ZKROH LV WKH VXP RI PDQ\ VPDOO SDUWV +RZHYHU WKH UHGXFWLRQLVW DSSURDFK LV IODZHG LQ WKH UHVSHFW WKDW LW PD\ PLVV WKH HPHUJHQW SURSHUWLHV RI D V\VWHP WKRVH WKDW FRPH DV D E\SURGXFW RI WKH LQWHUDFWLYH G\QDPLFV RI LQGLYLGXDO HOHPHQWV ,Q PDQ\ LQVWDQFHV D V\QWKHWLF DSSURDFK PD\ EH PRUH DSSURSULDWH ,Q WKH FRQWH[W RI WKLV GLVFXVVLRQ LW LQYROYHV VWXG\LQJ SKHQRPHQD E\ H[SHULPHQWLQJ ZLWK VLPSOH UXOHV IRU EHKDYLRU DQG DOORZLQJ FRQVWLWXHQW FRPSRQHQWV WR LQWHUDFW G\QDPLFDOO\ XQWLO PDFUR VFDOH SKHQRPHQD HPHUJHіD SLHFLQJ WRJHWKHU UDWKHU WKDQ D GLVVHFWLRQ 7D\ORU 7KLV LV ZKDW KDSSHQV LQ RXU RZQ ERGLHV 7KH UXOHV HQFRGHG LQ RXU '1$ VSHFLI\ D VHW RI EHKDYLRUV IRU WKH GHYHORSPHQW RI RXU ELRORJ\ RYHU WLPH 7KH SURGXFWV RI WKDW LQWHUDFWLYH GHYHORSPHQW RQ D JHQHWLF OHYHO DUH PDFURVFDOH VWUXFWXUHVіRUJDQV V\VWHPV DQG WUDLWVіWKDW EDUH OLWWOH UHVHPEODQFH WR WKH RULJLQDO FRPSRQHQWV RI RXU '1$ 7KH FHQWUDO QHUYRXV V\VWHP IRU H[DPSOH LV VLJQLILFDQWO\ PRUH FRPSOLFDWHG WKDQ WKH DUUDQJHPHQW RI ELWV RI JXDQLQH DGHQLQH WK\PLQH DQG F\WRVLQH DORQJ D JHQRPH 5HVHDUFKHUV DUH LQFUHDVLQJO\ DGRSWLQJ V\QWKHWLF 8

DSSURDFKHV WR WKH VWXG\ RI SKHQRPHQD SDUWLFXODUO\ LQ VWXG\LQJ OLIH ZKHUH LW KDV EHHQ QRWHG WKDW "Reductionism does not work with complex systems, and it is now clear that a purely reductionist approach cannot be applied when studying life: in living systems the whole is more than the sum of its parts." (Levy 1992, p.8) These methodologies are also extending into other fields, including the social sciences and urban studies. 2.4 Why treat cities as complex systems? There are many reasons why we might transfer these ideas to our understanding and conceptualization of cities. From the local-scale interactive behavior (commuting, moving) of many individual objects (vehicles, people), structured and ordered patterns emerge in the aggregate, such as peak-hour traffic congestion (Nagel, Rasmussen and Barrett 1996) and the large-scale spatial clustering of socioeconomic groups by residence (Schelling 1978). In urban economics, large-scale economies of agglomeration and disagglomeration have long been understood to operate from local-scale interactive dynamics (Krugman 1996). Also, cities exhibit several of the signature characteristics of complexity, including fractal dimensionality and self-similarity across scales, selforganization, and emergence (see Batty and Longley 1994; Allen 1997; Portugali 2000; as well as section 3.4 of this paper). 2.5 Criticisms of complexity Complexity studies are in their infancy as an academic discipline, but they have drawn a relatively heavy degree of criticism recently, perhaps as a by-product of the attention afforded the field and its pioneers in popular science journalism and publishing. In particular, there have been accusations that a gap exists between the `rhetoric' of complexity studies and reality (Horgan 1995). This is really a multifaceted reaction 9

against complexity studies. The field has been criticized for harboring a `reminiscence syndrome'. Also, there has been a backlash against the claim of some complexity researchers, particularly those at the flagship Santa Fe Institute, 2 that complexity can offer a unified theory of everything. Moreover, there have been growing concerns that the techniques the field is offering up for the study of complexity are even more complicated than the phenomena they purport to represent; that researchers are moving from complexity to perplexity (Horgan 1995). What was once thought to be the great strength of complexity has turned into one of its chief criticisms. The intuitive sense that the idea of complexity conjures owes a great deal to the idea of reminiscence: "Look, isn't this reminiscent of a biological or physical phenomenon." (Jack D. Cowan, co-founder of the Santa Fe Institute, quoted in Horgan (1995)). Reminiscence criticisms accuse researchers of yielding to the "seductive syllogism" of complexity, particularly in the use of computer-based models to explore complexity (Horgan 1995). Just because the dynamic activity displayed in a computer model resembles a real-life process, does not necessarily mean that it is a good model for that phenomenon (Horgan 1995). (Similarly, just because the patterns that a CA generates look like cities, that does not mean that CA are always appropriate for representing specific urban phenomena.) Researchers may assume that reminiscence alone is justification for a modeling paradigm, when really that reminiscence may be accidental, coincidental, or may be a construct of the researcher's own ideas. Others would defend themselves by countering that while complexity may be guilty of reminiscence, the mechanisms of processing in naturally appearing complex systems are very like those in computers, and particularly in CA (Wolfram 1994). One of the goals of complexity studies is to abstract simple features of complex behavior that are common across a wide-range of systems, and perhaps to devise universal laws of complex systems from those common principles. As Wolfram (1994) puts it, "To discover and analyze the mathematical basis for the generation of complexity, one must identify simple mathematical systems that capture the essence of the process." (p. 411). ґZKHUH FRPSOH[ SHRSOH VWXG\ FRPSOH[ WKLQJVµ +RUJDQ 10

Wolfram goes on to speculate that universal laws analogous to the laws of thermodynamics might be discovered for complex systems. However, there has been a backlash against the claims for a unifying theory of complex systems. Contrast Wolfram's sentiments with those of John Casti, expressed in the introduction to his own book on simulation and complexity: "it's really a pity that this book is not crammed full of mathematical arcana, since if it were it could only mean that we had something that looked like a decent theory of complex systems. In fact, we are not even close." (Casti 1997, p. ix). There are two justifications for doubting our ability to arrive at universal laws of complexity, both of which center on the use of computers to explore complex phenomena. The first relates to the fact that some problems are not computable. The second centers on a belief that complexity models may be more complex in themselves than the phenomena that they are trying to simulate. By their very nature, computing machines are rule following devices; yet, there is no reason to believe that all processes in the natural world are rule-based (Casti 1997). Some processes in the natural and physical worlds, and many complex systems, may not be computable. In geography and urban planning, the introduction of simulation techniques from complexity studies was heralded with suspicion. In particular, researchers feared that tinkering with the simple formalisms of techniques such as CA in order to better tailor them to simulating geographic phenomena might yield model structures as complicated as the realities that they were designed to represent (Couclelis 1985; O'Sullivan and Torrens 2000; Torrens and O'Sullivan 2000). In a true simulation model, the inputs and states of the real-world object must be encoded in the states of the simulated phenomena. Consequently, the simulated phenomena will have to have more states than the real-world object, and thus the simulation must by necessity be more complicated than the thing(s) being simulated (Casti 1997). The danger here is that in designing accurate models of complex systems, we may end up with simulations that can be no better understood than the systems that they simulate. The criticisms of complexity are appropriate in many instances. Yet, to reject complexity outright at this stage would be unwise; the field has a lot to offer. Really, the important 11

message to understand here is that complexity has relevance to many systems, but not to all. 3 This is also true in the context of the city. Many urban systems lend themselves to the complexity approach, but others--especially those that operate from the top-down-- really don't. Nevertheless, the approach does provide a rich environment for understanding how systems work dynamically and interactively, as well as offering some innovative techniques for simulating such phenomena. 3 Basic cellular automata By their very nature, CA are an excellent vehicle for exploring complexity. The finite state machines4 that form the engines of CA dynamics are capable of interacting in parallel at very local scales. Through the recursive interactive dynamics of this behavior across many machines, CA can generate large-scale, and often ordered, patterns at mesoand micro-scales through emergence (see section 3.2 and the discussion of Wolfram CA classes). Under certain specifications, CA have proven to support universal computation (see section 3.1). Section 3 explores the formulation of the basic CA model and its history. 3.1 Cellular automata, computers, and Turing Machines CA were first devised by John von Neumann (originator of game theory, and pioneer in set theory, quantum mechanics, and the specification of electronic computers) and Stanislaw Ulam (who worked on Monte Carlo simulation and the hydrogen bomb (as part of the Manhattan Project with Edward Teller) and was influential in set theory and number theory) in the 1940s as a framework for investigating the logical underpinnings $OWKRXJK LQ PDQ\ FDVHV \RX KDYH WR VLIW WKURXJK D ORW RI K\SH WR JHW WKLV PHVVDJH $ ILQLWH VWDWH PDFKLQH LV D VLPSOH W\SH RI DXWRPDWRQ D GHYLFH WKDW UHDGV DQ LQSXW VWULQJ DQG SURFHVVHV WKDW LQIRUPDWLRQ $W DQ\ JLYHQ PRPHQW D ILQLWH VWDWH PDFKLQH LV LQ RQH RI D ERXQGHG VHW RI VWDWHV ZKLFK FKDQJH DV LQSXW LV UHDG DQG SURFHVVHG E\ WKH PDFKLQH 7KH QHZ VWDWH LV GHWHUPLQHG E\ WKH FXUUHQW VWDWH RI WKH PDFKLQH DV ZHOO DV WKH LQVWUXFWLRQV UHDG IURP WKH VWULQJ 12

of life. "One can say that the "cellular" comes from Ulam and the "automata" comes from von Neumann". (Rucker 1999, p.69) Von Neumann and Ulam were interested in exploring whether the self-reproducing features of biological automata could be reduced to purely mathematical formulations--whether the forces governing reproduction could be reduced to logical rules (Sipper 1997). The idea for the CA owes a great deal to Alan Turing's specification of a Universal Turing Machine in the 1930s. The Universal Turing Machine was a hypothetical automaton (von Neumann went as far as to build computers on these principles), a machine with limited specifications and ranges of action that was capable of computing anything that could be computed: the Universal Turing Machine was capable of universal computation. A system may be regarded as a universal computer if, given a suitable initial program, it is capable of implementing any finite algorithm through its evolution over time, i.e., that it is capable of producing a working copy as complicated as itself, and the means to make further copies. A universal computer need only be reprogrammed, not rebuilt, to perform any calculation that is thrown at it (Wolfram 1994)5. ґ+H ILJXUHG RXW WKDW PDWKHPDWLFLDQV XQOLNH FDUSHQWHUV RQO\ QHHGHG WR KDYH RQH WRRO LQ WKHLU WRROER[ LI LW ZHUH WKH ULJKW VRUW RI WRRO 7XULQJ UHDOL]HG WKDW LW VKRXOG EH SRVVLEOH WR EXLOG D PHWDPDFKLQH WKDW FRXOG EH UHFRQILJXUHG LQ VXFK D ZD\ WKDW LW ZRXOG GR DQ\ WDVN \RX FRXOG FRQFHLYDEO\ GR ZLWK LQIRUPDWLRQ ,W ZRXOG EH D SURWHDQ GHYLFH WKDW FRXOG WXUQ LQWR DQ\ WRRO \RX FRXOG HYHU QHHG /LNH D SLSH RUJDQ FKDQJLQJ LQWR D GLIIHUHQW LQVWUXPHQW HYHU\ WLPH \RX KLW D SUHVHW EXWWRQµ 6WHSKHQVRQ S The Physical Church-Turing Hypothesis hypothesized that a Universal Turing Machine could duplicate the functions of both mathematical machines and those of nature (Levy 1992). The specifications for the Universal Turing Machine formed the principles on which CA were founded, as well as germinating the seeds of modern digital computers. $OO JHQHUDOSXUSRVH GLJLWDO FRPSXWHUV DUH IRU SUDFWLFDO SXUSRVHV XQLYHUVDO FRPSXWHUV PHFKDQLFDO DGGLQJ PDFKLQHV DUH QRW :ROIUDP 13

It is worth examining the specification of the Turing Machine as a preface to discussions about the parameterization of urban CA in later sections of this paper. The Turing Machine consisted of an infinitely long tape ruled off into sections. Each section of the tape contained a bit of information: a symbol with either a zero or a one. The Machine housed a scanning head that was capable of being in any of an n set of configurations or states (in this example the set is binary). Time was discrete in the world of the Universal Turing Machine, it moved along in chunks as large or as small as you liked. Between time steps, the tape head would examine its external world. Then, after consulting a rule table (see below), it would consider the information that it encountered on the tape, as well as the current state of the tape head, and from this it would determine its action in the next time step. The control mechanism on the tape head served as a finite state machine. The task that the tape head performed was to move along the infinitely long tape. When the head reached a section of tape, it could perform one of several actions (Casti 1997): (a) Change the current state of the head to another state (b) Retain the current state of the head (c) Print 1 on the section of tape (d) Print 0 on the section of tape (e) Move left along the tape by one square (f) Move right along the tape by one square (g) Halt movement From these simple rules and basic parameterizations, the Turing Machine was, hypothetically, capable of performing universal computation and thereby capable of selfreproduction. 14

3.2 One-dimensional cellular automata What exactly is a cellular automaton? An automaton essentially comprises a finite state machine (a Turing-like machine) that exists in some form of tessellated cell-space. The term automaton refers to a self-operating machine, but one of a very distinct nature: "An automaton is a machine that processes information, proceeding logically, inexorably performing its next action after applying data received from outside itself in light of instructions programmed within itself." (Levy 1992, p. 15) CA differ in an important way from Turing Machines: CA are parallel processors rather than serial processors. In parallel processing, more than one particular process is active at any given time. In serial processing, on the other hand, one stage in the process is computed before the next starts; only one stage is active at any given time. We can consider several elements that comprise an elementary cellular automaton: (a) The space on which the automaton exists (its lattice) (b) The cell in which the automaton resides, which contains its state(s) (c) The neighborhood around the automaton (d) Transition rules that describe the behavior of the automaton (e) The temporal space in which the automaton exists Lattice: The lattice of CA comprise the space in which the CA exist and evolve over time. In an elementary CA, this lattice is one-dimensional (as in figure 1). However, lattices can be n-dimensional. CA designed for geographic purposes are generally defined in two-dimensions,6 while lattices of several dimensions have been defined in other ,W ZRXOG VHHP UHDVRQDEOH WKDW &$ GHVLJQHG WR VLPXODWH FLWLHV ZRXOG EH GHILQHG LQ WKUHHGLPHQVLRQV FRQVLGHULQJ WKDW PXFK RI WKH EXLOW HQYLURQPHQW RI FLWLHV H[WHQGV LQ WKUHH GLPHQVLRQV +RZHYHU VXFK PRGHOV KDYH \HW WR EH ZLGHO\ GHYHORSHG PRVW OLNHO\ EHFDXVH RI WKH GLIILFXOW\ RI GHVLJQLQJ EXLOGLQJ DQG UXQQLQJ &$ ZLWK GLPHQVLRQV JUHDWHU WKDQ WZR 7KH RQO\ H[DPSOH DW WKH WLPH RI ZULWLQJ ZDV WKH 6HPERORQL PRGHO 6HPERORQL 15

disciplines. In an elementary CA, lattices are defined in a regular fashion, often as gridsquares or other combinations of regular shapes (hexagons and triangles have also been used).7 In theory, CA lattices can extend to infinite proportions within any given dimensionality, but for practical purposes some clever tricks are played to define the edges of CA lattices. Most commonly, CA are designed to wrap around on themselves, corresponding to a circular arrangement for one-dimensional CA, and a torus for twodimensional CA (figure 2). Figure 1. One-dimensional cellular automata $JDLQ WKH DVVXPSWLRQ RI D UHJXODU JULG IRU FLWLHV LV XQUHDVRQDEOH DQG XUEDQ &$ KDYH EHHQ PRGLILHG WR RSHUDWH RQ LUUHJXODU ODWWLFHV VHH 2 6XOOLYDQ IRUWKFRPLQJ 16

Cell-states: CA cell-states characterize the attributes of finite state machines in a CA lattice. In this sense, they constitute a description of the elemental building blocks and attributes that comprise a CA. In a Turing Machine, states are defined in a binary fashion, as consisting of symbols representing zero or one. Von Neumann, in his CA, provided for the existence of 29 cell states. Neighborhoods: A neighborhood comprises the localized region of a CA lattice, from which the finite state machine (cell) draws input. This input forms the information collected from a scan of cells within the neighborhood template (Langton 1992). A neighborhood consists of a CA cell itself and any number of cells in a given configuration around the cell. Transition rules: Transition rules are the real engines of change in a CA. They specify the behavior of cells between time-step evolutions, deciding the future conditions of cells based on a set of fixed rules that are evaluated on input from neighborhood templates. In a strict CA, these rules are applied uniformly across cells in a synchronous fashion8. Transition rules are generally formulated as IF, THEN, and ELSE statements that rely on input from a neighborhood template to evaluate their results. In this sense, transition rules replace traditional mathematical functions in models with rule-based procedures (Batty 1997a). Batty (1997a) argues that there are advantages to this methodological approach: rules reflect how real systems operate; also, they enable complicated systems to be reduced to the simple components that drive their dynamics. 7KH DVVXPSWLRQ WKDW WKH ODZV JRYHUQLQJ V\VWHP G\QDPLFV DUH XQLYHUVDO UHJDUGOHVV RI FRQWH[W LV XQUHDOLVWLF IRU PDQ\ VFHQDULRV RI FRXUVH ,Q DQ XUEDQ V\VWHP IRU H[DPSOH ODQG XVH ]RQLQJ ODZV PD\ EH KLJKO\ GLIIHUHQWLDWHG LQ WKHLU GLVWULEXWLRQ 9LFKQLDF 7DPD\R DQG +DUWPDQ KDYH H[SHULPHQWHG ZLWK QRQXQLIRUP WUDQVLWLRQ UXOHV DQG 6LSSHU KDV GHVLJQHG UXOHV WKDW FKDQJH DV &$ HYROYH PXFK DV D JHQHWLF DOJRULWKP ZRXOG 0LWFKHOO 17

Time: As with Turing Machines, time in CA is discrete. Time proceeds in iterative steps of whatever length the model designer cares to conjure. The temporal evolution of cells destroys the independence of initial cell states; instead prompting correlation between cell states at separated sites (Wolfram 1994). As a result, CA can generate structured patterns through their evolution. Figure 2. A wire frame rendering of a regular graph arranged as a torus (O'Sullivan 2000) In figure 1, we see a one-dimensional CA (its lattice extends in only one dimension) at time t and time (t + 1) in its evolution. The lattice consists of 13 finite state machines (cells), distributed continuously in a one-dimensional space. Each cell state can be in one of two states, either "empty" (depicted by the color white) or "full" (depicted by the color black). Each cell is driven by a transition rule table, which governs the state of the cells in 18

each time-step. In the example presented in figure 1, there are two time-steps in the life cycle of the CA. In the first time step, each cell draws input from its neighborhood, upon which a cell's finite state machine can base its behavior in the nest time step. Part A of the transition rule picks out those cells in the lattice that are "full". Part B of the rule asks the "full" cells to scan their two-cell neighborhood, both to the left and to the right. If that scan discovers that neighboring cells in its right-hand side neighborhood are "empty", then the "full" cell is directed to `move' (really, adjacent cells exchange state values) one cell to the right along the lattice in the next time step. We could also formulate the CA using mathematical notation. For an individual cell in the CA, the notation is:

( ) sit+1 =

f

si

t

,

I

h jt

(i)

Where si is the state of a given cell i at time (t + 1). f ( ) describes a functional relationship, where si and the input from a neighborhood I (of neighborhood size h) in the vicinity of cell j at time t influence cell state transition in the next time step. The entire CA may be described in notation as:

( { }) {St+1}=

f

{St }

I

h t

(ii)

In the above equation the notation is identical as before, except the letter S appears

{ } (without a subscript i), denoting the set of all states of cells in the CA, and

I

h t

refers to

the set of all input neighborhoods.

The number of possible configurations of the lattice is X n : the number of possible cell states (X), raised to the power of the number of cells in the lattice (n). For the example demonstrated in figure 1, there are two possible cell states ("full" or "empty"), and 13 cells in the lattice. That corresponds to 213 , or 8192 possible configurations of the lattice.

19

3.2.1 Wolfram's cellular automata classes The mathematician Stephen Wolfram experimented heavily with CA, exploring the range of possible configurations that CA could evolve to with simple parameterizations and basic rule sets. Wolfram discerned a broad typology of CA that consisted of four broad classes based on their dynamic behavior and the patterns that they generated (reported in Wolfram 1994 and also described in Langton (1992)). Class I CA: Evolve (or emerge!) to limit points: fixed homogenous states that exhibit the maximum possible order both at local and global scales. In a CA with just two possible states, zero and one, this results in a CA that evolves to a condition where all cells have a value of zero. Class II CA: Evolve to limit cycles: simple separated periodic structures that exhibit global order, but not of a maximal variety. Commonly the pattern of their evolution looks like a set of vertical stripes or cyclical "railroad" patterns. Class III CA: Evolve to chaotic aperiodic structures: patterns that exhibit maximal disorder at both local and global scales. The pattern that these CA generate need not necessarily be random; often they are self-organizing. Class IV CA: Evolve to complex structures, some of which are very long-lived. In some cases their complexity suggests that they may be capable of universal computation (Wolfram 1994). 3.3 Two-dimensional cellular automata Two-dimensional CA do not differ radically from one-dimensional CA in formulation; their lattice simply extends in an additional dimension. However, in terms of their simulation capacity, two-dimensional CA differ greatly from their one-dimensional 20

counterparts. If we were to extend our CA example from figure 1 into a second dimension, we would have a situation where the number of possible cell states remains the same (two), but the number of lattice sites grows from 13 to 132 , or 169. The number of possible configurations our lattice can now take on grows by orders of magnitude still: the number of possible cell states raised to the power of the number of possible lattice sites, 2169 , a significantly larger number than the 8192 possible configurations of the onedimensional CA9. Such a large range of possible configurations allows for the generation of very many scenarios, using very simple modeling frameworks. Of course, intuitively, running two-dimensional CA models makes more sense than one dimension in many examples, including urban applications. The two most commonly defined neighborhood templates for a two-dimensional CA are the Moore neighborhood and the von Neumann neighborhood (figure 2), although researchers have tinkered heavily with neighborhood template sizes and configurations.

,I ZH ZHUH WR H[WHQG RXU &$ ODWWLFH HYHQ IXUWKHU LQWR D WKLUG GLPHQVLRQ ZH ZRXOG H[WHQG WKH UDQJH RI

2 SRVVLEOH FRQILJXUDWLRQV WR

2197

21

Figure 3. Two-dimensional cellular automata 22

3.3.1 The Game of Life Perhaps the most famous instance of a two-dimensional CA (indeed, of any CA) is the mathematician John Conway's Game of Life. The Life CA was developed by Conway to explore the simplest possible configuration for a universal computer. Conway spent some time tinkering with different parameterizations and rule sets, finally settling on the CA known as Life. Its specifications are very simple. Only two possible states are permitted in the game of life: alive and dead. The lattice of the CA is a square grid of infinite dimensions and the lattice turns in on itself to form a torus. The neighborhoods of the Life CA are specified as Moore neighborhoods, consisting of nine cells. The transition rules are straightforward. There are three rules that govern dynamics (`life') in the game: birth, death, and survival. The birth rule specifies that a cell will be born (i.e., that it will transition from a state of `dead' to `alive') if it has three `alive' cells in its nine-cell neighborhood. Cells die (they transition from a state of `alive' to one of `dead') from overcrowding between time steps if they have more than three live neighbors. Cells die by exposure if there are fewer than two live neighbors. The survivor rule specifies that a live cell should remain alive in the next time step if it has either two or three live cells in its neighborhood. Birth rule if [cell state is "dead" in time t] and if [the number of cells with state "alive" in neighborhood 3] then [set state of cell to "alive" in time (t+1)] end 23

Death rule if [cell state is "alive" in time t] and if [the number of cells with state "alive" in neighborhood >3] or [the number of cells with state "dead" in neighborhood < 2] then [set state of cell to "dead" in time (t+1)] end Survival rule if [cell state is "alive" in time t] and if [the number of cells with state "alive" in neighborhood >2<3] then [set state of cell to "alive" in time (t+1)] end Once the game is run repeatedly with these simple parameterizations and rules governing play, persistent features begin to manifest themselves in the patterns that the game produces. In order to demonstrate that his CA was capable of universal computation, Conway needed a configuration within the game that could generate moving configurations of stable patterns. The search for such a configuration was opened to the public when Conway issued a challenge in Martin Gardner's column in the journal Scientific American; he described the problem and offered a cash prize for the first person to demonstrate the existence of such a configuration. The prize was claimed by R. Wilson Gosper at the Massachusetts Institute of Technology, who's team had coded a version of the Life CA into a computer and found `glider guns' that were capable of firing a steady stream of wandering gliders (Levy 1992). Essentially, the MIT team had demonstrated that the Life CA was capable of generating a machine that could, in turn, reproduce copies of itself that were as complicated in their structure. 24

Figure 4. The four evolving stages of glider evolution under the Life CA rules Figure 5. Glider movement, diagonally from the upper left to lower right of the lattice. 3.3.2 Specifying CA as urban systems It is relatively easy to generalize the basic specification of CA to represent urban systems. The cell space on which a cellular automaton operates might be considered equivalent in 25

an urban sense to an environment, a landscape, or a territory. The CA lattice can also be generalized to represent urban spatial structures, networks of accessibility, or the physical infrastructure of the city (particularly when the lattice is specified as an irregular tessellation). CA cells operate just like the pixels that comprise a television screen, except that each cell is capable of processing information, as well as visualizing its state. Cells can correspond to any zonal geography within a city: parcels of land, administrative boundaries, traffic analysis zones, etc. The cell state offers a flexible framework for encoding attributes of a city into the simulation model. In an urban context the cell state can be made to represent any attribute of the urban environment, e.g., land use (residential or commercial), density (high density or low density), land cover (forested or concrete), etc. Neighborhoods in urban CA represent spheres of influence or activity within the city, e.g., market catchment areas, the walking radius of individual pedestrians, the commuting watershed, etc. The rules of a CA drive the dynamics of change in the model. CA rules can be devised to mirror how phenomena in the real world operate, and can then be coded as algorithms within the simulation. 3.3.2.1 An urban example: Schelling's segregation model Schelling's model of social segregation was developed in the 1970s (Schelling 1969, 1978). It is not strictly an urban model, although it has relevance to cities. It is not strictly a CA either! Yet, in conceptual terms, it is an excellent example of how urban CA operate. Schelling set out to demonstrate the hypothesis that "the interplay of individual choices, where unorganized segregation is concerned, is a complex system with collective results that bear no close relation to individual intent." (Schelling 1969, p.488) He was concerned with phenomena of large-scale spatial segregation of socioeconomic-- particularly ethnic--groups in urban America. "The demographic map of almost any American metropolitan area suggests that it is easy to find residential areas that are all white or nearly so and areas that are all black or nearly so but hard to find localities in which neither whites nor nonwhites are more than, say, three-quarters of the total." (Schelling 1969, p.488) 26

Schelling was interested in finding out why ethnic groups did not live in spatially integrated areas of the city. Schelling proposed a simple model to test various hypotheses about the mechanisms driving metropolitan segregation. Conceptually, this moDel Closely resembles a two-dimensional CA. Cells could adopt three color types (states): (in our example these are) blue10 (`blue people'), white (`white people'), or grey (vacant sites without population). Each cell carried an additional state that denoted the `contentedness' of its population. Residents of a given cell were content with their location so long as the majority of their neighbors (in a Moore neighborhood) were the same color. If the residents were not content they moved to a new location in the next time step (i.e., the color of the cell transitioned to a new state). If a CA is devised along these principles, with these simple structural parameters, a simple rule set, and a randomly distributed pattern as a seed condition for the model (figure 5), you find that after several iterations a pattern of distinct segregation will emerge. Blues will cluster into large homogenous groups, with whites similarly arranged in their own independent clusters (figure 6). Extrapolating these conditions to a real world context, you end up with a divided city in which there is strong spatial segregation. Color-exclusive clusters develop even though people really don't mind living in integrated neighborhoods. This relates, theoretically, to the idea of the `tipping balance': a threshold, above which, a system shifts to a new phase and may settle in a new and distinct equilibrium. Such phase shifts are among the common characteristics of complex adaptive systems. 7KH\ PD\ DSSHDU DV GDUN JUH\ LI \RX DUH YLHZLQJ WKLV SDSHU LQ PRQRWRQH 27

Figure 6. Initial random seed condition for a Schelling segregation model (Source: Yale Wang's Schelling model; source code is at . KWWSZZZFVFDOWHFKHGXa\DOHHFVHJUHJDWLRQ 3.4 The complex characteristics of cellular automata CA are a good mechanism for exploring emergence in complex adaptive systems. They are dynamic and fine-scaled in resolution. Also, the use of neighborhoods is a good encapsulation of interaction amongst system elements. Not surprisingly, CA and the patterns that they generate also exhibit many of the signature trademarks of complex adaptive systems, such as phase shifts, power laws, self-organization, self-similarity, and fractal dimensions. 28

Figure 7. The Schelling segregation model after several iterations (Source: Yale Wang's Schelling model; source code is at http://www.cs.caltech.edu/~yale/ec126/segregation/). 3.4.1 Rank-size rules and power laws Rank-size rules or power laws (as they pertain to complexity and CA) link the frequency of occurrence of phenomena to their unit size with linear, consistent relationships across scales. The distribution of cities of various sizes of population follows a rank-size rule (Krugman 1996). There are many small-sized cities in the world, but only a few large cities. Of course, this makes intuitive sense, but what is remarkable is that the relationship between the population size of a city and the frequency of occurrence of cities of certain sizes is linear. The distribution of city sizes follows a power law: the number of cities whose population exceeds some size P is linearly proportional to the value of P raised to some negative power. this relationship, when plotted for the United States, for example, on a logarithmic scale, is almost perfectly linear, with an exponential value of 1. 29

Power laws are common in CA. The clustering of cell states, for example, often conforms to rank-size rules. Often, patterns in CA will display a relatively small number of regions of the lattice in which cell states are homogenous. In many cases this contrasts with a comparative abundance of medium-size and lower-sized clumps. Figure 8. Illustration of Zipf's rank-size rule for the United States (adapted from Krugman, 1996). 3.4.2 Self-organization The second law of thermodynamics in physics contends that closed systems progressively degrade from an initial structure, which may be organized, towards a state of maximum entropy, or disorder. In other words, things tend to disintegrate over time. Of course, lots of natural systems also tend towards disorder, but other, often open systems (and particularly biological systems) show the reverse tendency--they generate structure rather than disorder as they develop over time, even when starting from disordered or even structureless initial states (Wolfram 1994). Such systems may be regarded as self- 30

organizing. Self-organization in dynamic systems refers to the tendency for system structures to spontaneously develop ordered patterns, often on a large-scale (Krugman 1996). Self-organization can occur in both spatial and temporal dimensions. The organization of central places is a good example of spatial self-organization (e.g., the ordering of human settlements into city-systems with a central city at the core of a swirl of edge cities and satellite settlements), while the formation of investment cycles into booms and slumps in equity markets is an example of temporal self-organization. Often, self-organization is one of the characteristics of complex adaptive systems and also of CA. As we saw in section 3.2.1., some of Wolfram's CA classes exhibited a level of selforganization independently of the rules that governed their behavior. 3.4.3 Self-similarity and fractal dimension As CA develop over time, the patterns that they generate often exhibit a degree of regularity in structure. Often these regularities are self-similar (figure 9). With selfsimilarity, portions of the evolved pattern of a structure are indistinguishable from the whole; essentially, the structure of the pattern is scale-independent (Wolfram 1994). Often these patterns are fractal and can be characterized using fractal dimensions. In cities, as well as in CA, the recursive local-scale dynamics that generate well-defined geometrical structures in two-dimensional space often generate similar structural geometries at higher scales as the structure grows and changes (Batty and Longley 1994; Batty 1997b). In particular, cities often exhibit a bi-fractal structure, characterized by two or more zones (figure 10). Inner zones--the well-developed core of a typical monocentric city, for example--can generally be characterized with a fractal dimension of 1.92 (Batty and Longley 1994). This means that they have a dimensionality that lies between one (a linear city) and two (a city completely occupying a plane). Inner cores often comprise compact built environments. In terms of system dynamics, transition is stable and ordered; the system is well organized and the urbanization process is essentially complete (White, Engelen and Uljee 1997). Outer fringe zones, on the other hand, have a characteristic fractal dimension of just greater than one--they are sprawling (Torrens and Alberti 2000). In such examples system dynamics are still quite stochastic, as 31

urbanization is still underway (White, Engelen and Uljee 1997). This bifractal pattern also characterizes cities on lower-level scales, for example at the level of individual land uses (Batty and Longley 1994). Many of the structures that CA generate also exhibit selfsimilarity and are fractal in dimension. Figure 9. A fractal from the Mandlebrot Set, demonstrating self-similarity (source: Torrens and Alberti (2000)). 32

Figure 10. A fractal from the Mandlebrot Set, illustrating how fringe urbanization might be conceptualized in a fractal manner (source: Torrens and Alberti (2000)). 4 Cellular automata for urban simulation CA offer an interesting and innovative approach to the study of urban systems. In recent years there has been a prolific application of CA models to urban systems. CA models have been employed in the exploration of a diverse range of urban phenomena, from traffic simulation and regional-scale urbanization to land-use dynamics, polycentricity, historical urbanization, and urban development. CA models of sprawl, socio-spatial dynamics, segregation, and gentrification have been developed, as have simulations of urban form and location analysis (see also O'Sullivan and Torrens, 2000; Portugali, 2000; White, 1998). The popularity of urban CA models is in part due to weaknesses in the existing stock of urban models (Torrens 2000b), but also owes much to several advantageous properties that CA offer. 4.1 Advantages of using cellular automata for urban simulation 4.1.1 Weaknesses of traditional models Having been developed with fervor at the beginning of the decade, by the close of the 1960s, efforts to develop successful large-scale land-usetransportation models had 33

deteriorated and the novelty value of the models had waned substantially. Few large-scale urban models had been completed, and those that had fell short of their goals (see Lee 1973; Batty 1979; Openshaw 1979; Sayer 1979; Batty 1994; Harris 1994; Klosterman 1994; Lee 1994; Smith 1998). There are a variety of possible explanations as to what environment engendered such skepticism regarding urban simulation. Batty (1979) contends that the early-1960s represented a phase of immaturity in the evolution of planning as a discipline and that the turbulent popularity of modeling characterized growing pains of a sort. To many in the planning profession, he argues, urban models were perceived as a threat. Urban models were treated with growing hostility because they represented a "clash of cultures" between advocates of the idea of planning as science (the quest for pure knowledge) and those who believed in planning as design (the basis for effective action). Compounding these negative feelings were broader trends sweeping America and Europe in the 1970s and a general rejection of the scientific optimism that had been so prevalent in the 1960s. In the social sciences, these changing times impacted heavily upon the nature of academic inquiry. Within planning there was a shift from efficiency to equity (Batty 1994). The quantitative methods developed in the 1960s to address questions of efficiency simply had little relevance in a discipline now concerned largely with equity. As the social climate changed, so too did the character of the city. Urban structure was changing: monocentric cities spawned additional nuclei, which in turn began to challenge the traditional dominance of the downtown and infrastructure provision put increasing emphasis on the suburbs, altering the spatial pattern of urban accessibility. Urban modeling efforts, which were slow to adapt to rapid changes in the character of the city, became outmoded in many instances. It is perhaps useful to explore the criticisms leveled at urban models at the end of the 1960s, as a benchmark against which we might consider contemporary models. Largescale urban models developed in the 1960s were at times accused of unnecessary complication, while at others being rebuked for their simplicity.11 Critics disapproved of ,Q WKLV UHJDUG PD\EH OLWWOH KDV FKDQJHG VLQFH WKHQ 34

their expense, voracious appetite for data, hyper-comprehensiveness, mechanical organization, inadequate resolution, lack of transparency, poor dynamics, and inability to replicate their results; while denouncing their `black box' approach to simulation. Others contended that the models were fraught with distorting error and that they failed to advance theory while falling short of informing practice. Some argued that the models' reliance on the assumption of predictability doomed them to failure from the outset, that they were unsuitable as tools to describe many urban phenomena, and that a lack of evaluative measures undermined their effectiveness at the close of the modeling process. 12 CA models, while very much less than perfect, do address many of these concerns and deficiencies. In some key areas, CA models represent a significant improvement on previous generations of urban simulation models: spatiality, decentralization, affinity with new techniques for spatial analysis, attention to detail, linking function and form, dynamics, theory, simplicity, connection of micro- and macro-approaches, and visualization. 6SDWLDOLW\ CA are particularly adept at dealing with spatial phenomena. Traditional urban modeling techniques sometimes have a tendency to abstract from spatial detail. CA, on the other hand, make implicit use of that spatial complexity (White, Engelen and Uljee 1997). Additionally, CA are good at handling proximal space. If absolute (Cartesian) space provides an a priori frame of reference (site), and relative (Leibnitzian) space handles the relations between objects (situation), then proximal space is the space that connects the two, linking site and situation through the concept of the neighborhood (Couclelis 1997). "A neighborhood surrounds a localized item or place but it also embodies the notion of proximity to that place, which is a relation" (Couclelis 1997, p.170). Contemporary urban models are generally relative in their treatment of space (e.g., spatial interaction and gravity models, econometric models, location-allocation models, and core-periphery )RU D WKRURXJK DQG GHWDLOHG UHYLHZ RI WKLV GHEDWH WKH UHDGHU LV UHIHUUHG WR %DWW\ +DUULV .ORVWHUPDQ /HH 2SHQVKDZ 6D\HU DQG 6PLWK 35

models) (Couclelis 1997). Yet, the operational procedures used to analyze cities are generally absolute (e.g., Geographic Information Systems (GIS) and remote sensing (RS)). In this sense, CA hold many advantages over linear models of urban phenomena. 4.1.3 Decentralized approach Another advantage of CA, and their parallel processing approach in particular, is that they are highly decentralized. According to Resnick, the decentralized approach of CA is symptomatic and reflective of a very broad trend of decentralization--an "era of decentralization"--sweeping through society in general (Resnick 1994a). Up until recently, the world, and particularly our understanding of the world, was quite centralized. Central control was assumed to drive dynamics in many systems. The formation of groups of birds into flocks, and the organization of their flocking behavior, was assumed to be guided by a centralized `leader bird' (Resnick 1997). Resistance to evolutionary theory (which still persists: (see Belluck 1999) was based on the idea that the forces driving creation were a centralized, one-off event (Resnick 1996). In the eighteenth century, the Scottish economist Adam Smith even postulated the idea of an "invisible hand" that set the level of equilibrium between supply and demand in the market place. It is, perhaps, not unsurprising that a bias towards centralization exists. Many phenomena are, indeed, centralized. Also, people generally participate in social systems where power and authority are centralized. The experience of self and the mind as a singular entity also emphasizes individuality (see O'Sullivan and Haklay 2000). However, the world, and our ideas about how the world works, is becoming increasingly decentralized on many levels. Organizations have become decentralized, distributing rights, responsibilities, ownership, and power from the top down. Decentralization is also pervasive in science. In physics the domination of the Newtonian idea of a centralized and linear link between cause and effect is slowly being replaced by a decentralized approach that treats systems in terms of dynamic nonlinear interactions and feedback loops. In psychology the idea of a centralized mind has been challenged, most notably by Sigmund Freud, who proffered 36

the idea of simultaneous existence of multiple perspectives and narratives co-existing in separate areas of the mind (Resnick 1994b). More importantly for urban studies, cities are decentralizing! The old monocentric core and its orbital band of related settlement is rapidly giving way to polycentric city systems dispersed over a much less centralized network of relations and a spatial structure that is shaped by centrifugal forces, rather than centripetal activity. 4.1.4 Affinity with geographic information systems and remote sensing CA are commonly regarded as having a "natural affinity" with raster data (Couclelis 1997). They seem well suited to GIS and remotely sensed information. There are other similarities between CA and GIS. Both CA and GIS organize space into discrete areal units (grids in CA, and polygons or grids in GIS). Also, CA and GIS represent attribute information in a layered fashion (themes in GIS and state-spaces in CA), and manipulate that information with operators (overlay techniques, for example, in GIS and transition rules in CA) (Wagner 1997). In many cases, state data can be arranged in a GIS or via remotely sensed images before being introduced to the CA. In White and colleagues' model (White and Engelen 1997), states represent a plethora of information about cities, such as soil types, precipitation levels, legal restrictions on land use, arranged in many cases as weighted sums. In such cases GIS are ideal for preprocessing CA state-spaces. Other authors have suggested a closer coupling of CA and GIS, suggesting that CA act as the `analytical engine' for a GIS (Wagner 1997). In the Wu and Webster models (Wu and Webster 1998), for example, the CA is called from within a GIS. Yeh (1998) and Yeh and Xia (2000) have also developed CA-GIS models for urban research. 4.1.5 Attention to detail Before the advent of computers, we could only study systems with large numbers of interacting mechanisms by assuming that individual elements exhibited a typical or average behavior. The overall behavior of the system was assumed to be the sum of these average behaviors. But, of course, many systems are non-linear, and here it may not be 37

assumed that the aggregate constitutes the sum of the constituent parts (Holland 1995). This idea has carried through to urban systems simulation, where complacency in the substitutability of aggregate level data for detail has long proliferated. This approach has been well criticized; in particular, the consequences for the way in which we consider cities--as macro-structures that account for urban change--are especially unwelcome (Batty 1998). The result has been a generation of models and range of methodologies that are divorced from detail (Torrens 2000b). The capabilities of CA to handle fine-scale dynamics with computational efficiency has made them candidates for a new generation of detailed simulations. This is a logical progression from micro simulation efforts in operational land-use and transport models (Wegener 1996), 13 but with an explicit and welcome attention to spatial detail. 4.1.6 Function and form A major advantage of CA is the equal attention that they afford to space, time, and system attributes. This united approach has the benefit of imposing a modeling framework that forces model builders to consider the system that they are simulating in an interactive fashion, where a change in one element has profound effects on others (Batty 1997b). This has obvious advantages for modeling geographic phenomena, where actions are intertwined continuously over space. Essentially, CA allow use to model function and form, pattern and process, simultaneously and in an interactive manner. 4.1.7 Dynamics Previous generations of urban models have sometimes treated dynamics poorly: models moved in `jumps' from one time period to another. Often, these jumps spanned several years--a period in which much could change in a city. The weak representation of ,QGHHG PRGXODU VRIWZDUH DUFKLWHFWXUHV IRU ODQGXVH DQG WUDQVSRUW PRGHOV DUH PDNLQJ WKH LQFOXVLRQ RI FHOOXODU DXWRPDWD DQG DJHQWEDVHG PRGHOV DV GHWDLOHG PLFURVLPXODWLRQ HQJLQHV LQFUHDVLQJO\ IHDVLEOH :DGGHOO DQG $OEHUWL 1RWK %RUQLQJ DQG :DGGHOO :DGGHOO :DGGHOO DQG $OEHUWL 38

dynamics was a by-product of calibrating the models on cross-sectional data, often relying on information from the Census, which is produced decenially in most countries. Recent advances have seen models calibrated on longitudinal data, with time steps of as low as one year (for example, the UrbanSim model: Waddell (2000)). Nevertheless, the models still remain relatively static. They are updated rather than iterated between time steps. CA models represent a significant advance in the treatment of time. The models are inherently dynamic, and importantly they are interactively dynamic. Time is still discrete in CA models--they still move in `jumps'--but the jumps may be so small as to approximate real-time dynamism if necessary and if data permits. This is useful for modeling cities: CA are flexible enough to allow multiple timescales to be represented in the simulation. This is important in systems such as cities, where the lifecycle of interactive events--long-term economic cycles, daily commuting behavior, hour-by-hour social interaction, etc.--varies temporally. 4.1.8 Infusion of complexity theory Treating cities as complex adaptive systems is an innovative approach to urban studies. As we have seen, many urban systems may be regarded as emergent in their behavior and complex in their organization. The complexity approach to urban studies also parallels closely with postmodern schools of thought in urban geography, particularly ideas about deconstruction and the representation of multiple perspectives (for example, see Soja 1995). The complexity approach focuses on the `grassroots' of the system--emphasizing the interaction among elements--without sacrificing a holistic perspective. The complexity approach also focuses model development on important issues such as the importance of historical (seed) conditions, feedback between subsystems, interaction, dynamics, noise and perturbations, etc. Of course, urban CA also offer the potential of illuminating our understanding of complex adaptive systems in general. The opportunity to inform debates in complexity studies is rich. 39

4.1.9 Simplicity In CA models complicated and realistic patterns and processes emerge from simple rules and sparsely (but well) defined elements. The simplicity of the CA approach offers many advantages for urban simulation. Previously, many models--particularly large-scale landuse and transport models--were regarded as unnecessarily complicated and unwieldy (see Lee 1973; Torrens 2000b). In many cases users did not understand how the models worked. The models were regarded as `black boxes': things went in and things came out but the user was no wiser as to what went on inside the model. This is a serious weakness when the purpose of the model is to learn more about how a system functions. CA can help to `color' the black box, largely because of their intuitive simplicity, both in terms of parameterization and the derivation of algorithms (transition rules) for the model's behavior. The CA approach abstracts somewhat from potentially confusing aspects of model design--transition rules are derived (ideally!) from theoretically-informed research, and the complexity is allowed to emerge from within the model; the complexity does not strictly enter into the model design, per se. Of course, one always run the risk of adopting too simple an approach and omitting important detail in the system: "No models based on toy values and the homogeneity, uniformity, universality, etc, assumptions of classic CA can have a claim to the status of explanatory tools for real-world applications." (Couclelis 1997, p.167) Of course, the flip side of this is the danger that urban CA, through extension, may become too complicated! 4.1.10 Linking macro- to micro-approaches The city is a complex system with many sub-systems that operate interactively at different scales. CA have the capacity to `gel' these subsystems together in a seamless manner. They do this by allowing large-scale patterns to `emerge' from the interactive dynamics of local elements. There may be some incompatibility when it is necessary to model top-down subsystems, however. 40

4.1.11 Visualization CA are, by their very nature, a highly visual environment for simulation. This has several advantages for urban modeling. The visual aspect helps to engage model users--users can interact visually with the model. The same advantage also applies to uses in education (Resnick 1997). As the saying goes, a picture is worth a thousand words; CA can convey large amounts of information at once. Complex procedures, aggregated outcomes, statistical trends, and comparative measures can be presented visually and diagrammatically, enhancing the accessibility of the research. Because CA are visually dynamic, the evolution of the system can also be displayed as it changes over time. 4.2 Modifying CA for urban applications Urban models are an abstraction, simplified versions of real world objects and phenomena that are used as laboratories for exploring ideas about how things work in cities. CA are no exception to this characterization. However, the basic CA, as defined by Ulam, von Neumann, Conway, and Wolfram (Poundstone 1985; Wolfram 1994; Sipper 1997) is not well suited to urban applications; the framework is too simplified and constrained to represent real cities. To be successfully applied to the simulation of urban systems, it is necessary that CA be heavily modified from the formal parameterizations outlined in section 3. Indeed, quite radical modification is necessary before CA can approximate even a crude representation of an urban system. This often necessitates the introduction of additional components to add functionality to the basic CA design. The next sections discuss urban CA modifications in detail, referring to the adaptation of cellstates, lattices, neighborhoods, time, and transition rules. 4.2.1 Cell-states In the basic CA, the cell-space is a closed environment. External events cannot influence the model dynamics within the CA. When CA are configured in this manner, there is no place for independent forces that might enter the model at a macro-scale (Couclelis 1985). Naturally, system closure makes little sense in the context of cities, where 41

exogenous links and dependencies are numerous. To overcome this limitation, urban CA are often opened to outside influences, most commonly through constraints and algorithms applied to transition rules (see Couclelis 1985; Clarke, Hoppen and Gaydos 1997; Semboloni 1997; White and Engelen 1997; White, Engelen and Uljee 1997). Cell-states have also been reformulated in a hierarchical fashion in urban CA, mirroring discrete choice models in land-use and transport simulation (Torrens 2000b). The hierarchies are used to introduce the notion that state transition in urban contexts (landuse dynamics, for example) has a predilection towards pursuing fixed paths and proceeding in a sequential fashion (White and Engelen 1993). In the basic CA, cell-states have a certain level of homogeneity. Cells may adopt concurrent states (von Neumann's CA had 29 states, for example), but those states have often been of the same form. Research into urban CA models has attempted to introduce a greater degree of flexibility into cell-state design by permitting cells to adopt concurrent states in a variety of forms. For example, binary states--developable or not developable, for example--appear alongside integer state descriptions--land use categories, for example--and continuous values that correspond to various urban characteristics and properties such as land value and population counts (Wu 1998). A particularly innovative twist on this idea is the introduction of cell-state fixture (White and Engelen 1997). Here, a distinction is made between cell states that are `fixed' and those that are `functional'. In the context of land use, we may regard sites that are generally exempt from the urban development process (such as water bodies) as `fixed'; sites that are active in the development process (such as vacant lots) may be considered as `functional'. 4.2.2 Lattices The basic two-dimensional CA is commonly defined on an infinite plane that is structured into a tessellated grid of regularly spaced squares, or cells. Both the idea of an infinite spatial plane and that of a uniformly regular space are unrealistic for most urban contexts. CA used to study cities are often constrained to finite dimensions, with various tricks (such as buffers) for the treatment of edge effects (White, Engelen and Uljee 1997). Recently, researchers have also experimented with three-dimensional lattices for urban 42

CA, approaching a more realistic representation of the dimensionality of urban systems (Semboloni 2000). The idea of a cellular space for these models is also problematic for urban applications.14 Many features of cities are regular: some block configurations, building facades, internal floor plans, and many road networks. However, most objects in cities are not regular, and are certainly not square in shape. In a bid to afford urban CA models a greater degree of realism, researchers have introduced a variety of irregular lattice structures into the CA framework, re-specifying lattices as a graph, for example (O'Sullivan forthcoming). 4.2.3 Neighborhoods The strict formalism of the basic CA provides for a very limited specification of neighborhoods of influence. In the basic CA, a neighborhood consists of an individual cell itself as well as a set of adjacent cells at some distance from the cell in question. In basic two-dimensional CA, there are two neighborhood configurations: the Moore neighborhood of the eight cells that form a square around a cell, and the von Neumann neighborhood of the four directly adjacent cells that comprise a cross centered on a cell (figure 2). Clearly, such a limited range of action spaces is too limiting for urban applications. The rigidity of the basic CA suppresses direct action-at-a-distance (although action does propagate, indirectly, across distances as the models evolve). In the urban world, neighborhoods of influence vary significantly and, more often than not, they fail to fit into the neat typology offered by the basic CA. Social interaction, for example, can operate between adjacent properties, as well as functioning on a citywide scale. It is not surprising that urban CA models have modified neighborhood parameters. Distance decay effects have been introduced, often as weights applied to neighborhoods in transition calculations. Also, neighborhoods have been extended to comprise larger spaces (White and Engelen 1997; White, Engelen and Uljee 1997). The introduction of `fixed' and `functional' cell-states can also serve as a proxy for asymmetric ,Q IDFW &$ ZRXOG GR ZHOO WR LQWURGXFH D QDPH FKDQJH SHUKDSV WKH\ ZRXOG EH EHWWHU WHUPHG DV ¶VSDWLDOO\ WHVVHOODWHG DXWRPDWD· RU ¶ILQLWH VSDWLDO DXWRPDWD· 43

neighborhoods, as `fixed' cells can serve to remove areas of the neighborhood from the transition calculation. 4.2.4 Time The temporal space of CA is also an issue of concern for developers of urban CA models. In the basic CA framework, time is discrete and cells are made to evolve synchronously between time steps. Transition rules are applied uniformly: all cells are updated at the same time. The urban equivalent of this would be a situation in which everybody in a city is privy to every decision made, with all deals being settled at the same time. Researchers using CA for urban applications have experimented with asynchronous cell-update, attempting to circumnavigate the universal treatment of time (although, the ramifications of using asynchronous update are not yet fully understood in urban research). This has been approached through the use of agents on a CA space (Portugali 2000), which add a certain level of randomness to the temporal space of the CA. Others (see White and Engelen 1993; White and Engelen 1997; White, Engelen and Uljee 1997) have tinkered with the cell-state transition process so that it is only partly sequential, fashioned in dependence of exogenous constraints. 7UDQVLWLRQ UXOHV Transition rules are the real driving force behind CA dynamics. Transition functions serve as the algorithms that code real-world behavior into the artificial CA world. In the context of urban CA, transition rules are responsible for explaining how cities work. It is not surprising that CA models used to study cities have seen sweeping modifications to the transition rules specified in basic CA. As we have already seen, transition rules have been opened up to exogenous links, permitting urban CA to function as quasi-open systems. Also, they have been reformulated as probabilistic expressions, a departure from the deterministic specifications of strict CA. In this manner, rules can be made conditional upon a probability, introducing an element of randomness, or `noise', into the model. Also, 44

probabilistic rules can be made dependent on other rules formulated within the model, reflecting the idea that urban systems operate as a tangled web of co-dependent subsystems and phenomena. Self-modification, an idea not unlike evolution, has been used to expand CA functionality for urban purposes. Based on the idea of the genetic algorithm in computer science (Mitchell 1998), transition functions are allowed to change via feedback mechanisms as a CA model develops. In this sense, the rules `evolve' (perhaps to some level of fitness or optimal efficiency) in reaction to the problem space of the model, adapting over time as the CA progress iteratively. Transition rule modification has also absorbed other simulation techniques from urban modeling, particularly ideas from regional science and econometrics (Torrens 2000b). Economic principles, such as utility maximization, have also been woven into transition rules (see Webster and Wu 1998; Wu 1998; Wu and Webster 1998; Webster and Wu 1999a, b), as have accessibility algorithms based on spatial interaction (White, Engelen and Uljee 1997). However, CA models have been slow to adopt explicitly geographic or urban theory as a basis for transition rule formulation, missing a valuable opportunity to infuse the models with a solid theoretical foundation (Torrens and O'Sullivan 2000). 4.3 Moving forward with cellular urban models To some extent, the broad modification to the basic CA framework is necessary for the application of CA models to urban systems, but in many ways it has shadowed the progress of research. Model developers often focus their attention on the intricacies of model construction without proper attention to the reasons for which the models were developed and the applications to which they are put.15

2I FRXUVH WKH VDPH DFFXVDWLRQ FRXOG ZHOO EH DFFXUDWHO\ OHYHOHG DW WKLV ZRUNLQJ SDSHU LW LV DIWHU DOO HQWLWOHG +RZ &HOOXODU 0RGHOV RI 8UEDQ 6\VWHPV :RUN 7KDW LV WKH LQWHQGHG SXUSRVH RI WKLV SDSHU KRZHYHU LW LV QRW PHDQW

IRU DSSOLFDWLRQ WR DQ\ SDUWLFXODU XUEDQ V\VWHP RU WR WHVW D WKHRUHWLFDO K\SRWKHVLV 6R , FDQ VOHHS HDV\ LQ P\ EHG

WKDW DW QLJKW QRW IHHOLQJ DOO

JXLOW\

45

The introduction of CA modeling to urban studies was always an applied science. The models were intended, ideally, to be used as a tool to empower researchers, students, the public, and policy makers to explore their ideas about how complex urban system dynamics function. The simple, dynamic, and bottom-up approach of CA was particularly advocated for this purpose, and welcomed as an innovation in urban simulation. Given the recent enthusiasm for building CA models of urban systems, it is hard to believe that developments in the field have been shadowed by a sense of uneasiness (see Batty 1997b; Couclelis 1997; Torrens and O'Sullivan 2000). In particular, and perhaps quite ironically, anxieties about tinkering with the simple formulation of the basic CA were particularly well voiced. Researchers have been uneasy about the limited capacity for the constrained framework of the basic CA to represent complicated urban systems in even a crude fashion. Despite these concerns (and they are important concerns), work in the urban CA research community has shifted strongly towards modification; application and theory have fallen to the wayside as enthusiasm for the technology of model building--especially geocomputation--has come to the fore (Torrens and O'Sullivan 2000). Ironically, one of the principal concerns of urban CA developers is now a fear that the flood of modifications to the basic CA framework may lead to an unwieldy cocktail of simulations, more complicated in themselves than the systems that they purport to represent. Looking at the literature published on urban CA thus far, we can see some promising avenues for future research in the field, providing researchers with the opportunity to move forward with CA. The next section explores some avenues of development and preemptively suggests some of the difficulties that might pose a challenge to the future development of useful, theoretically informed, and academically innovative CA-based models of complex dynamic urban systems. These developments are classified into several areas, beginning with a taxonomy of cellular urban models: spatial complexity, dimensionality, the meaning of rules, theory, links with other disciplines, the generation of new urban forms, education and outreach, hybridization, and model validation. 46

Figure 11. A spectrum of cellular models. 4.3.1 A taxonomy for cellular urban models The issues surrounding modification and the implications of bolstering the basic CA with expanded functionality are influenced by the intended use of urban CA models. Cellular models of urban systems are generally developed for three (not always mutually exclusive) purposes: to explore spatial complexity, to test theories and ideas about cities in an abstract manner, and as operational urban planning support systems. CA models of spatial complexity are used to advance understanding of general complex adaptive systems (of which, urban systems are a candidate). Abstract urban-theoretical CA models, on the other hand, are used to examine the role that complexity has in driving dynamics in urban phenomena, such as fringe growth, redevelopment, suburban sprawl, edge city formation, polycentricity, agglomeration, inertia, diffusion, spatial structure, and social segregation. Essentially, abstract urban-theoretical CA models are used as laboratories for testing ideas and theories about the city (as opposed to complexity). Operational urban CA are used as planning support systems (although very few are actually operational) to assist planners, policymakers, and the public in managing and building cities. Generally, these serve as scenario-generating tools that form the basis of discussion. Operational urban models have increasingly turned to rule-based formulations based on logit models and decision theory (De la Barra 1989; Torrens 2000b). Also, in transport modeling, 47

activity-based simulations have been gaining ground (Ben-Akiva and Bowman 1998), and micro simulation with operational models has long been underway (Wegener 1996). It does not take a quantum leap to fuse those approaches with CA, which essentially add a dynamic and spatial spin to these existing techniques (Torrens 2000a, 2001). Indeed, following the development of the TRANSIMS model at Los Alamos National Laboratories (Nagel, Beckman and Barrett 1999), there has been a concerted drive to push metropolitan planning organizations into incorporating CA into operational forecasting models, with the implication that those models be used in the assessment of clean air legislation compliance (Travel Model Improvement Program 1999). Each of these application domains is quite different, with varying demands for what a cellular model should do and what structure it might adopt (figure 11). Models used to explore the simple principles that govern urban spatial emergence in dynamic contexts, for example, have little need for radical modification. With a few limited adjustments, the basic CA is adequate for these purposes. In many cases, the addition of extra components may be counterproductive for the tasks at hand. On the other extreme, however, CA models designed for uses in practice; such as urban planning, urban management, and policy formulation; must often be heavily transformed before they approach even vaguely realistic representations of urban systems. Here, modification is likely to be widespread and often essential. Nevertheless, even for practical applications, modification should be approached with care. CA exist, as it were, on the `edge of chaos' (Langton 1992). Launching into unbridled modification of the models, without a full appreciation of the dynamic implications, may produce simulations that we do not fully understand (our `perplexity' from earlier discussions). The risk here is that these models may have little operational value; without an understanding of how the model works, only negligible value can be attached to their predictions or recommendations. The simulations also run the risk of falling short as an exercise in simple model building. When urban CA models become unwieldy the beauty of their simplicity is forfeited, and with it the value of CA as a simulation technique is lost. In short, it is important to remember that urban geography and urban planning are applied sciences; the application domain should not be ignored. With this in mind, let us have a look at where CA models may be going in the future. 48

4.3.2 Explorations in spatial complexity Cities are excellent examples of complex emergent systems. From local-scale interactions such as individual movement habits, the geomarketing strategies of individual retail establishments, and social biases, large-scale and ordered patterns emerge in the aggregate: peak-hour congestion, economies of agglomeration, and social segregation. These aggregate patterns often emerge independently of the dynamics driving the individual components of the system. Complex urban systems also display many traits common to complex systems in the biological, physical, and chemical worlds. Researchers searching for the mechanisms driving complexity have a lot to learn from cities, and urban CA models are excellent vehicles for exploring urban spatial complexity. Experiments with fractal geometry and feedback mechanisms in urban CA are amongst the most common examples of how urban CA models are used to explore spatial complexity (White and Engelen 1993; Batty and Xie 1997). However, there is still plenty of room for advances in this area. Importantly, if research with urban CA is to make a lasting contribution to complexity studies, with relevance across disciplines from biology to physics and chemistry, and across scale boundaries, it is necessary that the form of urban CA preserve as many features of the strict and formal CA model as possible (so that the models can `converse' with each other). Alternatively, by adopting a limited, well-defined family of CA modifications, with origins in urban spatial complexity, other researchers may be encouraged to experiment with urban CA models (O'Sullivan and Torrens 2000). Findings might be compared with work in other disciplines and parallels could be drawn between urban research and advances in other areas of complexity. The idea behind using urban CA models to study spatial complexity is to look at the simple ingredients of complexity that we find in cities, and to examine how these findings compare with elements of complexity in other fields. However, there are significant avenues of inquiry that must be addressed before urban CA models of spatial complexity can fulfill these requirements. Specifically, urban CA models may have to turn their attention to multi-dimensional complexity. Also, there is a strong need for measured experimentation with the construction of transition rules within a relatively 49

formal CA structure and the patterns that those rules generate. Finally, exploration into agent-based models of complexity, built on CA-based city-like environments is likely to be required. 4.3.3 Dimensionality From the vantage point of urban geography--a field that is intrinsically dedicated to spatial relations in urban systems--it is surprising that apart from Conway's Game of Life CA (Poundstone 1985), much of the most widely cited CA literature in the natural sciences focuses on the behavior of one-dimensional CA. By limiting explorations to a single dimension, the richness of system dynamics across many dimensions is sometimes ignored. In an applied context, these models forfeit some of their explanatory power. Of course, in physics and chemistry the complex dynamics of emergent systems, in some cases, do actually function, in relative isolation, in single dimensions. This is not generally true of complexity in geography and cities (except, perhaps, on traffic networks). Urban CA have, for the most part, adopted a two-dimensional perspective on systems dynamics, but there have been very few applications of urban CA to multidimensional examples (Semboloni 2000 is the only example that the author is aware of). There is no reason why research designed to explore spatial complexity with urban CA models should not direct its attentions beyond two dimensions. Intuition suggests that the search for spatial complexity in urban systems and explanation in urban geography must lead researchers at least into three dimensions, if not more. Building urban CA that can handle complex dynamics in several dimensions is not trivial; it's really difficult! However, advances are being made, and the area represents a potentially rich and rewarding future avenue for investigation, both for urban geography and for complexity studies. 4.3.4 Infusing theory One of the potential drawbacks of urban CA models, is that they have may have done relatively little to inform theory. Many of these models claim to explore various 50

hypothetical ideas about the city, but model developers regularly mire their work in the fine details of model construction, at the expense of the theories that they set out to explore. (This is a flaw of much quantitative research in geography.) Research in urban CA modeling has perhaps become slightly confused as a result of a general emphasis on the nuts and bolts of model specification, rather than the theoretical environment in which they exist; researchers are explaining how without exploring why. This is often the case with new techniques in quantitative geography, where initial enthusiasm for analysis techniques dominates the early research agenda. As CA move into a relative degree of maturity as an academic exercise, however, calls for advances in this area may amplify. It is important that research with these models has neglected some significant areas of investigation, notably explorations into generating simulations of new urban patterns, and the potential use of the models as educational tools. These areas represent exciting ways in which urban CA models can really make a contribution to urban geography, public policy, urban studies, and urban planning. 4.3.5 The meaning of rules Transition rule formulation in operational urban CA models probably represents one region in which future advances in CA models will focus. The design of rules is an area in which operational models have the chance to associate with theory--an area that operational simulation has been somewhat divorced from. Some innovative advances have been made in the formulation of transition rules derived from urban economic theory and notions of accessibility. Batty and colleagues have developed several influential models along these lines (Xie 1994; Batty and Xie 1997; Batty 1998, 1999; Batty, Xie and Sun 1999), as have Webster and Wu (Webster and Wu 1998; Wu 1998; Wu and Webster 1998; Webster and Wu 1999a, b; Wu 1999). Other groups have also made important in-roads in the field (Benati 1997; Portugali, Benenson and Omer 1997; Sanders, Pumain, Mathian et al. 1997; Portugali 2000). These efforts can be extended to embrace other areas of urban theory--as well as other urban theories--such as social justice, location theory, urban design, political economy, environmental studies, urban sociology, and urban ecology. This would have the advantage of strengthening the 51

theoretical basis of urban CA. Additionally, it offers the opportunity for moving urban modeling away from an overarching allegiance to that old crutch (!), urban economics, and towards an expanded interdisciplinary focus. 4.3.6 Generating new urban forms One of the potentially rich uses of CA in urban research is to generate city-like phenomena from theoretically informed components. Because the technology is still in a `workshop' phase, urban CA models have focused on replicating well-documented urban phenomena, such as growth, multi-nucleation, and land-use transition. The opportunity to generate new organic urban forms with these models has not been capitalized upon. Potentially, urban CA models might allow us to preemptively explore our urban futures, simulating the next edge city, techno pole, or megalopolis phenomenon. Of course, much of this research may prove rather difficult; how would we recognize new urban forms if we did actually generate them? But, the possibilities that these models offer are too rich for the opportunity to be missed. 4.3.7 Education and outreach Urban models have always been employed to good use as educational tools. Conceptual models such as those developed by von Thunen, Hotelling, Burgess, and Losch, have contributed greatly to our understanding of the city, even with limiting assumptions and a much simplified description of the city (see Torrens 2000b for a review). CA really offer fantastic opportunities to follow suit in this tradition. In particular, the chance to use CA models in the classroom as a dynamic, visual, and interactive educational tool for urban geography is beginning to be seized upon (Rizzi and Buso 1999), especially as software specifically catered towards education and freely available in the public domain becomes available (Resnick 1997; Epistemology and Learning Group 2000; Freiwald and Weimar 2000). CA also hold potential for improving the interface between models and users in planning, policy, and elsewhere. The CA approach emphasizes simplicity in model formulation and 52

affirms dynamic visualization as a means of presentation. These properties lend CA an aptitude for engaging model users in an interactive manner. With these techniques, operational urban models have a chance to become more intelligible, accessible, userfriendly, and useful. 4.3.8 Hybrid models Traditionally, operational land-use and transport models have been developed in the spatial interaction framework (Fotheringham and O'Kelly 1989). The so-called `gravity models' (their algorithms are formulated with analogy to Newtonian physics) emphasize an aggregate and largely static approach to urban simulation. Several advances on the basic gravity approach have been formulated and forays into spatial choice simulation have been made (Torrens 2000b). However, the current stock of models in operational use remain largely centralized, aggregate, relatively static, and top down in their treatment of urban activity (with a few exceptions). The complexity approach has put decentralization, detail, dynamics, and bottom up approaches in the simulation spotlight. There is much justification for carrying those ideas through to urban simulation. Many urban systems do exhibit signs of emerging from micro-scale dynamics up to macro-level manifestations, and these systems may well be better modeled with CA. However, as suitable to the simulation of urban systems as CA models are, there are some things that they cannot model well, most notably constraints such as planning restrictions that are applied to urban systems from the top down and global level phenomena that strongly influence urban systems, but do not necessarily emerge from local components. In light if these considerations, there is a convincing argument for developing hybrid operational urban models. One potential framework for a hybrid model would combine the best elements of CA, traditional land-use and transport and regional science techniques, and models based on intelligent spatially mobile agents. A hybrid model would simulate the aggregate and global level (top down) dynamics of the urban system in the conventional manner using techniques widely employed in practice: spatial interaction, spatial choice, input-output models, demographic forecasting techniques, etc., but could delegate micro scale (bottom 53

up) dynamics to CA and agent models. Essentially, the macro-level models would feed the CA-agent models with a set of known zonal level conditions (these can serve as constraints on state values). The micro-level models would then distribute these values at the local level using theoretically informed dynamic `engines'. Ideally the connection between the two sets of models would be tightly integrated and seamless, but a hybrid approach could also constitute a `suite' of models, each with a unique perspective on the problem at hand. Tentative advances in this area have already been made (Phipps and Langlois 1997; White and Engelen 1997), and modular simulation architectures are paving the way for these hybrids (Noth, Borning and Waddell 2000). Also, the topic is the subject of ongoing work by the author, and constitutes the principal focus of my own research (Torrens 2000c, a, 2001). However, there are a number of obstacles that need to be overcome before adequate progress towards these objectives can be made. The nature of process directionality in dynamic, and intricately codependent urban systems needs serious attention so that an understanding of where connections should be made and feedback loops exist, for example. 4.3.9 Validating cellular urban models The issue of model validation is key to the development of all urban CA models, but particularly those applied in operational contexts. The emphasis thus far in urban CA modeling has been on pattern based validation techniques: pattern recognition, measures of match such as the chi-squared and kappa-statistics. The weakness of these approaches have been well-documented (White, Engelen and Uljee 1997; Wu 1998) and much energy is being expended on advancing our ability to calibrate urban CA models (Power, Simms and White 1999). However, much of this effort is still bogged down in the pattern-based approach. This ignores the fact that CA comprise pattern and process, form and function. Future research may therefore have to look to new process-related validation measures such as Monte Carlo averaging, spatial information statistics (Wolfram 1994), and measures of complexity. There is also some rich potential to make connections with our existing repertoire of pattern-based techniques. 54

5 Conclusions This paper has (hopefully!) provided an introduction to the theory of how cellular models of urban systems work, tracing the intellectual roots of urban CA from complexity studies through to computer science and urban simulation. It can be seen that CA have several desirable qualities for studying urban systems and in many instances they specifically address the weaknesses of previous generations of urban models. The advantages of using CA for urban research include their spatiality, a decentralized approach to problem solving, and affinities with other forms of spatial analysis. CA also have the benefits of handling detail with relative ease, providing a connection between function and form, facilitating dynamic simulation, and infusing models with elements of complexity theory. Their relative simplicity compared to other urban simulation models, the link that they provide between micro- and macro-approaches, and their visual environment are also desirable qualities. In most cases, urban CA bare only a passing resemblance to what we might call basic or classic CA (those discussed in section 3). Often, CA must be modified for application to urban problems. This paper has described how such modifications might take place, with reference to cell-states, lattices, neighborhoods, time, and transition rules. CA remain in relative infancy as a form of urban simulation and as such the future offers many avenues for exploration with model building and application to urban studies. These include new application in the study of spatial complexity, experiments with the dimensions of urban CA, and opportunities to work more closely with theory and rule building. The generation of new urban forms with CA also holds much promise, as do opportunities for using the models as instructional tools for education and engaging user communities. Finally, the issue of calibrating urban CA models with known conditions in the real world represents one significant area in which research with urban CA is likely to engage further. Research work here at the Centre for Advanced Spatial Analysis (CASA)--in the realm of urban simulation models--is focused on developing new software architectures for urban CA and complexity models in general, as well as integrated environments that support the development of hybrid tools for studying urban systems. Two projects that I 55

am involved with include the SprawlSim model (my Ph.D. work, which is in early development!): a multi-agent simulation system overlaid on a CA environment that is integrated with land-use and transport models. SprawlSim is intended for use as a scenario-generating simulation for exploring spatial complexity and sprawling urban growth in North American cities (see http://www.geosimulation.com). Ideally, users will be able to interact with the model to explore various growth management scenarios relating to sprawl to explore potential outcomes before they are tested in the real world (you might also want to take a look at Torrens and Alberti 2000, if you are interested). The second project is NEXSUS. The research is concerned with the application of complex systems thinking and approaches to increase understanding of sustainability in socioeconomic systems. At the core of NEXSUS are six individual projects across five UK universities. While each project tackles a different problem, the stated aim is to try to create bridges across these problems, leading to common understandings, integration in methodologies and some communality in the eventual outcomes (http://www.nexsus.org). CASA's involvement with NEXSUS is to develop an agent-based modeling environment for exploring how complexity influences micro-scale urban development dynamics in the city of London. The next step in this series of papers is to develop a set of abstract urban experiments-- such as generating compact and sprawling cities from seed conditions, examining how edge cities form, and tinkering with the parameterization of models. These models are intended to demonstrate how urban CA are built in a practical context. The experiments will be built in the StarLogoT environment, originally cultivated at the Massachusetts Institute of Technology Media Lab (Epistemology and Learning Group 2000), but now under development in additional universities (Center for Connected Learning and Computer-Based Modeling 2000). Each of these experiments will be described in detail as they are built from the ground up, and annotated software code will be provided. I hope to place some of these models on our website at http://www.casa.ucl.ac.uk so that readers can interact with them. With this paper as a theoretical foundation, it is hoped that the set of papers will encourage and assist others in their own research with Urban CA. 56

References Allen, P. M. (1997). Cities and Regions as Self-Organizing Systems: Models of Complexity. Amsterdam, Gordon and Breach Science Publishers. Batty, M. (1979). 'Progress, success, and failure in urban modeling'. Environment and Planning A 11: 863-878. Batty, M. (1994). 'A chronicle of scientific planning: the Anglo-American modeling experience'. Journal of the American Planning Association 60 (1): 7-16. Batty, M. (1997a). 'Cellular automata and urban form: A primer'. Journal of the American Planning Association 63 (2): 266-274. Batty, M. (1997b). 'Editorial: Urban systems as cellular automata'. Environment and Planning B 24: 159-164. Batty, M. (1998). 'Urban evolution on the desktop: simulation with the use of extended cellular automata'. Environment and Planning A 30: 1943-1967. Batty, M. (1999). 'Modeling urban dynamics through GIS-based cellular automata'. Computers, Environment and Urban Systems 23: 205-233. Batty, M. and P. Longley (1994). Fractal Cities. London, Academic Press. Batty, M. and Y. Xie (1997). 'Possible urban automata'. Environment and Planning B 24: 175-192. 57

Batty, M., Y. Xie and Z. Sun. (1999). The dynamics of urban sprawl. CASA Working Paper 15. University College London, Centre for Advanced Spatial Analysis (CASA). London. http://www.casa.ucl.ac.uk/working_papers.htm. Belluck, P. (1999). 'Board for Kansas deletes evolution from curriculum'. New York Times: August 12. Ben-Akiva, M. and J. L. Bowman (1998). 'Integration of an activity-based model system and a residential location model'. Urban Studies 35 (7): 1131-. Benati, S. (1997). 'A cellular automaton for the simulation of competitive location'. Environment and Planning B 24: 175-192. Casti, J. L. (1997). Would-be Worlds: How Simulation is Changing the Frontiers of Science. New York, John Wiley & Sons. Center for Connected Learning and Computer-Based Modeling (2000). StarLogoT 2001. Boston, MA. Tufts University. www.ccl.tufts.edu/cm Clarke, K. C., S. Hoppen and L. Gaydos (1997). 'A self-modifying cellular automaton model of historical urbanization in the San Francisco Bay area'. Environment and Planning B 24: 247-261. Couclelis, H. (1985). 'Cellular worlds: A framework for modeling micro-macro dynamics'. Environment and Planning A 17: 585-596. 58

Couclelis, H. (1997). 'From cellular automata to urban models: New principles for model development and implementation'. Environment and Planning B 24: 165-174. De la Barra, T. (1989). Integrated Land Use and Transport Modelling: Decision Chains and Hierarchies. Cambridge, Cambridge University Press. Epistemology and Learning Group (2000). StarLogo Cambridge, MA. Massachusetts Institute of Technology Media Lab. http://www.media.mit.edu/macstarlogo/ Fotheringham, A. S. and M. E. O'Kelly (1989). Spatial Interaction Models: Formulations and Applications. Dordrecht, Kluwer Academic Publishers. Freiwald, U. and J. R. Weimar (2000). JCASim--A Java system for simulating cellular automata. In Theoretical and Practical Issues on Cellular Automata. S. Bandini and T. Worsch. London, Springer-Verlag: 47-54. Harris, B. (1994). 'The real issues concerning Lee's "Requiem"'. Journal of the American Planning Association 60 (1): 31-34. Holland, J. H. (1995). Hidden Order: How Adaptation Builds Complexity. Reading, MA, Addison-Wesley. Holland, J. H. (1998). Emergence: From Chaos to Order. Reading, MA, Perseus Books. Horgan, J. (1995). 'From complexity to perplexity: Can science achieve a unified theory of complexity systems? Even at the Santa Fe Institute, some researchers have their doubts.'. Scientific American. http://www.sciam.com/explorations/0695trends.html. 59

Klosterman, R. E. (1994). 'Large-scale urban models: retrospect and prospect'. Journal of the American Planning Association 60 (1): 3-6. Krugman, P. (1996). The Self-Organizing Economy. Malden, MA, Blackwell. Langton, C. G. (1992). Life at the Edge of Chaos. In Artificial Life II. C. G. Langton, C. Taylor, J. D. Farmer and S. Rasmussen. Redwood City, CA, Addison-Wesley: 41-93. Lee, D. B. (1973). 'Requiem for large-scale models'. Journal of the American Institute of Planners 39: 163-178. Lee, D. B. (1994). 'Retrospective on large-scale urban models'. Journal of the American Planning Association 60 (1): 35-40. Levy, S. (1992). Artificial Life: The Quest for a New Creation. London, Penguin Books. Mitchell, M. (1998). An Introduction to Genetic Algorithms. Cambridge, MA, MIT Press. Nagel, K., R. J. Beckman and C. L. Barrett. (1999). TRANSIMS for urban planning. LAUR 98-4389. Los Alamos National Laboratory. Los Alamos, NM. http://transims.tsasa.lanl.gov/. Nagel, K., S. Rasmussen and C. L. Barrett. (1996). Network traffic as self-organized critical phenomena. TSA-DO/SA MS-M997 and CNLS MS-B258. Los Alamos National Laboratory. Los Alamos, NM. http://transims.tsasa.lanl.gov/. 60

Noth, M., A. Borning and P. Waddell. (2000). An extensible, modular architecture for simulating urban development, transportation, and environmental impacts. University of Washington, Department of Computer Science and Engineering. Seattle. http://www.urbansim.org. Openshaw, S. (1979). 'A methodology for using models for planning purposes'. Environment and Planning A 11: 879-896. Openshaw, S. (1983). The Modifiable Areal Unit Problem. Norwich, GeoBooks. O'Sullivan, D. (2000) Graph-based cellular automata models of urban spatial processes. Ph.D. Thesis. University College London, London. O'Sullivan, D. (forthcoming). 'Exploring spatial process dynamics using irregular graphbased cellular automaton models'. Geographical Analysis. O'Sullivan, D. and M. Haklay (2000). 'Agent-based models and individualism: is the world agent-based?'. Environment and Planning A 32 (8): 1409-1425. O'Sullivan, D. and P. M. Torrens (2000). Cellular models of urban systems. In Theoretical and Practical Issues on Cellular Automata. S. Bandini and T. Worsch. London, Springer-Verlag. http://www.casa.ucl.ac.uk/working_papers.htm. Phipps, M. and A. Langlois (1997). 'Spatial dynamics, cellular automata, and parallel processing computers'. Environment and Planning B 24 (193-204). 61

Portugali, J. (2000). Self-Organization and the City. Berlin, Springer-Verlag. Portugali, J., I. Benenson and I. Omer (1997). 'Spatial cognitive dissonance and sociospatial emergence in a self-organizing city'. Environment and Planning B 24: 263-285. Poundstone, W. (1985). The Recursive Universe : Cosmic Complexity and the Limits of Scientific Knowledge. New York, Morrow. Power, C., A. Simms and R. White. (1999). Hierarchical Fuzzy Pattern Matching for the Regional Comparison of Land Use Maps. MATRIKS: Maastricht Technological Research Institute for Knowledge and Systems, University of Linburg. Maastricht, Netherlands. Resnick, M. (1994a). 'Changing the centralized mind'. Technology Review (July): 32-40. Resnick, M. (1994b). 'Learning about life'. Artificial Life 1 (1-2). Resnick, M. (1996). 'Beyond the centralized mindset'. Journal of the Learning Sciences 5 (1): 1-22. Resnick, M. (1997). Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds. Cambridge, MA, MIT Press. Rizzi, P. and M. Buso (1999). 'Cellular Automata applications: from environmental education to urban and regional analysis'. CUPUM 99: Sixth International Conference 62

in Urban Planning and Urban Management, Venice. http://www.iuav.unive.it/stratema/cupum/. Rucker, R. (1999). Seek! Selected Nonfiction by Rudy Rucker. New York, Four Walls Eight Windows. Sanders, L., D. Pumain, H. Mathian, F. Guйrin-Pace and S. Bura (1997). 'SIMPOP: A multiagent system for the study of urbanism'. Environment and Planning B 24: 287305. Sayer, R. A. (1979). 'Understanding urban models versus understanding cities'. Environment and Planning A 11: 853-862. Schelling, T. C. (1969). 'Models of segregation'. American Economic Review 59 (2): 488493. Schelling, T. C. (1978). Micromotives and Macrobehavior. New York, WW Norton and Company. Semboloni, F. (1997). 'An urban and regional model based on cellular automata'. Environment and Planning B 24: 589-612. Semboloni, F. (2000). 'The dynamic of an urban cellular automata model in a 3-D spatial pattern'. XXI National Conference Aisre: Regional and Urban Growth in a Global Market, Palermo. 63

Sipper, M. (1997). Evolution of Parallel Cellular Machines: The Cellular Programming Approach. Berlin, Springer. Smith, M. (1998). 'Painting by numbers--mathematical models of urban systems'. Environment and Planning B 25: 483-493. Soja, E. (1995). Postmodern urbanization: the six restructurings of Los Angeles. In Postmodern Cities and Spaces. S. Watson and K. Gibson. Oxford, Blackwell. Stephenson, N. (1999). Cryptonomicon. New York, Avon Books. Taylor, C. E. (1992). "Fleshing Out" Artificial Life II. In Artificial Life II: Proceedings of the Workshop on Artificial Life held February, 1990 in Santa Fe, New Mexico. C. G. Langton, C. Taylor, J. D. Farmer and S. Rasmussen. Redwood City, CA, AddisonWesley: 25-38. Torrens, P. M. (2000a). 'Geocomputation, complexity, and urban systems simulation'. Meeting of Special Interest Group 1 (Transport and Spatial Development) of the World Conference on Transport Research, Portland, Oregon. http://www.casa.ucl.ac.uk/geosimulation/publications.htm. Torrens, P. M. (2000b). How Land-Use--Transportation Models Work. CASA Working Paper 20. Centre for Advanced Spatial Analysis, University College London. London. http://www.casa.ucl.ac.uk/working_papers.htm. Torrens, P. M. (2000c). SprawlSim: A Scenario-Generating Simulation Model for Exploring Spatial Complexity and Sprawling Urban Growth. Economic and Social 64

Research Council (ESRC) Studentship Award. Centre for Advanced Spatial Analysis (CASA), University College London. London. Copy available from author. Torrens, P. M. (2001). 'A hybrid geocomputation model for operational land-use and transport simulation'. 97th Annual Meeting of the Association of American Geographers, New York. Torrens, P. M. and M. Alberti (2000). 'Measuring sprawl'. Annual Conference of the Association of Collegiate Schools in Planning, Atlanta. http://www.casa.ucl.ac.uk/working_papers.htm. Torrens, P. M. and D. O'Sullivan (2000). Cities, cells, and cellular automata: Developing a research agenda for urban geocomputation. In Proceedings of the Fifth Annual Conference on GeoComputation. Manchester, GeoComputation CD-ROM. http://geocomp.gre.ac.uk/gc2000/index.htm. Travel Model Improvement Program. (1999). Early deployment of TRANSIMS. Los Alamos National Laboratories. http://www.bts.gov/tmip/publ/issue_paper/issue_paper.htm. Vichniac, G., P. Tamayo and H. Hartman (1986). 'Annealed and quenched inhomogenous cellular automata'. Journal of Statistical Physics 45: 875-883. Waddell, P. (2000). 'A behavioural simulation model for metropolitan policy analysis and planning: residential location and housing market components of UrbanSim'. Environment and Planning B 27 (2): 167-324. 65

Waddell, P. and M. Alberti (1998). 'Integration of an urban simulation model and an urban ecosystems model'. Proceedings of the International Conference on Modeling Geographical and Environmental Systems with Geographical Information Systems. Waddell, P. and M. Alberti (2000). 'Integrated simulation of real estate development and land cover change'. Fourth International Conference on Integrating GIS and Environmental Modeling (GIS/EM4), Banff, Alberta, Canada. Wagner, D. F. (1997). 'Cellular automata and geographic information systems'. Environment and Planning B 24: 219-234. Webster, C. J. and F. Wu (1998). Simulations of urban growth with models of pollution property rights and subcentre formation. In Graphics, Visualisation and the Social Sciences: Report from Workshop held May 8-9. Advisory Group on Computer Graphics (AGOCG) Technical report Series No. 33. A. Mumford. Loughborough, Loughborough University Joint Information Systems Committee (JISC): 113-122. Webster, C. J. and F. Wu (1999a). 'Regulation, land use mix and urban performance. Part 1, performance'. Environment and Planning A 31 (8): 1433-1442. Webster, C. J. and F. Wu (1999b). 'Regulation, land use mix and urban performance. Part 2, theory'. Environment and Planning A 31 (9): 1529-1547. Wegener, M. (1996). The potential of microsimulation for urban models. In Microsimulation for Urban and Regional Policy Analysis. G. P. Clarke. London, Pion. 66

White, R. (1998). 'Cities and cellular automata'. Discrete Dynamics in Nature and Society 2: 111-125. White, R. and G. Engelen (1993). 'Cellular automata and fractal urban form'. Environment and Planning A 25: 1175-1199. White, R. and G. Engelen (1997). 'Cellular automata as the basis of integrated dynamic regional modelling'. Environment and Planning B 24: 235-246. White, R., G. Engelen and I. Uljee (1997). 'The use of constrained cellular automata for high-resolution modelling of urban land use dynamics'. Environment and Planning B 24: 323-343. Wolfram, S. (1994). Cellular Automata and Complexity. Reading, MA, Addison-Wesley. Wu, F. (1998). 'An experiment on the generic polycentricity of urban growth in a cellular automatic city'. Environment and Planning B 25: 731-752. Wu, F. (1999). 'A simulation approach to urban changes: experiments and observations on fluctuations in cellular automata'. Sixth International Conference on Computers in Urban Planning and Urban Management, Venice, Italy. http://brezza.iuav.it/stratema/cupum/. Wu, F. and C. J. Webster (1998). 'Simulation of land development through the integration of cellular automata and multicriteria evaluation'. Environment and Planning B 25: 103-126. 67

Xie, Y. (1994) Analytical models and algorithims for cellular urban dynamics. Ph.D. Thesis. University of New York at Buffalo, Buffalo, NY. Yeh, A. G.-O. (1998). 'Sustainable land development model for rapid growth areas using GIS'. International Journal of Geographical Information Systems 12 (2): 169-. Yeh, A. G.-O. and L. Xia (2000). Simulation of compact cities based on the integration of cellular automata and GIS. In Theoretical and Practical Issues on Cellular Automata. S. Bandini and T. Worsch. London, Springer-Verlag: 170-178. 68

Psychological preparation of athletes for the Olympic context: The New Zealand summer and winter Olympic teams, 14 pages, 0.09 Mb

doc.uments.com

About Us :: Privacy Policies :: Terms of Service :: Feedback :: Copyright :: Contact Us :: DMCA Policy

Copyright © 2018 doc.uments.com