3.1 The Agent-based Cellular Automata (ABCA) : Combining CA and Agent - based Models

Based on available approaches for modelling geo-spatial phenomena using traditional cell-based CA techniques, the future of geo-spatial simulations is being aimed at integrating agent-based modelling techniques with dynamic capabilities to handle spatio-temporal phenomenon for better and efficient decision-making. Batty and Jiang (1999) illustrate the correspondence of these ideas in Figure 3.1 showing the progression of cell-based approaches to CA to agent-based models.

Figure 3.1: Relations between Cell-Based GIS, CA Modelling, and MAS (Batty and Jiang, 1999)

In this backdrop, an Agent-based Cellular Automata (ABCA), which combines CA and agent-based models, is proposed. In the ABCA framework, the object-oriented approach to cells is coupled with the transition rules defined by the models as automata. The agent-based models defining the transitional rules are termed as agent-automata.

3.2 Agent-based Models as Geographic objects

A topology is the definition of spatial relationships between features. From earlier discussions (Chapter 2), it is clear that even though there are significant tools for building agent-based models, they lack the spatial relationships or the topology definitions without corresponding geometry to the agents thus inhibiting them to operate in the geo-spatial domain. A key aspect of these agent-automata is that the spatial relationships are defined with respect to certain geometry to these and so they are conceived to act over a geo-spatial domain. In the geographic perspective, the topology or the spatial relationships are defined with respect to Euclidean space, wherein every point in the space can be represented by a set of coordinates. The representations of geographic objects within the context of topological features are the simple geometric shapes in respective dimensions are called ‘simplices'. These are point (0-simplex), line (1-simplex), polygon (2-simplex) and tetrahedron (3-simplex). Since the present research is confined to the two-dimensional Euclidean space, the definitions of objects are restricted to points, lines and polygons. Typically these representations of geographic objects refer to the vector data types. However, the main focus of this research is on to simulate the agent-based models over a CA model, which is essentially a cell-based model. Thus, it would be inconclusive for simulation of agent-based models, defined as geographical objects (with spatial relationships) only, with the CA model. And so, it is suggested that these agents as geographical objects would be designed to associate to the cell resolution corresponding to that of the CA model. In the current research, this association of objects as cells is assumed over the resolution of the CA model. However a detailed study can point out the implications of scale for such association of objects as cells. In the present context, these agent-based models are attributed the spatial relationships defined over a cellular space representing discrete entities of the phenomenon. Such agents defined over a cellular geographic space are also conceived with the typical properties of the agent-based models of being deliberative or reactive and importantly autonomous. The diffusion of agent action on cellular space is discussed in the subsequent paragraphs.

3.3 Agent -based Models and Simulation Time

Apart from the definition of a spatial relationship to these automata, the notion of time perceived by the simulations with respect to the agent-based models is discussed. Normally, the physical system or process in question is modelled with respect to the physical time. In this context, if the urban sprawl is modelled to predict the sprawl annually, the physical time considered is in terms of ‘years'. A simulation time is defined as a totally ordered set of values where each value represents an instant of time in the physical system being modelled. On the same lines, if sprawl is modelled from 1990 to 2000 as the physical time, the same in simulation time would be in terms of t i where, i =1 to 10. In the CA paradigm, if the transition rules are defined for a certain period (say, t₁= t_i = t₁₀), the simulation takes place in iterations with respect to the simulation time of t₁, t₂, t_3,… t₁₀. The agent-based models would be defined based on the process of interest. In reality, the behaviour of such models need not be modelled for the same simulation time of the CA. Thus , in this research the simulation time for the CA and agents are assumed to have a single time advancement mechanism (Figure 3.2). However, each of the agent-based models could be defined separately with different time advancement mechanisms depending upon the events for which they are defined, as discrete-event models. Then a significant issue would be to address the synchronization of these models with different time advancement mechanisms, this however is beyond the current scope of research.

3.4 Formation of the Agent-based Cellular Automata

A formal definition of the ABCA is deduced from the traditional CA transitional rule mentioned in Equation 1. It should be noted that Equation 1 accounts for the state, s , and neighbourhood, N, of the cell at time, t, to define the transition to the state at time, t+1. Equation 1 accounts for the discrete time-stepped simulation of the entire region from time t to t+1. The agent automata that are suggested are those, which can be as many in number for the region with varied spatio-temporal characteristics. The variation in space is to denote the sphere of activity or influence of the agent automata in question and the temporal variability indicates the discreteness of the agent automata and the different start and end time of the agent automata. In this regard, the agent automata are considered as distinct discrete-time simulation types. On the lines of a CA transition rule, an agent automaton is defined:

…Equation 2

where,

K is the type of agent

f ( A ) is the agent-based model driving the transition of the cell

E x, y, t is the extents of the agent-based model spatially and temporally

Figure 3.2: Time Advancement Mechanism for CA and Agent-based Models

The type of agent governs the behaviour of the automata accordingly whether the agent is reactive or deliberative. This condition of the automata would enable it to act autonomously. Further, the function f ( A ) defines the behaviour for the agents in the agent-based model. This behaviour will be responsible for initiating or responding to the transitions of cell states. The extents of the agent automata are defined to streamline the specific sphere of activity or influence of the agent automata within that space and time.

In the real sense, only those agent automata types would be defined the modeller is interested in and so there can be a case where in certain cell space and over a certain time there might not be any agent automata accounted. And so, even in such cases, the CA transition would any way account for such instances. However for effective overall process simulations, both CA and agent automata have to be combined effectively to simulate each discrete time-stepped models at their respective scales of space and time. In this context the unification of CA and agent automata is termed as Agent-Based Cellular Automata (ABCA). A formal definition of an ABCA is given as a set of all the individual agent automata and the general CA by the following:

...Equation 3

where,

; ; ; etc.

3 . 5 Agent Action in Cellular Space and Discrete Time

The kind of agent-automata described are those, which can initiate, respond and react to the dynamic conditions prevalent in the system in question. It is assumed that a CA transition rule would act globally over the region under question. However, the utility of engaging the agent-automata is to enable the local spatial interaction of the drivers of the systems, initiate transitions based on system variables attaining certain levels of threshold, and respond to the interactions among the different agent-automata. In such scenarios these agent-automata would diffuse across the cells during that simulation time for which the agent- automata are defined. Thus if the cell state at C (x_i, y_j) in the system is to be updated iteratively by the CA, then according to equation 1:

In the instances of agent-automata defined for the system in question, these agent-automata are to diffuse into these transition rules to initiate, interact and respond to the cell state transitions. Assuming the agent-automata are defined for the system in question, in the ABCA framework the updating of the cell states would be as follows:

The agent-automata would act at those cell spaces or extents and during the time for which they are defined. In the absence of any activity for the agent in certain spatial extents and over certain simulation time, the actions of agent-automata would act as an identity element (in effect there would be null updates from the agent-automata). The set of all the agent-automata and the CA can be part of the simulation application, while the simulation executive would execute these automata for the simulation time.

With the unification of agent automata and CA, the imminent problem foreseen is to achieve the synchronized update of the cell states, initiated by both of these. For achieving the synchronization of the different individual automata and the CA, the concept of having a geo-spatial analyser is suggested. The description of the functionalities of the geo-spatial analyser (GSA) is dealt in the subsequent sections.

3.6 Scope and Limitations

The unification of agent automata and CA offers opportunities for geo-spatial modelling and simulation. With the available spatial and temporal data, satellite remote sensing and the capabilities of geo-information processing through GIS, the technique of modelling spatial phenomena using CA was already mastered as can be inferred from the various investigations. The limitation of CA being not able to respond to drivers and to various externalities dynamically are now being addressed through the agent-based approach which upon unification with CA would now enable the geo-spatial modellers to plug-in any process model as an agent and apply it within the ABCA framework. The ABCA is limited by the consistency of the input data sets and the type of relationships, which are modelled amongst agents. The key conditions for the integration of these agent-based models with CA models are that the spatio-temporal extents of these models/processes in question are to be predefined. By ensuring such a measure of predefining the spatio-temporal characteristics of the models, GSA would schedule these automata while the HLA offers synchronization of different models. It is believed that this framework is more robust to tackle, analyse, test and evaluate the different geo-spatial processes dynamically at discrete space and time than the Geographic Automata System (GAS) framework (Benenson and Torrens, 2003).

3.7 The High Level Architecture

Processes in environmental systems take place at their own respective scales in both space and time. The geo-spatial community has for long until now attempted to model and simulate these different processes on the desktop aided by the advances in the computational capabilities. A significant challenge faced by the geo-spatial community is the need of dynamic systems for modelling and simulation of the spatio-temporal and thematic databases in real-time. Further, as there are numerous processes taking place in space and time within an environmental phenomenon in question, a typical GI system should be capable of integrating or synchronizing the different models of environmental processes at their respective scales.

In the modelling and simulation domains of computer science and engineering numerous advances are made with respect to distributed and parallel simulations. A key distinction is that the modelling and simulation community is able to achieve the synchronization of time-variant simulation models by using a standardized simulation framework, the High Level Architecture (HLA) initially developed by the United States Department of Defence and now an IEEE standard (1516) (Dahmann, Fujimoto and Weatherly, 1998; IEEE, 2000). Wilcox, Burger and Hoare (2000) present a review of the history, evolution, current and future developments concerning the advanced distributed simulations (ADS) notably by the emergence of HLA .

The HLA is the architecture for reuse and interoperation of simulators. The intent of the HLA is to provide a structure that will support reuse of capabilities available in different simulators, ultimately reducing the cost and time required to create a synthetic environment for a new purpose and providing developers the option of distributed collaborative development of complex simulation applications. Thus the HLA offers a federation approach and addresses the interoperability and reuse of individual components. In order to facilitate interoperability, each member (federate) of a distributed simulation (federation) is equipped with appropriate interfaces to interact via a run-time infrastructure. The HLA does not prescribe a specific implementation, nor does it mandate the use of any particular software or programming language. Figure 3.3 shows the functional view of a HLA federation. A detailed description of the HLA is given in Appendix 1.

Carothers et al., (1997) present the design and algorithms used to implement the HLA Time Management Services in the Run-Time Infrastructure (RTI) component of the HLA. Fujimoto (2003) addresses how the two key categories of time management algorithms, conservative and optimistic synchro nization are supported in the HLA. The paper discusses in detail the issues of time management in the distributed event simulations concerning the synchronization of computations on different processors.

Figure 3.3: Functional View of an HLA Federation (Dahmann, Fujimoto and Weatherly, 1998)

On similar lines with respect to time synchronization, Tacic and Fujimoto (1998) describe a mechanism to realize properly synchronized data distribution in distributed simulations using logical time. This is achieved using a connection look-ahead approach that allows dynamic network topology changes where federates can advance further away from each other, yielding the better performance.

With the development of HLA and subsequent notification of the same as an IEEE standard (1516), the simulation framework has seen tremendous scope in the modelling and simulation community moving from the defence sectors to application areas of public domains. Borshchev, Karpov and Kharitonov (2002) develop approaches to model and simulate hybrid systems in a distributed manner, where hybrid state machines are used to model complex interdependencies between discrete and continuous time behaviours. Lindenschmidt, Hesser and Rode (2004) present an interesting application of using the HLA to integrate various water quality models, in which the simulations of a hydrodynamic model, eutrophication model and sediment and micro-pollutant transport model are interlinked and coordinated by the HLA RTI environment.

Since the development of HLA, the modelling and simulation community are using the framework extensively to achieve interoperability amongst heterogeneous simulators. However a notable drawback with these is that they lack the spatial component in them (Schulze et al., 2002). A possible bridging of the concepts of HLA into the geo-spatial domain is attempted recently with a view of providing a set of respective web services. In this regard, Simonis, Wytzisk and Streit (2003) suggest and describe an interoperability framework to bridge the High Level Architecture and the Open Geospatial Consortium (OGC) specifications. The thrust is on providing simulation-born spatio-temporal data in an interoperable manner facilitating benefits for a wider user community at large.

Apart from the application of HLA for integration of different simulation models elsewhere in the simulation community, within the GIS another framework is suggested based on the emerging Open GIS standards, which will allow the integration of parallel computing technology such that it becomes a viable component of a new generation of geographical information system software (Dowers, Gittings and Mineter, 2000). Ammerlhan et al., (2000) address the integration of geographically distributed functions with interactive human control where most of the components are distributed which is achieved through a coordination of the simulation through a new parallel discrete-event simulation system. Their solution is provided through a Java-based distributed discrete event simulator, called infrastructure for distributed enterprise simulation (IDES).

Thus, numerous advances are made within the modelling and simulation community with little focus on enabling the spatial aspects for synchronisations of different models. The direction of the current research is to fill the gap of spatial synchronisation for these models for effective simulations within the geo-spatial domain retaining the HLA framework for synchronising time variant simulations.

3.8 The Spatial and Temporal Synchronization

3.8.1 Geo-Spatial Analyser(GSA)

Spatial scheduling refers to the ordering of simulators for execution based on the spatial extents defined. To enable the spatial scheduling of the various simulations, it is suggested to incorporate a “ Geo-Spatial Analyser”. Each of the discrete entities of the phenomenon being modelled as an agent-based model is considered as a discrete time-stepped simulation. These models would have specific spatial and temporal extents. A spatial extent for a specific model would imply that the agents would be acting in that specific spatial extent, as well as a temporal extent would also be necessary. In such cases, the duration of the process would be required for executing different automata over time Mostly, the temporal synchronization of distributed simulators could be addressed by the HLA. In the instances, where there are two or more simulators that need to be executed over different time, HLA offers to synchronize these simulators. But, if the simulators would be acting over the same spatial extent, at the same time, now synchronized by HLA, there can be a conflict for which simulator execution would be first required to have the implication on the spatial extent. With a GSA, this can be resolved. Thus, the key functioning of GSA would be to facilitate different simulators to take place at their specified locations based on the spatial extent of influence of the agents. To enact such a functioning, the GSA would be made up of two components, a Simulation Control Service (SCS) and the Geo-scheduler. The functionalities of the SCS is similar the one suggested by Schulze et al. (2002). The SCS would act as an interface between the different simulations at two levels. In the first level, SCS would act as the interface for the geo-scheduler to schedule the different simulations and then in the next level the SCS would actually be controlling different distributed simulations in terms of initiating and ending different federations.

During the execution of the model for every simulation time, the geo-scheduler would analyze the spatial extents of the different agents to ascertain which agent is influencing over which spatial extents. In the case of overlapping of the spatial extents (say a process taking place at the same location), the geo-scheduler would then evaluate the spatial extents of these agents and schedule accordingly based on the agents with least spatial extent first followed by the agents with higher spatial extents. Suppose there are several agent automata defined for a geographic phenomenon as in equation 3. The key functionality of the GSA would be to schedule the automata as given by the following during the iteration:

These scheduled simulators would then be directed to the SCS. Based on the evaluation, supposing few agents influencing at the same place and time, these federates would run interacting with the run-time infrastructure to undertake the overall simulation.

Functionalities of the GSA

• When simultaneous simulations are initiated, all simulations are directed to the Simulation Control Service (SCS), which would act as an interface with the geo-scheduler .
• The SCS in the first level would address all the simulations to the geo-scheduler .
• The geo-scheduler analyses each of these simulations at runtime for any spatial overlaps evaluating the spatial extents of individual simulations.
• Based on the spatial extents, the geo-scheduler of the GSA schedules the simulations into different federates through the SCS of the second level.
• The SCS in the second level deploys these federates by starting, controlling and destroying the federates.
• The GSA assumes a bottom-up approach, wherein the underlying assumption that all individual local interactions lead to the global variations. Thus the scheduling of different simulations would be based on the least spatial extent first followed by the higher spatial extents.
• When two or more simulations are waiting to be run within the same spatial extent, it can also be that certain agent-based models are to obtain inputs based on certain specific earlier simulations in time. The agent type defined in the agent automata and the function specified will be able to handle such scenarios.
• The scheduled simulations which form the federates through the SCS of second level that are synchronized for different time-variant simulations by the runtime infrastructure.

The overall framework for the simulations is shown in Figure 3.4.

Figure 3.4: Framework of the overall simulations integrating the CA model with the agent-based model using the HLA framework and the GSA

ABM : Agent-based Model ; SCS : Simulation Control Services

3.9 Application Scenario

To illustrate the applicability of this framework, an example from the urban sprawl dynamics is considered. Considering a city with some spatial extent, the land-use change for a period of time is modelled using CA. Further different processes like the infrastructure and population growth can take place over the region. An agent-based model can be thought of to represent the addition of new infrastructure, like the construction of a new ring road. This, when considered as an agent-based model, would have agents in it to initiate cell transitions along the specified areas (5 km – linearly) representing the road over duration of time, such as 6 years. Along with it is another agent-based model, the population development process, acting in the same region also during the same decade. The agents of the agent-based model (population) would initiate transitions like increasing the built-up area for every ‘n' number of people increased and ‘m' number of density crossed. To illustrate, how the interaction with the CA can take place, the same scenario of ring road development and population growth is described with reference to the time advancement as shown in Figure 3.2. If you consider the agent-based model 1 in the Figure 3.2 as the ring road development and agent-based model 2 as population development process, the interactions among these would be as follows. The agents of the ABM 1 would initiate the transitions for the change in state in the specified region from the other land use class to road from the iteration 1 to 6 sequentially over the years. Consequently, wit the development of a ring road, other processes like the establishment of industrial areas, commercial places or the residential areas can come up around the vicinity of the region. This would ideally start during the iteration 5 and go on until 10. The agents of these can represent the industrial layouts, commercial establishments, or residential layouts, implying that in the cell states surrounding ring road would eventually be built-up. With in the sub-model of an industrial layout, different agents can represent each industry in that layout. Even though the cell states pertaining to the layout might eventually be converted in to built-up from other land uses in iterations 5 to 10, certain agents representing individual industries can initiate these transitions from iterations 5 to 10; there by collectively the land use is converted into developed. With the development of ring road and other development activities, the population would increase; the agents representing the same can efficiently do this task. Each of the agent action is one simulation of the model. However, only with the establishment of each industry first, the industrial layout is complete. It would be inappropriate representation for the agents to first represent the industrial layout and then the industries as such. In such scenarios, the GSA will play a significant role. The same analogy holds good for the houses and the entire residential layouts. In such scenarios, the role of GSA would be to evaluate the spatial extents of these two agent-based models and then utilize the HLA framework to synchronize the overall simulations, and ultimately facilitating the synchronisation of the individual processes in the overall simulations.

3.10 Interoperability of the ABCA Framework

The ABCA framework is a combination of the domains of GIS, simulation (HLA) and the artificial intelligence (agent-based modelling) for ensuring the geo-spatial simulations of dynamic physical processes. An ideal framework for simulation should be reusable and interoperable for different use cases and multidisciplinary research teams thereby minimizing the cost of effort and time for modellers to rebuild a simulation framework specific to their use case or research problems.

To promote the interoperability of solutions and applications for geo-spatial services, data and applications, the Open Geospatial Consortium has established the necessary standards and specifications (OGC, 2003). For the simulation applications, the High Level Architecture developed by the US Department of Defence is now established as an IEEE standard (1516) (Dahmann, Fujimoto and Weatherly, 1998; IEEE, 2000). The HLA is the architecture for reuse and interoperation of simulators.

Similarly in the agent-based modelling domain, the Foundation for Intelligent Physical Agents (FIPA) has been actively developing the specifications and standards to promote the interoperability of the agents and the services they can represent. Accordingly, FIPA has specifications categorized into few categories based on the Applications, Abstract Architecture, Agent Communication, Agent Management, and Agent Message Transport. The abstract architecture specification (FIPA, 2002) defines the architectural elements and relationships, guidelines for the specification of agent systems in terms of particular software and communications technologies and specifications governing the interoperability and conformance of agents and agent systems.

Even though, since the development of HLA, the modelling and simulation community are using the framework extensively to achieve interoperability amongst heterogeneous simulators, these lack the spatial component in them (Schulze et al., 2002). Very few have addressed the need for interoperability among the simulation models in geo-spatial domain and the time management of simulations bridging the OGC and the HLA (Schulze et al., 2002; Simonis et al., 2003). A possible bridging of the concepts of HLA into the geo-spatial domain is attempted recently with a view of providing a set of respective web services. Simonis et al. (2003) suggest and describe an interoperability framework to bridge the High Level Architecture and the Open Geospatial Consortium (OGC) specifications.

An important paradigm here is that there are separate architectures offering interoperability in the respective domains of GIS, simulation and agent-based modelling. However, for the proposed ABCA framework to promote interoperability, it has to comply on these architectures separately and not collectively. In this regard, Schulze et al., (2002) suggest the integration of two standardization techniques, the OGC and HLA, for offering features and services accessible to both basic architectures and provide a robust interoperable architecture for distributed web-based spatio-temporal simulation. Accordingly, Schulze et al. (2002) propose the DALI-Architecture (Distributed spAtio-temporaL Interoperability-Architecture). The DALI-Architecture is ideally suited for web-based simulations.

A comparison of these different architectures gives an outlook on their usability in the ABCA framework. The ABCA is inherently intended to comply with the OGC and HLA. An overview of the comparison of the different architectures is provided in Table 3.1. While the OGC has sense of space, the HLA has the sense of time and the agents the sense of the behaviours there in. The key aspect of the availability of the services is that for the OGC it is permanent and for HLA and FIPA they are during the runtime.

Table 3.1: Key Comparisons of OpenGIS, HLA and FIPA (Adapted from Schulze, et al., 2002)

In the current research, integration of agent-based models over CA has been attempted in the geo-spatial domain and subsequently a framework has been proposed for ensuring the geo-spatial simulations. Thus, it is suggested that an integrated architecture combining the standards and specifications of OGC, HLA and FIPA would help in the realization of the overall goal of achieving the interoperability across the domains.