International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: editor@ijaiem.org, editorijaiem@gmail.com Volume 1, Issue 3, November 2012 ISSN 2319 - 4847

Agent Based Cellular Automata: A Novel Approach for Modeling Spatiotemporal Growth Processes
Shanthi.M1, Dr.E.G.Rajan2
1

Research Scholar, Mysore University, Hyderabad, Andhra Pradesh, India

2

Director, PRC Pvt Ltd, Hyderabad, Andhra Pradesh, India

ABSTRACT
Cellular automata (CA) modelling is one of the recent advances in spatialtemporal modeling techniques in the field of growth dynamics. Spatio-temporal modeling of growth patterns has gained more importance in the recent years especially in the field of urban growth, biological growth etc. It has become an interest for researchers to study the model on spatial and temporal dynamic behaviour. This paper aimed at integrating agent-based modeling techniques with dynamic capabilities to handle spatio-temporal phenomenon for better and efficient decision-making. In the traditional model, cell based CA models are used and in order to the increase the efficiency and the performance of the existing modeling techniques the agent based cellular Automata (ABCA) is being used. By combining both, there is a progression from cell based approach to agent based approach. The drawbacks of the traditional methods will be overcome by using the agent based cellular automata.

Keywords: spatiotemporal, Cellular automata, Cellular automata Modeling, Agent Based Model, ABCA model

1. INTRODUCTION
Cellular automata (CA) based models and agent based models (ABM) are flourishing in the present trend. The increasing use of these approaches has begun to enhance the existing interaction and synchronization between different scales over the model and capture the emergent phenomena resulting from the interactions of individual entities. The spatial dimension plays a key role in many social phenomena. Spatial dynamics refers to the sequence of changes in space and time. The changes which takes place with respect to space is called spatial process, the latter is called temporal process. The spatial and the temporal process are one and the same and they cannot be separated. This spatiotemporal process is used in planning, urban development and issues related to geographical phenomenon. All geographical phenomena are bound to have a spatial and a temporal dimension. The aim of modelling is to abstract and represent the entity being studied. Modeling can be conceptual, symbolic or mathematical, depending on the purposes of the specific application. Modeling can be utilised for analysing, evaluating, forecasting and simulating complex systems to support decision-making. From the perspective of spatial science, modelling must take both the spatial and temporal dimensions. Model can be represented as a schematic representation of reality, developed with the goal of understanding and explaining it. Spatial interactions can also be expressed as an influence of a location on another, without being explicitly embodied in the form of a measurable exchange or flow. Spatial dynamics are easy to implement when compared to that of temporal dynamics since the change in time should be also be taken into account while modeling. Many techniques were currently used to model spatial and temporal growth especially in the field of urban growth. The traditional approaches use different kinds of modeling such as using cellular automata, artificial neural networks, multiagent models etc.but still many factors based on complex dynamics are not yet resolved. So to overcome the drawbacks of the traditional approaches, the Agent Based cellular Automata are proposed incorporating the cellular automata method as well the agent based method.

2. CELLULAR AUTOMATA
CA is individual-based models designed to simulate systems in which states, time, and space are discrete. It provides a way of simulating complex systems and self-organizing processes over space and time (Wolfram, 1994)[1]. Because of the capabilities of CA, it can able to generate complex patterns through local rules, and for linking rules to their consequences.CA[2] is a discrete dynamical system that is composed of an array of cells, each of which behaves like a finite-state automaton. Any CA system is composed of four components cells, states, neighbourhood (Moore, circle

Volume 1, Issue 3, November 2012

Page 56

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: editor@ijaiem.org, editorijaiem@gmail.com Volume 1, Issue 3, November 2012 ISSN 2319 - 4847
...etc) and transition rules. All interactions are local, with the next state of a cell being a function of the current state of itself and its neighbours.[2](G.W. Flake's, 2000) CA are models in which contiguous or adjacent cells, such as it may contain a rectangular grid, vary their states- their attributes or characteristics - through the monotonous application of simple rules. Every entity (in two dimensions represented by a cell) is interacting with the surrounding cells only. Thus, CA has been considered most suitable for processes where the immediate surroundings have an influence on the cell, such as diffusion processes. It has to a large extent demonstrated its capability for modeling complex, self-organization and emergent systems such as urban systems [5][13].

Figure 1: Sketch of a Cellular Automata They focus on the following aspects: Discrete entities in space and time; (cell size and time for each generation) Neighbourhood definitions (types and sizes) Model structures and transition rules Parameter values and variables (according to the variables and the values the simulation takes into account, some assumptions should be made.

Figure 2: Types of Neighbourhood CA proposes the advantages of spatiality, dynamics, simplicity and computational efficiency and capability of mimicking real spatial behaviour. It provides an effective spatial-temporal modeling technique for urban dynamics and growth. CA model have been studied on presenting spatial and temporal dynamics of a system [6]. With CA model, they can explore the complex knowledge of spatiotemporal dynamic by simple computational formulas. Moreover, with adequate thematic and attributes data support and an expert knowledge are needed to formulate an accurate transition rules. This simplicity cause increasing the implementation of CA model, particularly in urban and land use dynamics. Spatial interactions can also be expressed as an influence of a location on another, without being explicitly embodied in the form of a measurable exchange or flow. Cellular automata are often used to formalize the effect of such influences on local change and simulate the spatial configurations that arise at a global level [7].

3. CELLULAR AUTOMATA MODELING

Cellular Automata is based on Simple rules and simple initial conditions which gives rise to the most computationally complex behaviour. The Complex behaviour arises mainly because of the local interactions with the cell. The local behaviour gives rise to the global behaviour. This property of cellular automata forms the base for modelling. Since the base for growth process emerges from the very basic unit, Cellular Automata plays a vital role in modelling especially in the fields of urban dynamics, geographical phenomenon etc.Usually in cellular automata modelling 2-dimensional is used, giving rise to the grid structure. Cellular automata modelling. Cellular automata are similar to spatially-explicit, grid-based, immobile individual-based models. However CAs are always homogeneous and dense (all cells are identical), whereas a grid-based individual-based model might occupy only a few grid cells, and more than one distinct type of individual might live on the same grid. CA models focus on landscapes and transitions, CA are only capable of exchanging data spatially with their neighbourhoods. 3.1 Advantages of CA Modeling CA have many advantages for modelling, including their decentralised approach, simple to the complexity theory, the connection of form with function and pattern with process, the relative ease with which model results can be visualised,

Volume 1, Issue 3, November 2012

Page 57

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: editor@ijaiem.org, editorijaiem@gmail.com Volume 1, Issue 3, November 2012 ISSN 2319 - 4847
their flexibility, their dynamic approach, and also their affinities with geographical information systems and remotely sensed data (Torrens and O'Sullivan, 2001).The most significant advantage is being its simplicity. 3.2 Drawbacks of CA Modeling The rules are simple to ease and visualize but CA because of its poor spatial representation it has its own limitation.CA lacks the ability to reflect the feedback of system and social economic influence on decision making.

4. AGENT BASED MODEL

The ABM is used for aspatial dynamics and CA is used for spatial dynamics. The major objective of the study is to examine the feasibility and utility of implementing agent-based models with a Geographic information system in order to simulate selected growth processes. In this model, systems dynamic behaviour is represented through rules governing the actions of a number of autonomous agents. An agent-based model is a generalization of cellular automata in which agents are able to move around in space, rather than being confined to the cells of a raster [3]. 4.1 Agent An Agent is defined as a computational entity such as a software program or robot that can be viewed as perceiving and acting upon its environment and that is autonomous in that its behaviour at least partially depends on its own experience. An agent can be a system that decides for it what it needs to do in order to satisfy its objectives An agent is an entity which has: (i) an internal data representation (memory or state); (ii) means for modifying its internal data representation (perception); (iii) means for modifying its environment (behaviour). Agent-based models can be considered as an extension and generalization of cellular automata. Agent-based models are useful in conceptualizing land use changes and urban growth. Geographical phenomena include spatial and aspatial dynamics. So we defend that the inclusion of CA for spatial dynamics and ABMs for aspatial dynamics is a better solution for modeling. CA has evolved greatly from its initial concepts, many functions have been improved (e.g., action at a distance, calibration and definition of transition rules) to make CA more flexible and efficient approach.

Figure 3: Agent 4.2 Structure of an agent-based model: A typical agent-based model has three elements: 1. Agents, their attributes and behaviours. 2. Agent relationships and methods of interaction. An underlying topology of connectedness defines how and with whom agents interact. 3. Agents environment. Agents live in and interact with their environment in addition to other agents. A model developer must identify, model, and program these elements to create an agent-based model [10].

Figure 4: Elements of an agent based model

Volume 1, Issue 3, November 2012

Page 58

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: editor@ijaiem.org, editorijaiem@gmail.com Volume 1, Issue 3, November 2012 ISSN 2319 - 4847
An agent-based model gives an idea about the collective phenomenon emergence and the individual interactions and processes, which led to the origin of the aggregate phenomenon. The individual level interactions and processes help understand the dynamics that drive and influence an emergent phenomenon. Agent-based modeling is clearly distinguished from other kinds of modeling research by this focus on the concept of agents. 4.3 Emergence in agent based model One of the motivating concepts for agent-based modeling is its ability to capture emergence. Agent-based models that are completely described by simple, deterministic rules and based only on local information can produce sustainable patterns that self-organize themselves and have not been explicitly programmed into the models. Emergence refers to the emergence of order. Emergence can be illustrated by simple agent-based models such as Life and Boids [3][4][11]. 4.4 Advantages of agent based model Agent based models has the ability to represent the impacts of autonomous, heterogeneous, and decentralized human decision making and this can be incorporated along with CA for improving it. Thus, the hybrid model, which is composed of CA and ABM, is a more appropriate method for modelling since it possesses the advantages of both CA and ABM. 4.5 Agent Based Model Vs Cellular Automata Agent-based models are simulations based on the global consequences of local interactions of members of a population. These models typically consist of an environment or framework in which the interactions occur and some number of individuals defined in terms of their behaviours (procedural rules) and characteristic parameters. In an agent-based model, the characteristics of each individual are tracked through time. There is an overlap between agent-based models and cellular automata. Certainly cellular automata are similar to spatially-explicit, grid-based, immobile individualbased models. However CAs are always homogeneous and dense (all cells are identical), whereas a grid-based individual-based model might occupy only a few grid cells, and more than one distinct type of individual might live on the same grid. the significant difference is whether the simulation's inner loop proceeds cell by cell, or individual by individual. The philosophical issue is whether the simulation is based on a dense and uniform dissection of the space (as in a CA), or based on specific individuals distributed within the space.[8] ABM is well suited for the simulation of situations where there are a large number of heterogeneous individuals who may behave somewhat differently and is therefore an ideal simulation method for the social sciences.

5. INTEGRATION OF CELLULAR AUTOMATA MODEL AND AGENT MODEL

An Agent-based Cellular Automata (ABCA), which combines CA and agent-based models. In the ABCA framework, the object-oriented approach to cells is combined with the transition rules defined by the models as automata. The agent-based models defining the transitional rules are called as agent-automata [8][9]. A formal definition of the ABCA [8], [9] is deduced from the traditional CA transitional rule. state, s, and neighbourhood, N, of the cell at time, t, to define the transition to the state at time, t+1. It represents for the discrete time-stepped simulation of the entire region from time t to t+1. The agent automata 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 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.

Figure 5: Combining Cellular Automata and ABM (ABCA)

6. PROPOSED METHOD
CA model social dynamics with a focus on the emergence of properties from local interactions while ABMs simulate more complex situations than the CA where the agents control their own actions based on their perceptions of the environment. CA and ABMs each have a different focus, but they all model the studied system at individual levels, and

Volume 1, Issue 3, November 2012

Page 59

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: editor@ijaiem.org, editorijaiem@gmail.com Volume 1, Issue 3, November 2012 ISSN 2319 - 4847
there is some common ground among the approaches. Firstly, all approaches are simulations based on the global consequences of local interactions of members of a population. Unlike the aggregated models that often overlook the details at a more refined level, they provide a more effective and natural way to handle individual behaviours. Secondly these approaches all track the characteristics of each individual through time, in contrast to traditional modeling techniques where the characteristics of the population are averaged together. Finally the emergence of global phenomena through local interactions in all ABMs offers more than changes that are simulated on the basis of average data for the whole population as in traditional models. It can provide the capability for behaviour modelling and allow us to study the interaction at both macro and micro levels, as well as interactions in both directions. Agent-based cellular automata (ABCA) models are used to show that this model can act as a synthetic interface to the dynamic drivers of the system and the simulation framework. The key characteristics of the agent include, autonomous, social ability, responsiveness, and proactive. These agents are diffused into the CA model, which then initiate transitions; respond to the transition and exchange and report accordingly to the properties related with each of the agent-based models[8][9][12]. Human decision making for agents is made ease by making use of these properties as well as the simulation is more realistic. Thus agents of an agent-based model to initiate transitions would diffuse into the CA transition to enact such functions. Likewise, agents of those agent-based models to respond or react would act accordingly. Feedback Loops are used along with CA transition for making interactions among the drivers. The agent based transition rules are combined into the CA transition rules and the resulting final transitions based on the feedback loops. The feedback loops are associated with the different agents and according to their behaviours they are modelled. Subsequently, the final transition rule gets the update from these agents before updating the cell state in the subsequent iterations apart from the inherent CA transition rules. An important aspect which is to be addressed involving these feedback loops in a geo-spatial discrete-time model is the capabilities of these different models. These models have to represent the dynamics and respond to them at the respective spatial and temporal scales of the models. Each of the agent-based models representing the drivers is considered as a discrete-time stepped model, while the general CA being another discrete time stepped model both are similar but with time advancement mechanisms. Synchronization is an important aspect that has to be ensured while dealing with these different space and time variant models [12].

Figure 6: Feedback Loops

7. SCOPE AND LIMITATIONS

The association of agent automata and CA offers more opportunities for geo-spatial modeling and simulation. Agent based model approach can be able to solve the limitation of CA, to respond to drivers and to various externalities dynamically. The ABCA is limited by the consistency of the input data sets and the type of relationships, which are modeled 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 are to be predefined. This framework ABCA is more robust to model, tackle, analyze, test and evaluate the different geo-spatial processes dynamically at discrete space and time.

8. CONCLUSION
Cellular automata (CAmodeling is one of the recent advances in spatialtemporal modeling techniques in the field of various growth dynamics.These models provide novel tools that support for better understanding of the modeling process. In this paper, cellular automata modeling and agent based modeling are discussed. The limitations of the existing models are overcome by using the proposed model Agent based Cellular Automata Model (ABCA). Agentbased cellular Automata simulations can also capture reality more effectively In contrast, ABCA possesses more advantageous features for simulating urban development process. ABCA would certainly provide a more realistic representation of complex problems, as well as provide us the flexibility to vary quantities and population characteristics. Finally, ABCA can be used as an effective model for modeling the growth dynamics.

REFERENCES
[1] S.Wolfram, Cellular Automata and Complexity, Addison-Wesley Publishing Company, 1994 [2] Wolfram, S. (2002). A New Kind of Science. Wolfram Media, Inc., Champaign, IL

Volume 1, Issue 3, November 2012

Page 60

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: editor@ijaiem.org, editorijaiem@gmail.com Volume 1, Issue 3, November 2012 ISSN 2319 - 4847
[3] Agent-based modeling and simulation: abms examples Proceedings of the 2008 Winter Simulation Conference S. J. Mason, R. R. Hill, L. Mnch, O. Rose, T. Jefferson, J. W. Fowler eds. [4] Introductory tutorial: agent-based modeling and simulation Proceedings of the 2011 Winter Simulation Conference S. Jain, R.R. Creasey, J. Himmelspach, K.P. White, and M. Fu, eds. [5] Modeling Urban Growth Dynamics using Cellular Automata and GIS Khalid Al-Ahmadia*, Alison Heppenstallb, Linda Seeb and Jim Hoggb [6] Geographic spatiotemporal dynamic model using cellular automata and data mining techniques IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 3, No. 2, May 2011 [7] Spatial and dynamic modeling techniques for land use change dynamics study novaline jacoba, krishnan r, prasada raju pvsp, saibaba j [8] Framework for Integration of Agent-based and Cellular Automata Models for Dynamic Geospatial Simulations H. S. Sudhira, T. V. Ramachandra, Andreas Wytzisk & C. Jeganathan, March 2005, Technical Report: 100 [9] Development of the Integration Framework for CA and Agent-based Models. [10] Models, Agent-Based Models, and the Modeling Cycle [11] Computational features of agent-based models Massimo Bernaschi, Filippo Castiglione Istituto Applicazioni del Calcolo (IAC) M. Picone [12] Integration of Agent Based Model and cellular Automata Models for simulating Urban Sprawl by sudhira [13] Modeling spatial and Temporal urban Growth, Jianquan Cheng [14] Simulating spatial dynamics: cellular automata theory .Robert M. Itami.School of Environmental planning and Centre for Geographic Information Systems and Modelling, University of Melbourne, Parkville, Vie. 3052, Australia.

Volume 1, Issue 3, November 2012

Page 61