Cellular Automata as Analytical Engines in Geographic Information Systems

Soohong Park and Daniel F. Wagner
Department of Geography, The University of South Carolina, USA

Contemporary Geographic Information Systems (GIS) suffer from a variety of problems. These include poor performance for many operators, poor ability to handle dynamic spatial models, and poor handling of the temporal dimension. Cellular Automata (CA) have much in common with raster GIS and also excel in many of the areas of deficiency of GIS. CA are dynamic systems based on discrete time and space. While CA are generally described for synthetic universes, the CA's discrete model of space is analogous to the tessellation models of contemporary raster GIS. CA systems evolve in discrete time steps through the synchronous application of universal transition rules. Through these transition rules, the state of each cell is determined for time t based on the states of neighbouring cells at times t-l ... t-n. The transition rules of CA thus correspond to the spatial operators of GIS.

GIS spatial operators can be implemented using CA transition rules: examples include filtering and buffering; similarly CA transition rules can be implemented using GIS: examples include voting rules, counting rules, and the classic 'Game of Life'. By considering the spatial operators of GIS as CA transition rules, an improved ability to mathematically characterise the operators is achieved. Further, while contemporary GIS do not explicitly handle the temporal dimension, CA systems do, resulting in a powerful spatial dynamic modelling capability for CA. In addition, if special hardware - Cellular Automata Machines (CAM) - are used, the potential for performance benefits exist.

Although CA offer advantages in dynamic spatial modelling over GIS, they cannot themselves be considered as GIS. CA lack the GIS's sophisticated capabilities for data input, storage & retrieval and output. In order to fully exploit the advantages of each system: GIS and CA, this research presents an approach to tightly couple the two systems. In the integrated system, the CA functions as an advanced spatial analysis engine. In order to achieve the tight coupling, a common user interface, a data model translator, and an inter-operation handler (consisting of both constructor and accessor modules) are utilised. Through the common user interface, both systems are wrapped into one, and the user can transparently access GIS built in functions, CA dynamic models, and hybrid models utilising both GIS and CA functions. The data model translator converts data files between the GIS and CA and vice versa. The inter-operation handler is the critical piece in the tight coupling strategy. As constructor, the inter-operation handler generates commands needed for invoking each system and running models on the appropriate system. As accessor, the inter-operation handler actually executes the sequence of commands created by the accessor. Within a single dynamic modelling operation both GIS functions and CA models may be accessed with intermediate results passed between the two systems.

This research describes the design and implementation of such an integrated system. The tight coupling strategy described is platform and software independent. The prototype system developed uses the IDRISI raster GIS and both CAM-6 and Cellular CAs and is based on an IntelTM platform. Benefits of the integrated system include: new spatial operators including spatial and temporal filters, time-series and diffusion operators; improved performance for some existing spatial operators, and most significantly a flexible system for spatial dynamic modelling. Spatial dynamic models implemented in the prototype system include: an innovation diffusion model, a forest fire model, and an urban growth model.

Since the tight coupling strategy is platform independent, virtually any raster GIS and CA system can be similarly integrated. We conclude that CA represent a viable alternate analytical engine for GIS and provide increased ability for dynamic modelling within GIS. In addition, based on the prototype system, it is clear that such an integrated GIS-CA system holds promise for higher dimensional spatial analysis including both three-dimensional and spatio-temporal analyses.