This is the html version of the file http://www.actapress.com/PDFViewer.aspx?paperId=17339.
G o o g l e automatically generates html versions of documents as we crawl the web.
To link to or bookmark this page, use the following url: http://www.google.com/search?q=cache:jfIwHyb6hYEJ:www.actapress.com/PDFViewer.aspx%3FpaperId%3D17339+%2Bwainer+%2Bsimulation&hl=en

Google is not affiliated with the authors of this page nor responsible for its content.
These search terms have been highlighted:  wainer  simulation 
Page 1
A CELLULAR AUTOMATA AND INTELLIGENT AGENTS USED TO MODEL
NATURAL DISASTERS WITH DISCRETE SIMULATION
Pau Fonseca; Josep Casanovas; Jordi Montero
Departament d’Estadística i Investigació Operativa i LCFIB., Campus Nord – B6. Universitat Politècnica de Catalunya,
c/ Jordi Girona 1-3, 08034 Barcelona (SPAIN) T.+3493 4016941 F.+3493 4017040
E-mail: {pau, josepk, monty}@fib.upc.es
ABSTRACT
Some of typical industry problems can be analyzed using
discrete simulation, in concrete the simulation event
scheduling paradigm has been used over decades in
industry area offering good results.
However, although simulation can represent the reality
closer than any other approximation, in other systems like
ecological, economical or social don’t present similar
results. In fact, currently is very difficult to depict this
kind of systems. One of the first problems resides in his
evolving nature. But, event scheduling simulations can be
used in this sort of systems adding cellular automata and
intelligent agents to the model structures, adding intrinsic
evolving nature. Although the prediction usually cannot
be done, there are other important benefits that can be
considered, like data collection between the researchers of
the domain, the recognition of gaps in the knowledge, and
of course, better understanding of system in a global
approximation. Nowadays these are the main goals
attended to construct this sort of models.
The brief description of this architecture, which allows the
simulation of evolving systems, like natural disasters, is
the target of this paper.
KEY WORDS
Cellular automata, intelligent agents, natural disaster,
event scheduling, GIS.
1. Introduction
This paper merge three important areas, discrete event
simulation, that represent the simulation model kernel and
determines main system architecture, GIS data
manipulation and his utilization inside a simulation model
which enables landscape data use inside simulation
model, and finally use of artificial intelligent techniques
(like cellular automaton or intelligent agents) in order to
enable system evolution.
Natural disasters, like wildfire, flooding, earthquakes or
tsunamis, currently are unpredictable, and represent one
of the biggest hazards to population of some earth areas.
Understand through simulation techniques this disasters
represent not only the possibility of human life salvation,
also enables the capability of calculate the behavior of
some other different systems that present evolving
behavior.
In this paper a wildfire propagation and containment
model is presented like a sample. Propagation model is
based in the BEHAVE model (Andrews 1986, Andrews
and Chase 1989, Burgan and Rothermel 1984, Andrews
and Bradshaw 1990) [15] [1].
2. GIS Data
Natural disasters simulation models are focused in nature,
and for this reason may require a massive set of GIS data,
in our wildfire sample is necessary to define land slope,
vegetation, combustible, wind speed, etc, consequently is
necessary establish an interface, between this data and
simulation model, that enables the representation and his
use in the model.
Data that represents the elements (layers) are stored in
files that follows IDRISI raster format (IDRISI is a GIS
developed by Clark university). Each of these files
represents a matrix, and each one of their cells defines
propagation model features (all layers are represented by
two files *.img file that contains data, the matrix, and
*.doc files that contains data documentation).
The files used are (following the behave model):
• Mapa: file containing the DEM (Digital Elevation
Model).
• Model: file that represents the propagation model
implemented for each cell.
• Slope, Aspect: files that stores the slope and his
direction. These files are calculated using the DEM.
(Mapa files)
• M1, M10, M100, Mherb, Mwood: files that contains
the combustible description.
The results files are two:
• ignMap.dtm: Stores ignition time.
• flMap.dtm: Stores flames elevation.
All these data can be represented in virtual reality format,
which enables landscape representation. The relevance of
this technology is not only in the visual representation
facet, also in his computer data representation. Virtual
reality stores physical structures of landscape, structures
that are required by the simulator in order to enable the
interaction with the landscape elements. This also enables
432-093
96
Page 2
active queries possibility over the outdoor simulation
model.
The difference between the virtual DEM representation
and a simple DEM is the existence of some rules over
virtual world, like collision detection or gravity, for
instance, which can be defined in virtual representation of
DEM, but are never defined in a DEM.
This rules definition is useful because the simulator not
only needs landscape structure, also need rules applied to
landscape (gravity, collision detection, lights, etc).
In our wildfire implementation, GIS stores in virtual
reality format data that represents the DEM, and data that
represents vegetation. Through this representation the user
can interact with simulation model.
The virtual reality language used is VRML 2.0 as standard
representation language [8].
Transformation of GIS data to VRML 2.0 is possible
using software like VirtualLands© [6], which enable the
automatic virtual reality geographic structures generation.
Figure 1 VirtualLands
The data used in the simulator must be structured in
different layers.
Each of these layers can have her structure; the
classification is showed in the next table, where:
• GeR: Geo referenced, the object is added in the
virtual world in the position market by his
geographical reference. This allows integration of
models with GPS or geo referenced data.
Layer
Description
GPS Integration
2DLayers
Point, lines, text or
polygons.
GeR
3DLayers
Fixed elements with a
3D structure, like trees
belonging to a forest.
GeR
2DObjects
Single elements (point,
line, polygon or text).
Waypoints
3DObjects
Single elements with a
3D structure.
Waypoints
Routes
Usually tracks from a
GPS.
Tracks
Table 1. LeanSim® GIS layers.
In the wildfire model all layers used are 3DLayers over a
DEM.
3. LeanSim® paradigm
There are many ways to model a real system, which differ
in system elements conception and definition [3].
LeanSim is, primarily, a discrete simulation developing
environment [4] using process interaction for models
description. Each process definition supplies complete
information of different operations or activities that can be
performed in the model by a specific entity.
The particularity of LeanSim process interaction model
definition is that processes describe activities that must be
applied to one entity. All process in LeanSim ends with a
“destroy” operation (destroying the entity and acquiring
statistical data) or “bifurcation” operation (“route
selection” or “go to” are operations implemented to
change active entity process).
This paper doesn’t include a description of LeanSim®
system for more information you can see [9].
4. Cellular automata
Cellular automata are discrete dynamical systems whose
behavior is completely specified in terms of a local
relation. [11]
One-dimensional cellular automatons are based in a row
of "cells" and a set of "rules". A two-dimensional cellular
automata use rectangular grids of cells.
Each of the cells can be in one of several "states". The
number of possible states depends on the automaton.
Thinking in states as numbers, in a two-state automaton,
each of the cells can be only in 1 or 2
The cells represents the automaton space; time advances
in discrete steps following the “rules”, the laws of the
“universe” usually expressed in a small look-up table,
through which at each step each cell computes its new
state from that of its close neighbors. Thus, the system's
laws are local and uniform.
In the next figure there’s a one-dimensional cellular
automaton initial state and the first two states after apply
the rules.
Figure 2: One-dimensional cellular automaton
4.1. Multi two dimensional cellular automaton
A multi two dimensional cellular automaton (m2-cellular
automaton) is a generalization, implemented in LeanSim,
of a two dimensional cellular automaton. These m2-
cellular automatons have one main matrix and a set of
secondary matrix that complements with his data the state
definition.
The transition in a multi two dimensional cellular
automaton is defined like in a two dimensional
automaton, but the state of each cell in the main matrix
97
Page 3
are based in data contained in the main cell plus
combination with data contained in all the others matrixes
in same position (is necessary to define a function that
allows this combination, fixing, if is necessary, the initial
state for each cell of the main matrix using data of
secondary matrixes cells, and defining the use of the
secondary data in the automata evolution)
In secondary matrixes are not necessary define the same
number of columns and rows that in main matrix, and all
the matrixes can be displaced respect the main matrix
origin. If all the matrixes have the same numbers of rows
and columns, the same size and the same origin, the multi
two dimensional cellular automata is normalized.
Obviously all the matrix must be referenced with the same
coordinate system allowing data positioning.
5. GIS data representation.
In LeanSim® there are different machines, or elements,
that allow the simulation system construction. For
instance, generator allows introduction of elements in the
system, and generic, allowing delays or model elements
transformation.
In next sections there are descriptions about the use of
cellular automata in simulation model, through LeanSim®
elements to represent different Layers and objects that
configure the landscape in a GIS.
5.1. Objects (2D and 3D) modeling
The representation of these objects is direct, and only is
necessary to select the object, from the LeanSim® objects
library, that represents better the behavior of the element.
In the wildfire sample is possible to represent a water
source with a generator element, which generates water
that can be used by fireman to fight fire.
5.2. 2DLayers modeling
VirtualLands generate one single object that represents
entire 2Dlayer. These objects can be added to model with
his own behavior. Usually these elements don’t have
implications in the model (for instance the territorial
divisions).
5.3. 3DLayers modeling using cellular automata
For the integration of the simulation model with 3DLayers
GIS data is necessary to use Cellular automata element,
due his ability to effectively represent large-scale spatial
dynamic phenomena [12] [13] [14].
The cellular automata stores in his matrixes the GIS data
used in the transitions, and implements a concrete logic
that enables the transitions calculations.
In the wildfire sample this element implements a multi
two-dimensional cellular automaton in our case
normalized.
Main matrix represents the DTM, and determines the
detail of the burning cell. All the other layers needed for
the fire propagation algorithm are stored in the secondary
matrixes. These matrixes are Model, Slope, Aspect, M1,
M10, M100, Mherb and Mwood, representing the layers
of the GIS data (see section 2).
With these data loaded in the cellular automata is possible
simulate fire propagation and integrate wildfire evolution
in a discrete simulation model. For instance is possible to
combine wildfire simulation model with a traffic
simulation model or an industry simulation model.
6. SDL WildFire cellular automata specification
The specification is based in the SDL specification
language like other LeanSim elements [9].
The events that lead propagation model are:
• EBurn: Associate to ignite fire into simulation cell.
• EPropagation: Programmed time for fire
propagation to neighbor cell.
• EExtinguish: Programmed time to put out fire in a
cell.
• dataUpdate: Event that represent a modification in
the data used to calculate spread time. When this
event is received is necessary to recalculate
propagation model, (for instance a modification of
the wind speed or direction).
Cellular automata process event EBurn using BEHAVE
model that implements, generating new simulation events
like EPropagation.
The simulation engine processes new events and sends
these events to different simulation elements affected by
them.
Obviously some of these events are received by the
cellular automata that represent landscape, processing
these events and generating new events following
BEHAVE model.
Parallel to main execution is possible to run a containment
model that interacts with propagation model.
This architecture enables simulation model construction
possibility using GIS data inside the model easily.
The behaviour for cellular automata is divided in two
areas, the whole cellular automata and each cell of cellular
automata. Cellular automata follow the LeanSim generic
machine specification. States diagram can be viewed in
[9]. Owing to space reasons is impossible to represent the
whole generic machine specification. The next diagram
shows structure for a cellular automaton cell.
98
Page 4
In S
Out S
In N
Out N
In E
Out E
In W
Out W
In
/
Ou
t
NW
In/
Out
SW
In
/
Ou
t
SE
I n/
O
u t
N
E
Figure 3: In/Out Ports
Figure 3 represents the in/out ports that allow the
communication of the cell with the neighbour’s cells of
cellular automaton.
The next diagram shows the state transition diagram for a
cell.
Burning
UnBurned
Burned
eBurn
eExtinguish
ePropagation
eBurn
eBurn
dataUpdate
Figure 4: Cell state diagram
The next diagram shows the SDL specification for a cell
Burning
eBurn
ePropagatio
n
Burning
Propag.
Algorithm
eBurn
Propagat
ion ?
Si
ePropaga
tion
No
Burned ?
eEstingui
sh
Si
No
Burning
eExtinguish
Burned
dataUpdate
Propag.
Algorithm
ePropaga
tion
Burning
Figure 5: Burning SDL
UnBurne
d
eBurn
Alg.
Rotherm
el
ePropag
ation
Burning
Burned
eBurn
Burned
Figure 6: Unburned, burned SDL
99
Page 5
7. BEHAVE model validation
Although the modification in the architecture that
implements the model, due the LeanSim cellular
automaton are based in the BEHAVE model, the results of
fire simulation must be the same.
In the next picture (Figure 7) is showed the height of fire
over virtual map in regular conditions (slow wind in north
direction and the same combustible in all cells).
Figure 7: Height of the flames
Using the same simulation conditions, the GIS data in the
LeanSim cellular automata, and the arrays in the
BEHAVE library (Andrews 1986, update on 1999) the
results are identical, but with the new architecture the
modifications in the conditions can be done through GIS
data, and the whole model mow are simulated in a generic
simulation engine allowing the combination of BEHAVE
model with other simulation models. For instance is
possible to implement a new cellular automata that
models the climatology and merge the behavior of the two
models, or is possible to add elements with a complex
behavior, like animals or persons that interact with the
model like is described in the next section.
8. Intelligent agent LeanSim element
Like cellular automata LeanSim element, LeanSim
intelligent agent inherits the structure from the generic
machine, but also inherits some structures from the entity
element. This enables that LeanSim intelligent agent
(IAgent) can make operations to different entities or other
simulation elements, can send signals, and also can die.
The intelligent agents have an internal process that defines
his life in the whole system. This process has two new
operations, life and death that allow the creation and
destruction respectively of the machine.
The communication of IAgent with whole system is based
in the LeanSim signals mechanism described in [5, 9].
The combination of agent in the simulation model allows
the description of new sort of models [10].
The IAgent follows the next architecture:
Figure 8: LeanSim IAgent
In order to interact with the model, IAgent belongs to one
Cellular automaton that defines his world.
The IAgent can send messages (signals) to other IAgents
or LeanSim Machines (of course can send messages to the
Cellular Automata that defines his world), and to
simulation engine.
Basically LeanSim signals are information that can be
sending from one object to another to make changes in the
object state or behavior.
In the next table there’s a short description of the signals
implemented actually.
Signal
Description
CloseInDoor
Blocs the input door of a
machine, no other entities
can access inside the
element.
OpenInDoor
Unblocks the input door of
a machine.
CloseOutDoor
Blocs the output o an
element.
OpenOutDoor
Unblocks the output o fan
element.
PauseProcess
Pause
the
selected
simulation process.
RestartProcess
Restarts
the
selected
simulation process.
StopProcess
Ends the selected process.
ForceSetUp
Oblige a setup.
StopSimulation
Ends the simulation.
GenerateByDemand
Generate an entity.
ForceLostEntity
Force to lose an entity.
ForceFail
Oblige an element to fail.
ForceRepair
Repair an element.
Table 1: LeanSim signals
In our sample there’s a set of IA named
CLeanMachineIAFireman
that
enables
the
implementation of fire containment model. Each
IAFireman have his own behavior inside the model,
defined with the logic that the fire department wants to
evaluate. The interaction of IAgents modifies the model
behavior allowing the implementation of the fireman
actions over the wildfire.
100
Page 6
Actually the fireman behavior and the location of the
fireman are code based, but in the future the position of
the fireman must be acquired from a GIS (or a GPS
system for instance).
In the Figure 9 is represented the fire propagation
modification using a set of fireman IAgents that clean the
forest (remove the combustible from an area).
Figure 9: Fireman action over fire
The final result is an emergent behavior of model that
represents interaction between the propagation model and
containment model.
9. Conclusions and future work
Multi two dimensional cellular automatons are presented,
allowing the direct use of GIS data inside simulation
model. Due that geographical data can be use like a
common simulation object, sending and receiving events
like other simulation elements, this architecture allows the
construction of models that require GIS data and enables
evolution possibility, in fact, join between GIS, cellular
automata, intelligent agents and event scheduling
simulation engine, allows the modeling of systems
concerning the landscape and in concrete some natural
disasters, like wildfires
A BEHAVE model using LeanSim cellular automaton
have been implemented and validated using this method,
allowing the use of the model in the whole LeanSim
system and the combination with LeanSim intelligent
agents.
The future work are focused in the representation of
IAgents positioning through a SIG and GPS systems, and
the improvement of the implemented behavior in the
IAgents to represent the containment model.
10. References:
[1] Rothermel, R. A mathematical model for predicting
fire spread in wildland fuels. Research Paper INT115.
Ogden, UT: U.S. Department of Agriculture, Forest
Service, Intermountain Forest and Range Experiment
Station; 1972. 40 p.
[2] Rothermel,R.C . How to predict the spread and
intensity of forest and range fires USDA Forest Service
Research Paper, INT 115 . USDA For. Ser. Gen. Tech.
1983 Rep. INT-114.
[3] Law, A. M., Kelton, W. D. Simulation modeling and
analysis. McGraw-Hill, 2000
[4] Antoni Guasch, Miquel Àngel Piera, Josep Casanovas,
Jaime Figueres, Modelado y simulación. Aplicación a
procesos logísticos de fabricación y servicios. Ediciones
UPC, 2002
[5] Pau Fonseca i Casas, Josep Casanovas i García, Jordi
Montero i García, LeanSim: Un sistema de simulación
para el entrenamiento de personal especializado dentro
de sistemas complejos; Memorias de la 2ª Conferencia
Iberoamericana en sistemas, cibernética e informática
CISCI 2003, Volumen I. pp 318-323.
[6] Pau Fonseca i Casas, Josep Casanovas i García, jordi
Montero i García, GIS and simulation integration in a
virtual reality environment. Proceedings GISRUK 2004.
pp 403-408.
[7] Ulises Cortés García, Javier Béjar Alonso, Antonio
Moreno Ribas Inteligencia
Artificial, Ediciones
UPC,1994
[8] Andrea L. Ames, David R. Nadeau, John L. Moreland
VRML 2.0 Sourcebook, 2E. 688, 2000
Robinson, A. and others, Elementos de Cartografía.
Omega, Barcelona, 1987
[9] Pau Fonseca, Josep Casanovas, Jordi Montero,
Leansim® virtual reality distributed simulation suite
Proceedings MSO 2004.
[10] Jim Doran, Hard problems in the use of agent based
modeling, Proceedings of the Fifth International
Conference on Logic and methodology, 2000
[11] Claus Emmeche Vida Simulada en el ordenador,
Editorial Gedisa 1998
[12] Ntaimo, L., Zeigler, B.P., Expressing a Forest Cell
Model in Parallel DEVS and Timed Cell-DEVS
Formalisms, to appear in Proceedings of SCSC July, San
Jose, CA 2004.
[13] Wainer, G. and Giambiasi, N. Timed Cell-DEVS:
modelling and simulation of cell spaces. Discrete Event
Modeling & Simulation: Enabling Future Technologies,
Springer-Verlag. 2001
[14] J. Ameghino, A. Trccoli, G. Wainer, Models of
complex physical systems using CellDEVS. Proceedings
of Annual Simulation Symposium. Seattle, WA. U.S.A..
2001
[15]Andrews, P.L. 1986. BEHAVE: Fire Behavior
Predictions and Fuel Modeling System-Burn Subsystem
Part 1, USDA Forest Service General Technical Report
INT-194. 130 p.
101