GeoComputation Logo

Return to Main Index

Cities, cells, and complexity: developing a research agenda for urban geocomputation

Paul M. Torrens
Centre for Advanced Spatial Analysis, University College London,
London WC1E 6BT, UK.
E-mail: ptorrens@geog.ucl.ac.uk

David O'Sullivan
The Pennsylvania State University, Department of Geography,
University Park, PA 16802, USA.
E-mail: osullivan@geog.psu.edu

Abstract

Cellular automata are widely employed in urban geocomputation and have been applied to urban systems simulation with a recent fervour. Despite the popularity of these models, however, researchers have been slow to heed the doubts and disclaimers expressed in the early days of their application to urban phenomena. This is, in part, a response to advances in the field. However, many of these concerns remain as appropriate today as they did in the 1980s, and have not been addressed largely because the study of cellular urban modelling, and the broader field of urban geocomputation, lacks a defined research agenda. This paper addresses an apparent imbalance in the field and re-evaluates the research agenda of urban geocomputation, in particular cellular-based modelling of urban systems, pre-emptively suggesting future avenues for exploration and considering the challenges that might lie ahead.

1. Introduction

The popularity of cellular automata (CA) modelling of urban systems, and recent enthusiasm for their application to urban studies, is impressive. CA models have been employed in the exploration of a diverse range of urban phenomena, from traffic simulation and regional-scale urbanisation to land-use dynamics, polycentricity, historical urbanisation, 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).

It is not surprising that the list of applications to urban systems is so extensive. CA are a powerful tool for urban systems simulation and go some way towards remedying the deficiencies of traditional simulation models. Traditional models --- particularly those derived from early waves of land-use and transportation modelling --- have been criticised for their weak treatment of dynamics, misalignment with urban and spatial theory, poor attention to detail, the flaws inherent in zonal geography, and alienation of model users (Harris 1994; Lee 1973; Openshaw 1983; Oryani and Harris 1996; Sayer 1979; Smith 1998; Torrens 2000). CA, on the other hand, have many advantages for modelling urban phenomena, including their introduction of complexity theory, connection of pattern and process, encapsulation of proximal space, attention to detail, visual presentation, inherently dynamic nature, and affinity to geographic information systems and remotely sensed data. The most significant of their qualities, however, is their relative simplicity. By mimicking how macro-scale urban structures may emerge from the myriad interactions of simple elements, CA have the potential to reduce the formidable complexity of urban systems to a manageable level. However, to a significant degree, CA models of urban systems are also constrained by that simplicity and their ability to represent real-world phenomena is often diluted by their abstract characteristics.

Given the profusion of recent uses of CA models in urban studies, it is hard to believe that developments in the field have been shadowed by a sense of uneasiness regarding their application to urban problems. In particular, anxieties have been articulated about tinkering with the strict formalism of CA. Researchers are uneasy about the limited capacity of strict CA to represent complicated urban systems, but are also concerned that adding components to supplement that simple formalism may yield unwieldy simulations, defeating the purpose of using simple cellular models in the first place (Batty 1997b; Couclelis 1997). To a degree, many of those concerns are now overlooked and ignored, cast to the side as optimism and enthusiasm has swept through the field of geocomputation. This casual approach to what are justified doubts is due, in part, to technological and methodological advances in the field, and to the growing sophistication of the models. This stance owes much to the fact that many of the problems are not easily overcome. The approach also stems from the lack of a defined research agenda for cellular modelling of urban systems, and for the broader field of urban geocomputation.

We can consider geocomputation as the "computational approach to the solution of complex geographical problems" (Couclelis 1998). Given that, for many of us, the testing ground for research in geocomputation is the city, we might envisage a subset of that field --- urban geocomputation --- concerned with exploring problems in urban studies using spatial computation as the research vehicle. Although incorporating activities from fields such as spatial analysis and urban modelling, the emphasis here is on the use of computation as distinct from computers or computer science. Consequently, the research toolbox of urban geocomputation contains apparatus such as artificial intelligence (Kurzweil 1999), artificial life (Levy 1992), agent-based models and bots (Leonard 1997), genetic algorithms (Mitchell 1998), and of course, one of the cornerstones of computation: cellular automata (Sipper 1997). Further, many of the systems under investigation in the field can be considered to be complex adaptive systems, and much of the urban geocomputation approach incorporates computational techniques that derive from complexity studies (Lewin 1992).

This paper seeks to address what appears to be an imbalance in the field by re-evaluating the research agenda for cities, cells, and cellular automata and by proposing one possible approach to future exploration in urban geocomputation. The discussion continues in section 2 with an evaluation of how cellular models of urban systems depart from strict CA and to what extent urban models can in fact be considered as CA. This in turn informs the introduction of a research agenda in section 3. The paper concludes in section 4 with a brief discussion of the future of urban systems simulation using cellular models, their influence on urban geocomputation, and their role in urban and spatial theory and in city planning.

2. Cellular automata and cellular models of urban systems

Like many simulations, CA are an abstraction --- simplified representations of phenomena that operate in the physical world employed as aids in the understanding of how the dynamics of those systems function. However, the character of CA as applied to the study of urban phenomena departs significantly from the strict formalism described by the original pioneers of the field: Ulam, von Neumann, Conway, and Wolfram (Levy 1992; Poundstone 1985; Sipper 1997; Wolfram 1994). In many cases, the strict approach to CA modelling has proven to be ill suited to the study of urban dynamics. CA must, in many cases, be quite heavily modified before they can approximate to even a crude representation of an urban system. This often necessitates the introduction of additional components to supplement the functionality of the formal CA.

At the most rudimentary level, a cellular automaton is represented as a two-dimensional (often one-dimensional) array of regular spaces (cells) At any given time, a particular cell is in a discrete state that is determined by the attributes of its neighbouring cells according to some uniformly applied transition rules. Cells alter their states iteratively and synchronously through the recursive application of these rules. A CA is thus composed of four principle elements: a lattice, a state-space, neighbourhoods defined by the lattice, and transition rules. In addition we might consider a fifth, temporal component. Formal CA offer only a limited range of configuration of these elements. Urban cellular models invariably modify this structure to a significant degree in a bid to represent cities in a realistic fashion.

Adaptation of, and experimentation with, urban CA has been both prolific and innovative, dominating much of the recent published work in urban geocomputation. The dimensions and structure of CA lattices have been modified and the range of cell states has been expanded both in terms of concurrency, character, and value. Additionally, neighbourhoods have been varied considerably to accommodate action-at-a-distance above and beyond the simple Moore and von Neumann manifestations of formal CA (Batty 1997a). Transition rules have also been modified and expanded to include notions such as hierarchy, self-modification, probabilistic expressions, utility maximizing, accessibility measures, exogenous links, weights, inertia, and stochasticity. To a lesser extent the temporal dimensions of urban cellular models have also displayed a degree of departure from the strict formalisms. In fact, many --- if not all --- urban CA bear little resemblance to the formal CA model. Modification has been so extensive that it remains in doubt as to whether urban CA actually constitute CA at all, or are in fact simply cellular models of urban systems (O'Sullivan and Torrens 2000).

2.1 Lattice structures

Strict CA in two dimensions are commonly defined on an infinite plane that is structured into a tessellation of regularly spaced grid squares. Of course, the idea of an infinite spatial plane is unrealistic in most urban contexts. Consequently, CA employed for urban research are often constrained to finite dimensions, with various tricks for the treatment of edge effects (White and Engelen 1997). The assumption of regularity in lattice structure is also problematic for urban applications. While many features of cities are regular --- some block configurations, building facades, internal floor plans, and many road networks --- the majority are not. To cope with this problem, and in a bid to afford cellular models a greater degree of realism, researchers have departed from the strict CA formalism by introducing irregular lattice structures (O'Sullivan 2000).

2.2 State-space

The cell-space in a strict CA is a closed environment: it cannot be influenced by external events. With this configuration there is no place for independent forces that might enter cell-space at the macro-scale (Couclelis 1985). Naturally, this makes little intuitive sense in the context of the city, in which exogenous links and dependencies are widespread. This limitation has been overcome in cellular urban models by opening the cell-space to outside influences, often through constraints and rules applied to transition functions (Clarke, Hoppen, and Gaydos 1997; Couclelis 1985; Semboloni 1997; White and Engelen 1997; White, Engelen, and Uljee 1997). Cell-states have also been reformulated in a hierarchical fashion, reflecting the notion that state transition in urban contexts (land-use dynamics, for example) has a tendency towards pursuing fixed paths and proceeding from one state to another sequentially (White and Engelen 1993).

Recent research has attempted to introduce a greater degree of sophistication into cell-state design by permitting cells to adopt several concurrent states in a variety of forms. For example, binary states --- developable or not developable --- appear alongside integer state values --- land use categories, for example, and continuous values corresponding to various urban characteristics and properties, such as population counts (Wu 1998).

Heterogeneous definition of cell-states has also been introduced into the design of cellular urban models, marking yet another departure from formal CA representations. White and Engelen (1997) introduce the notion of cell-state fixture in their model of Cincinnati. They distinguish between cell states that are fixed and those that are regarded as functional. These definitions refer in this case to land uses that are generally exempt from urban development (such as water bodies) and those that are active in the development process (vacant lots, for example).

2.3 Neighbourhoods

The neighbourhood of a cell in the CA formalism consists of an individual cell itself as well as a set of adjacent cells. In strict two-dimensional CA this results in two possible neighbourhood configurations: the Moore neighbourhood of the eight cells that form a square around the cell in question, and the von Neumann neighbourhood of the four directly adjacent cells comprising a cross centred on a cell (Batty 1997a). Urban modellers have criticised this uniformity in neighbourhood specification, particularly for its rejection of action-at-a-distance (Batty and Xie 1997; Couclelis 1997). In the real world neighbourhoods vary significantly depending on the process in question. Social interaction, for example, can operate between adjacent properties as well as functioning on a city-wide scale. Recent developments in urban cellular models have therefore moved away from this simple approach to neighbourhood configuration. Distance decay effects have been built into neighbourhoods, often by weighting cell neighbourhoods by varying amounts. Neighbourhoods have also been extended to comprise larger spaces (White and Engelen 1997; White, Engelen, and Uljee 1997).

2.4 Transition rules

The greatest number of adaptations to the strict CA formalism have appeared in the formulation of transition rules. As already mentioned, transition rules have been opened up to exogenous links. Also, they have been expressed as probabilistic functions, a departure from the deterministic specification of strict CA. In probabilistic expressions, the action of a transition function is rendered contingent upon a probability or made dependent on other decision rules formulated within the model.

Transition rules for urban models have also been redesigned to introduce a degree of self-modification. Reflecting ideas such as the genetic algorithm in computer science (Mitchell 1998) and evolutionary principles in biology (Holland 1998), the transition function is allowed to change via a feedback mechanism as a cellular automaton evolves (Clarke, Hoppen, and Gaydos 1997). Adaptation in transition rule formulation has also included other simulation techniques from urban modelling, particularly ideas from regional science and econometrics. Wu (1998) has formulated a cellular automaton with its rules rooted in utility theory, and other economic principles have featured heavily in transition rule formulation (Webster and Wu 1998, 1999a, 1999b; Wu and Webster 1998). Accessibility calculations, commonly expressed in spatial interaction equations, have also featured in CA modifications for urban purposes (White and Engelen 1997).

2.5 Time

The treatment of time in CA has not escaped the tinkering of researchers in urban studies. In strict CA, time is treated in a discrete fashion and cells are made to evolve uniformly in the temporal domain, with all cell states updated synchronously as transition rules are applied simultaneously at every location. Portugali (2000) has experimented with effective asynchronous cell-state update via the actions of agents in a CA space, and the models of White and colleagues (White 1998; White and Engelen 1993, 1997; White, Engelen, and Uljee 1997) have modified the cell update process so that it is partly sequential, with a dependence on exogenous constraints. In another example, Wu (1999) introduces asynchronous operation as a fundamental aspect of system dynamics, relating an urban development model driven by 'investment niches' to notions of self-organised criticality.

2.6 So what?

Obvious questions arising from this discussion are, "So what?" and, "Does this matter?" These are straightforward questions with no simple answer. In some cases the implications of tinkering with the structure of formal CA are of minor significance, with no bearing on urban systems simulation; in others, there may be significant consequences. In some senses, tinkering with the strict CA formalism is irrelevant. As long as the innovations advance our capacity to generate more functional models of urban systems and open up new avenues of academic inquiry, then the modifications are welcome.

However, the implications for system dynamics of many CA variants are not well understood and may thus have significant consequences. Elsewhere, we have suggested that most of the CA modifications considered in the preceding discussion can be grouped into a few major variations and that these could form the basis of a more coherent approach to research in this area in future (O'Sullivan and Torrens 2000). Among other possibilities, we have suggested that strict CA models of a limited range of geographical processes, models with irregular lattice structures, cellular models with agent populations, and CA with asynchronous cell update represent a formally definable 'family' of cellular, computational models. In fact, we can only hope to answer our questions about the significance of even such a limited diversity of CA variants with reference to the aims of the research in which modified CA are introduced, and more generally, with reference to an as yet ill-defined research programme for urban modelling and geocomputation. It is to the definition of this research agenda that we now turn.

3. A research agenda for cellular models of urban systems

Reconsidering the use of CA models of urban systems, we can conceive of applying our family of cellular urban models to three principle research goals: (i) the exploration of spatial complexity, (ii) abstract models for testing hypotheses and theories relating to the city, and (iii) the development of operational urban models to inform policy-making and urban management in the real world. Of course, these classifications are not unrelated, and there is a degree of overlap between these research goals (see figure 1). Strict CA are not suitable for pursuing any of these lines of inquiry. It is therefore understandable that cellular urban models have been so widely adapted in order that they can be moulded to better suit research needs.


CA Spectrum

Figure 1. A spectrum of cellular models

The modification of CA designed to explore spatial complexity and to inform urban theory may have far-reaching consequences for system dynamics and behaviour. Where the promise of CA modelling has been to deliver models that generate complex patterns from simple elements, the introduction of new ingredients into the simulation soup may have unpredictable and unforeseen consequences for the flavour of the resulting models. It is already understood that CA and CA-like model behaviours can be highly sensitive to small changes in their transition rules. These models exist, as it were, on the edge of chaos (Langton 1992), and tinkering with their structure casually and hastily, puts researchers in danger of fulfilling early premonitions that the power of simple CA to inform urban studies and simulation would be lost. For operational models a radical level of departure from formal expressions is, on the other hand, more forgivable. Operational models are judged by criteria that differ from those applied to models developed for more academic purposes, principally their capacity to inform urban planning and urban management. However, operational models are also charged with delivering as realistic an expression of urban systems as possible and the introduction of modified cellular modules into operational simulations, without a full understanding of the dynamic implications, must also be approached with care.

The value of CA and cellular models in complexity studies, urban studies, and urban geocomputation is not doubted here. What is clear, though, is that there is a strong need to develop an agenda for future research in the field, lest the mistakes of earlier generations of large-scale urban modelling are replicated and our research is doomed to the contempt and disillusionment with which many of those models were met (Couclelis 1997). Indeed, we would do well to mould our applications of CA and cellular urban models around the three research goals outlined at the beginning of this section, and to shape and consider our adaptations of the strict CA formalism accordingly. This section paints a picture of the likely nature of such a research agenda and pre-emptively considers some of the challenges which may pose difficulties.

3.1 Cellular models of spatial complexity

The system dynamics of many actual and possible CA variants are not well understood and this constitutes a major line of inquiry wherein geocomputation may contribute to computational theory and to studies in the sciences of complexity. Cities are amongst the finest examples of complex systems. From local-scale interactions such as individual movement habits and social biases regular patterns emerge across a variety of urban scales, such as traffic congestion, economies of agglomeration, and social segregation. Moreover, these systems display many traits common to complex systems in the biological, physical, and chemical worlds. Researchers in complexity studies have a lot to learn from cities and CA and cellular urban models are excellent vehicles for exploring spatial complexity. Experiments with fractal geometry and feedback mechanisms in CA are amongst the most influential works in this area (Batty and Xie 1997; White and Engelen 1993). However, if urban CA research is to contribute to theories of complexity, with relevance across disciplines from biology to physics and chemistry, and at all scales of organisation from the nano-scale to that of the cosmos, it is necessary that the form of cellular urban models preserve as many features of formal CA as possible. Alternatively by adopting a limited, well-defined family of departures from strict CA with origins in urban complexity, other researchers may be encouraged to experiment with such models also. Either way findings might be compared with work in other disciplines and parallels could be drawn between urban research and advances in other areas, a mutually beneficial exchange which has so far been rare.

The key to explorations of spatial complexity should not focus strictly on simulation: rather, it should be concerned with the search for the simple ingredients of complexity that we find in cities and examine how these compare with simple complex elements in other fields. With this in mind, there exist several areas of continued and uncharted exploration into spatial complexity: the investigation of multi-dimensional complexity, the construction of transition rules within a relatively formal CA structure and the patterns that those rules generate, and also the exploration of agent-based models of complexity in city-like environments.

It is striking to the geographer that apart from the notorious Game of Life example (see Poundstone 1985), much of the most widely cited CA literature in physics and the natural sciences focuses on the behaviour of one-dimensional CA. Research from a geographical perspective into CA has usually adopted two-dimensional CA but has not attempted any systematic exploration of the properties of such systems. Along with examining the dynamics of higher dimensional CA, research which explores the impact of other spatial structures on cellular models is required (see O'Sullivan forthcoming). There is no reason why research designed to explore spatial complexity with cellular urban models should not direct its attentions beyond two dimensions. Intuition suggests that the search for spatial complexity in urban systems must lead researchers at least into three dimensions, if not more. Multi-dimensional cellular models of complexity represent a potentially rewarding avenue for future investigation.

CA research into spatial complexity must also investigate the meaning of transition rules applied within strict CA and the capacity for those rules to generate complex patterns from simple ingredients. To this end, research should explore issues of emergence, positive feedback, path-dependence and lock-in, bifurcation, and self-organisation and what rules generate these characteristics in CA settings. These efforts should be supplemented (or in some cases supplanted) by other more appropriate techniques, such as agent-based models and fractal-based techniques for investigating scaling and power relationships. Indeed, the continued application of agent-based models in the search for complexity in urban systems will likely be instrumental in shaping our future understanding in this area. As yet, agent-based modelling has not enjoyed the popularity afforded cellular approaches, but this seems set to change and the Free Agents in Cellular Space models of Portugali and his colleagues (Portugali 2000) seems a useful starting point for such investigations.

Research with cellular urban models has demonstrated the potential for exploring spatial complexity in urban systems, but that research effort has been slow to link with complexity studies in other disciplines. Equally, there is a need for research to broaden its search for spatial complexity and extend the range of its investigation to other urban phenomena that have escaped detailed research attention. In particular, cellular models will need to consult and draw parallels with work in areas such as environmental simulation (geological, atmospheric, ecological, and hydrological modelling) and sociology. Here, the application of CA to systems simulation has been widespread and has the capacity to greatly inform our understanding of urban complexity beyond what is already known about complexity in urban form, land use, and urban development.

3.2 Cellular models of urban theory

The second item on our research agenda is the application of our suggested family of models (and others) to test hypotheses and theories relating to the city. We can learn a great deal about complexity by examining cities, and the relationship is reciprocal --- urban theory has a lot to learn from complexity. As has long been suspected, and as existing models have demonstrated, complexity is a key idea in understanding the processes driving urban patterns. In this sense, theoretical cellular urban models are closely allied with those developed to explore spatial complexity, but are distinct. The purpose of cellular models of spatial complexity in cities is to inform our understanding of complex adaptive systems. Cellular models of urban theory on the other hand, are used to explore the role that complexity has in driving the core components of urban phenomena such as growth, sprawl, edge city formation, polycentricity, agglomeration, inertia, diffusion, spatial structure, and segregation. Essentially, these models might be used as laboratories for testing theories relating to the city, much in the vein of the theory-building models of Losch, von Thünen, Burgess, and Christaller --- rather than complexity theory, per se. Much headway has already been made in this area of cellular urban modelling, particularly by Batty and colleagues (Batty 1997a, 1998, 1999; Batty and Xie 1994, 1997; Batty, Xie, and Sun 1999; Xie 1994) and Webster and Wu (1998, 1999a, 1999b; Wu 1998; Wu and Webster 1998). Other researchers have also made important in-roads in this area (Benati 1997; O'Sullivan 2000; Portugali, Benenson, and Omer 1997; Sanders et al. 1997; Semboloni 1997). Indeed, the range of urban phenomena remaining to be addressed by cellular models is narrowing steadily. These models inevitably incorporate heavy modifications to the strict CA formalism, departing significantly in character from those mentioned in the previous section, but falling short of the outright abandonment of the formalism evident in operational models.

However, as in the physical sciences (Goldenfield and Kadanoff 1999), cellular models of urban theory have so far done little to inform theory. Many models purport to the exploration of hypotheses, but the direction of much of this research has become clouded. Modellers often get mired in the details of model construction at the expense of the theories that they set out to explore, so that the distinction between these research goals is often muddied. These models cannot fully claim to be complexity models, yet neither are they operational in any sense, often being developed for hypothetical situations or with severely limiting assumptions. The remit of cellular models of urban theory should focus on the careful and measured variation of the components that make up cellular urban models. Developments originating in urban theoretic considerations should be used to investigate what are the necessary and contingent implications of those theories, and hence to shed light on their interaction. At the same time, such research may uncover the effects of altering the character of CA-lattice structures, the dimensions of cell space, the nature of cell states, neighbourhood configurations and sizes, temporal dynamics and should study the impacts of those adaptations on patterns generated from process-driven transition rules.

Thus the goals of research discussed in this and the previous section are closely linked, and in many cases will be concurrent. For urban theory investigations, links to theory should be clear and explicit. Research into this area has the potential to offer new insights into both spatial and urban theory as well as informing the development of new simulation techniques. However, as with models of spatial complexity, research into cellular models for theory building has neglected some important areas of investigation, principally the capacity for these models to generate new urban patterns and the value of CA as an educational tool.

One of the great advantages of using CA to test ideas relating to the city, or indeed as inspiration for new ideas, is their capacity to generate city-like patterns from theoretically informed components. Yet, to date, the capacity for models to generate organic forms has been used to replicate already well-documented urban processes, such as growth, multi-nucleation, and land use transition, within a controlled computer environment. The fruits of that work have been rich, but only as validation: models do little to actually inform urban theory, while often falling short in providing us with new simulation methodologies for operational models. Importantly, the capacity of models to generate new urban patterns and phenomena suggestive of the likely future of urban environments --- the next edge city, technopole, or megalopolis --- has not been fully explored. Of course, such research may prove rather difficult: how would we recognise new urban forms if we saw them? But the possibilities that these models offer are too rich for the opportunity to be missed.

Earlier in this section we drew analogies between cellular models for theory building and the conceptual models of classic urban geography. However, while those classic conceptual models, based on limiting assumptions and a simplified description of cities, contribute a great deal to our understanding of the city, the opportunity for cellular models to serve in this fashion has yet to be capitalised upon. Particularly, the chance to use cellular models in the classroom as a dynamic, graphic, and interactive educational tool for geography and geocomputation has not been widely embraced, despite the availability of software specifically catered towards education and freely available in the public domain (Resnick 1997).

Finally, abstract cellular models for testing urban theory are, in many cases, massaged into compliance with urban theories, rather than serving as vehicles for the generation of new ideas and as a laboratory for hypothetical experimentation. This runs counter to the goal of informing theory and serves to validate existing knowledge, but only in an artificial and contrived manner. The potential to learn from these models is likely to be much greater if simulations are left lean, with minimal 'tweaking' so that the focus is returned to the exploration of ideas rather than the generation of convincing results.

3.3 Operational cellular models

By virtue of their use in decision support, urban planning, and urban management, operational cellular models of cities will likely depart most markedly from strict formal CA. Cellular approaches offer great potential for operational urban modelling. Many significant advances have been made in the design of operational cellular models, particularly by White and colleagues (White 1998; White and Engelen 1993, 1997; White, Engelen, and Uljee 1997), as well as Clarke (1997) and the TRANSIMS team (Nagel, Barrett, and Rickert 1996; Nagel, Beckman, and Barrett 1999). The advantage of their relative simplicity, coupled with their affinity to graphical presentation, opens up new and exciting opportunities for engaging with the model user in an interactive fashion. The infusion of new behavioural foundations from complexity theory into urban modelling --- a field often criticised for its ignorance of theory --- is also welcome. Moreover, CA and cellular approaches have the capacity to handle data from geographic information systems and remote sensing with ease. Indeed, land-use and transport modelling is ripe for the introduction of CA-like approaches. Models formulated on principles of decision theory closely approximate the transition-based techniques of CA and the introduction of an essentially spatial component to supplement those methodologies has the capacity to open up new avenues for operational model development. Indeed, following the development of the TRANSIMS model at Los Alamos National Laboratories, there has been a concerted drive to push metropolitan planning organisations into incorporating cellular elements in their forecast models (Travel Model Improvement Program 1999). Nevertheless, some important avenues for development, as well as serious limitations, remain. There is room for improving the formulation of transition rules driving operational cellular models. Additionally, the impact that CA-like approaches may have on the user community has yet to be fully explored. Equally, there is a strong need for the investigation of directionality in urban systems (which processes operate from the top-down, and which emerge from the bottom upwards?) and a strong framework for hybrid models needs to be developed. Also, the validation of cellular models poses a major barrier to the continued use of a rich simulation methodology in real-world applications.

The issue of transition rule formulation in operational cellular urban models offers great potential for innovation. The design of rules is one area in which operational models have the chance to associate with theory. Some advances have been made in the formulation of transition rules derived from urban economic theory, particularly in models of development (Webster and Wu 1999a, 1999b; Wu and Webster 1998), but this success ought to be extended to encompass other areas of urban theory, such as social justice, location theory, urban design, political economy, environmental science, urban sociology, and landscape ecology. This would have the advantage of placing operational models on a more solid theoretical foundation. Additionally, it offers the potential for moving operational urban modelling and urban geocomputation away from an overarching allegiance to urban economics and towards a more interdisciplinary focus.

As we have mentioned, the educational merits of cellular urban models have not been well exploited. Equally the value of cellular models in the operational user community is not yet well understood. One of the main advantages of the emphasis of the cellular approach on simplicity and visualization is the potential that it offers for engaging with model users in an interactive fashion, greying the black box approach to operational simulation and rendering operational models more intelligible, accessible, and user-friendly. Yet, there has been little investigation as to what the benefits of cellular modelling in the user community are. What visualization methods work well with users and for public outreach? How can users best participate in model development --- through transition rule formulation, or model testing, or both? And to what extent does the cellular approach actually improve our ability to plan and manage urban systems in the real world?

There is much justification for approaching urban simulation from the local level. 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 the global level phenomena that strongly influence urban systems, but do not emerge from local components (O'Sullivan and Torrens 2000). In light of this consideration, there is a convincing argument for developing hybrid operational models. Such models could simulate the aggregate and global level dynamics of urban systems in the conventional sense using techniques widely employed in practice: spatial interaction, spatial choice, input-output models, demographic forecasting techniques, and so on, but could delegate micro-scale dynamics to cellular and agent-based models in an integrated and seamless fashion. In this sense, urban systems with processes operating from the bottom up as well as from the top down could be modelled from micro to macro level in a coherent manner. Advances in this area are already underway (Phipps and Langlois 1997; White and Engelen 1997), but there is room for the investigation of top-down versus bottom-up process directionality in dynamic urban phenomena, and exactly how techniques from CA and complexity studies can be merged with traditional methodologies --- where the connections should be made and where do feedback loops exist, for example.

Finally, the issue of model validation is of serious importance to all cellular urban models, but particularly those applied in operational contexts. The emphasis thus far in urban cellular modelling has been on pattern-based validation techniques: pattern recognition, measures of match such as the chi-squared and kappa- statistics. The weaknesses of these approaches have been well documented (White, Engelen, and Uljee 1997; Wu 1998) and while much effort is being devoted to advancing our ability to calibrate cellular models (Power, Simms and White 1999), research is still bogged down in the pattern-based approach. By focusing largely on validating the patterns that cellular models have generated, this approach ignores the fact that CA comprise both pattern and process, form and function. Future research must therefore address more process-related measures such as Monte Carlo averaging, spatial information statistics, and measures of complexity, but will also need to connect these metrics to pattern-based measures.

4. Conclusions

Analogies have been drawn between the development of geocomputation as a geographical discipline and the development of other areas of geography. Bill Macmillan has argued that, "if we understand geocomputation as being related to the theory of computation, its impact could be similar to that of the quantitative revolution" (Macmillan 1998). These are high aspirations indeed, but perhaps the comparison also harbours a warning for the field of geocomputation. The quantitative 'revolution' was, after all, regarded quite negatively by many in geography, as it continues to be. Equally, it was not whole-heartedly acknowledged by the disciplines from which it drew inspiration (statistics and mathematics, for example). The danger of a similar fate looms for geocomputation. Researchers could face alienation from other geographers as well as from computer scientists and those involved in complexity studies. There is also a risk of trying the patience of those in practical fields such as public policy and planning, as well as potential funding bodies.

To an extent, these concerns stem from the lack of a common programme for geocomputation generally, and urban geocomputation in particular. Without a defined focus, advances in the development of simulation techniques are being made, but the opportunity to apply those tools to spatial problems and to connect to both theory and practice is being squandered. One way to steer the field back on track is to agree on a research agenda. This paper has attempted to sketch such an agenda and suggests that research focus on three areas: cellular models of spatial complexity, cellular models of urban theory, and operational cellular urban models. This discussion has limited itself to cities, cells, and complexity, but it is hoped that the relevance of this message to geocomputation more generally is apparent. Of course, these challenges are considerable and the longevity of the field is by no means assured. Nevertheless, as the field moves out of its infancy, the time is ripe for geocomputation to contribute to science, and to theory and practice in geography in profound and innovative ways.

References

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(2), 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 Y. Xie, 1994. From cells to cities, Environment and Planning B, 21, s31-s48.

Batty, M. and Y. Xie, 1997. Possible urban automata, Environment and Planning B, 24(2), 175-192.

Batty, M. Y. Xie, and Z. Sun, 1999. The dynamics of urban sprawl, University College London, Centre for Advanced Spatial Analysis, Working Paper 15. Available online at http://www.casa.ucl.ac.uk/sprawl.pdf.

Benati, S., 1997, A cellular automaton for the simulation of competitive location, Environment and Planning B, 24(2), 175-192.

Clarke, K. C., 1997, Land transition modeling with deltatrons, Department of Geography, University of California, Santa Barbara. Available online at http://www.geog.ucsb.edu/~kclarke/Papers/deltatron.html.

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(2), 247-261.

Couclelis, H., 1985. Cellular worlds: A framework for modeling micro-macro dynamics. Environment and Planning A, 17, 585-596.

Couclelis, H., 1997. From cellular automata to urban models: New principles for model development and implementation. Environment and Planning B, 24(2), 165-174.

Couclelis, H., 1998. Geocomputation in context, pp. 17-29 in Geocomputation: A Primer, edited by P. A. Longley, S. M. Brooks, R. McDonnell and B. Macmillan, London: John Wiley and Sons.

Goldenfield, N., and L. P. Kadanoff, 1999. Simple Lessons from Complexity, Science, 284, 87-89.

Harris, B., 1994. The real issues concerning Lee's 'Requiem', Journal of the American Planning Association, 60(1), 31-34.

Holland, J. H., 1998. Emergence: From Chaos to Order, Reading, MA: Perseus Books.

Kurzweil, R., 1999. The Age of Spiritual Machines: How We Will Live, Work and Think in the New Age of Intelligent Machines, London: Phoenix.

Langton, C. G., 1992. Life at the Edge of Chaos, in Artificial Life II, edited by C. G. Langton, C. Taylor, J. D. Farmer and S. Rasmussen, Redwood City, CA: Addison-Wesley.

Lee, D. B., 1973. Requiem for large-scale models. Journal of the American Institute of Planners, 39,163-178.

Leonard, A., 1997. Bots: The Origin of a New Species, San Francisco: Hardwired.

Levy, S., 1992. Artificial Life: The Quest for a New Creation, New York: Pantheon.

Lewin, R., 1992. Complexity: Life at the Edge of Chaos. New York: Macmillan.

Macmillan, B., 1998. Epilogue, pp. 257-264 in Geocomputation: A Primer, edited by P. Longley, S. M. Brooks, R. McDonnell and B. Macmillan, London: John Wiley and Sons.

Mitchell, M., 1998. An Introduction to Genetic Algorithms, Cambridge, MA: MIT Press.

Nagel, K., C. L. Barrett, and M. Rickert, 1996. Parallel traffic microsimulation by cellular automata and application for large-scale transportation modeling, Los Alamos, NM: Los Alamos National Laboratory. Available online at http://www-transims.tsasa.lanl.gov/PDF_Files/LAUR96-50.pdf.

Nagel, K., R. J. Beckman, and C. L. Barrett, 1999. TRANSIMS for urban planning. Los Alamos, NM: Los Alamos National Laboratory. Available online at http://www-transims.tsasa.lanl.gov/PDF_Files/LAUR98-4389.pdf.

Openshaw, S., 1983. The Modifiable Areal Unit Problem, Concepts and Techniques in Modern Geography (CATMOG) 38, Norwich: GeoBooks.

Oryani, K., and B. Harris, 1996. Enhancement of DVRPC's Travel Simulation Models Task 12: Review of Land Use Models and Recommended Model for DVRPC, Philadelphia: URS Consultants, Inc. Available online at http://www.bts.gov/tmip/papers/landuse/compendium/dvrpc_toc.htm.

O'Sullivan, D., 2000. Graph-based cellular automaton models of urban spatial processes, unpublished Ph.D. thesis, University College London, London.

O'Sullivan, D., forthcoming. Exploring spatial process dynamics using irregular graph-based cellular automaton models, Geographical Analysis.

O'Sullivan, D., and P. M. Torrens, 2000. Cellular models of urban systems. In Theoretical and Practical Issues on Cellular Automata, Proceedings of the Fourth International Conference on Cellular Automata for Research and Industry, Karlsruhe, 4-6 October, edited by S. Bandini and T. Worsch. London: Springer-Verlag.

Phipps, M., and A. Langlois, 1997. Spatial dynamics, cellular automata, and parallel processing computers, Environment and Planning B, 24(2), 193-204.

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(2), 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, Research Institute for Knowledge Systems, Research Paper, Maastricht, The Netherlands.

Resnick, M., 1997. Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds, Cambridge, MA: MIT Press.

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(2), 287-305.

Sayer, R. A., 1979. Understanding urban models versus understanding cities, Environment and Planning A, 11, 853-862.

Semboloni, F., 1997. An urban and regional model based on cellular automata, Environment and Planning B, 24, 589-612.

Sipper, M., 1997. Evolution of Parallel Cellular Machines: The Cellular Programming Approach, Lecture Notes in Computer Science 1194, Berlin: Springer.

Smith, M., 1998. Painting by numbers--mathematical models of urban systems, Environment and Planning B, 25, 483-493.

Torrens, P. M., 2000. How land-use-transportation models work, University College London, Centre for Advanced Spatial Analysis, Working Paper 20. Available online at http://www.casa.ucl.ac.uk/models.pdf.

Travel Model Improvement Program, 1999. Early deployment of TRANSIMS: Los Alamos National Laboratories. Available online at http://www.bts.gov/tmip/publ/issue_paper/issue_paper.htm.

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, edited by A. Mumford, Loughborough: Loughborough University Joint Information Systems Committee (JISC). Available online at http://www.cf.ac.uk/cplan/chris/AGOCG4.bin.

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.

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(2), 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, paper presented at Sixth International Conference on Computers in Urban Planning and Urban Management, 7-10 September, in Venice, Italy, available online at http://www.iuav.unive.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.

Xie, Y., 1994. Analytical models and algorithms for cellular urban dynamics, unpublished Ph.D. thesis, Department of Geography, University of New York at Buffalo, Buffalo, NY.