Dynamic Spatial Modelling, Multi-Agent Systems and Simplicial Complexes

Christopher B. Jones, G.L. Bundy and J.M. Ware
Department of Computer Studies, University of Glamorgan, Ponypridd, Mid Glamorgan, CF37 1DL, United Kingdom

There is increasing interest in applying the spatial data modelling capabilities of geographical information systems (GIS) to processes that are dynamic in some sense. Examples may be found in the fields of hydrological modelling, ecological studies, retailing, and in urban and regional planning. In those applications in which it is of particular interest to study change in the spatial distribution of phenomena such as water, vegetation or human population groups, there appears to be a preference for grid-based spatial data models (Livingstone & Raper, 1994). Such models lend themselves to the use of finite difference methods (see Sham et al., 1995, for a recent example) and to experimentation with cellular automata (Benenson and Portugali, 1995), in which the value or state of individual cells may be updated repeatedly in response to numerical or rule based methods.

Undoubtedly, the grid-based approaches to spatial modelling have much to offer for phenomena that are viewed as continuously variable in space, corresponding to the field view of GIS spatial models, but they are less well adapted to the study of regions or groups of phenomena that may operate at a higher level, reflecting either some aspect of social cohesion or of physical or structural cohesion. For example, the characteristics of an urban area cannot be regarded as the sum of a set of discrete cells, each of which can only communicate with its immediate neighbours. Individuals living at the boundary of an urban area may only be there because of spatially distant properties of the centre of the region.

For purposes of automated simulation of situations that involve aggregate spatial phenomena, there is a need for an alternative to the cell-based models typically used to address dynamic processes. In this paper we consider the potential of multi-agent software architectures to represent the behaviour of aggregate objects and the spatial interactions that may occur between them.

There are several concepts associated with software agents and with multi-agent systems that are relevant to modelling spatial interactions. Agents, like software objects, may be regarded as corresponding to individual real-world phenomena, but they are characterised by the property of autonomy. Thus an agent may be treated as an individual concurrent process which can, in theory at least, continue to perform various actions according to preprogrammed rules, while communicating, through an agent communication language, with other autonomous agents that exist in parallel. Individual agents may be programmed to exhibit particular forms of behaviour which determine the nature of their interactions with other agents.

Multi-agent systems are concerned as the name implies with establishing and to some extent controlling the behaviour of a set of agents. In most earlier multi-agent systems the interactions between agents were controlled by means of a plan which may be maintained either by a blackboard system, or by facilitator agents (Genesereth & Ketchpel, 1994). In this way some intelligence is imposed on the system from without. An alternative approach, which in fact has led to more successful uses of agents, particularly in applications concerned with robotics, is to allow the individual agents to be controlled entirely by their internal rules, which are typically very simple in nature. This is described as a subsumption architecture (Brooks, 1986) and can result in a considerable degree of 'intelligence' being displayed by the resulting interactions. This latter approach is analogous to the situation in cellular automata in which each cell is updated according to some simple rule which, because it is some function of itself and the surrounding cells, can produce some interesting behaviour. Artificial life simulations are based on this principle and their potential to assist in modelling geographical phenomena has been highlighted by Openshaw (1992).

In this paper it is proposed that the subsumption approach to multi-agent systems may be applied to the simulation of geographical phenomena that change over time. By endowing individual agents with particular behaviour patterns that reflect assumed real world processes, it may be possible to simulate these processes according to differing rule sets, in order to find those assumptions which best simulate previous known processes and hence may be most effective in predicting future processes. There are many situations in which spatial characteristics may vary dynamically in response to events. For example, the spatial extent of urban areas might be modified in response to factors such as population profile, economic development, the location of available housing, the planning zones, communication systems and the proximity of other, separate urban areas. The growth of an individual patch of plant species might be a function of the soil characteristics and the slope and altitude of neighbouring zones which might or might not be connected with itself.

The approach proposed here assumes that the rules governing the behaviour of agents can be modified, and their effects studied. It also employs a sophisticated spatial data model that facilitates the determination of proximity relationships between sets of disjoint objects and allows the formation and transformation of spatial objects of arbitrary shape and size.

A spatial model which combines the use of arbitrary spatial objects with the capacity to determine efficiently the nature of proximal relationships between neighbouring objects is one based on a simplicial complex, which in two dimensions consists of a set of triangles. The authors have developed a simplicial data structure (SDS) which uses a constrained Delaunay triangulation to represent point, line and areal objects as sets of vertices, edges and triangles. Object-oriented software (Kappa) has been used to implement functions to update the SDS, to apply geometric transformations to embedded objects, to determine neighbourhood relations between sets of objects and to apply a variety of spatial operations to individual and multiple objects, concerned for example with merging neighbouring objects and with pushing nearby objects apart. These operations can be performed subject to various constraints on the behaviour of those objects contributing to the interaction. Functions are also being implemented with the SDS to support fuzzy modelling and probabilistic representation of boundaries based on vector data.

In the remainder of this paper we describe in more detail the properties of the SDS and discuss its incorporation within multi-agent systems in a number of applications.

Benenson, I. and Portugali, J. 1995. "Internal vs external spatial information and cultural emergence in a self-organizing city", Spatial Information Theory - A Theoretical Basis for GIS, Lecture Notes in Computer Science 988, Springer, 431-437.

Brooks, R.A. 1986. "A robust layered control system for a mobile robot", IEEE Journal of Robotics and Automation, 2(1), 14-23.

Genesereth, M.R. and Ketchpel, S.P. 1994. "Software agents", Communications of the ACM, 37(7), 48-53.

Livingstone, D. and Raper, J. 1994. "Modelling environmental systems with GIS: theoretical barriers to progress", Innovations in GIS 1, Taylor and Francis, 229- 240.

Openshaw, S. 1992. "Some suggestions concerning the development of artificial intelligence tools for spatial modelling and analysis in GIS", Annals of Regional Science, 26, 35-51.

Sham, C. H., Bawley, J.W. and Moritz, M.A. 1995. "Quantifying septic nitrogen loadings to receiving waters: Waquoit Bay, Massachusetts", International Journal of Geographical Information Systems, 9(4), 463-473.