Go to Paper
Return to GeoComputation 99 Index

Exploring the Structure of Space: Towards Geo-computational Theory

O'SULLIVAN, David (david.osullivan@ucl.ac.uk),University College London, Centre for Advanced Spatial Analysis (CASA), Gower Street, London, WC1E 6BT, U.K.

Key Words: spatial models, cellular automata, Geocomputation

This paper describes ongoing research that seeks to answer Couclelis' (1998a, 1998b) call for a specifically geocomputational theory in her Challenges for Geocomputation, through a phenomenological investigation of a new class of models of spatial processes.

The models themselves are not novel, but are a recently proposed adaptation of cellular automata (CA) models familiar from the field of computation. Conventional cellular automata consists of three elements: a cell space, a set of allowed cell states, and a set of rules governing the evolution of cell states over time. In these traditional CA, the cell space is an infinite regular lattice such as a grid, in which each cell has an identical neighbourhood composed of the cells that are immediately adjacent to it in the lattice. Although CA have been successfully applied in geography (see for example: Tobler, 1979, Clarke et al., 1997, White and Engelen, 1993, Xie, 1996, Batty, 1996, Batty and Xie, 1997), Couclelis (1997) points out that the spatial model implied by such models is somewhat simplistic, and that it may be appropriate to relax the requirement for a regular lattice (Couclelis, 1997, Takeyama and Couclelis, 1997). In this paper such models are referred to as graph-based CA, because this draws attention to the underlying relational structure implicit in them.

The remainder of this paper proposes a method by which the properties of such models might be usefully explored, and concludes with some initial results from such an exploration. The approach adopted seems relevant to geocomputation in that it seeks to develop our understanding of the relationships between the structure and dynamics of spatial models, and so may help in the development of more coherent perspectives on geographic space.

Model structure may be characterised by using some of the numerous graph structural measures that have been proposed. A brief survey of some graph measures of the sort that may be of interest is presented.

The dynamics of model behaviour may be characterised by reference to Wolfram's (1983) classification of (regular) CA behavioural classes. Wolfram and others (for example Wuensche, 1998) have suggested entropy-like measures that may be used to classify the dynamic behaviour of these discrete systems as variously homogeneous, cyclic, complex, or chaotic. An adaptation of these entropy measures is proposed that takes into account the variations in cell neighbourhood sizes present in graph-based CA.

It is suggested that it may be profitable to bring these two sets of mathematical ideas together in a phenomenological investigation of graph-based CA models. By building a graph-based CA, running a number of starting configurations, and using the proposed entropy measures, its behavioural class can be determined. Such a set of experiments constitutes one observation. Further observations are generated by successively deforming the underlying graph, while holding the behavioural rules constant, and running the same set of starting configurations on each deformed graph-based CA. Graph structure measures may then be used as the independent variable, as the dependent variable of dynamic behavioural class is investigated. Such a program of research is analagous to the search in the life sciences for a relationship between the structure of CA rules and their dynamic behaviour (Langton, 1990), and might be described as an exploration of spatial structure.

The final part of the paper will present initial results from some experiments of the type described.

A final section will suggest practical additions to this class of models, and possible avenues for further research.

References

Batty, M. (1996), Urban Evolution on the Desktop: Simulation with the Use of Extended Cellular Automata, Environment and Planning A, 30, 1943-1967.

Batty, M. and Y. Xie, (1997), Possible Urban Automata, Environment and Planning B: Planning & Design, 24(2), 175-192.

Clarke, K. C., S. Hoppen and L. Gaydos, (1997), A Self-Modifying Cellular Automation Model of Historical Urbanization in the San Francisco Bay Area, Environment and Planning B: Planning & Design, 24(2), 247-262.

Couclelis, H. (1997), From Cellular Automata to Urban Models: New Principles for Model Development and Implementation, Environment and Planning B: Planning & Design, 24, 165-174.

Couclelis, H. (1998a), Geocomputation and Space, Environment and Planning B: Planning & Design, 25th anniversary issue, 41-47.

Couclelis, H. (1998b), Geocomputation in Context, pp. 17-29 in Geocomputation A Primer, Eds: P.A. Longley, S.M. Brooks, R. McDonnell, and B. MacMillan, (John Wiley & Sons: Chichester, England).

Langton, C. G. (1990), Computation at the Edge of Chaos: Phase Transitions and Emergent Computation, D. Physica, 42, 12-37.

Takeyama, M. and H. Couclelis, (1997), Map Dynamics: Integrating Cellular Automata and GIS through Geo-Algebra, International Journal of Geo-Information Science, 11, 73-91.

Tobler, W. R. (1979), Cellular Geography, pp. 379-386 in Philosophy in Geography, Eds: S. Gale and G. Olsson, (D. Reidel Publishing Company: Dordrecht, Holland).

White, R. and G. Engelen, (1993), Cellular Automata and Fractal Urban Form: A Cellular Modelling Approach to the Evolution of Urban Land-Use Patterns, Environment and Planning A, 25(8), 1175-1199.

Wolfram, S. (1983), Statistical Mechanics of Cellular Automata, Review of Modern Physics, 55, 601-643.

Wuensche, A. (1998), Classifying Cellular Automata Automatically, Santa Fe Institute, Working Paper 98-02-018.

Xie, Y. (1996), A Generalized Model for Cellular Urban Dynamics, Geographical Analysis, 28(4), 350-373.