Enviromental Modelling
Introduction to TerraME
Tiago Garcia de Senna Carneiro
(UFOP)
Gilberto Câmara (INPE)
Dynamic Spatial Models
f (It)
f (It+1)
F
f (It+2)
f ( It+n )
F
..
“A dynamical spatial model is a computational
representation of a real-world process where a location
on the earth’s surface changes in response to variations
on external and internal dynamics on the landscape”
(Peter Burrough)
Dynamic Spatial Models
Forecast
tp - 20
tp - 10
tp
Calibration
Source: Cláudia Almeida
Calibration
tp + 10
Spatial dynamical models have a common
structure
1980
1990
How much?
2000
t+1
load
When?
Where?
t ≥ tf
GIS
CLUE
Model
play
idle
How?
What is a spatial dynamical model?

A closed microworld with
 Spatial and temporal structure
 Entities
 Rules of behaviour
What is
changing?
When?
Where?
Why?
Computational Modelling with Cell
Spaces
Cell Spaces
Hybrid automata
Event
Control
Mode A
Control
Jump
Mode B
Flow
Flow
Condition
Condition
Generalized Proximity Matrix
Database support
Cell Spaces
Cellular Data Base Resolution
2500 m
2.500 m e 500 m
Software: Open source GIS
Visualization (TerraView)
Modelling (TerraME)
Spatio-temporal
Database (TerraLib)
Statistics (R interface)
Data Mining(GeoDMA)
TerraME architecture
RondôniaModel
DinamicaModel
TROLLModel
CLUEModel
TerraME Language
TerraME Compiler
TerraME Virtual Machine
TerraLib Enviromental
Modeling Framework
C++ Signal
Processing
librarys
TerraLib
C++
Mathematical
librarys
C++
Statistical
librarys
TerraME functionality
TerraME INTERPRETER
• model syntax semantic checking
• model execution
TerraView
• data acquisition
• data visualization
• data management
• data analysis
LUA interpreter
TerraME framework
data
model
model
TerraME/LUA interface
MODEL DATA
Model
source code
TerraLib
database
data
Eclipse & LUA plugin
• model description
• model highlight syntax
Enviromental Modelling
Introduction to LUA
Tiago Garcia de Senna Carneiro
(UFOP)
Gilberto Câmara (INPE)
Por que Lua?





Pequena
Portátil
Eficiente
Fácil integração com C/C++
Simples e flexível
 Sintaxe simples
 Facilidades para descrição de dados
 Mecanismos de extensão
 “Simple things simple, complex things possible”
Como é Lua?
Sintaxe convencional
function fat (n)
if n == 0 then
return 1
else
return n*fat(n-1)
end
end
Unidade básica de execução: chunk
 Chunk = lista de comandos
 Arquivo ou string do programa hospedeiro
Tipos

Tipos associados a valores
 Variáveis armazenam qualquer tipo
 Polimorfismo natural

Tipos existentes
 nil
 boolean
 number
 string
 table
 function
 userdata
 thread
Tipo nil

Propósito maior: ser diferente dos demais

Tipo do valor default das variáveis

Também significa o falso booleano
 Qualquer valor de outro tipo significa verdadeiro

Com exceção de false
Tipo boolean

Valor booleano
 Falso (false) ou verdadeiro (true)
 if
(choveu == true) then ....
Tipo number

Único tipo nativo para valores numéricos
 double (por default)
local a = 3
local b = 3.5
local c = 4.5e-8
Tipo userdata

Armazena um ponteiro void* de C

Tipo opaco para a linguagem
 Somente atribuição e teste de igualdade

Linguagem extensível em C
 “Esqueleto” para construção de linguagens de domínio
específico
Tipo string


Valores imutáveis
Sem limite de tamanho
 É comum ler arquivo completo em uma string

Strings não usam ‘\0’ para terminação
 Podem armazenar dados binários quaisquer

Pattern-matching poderoso
 Implementado via biblioteca padrão
 meunome
= “Silvana Amaral”;
Tipo table

Resultado da expressão {}

Arrays associativos
 Qualquer valor como chave
 Com

exceção de nil
Único mecanismo de estruturação de dados
 São para Lua o que listas são para Lisp
Tables

The only structured data type is table.
 implements associative arrays, that is, arrays that can be
indexed not only with integers, but with string, double,
table, or function values.
 For table indexing, both table.name and table[''name''] are
acceptable. Tables can be used to implement records,
arrays, and recursive data types.
Tipo Table
loc = {
cover = "forest",
distUrban = 2 };
Campo
cover
distRoad
distUrban
distRoad
=
Valor
“forest”
0.3
2
0.3,
Tipo Table
loc = {
cover = "forest",
distRoad = 0.3,
distUrban = 2 };
loc.cover = “cerrado”;
loc[“cover”] = “soja”;
if (loc.distUrban > 1.5) then
loc.desfPot
=
loc.distRoad
loc.distUrban;
+
Tables and functions in Lua
loc = { cover = "forest", distRoad =
0.3, distUrban = 2 };
...
loc.reset = function( self )
self.cover = "";
self.distRoad = 0.0;
self.distUrban = 0.0;
end
loc = { cover = "forest", distRoad =
0.3, distUrban = 2, reset };
Data structures with tables


Simple and efficient implementation
Records

Syntactic sugar t.x for t["x"]:
t = {}
t.x = 10
t.y = 20
print(t.x, t.y)
print(t["x"], t["y"])
Data structures with tables (2)

Arrays
for i=1,n do print(a[i]) end
 Use integers as indexes

Sets
 Use elements as indexes
t = {}
t[x] = 1
-- t = t  {x}
if t[x] then... -- x  t?

“Bags"
 Elements as indexes, counters as values
Data structures with tables (3)

Listas
 Tables in Lua are “objects”, that is, dynamically allocated
“things” manipulated through pointers to them.
 Tables in Lua can directly represent dynamic structures
such as trees and graphs, even cyclic structures.
list = {value=v, next=list}
list
old list
...
value - v
next -
Library functions for tables



table.insert
 Inserts a new element
table.remove
 Removes an element
table.sort
 Orders the elements
My first Lua program
C = 2; -- rain/t
-- defines a location with an absortion
capacity and makes it rain
solo = { acum = 0, k = 0.4; }
for time = 0, 20, 1 do
solo.acum = solo.acum + C –
solo.k*solo.acum;
end
Type function
Funções are first-class values
function inc (x)
return x+1
end
sugar
inc = function (x)
return x+1
end
Functions can be assigned to table fields
w = {
redraw = function () ... end,
pick = function (x,y) ... end,
}
if w.pick(x,y) then
w.redraw()
end
Type function (2)
Passagem por valor e retorno múltiplo
Suporte a atribuições múltiplas (x,y = y,x)
a, b = f()
print(f())
function f()
return 1,2
end
Suporte a número variável de argumentos
 Argumentos
"empacotados" em uma tabela
function f(...)
print(arg[1], arg[2])
end
Lexical scope


Acesso a variáveis em escopos externos
Expressão cujo valor é calculado quando a função
que a contém é criada
 Quando o fecho é feito
function add (x)
return function (y)
return y+x
end
end
add1 = add(1)
print(add1(10)) --> 11
upvalue
Constructors
Data description + imperative semantics
article{
author="F.P.Brooks",
title="The Mythical Man-Month",
year=1975
}
temp = {}
temp["author"] = "F.P.Brooks"
temp["title"] = "The Mythical Man-Month"
temp["year"] = 1975
article(temp)
Objects

Funções 1a classe + tabelas = quase OO
 Tabelas podem ter funções como campos

Sugar para definição e chamada de métodos
 Trata parâmetro implícito self
 Ainda falta herança...
function a:foo (x)
...
end
sugar
a.foo = function (self,x)
...
end
a:foo(x)
sugar
a.foo(a,x)
Exemplo: tipo Point
-- Metatable de Point
local Point_metatable = {
__add = function (p1,p2)
return Point(p1.x+p2.x,p1.y+p2.y,p1.z+p2.z}
end
}
-- Construtor
function Point (self)
self.x = tonumber(self.x) or 0.0
self.y = tonumber(self.y) or 0.0
self.z = tonumber(self.z) or 0.0
setmetatable(self,Point_metatable)
return self
end
----------------------------------------------local p = Point{x=3.0,y=1.3,z=3.2}
local q = Point{x=4.2,y=1.0}
local r = p+q
-- {7.2, 2.3, 3.2}
Herança Simples: mecanismo de delegação
-- Métodos
local Point_methods = {
Print = function (self)
print(self.x, self.y, self.z)
end,
...
}
-- Metatable
local Point_metatable = {
__index = Point_methods,
__add = function (p1,p2)
return Point(p1.x+p2.x,p1.y+p2.y,p1.z+p2.z}
end
}
-----------------------------------------------local p = Point{x=3.0,y=1.3,z=3.2}
local q = Point{x=4.2,y=1.0}
local r = p+q
r:Print()
Bibliotecas padrão








Basic
String
Table
Math
IO
OS
Debug
Coroutine
Basic

Oferecem funções básicas
 print
 type
 setmetatable
 pairs
String

Funções para manipulação de strings
 Casamento de padrões (pattern matching)

string.find


Permite buscar a ocorrência de um padrão numa string
string.gsub

Permite substituir ocorrâncias de um padrão por uma sequência de caracteres
dentro de uma string
Meu segundo programa em Lua
C = 2; -- rain/t
K = 0.4; -- flow coefficient
q = 0; -function chuva (t)
if (t < 10) then
return 4 – 4*math.cos(math.pi*t/10);
else
return 4 – 4*math.cos(math.pi*(t-10)/10);
end
end
-for time = 0, 20, 1 do
-- soil water
q = q + chuva(time) - K*q;
end
-- report
print(“q = "..q);
Defining a model in TerraME
Part 1: The cell space
Computational Modelling with Cell
Spaces
Cell Spaces

fonte: Carneiro (2006)
Components

Cell Spaces

Generalizes Proximity Matriz – GPM

Hybrid Automata model

Nested enviroment
Basic concepts
A dynamical model…
is represented as a cell space environment…
… where automata rules change the space properties in
time.
Several agents can share the same environment.
The TerraME spatial model
GIS
The
space local
properties,
and connectivity can be modeled by:
A cell-space
where
each cellconstraints,
a unique neighborhood
-a
spatial
a lattice of
cells
Space
is structure:
nether isomorphic
nor
structurally homogeneous. (Couclelis 1997)
- Actions
a distancedata:
are considered.
(Takeyana
1997), (O’Sullivan 1999)
a set of at
geographic
each cell has various
attributes
TerraME extensions to Lua

To build spatial dynamic models, TerraME includes
new value types in LUA using the constructor
mechanism.

These values are: CellularSpace, Cell, Neighbourhood
Cellular Space

A CellularSpace is a multivalued set of Cells.

It consists of a geographical area of interest, divided
into a regular grid.

Each cell in the grid has one or more attributes.

CellularSpaces are stored and retrieved from a
TerraLib database, so the modeller should specify
the properties of the CellularSpace
Constructors in Lua

LUA has a powerful syntactical tool, called
constructor.

When the modeller writes name{…}, the LUA
interpreter replaces it by name({… }), passing the
table {…} as a parameter to the function name( ).

This function typically initializes, checks properties
values and adds auxiliary data structure or methods.
Loading Data
-- Loads the TerraLib cellular space
csQ = CellularSpace
{
dbType = "ADO",
GIS
host = “localhost",
database = "c:\\TerraME\\Database\\CabecaDeBoi.mdb",
user = "",
password = "",
layer = "cellsLobo90x90",
theme = "cells",
select = { "altimetria", “soilWater", “infCap" }
}
csQ:load();
createMooreNeighborhood(csQ);
csCabecaDeBoi:loadNeighborhood(“Moore_SerraDoLobo1985");
Database management
-- loads a cellular space
csAmazonia:load();
csAmazonia:createMooreNeighborhood();
-csAmazonia:loadNeighborhood
(“GPM”);
…
-save
(time,
attrTableName) -for time = 1, 10,1 do
themeName,
Referencing cells
A CellularSpace has a special attribute called cells. It is
a one-dimensional table of references for each Cell
in the CellularSpace
-- c is the seventh cell in the
cellular space
c = csCabecaDeBoi.cells[ 7 ];
-- Updating the attribute “infcap”
from the seventh cell
c.infcap = 10;
print
(csCabecaDeBoi.cells[7].infCap);
The Cell type
A Cell value has two special attributes: latency and
past.
The latency attribute registers the period of time since
the last change in a cell attribute value.
The past attribute is a copy of all cell attribute values in
the instant of the last change.
if(cell.cover
==
"abandoned"
and
cell.latency
>=
10
)
then
cell.cover = "secFor"; end
cell.water = cell.past.water + 2;
Traversing a Cell Space

ForEachCell(cs, function())

Applies the chosen function to each cell of the
cellular space. This function enables using different
rules in a cellular space.
ForEachCell(csQ, function(i, cell)
cell.water = cell.past.water + 2;
return true; end);
Traversing a Neighbourhood
ForEachCell(csQ,
function(i, cell)
count = 0;
ForEachNeighbor(cell, 0,
function(cell, neigh)
if (neigh ~= cell) then
count = count + 1;
end -- if
end
); -- for each neighbor
cell.value = count;
….
end); --
Isotropic neighbourhoods in cell spaces
Von Neumann
Neighborhood
Moore Neighborhood
Generalized Proximity Matrix (GPM)


In a cell-space, each cell has a different
neighbourhood
Defined by a NxN matrix
 w11
w
W   21
 w31

w41
w12 w13 w14 
w22 w23 w24 
w32 w33 w34 

w42 w43 w44 
One simple example



Consider a 5x 5 cell-space
For each cell, a different matrix
The neighbours of a cell (the (2,3) cell are):
0
0
1
1
0
0
0
*
1
0
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
Using Generalized Proximity Matrices
Consolidated area
Emergent area
Synchronization
Leia sempre do antigo (“past”)
Escreva sempre no novo (“present”)
Sincronize no final
Syncronization
fonte: Carneiro (2006)
tn
tn+1
rule
count = 0 ;
ForEachCell ( csValeDoAnary )
Function (I, cell)
if ( cell.past.cover == “forest” ) then
cell.cover = “deforested”;
count = count + 1 ;
end
end
cell.synchronize( );
?
print(“Number of deforested cells: ”.. count);
TerraME basics: some
simple examples
An Example: The Majority Model for
Segregation

Start with a CA with “white” and “black” cells
(random)

The new cell state is the state of the majority of the
cell’s Moore neighbours, or the cell’s previous state if
the neighbours are equally divided between “white”
and “black”
 White cells change to black if there are five or more black
neighbours
 Black cells change to white if there are five or more black
neighbours

What is the result after 50 iterations?
The Modified Majority Model for
Segregation



Include random individual variation
Some individuals are more susceptible to their
neighbours than others
In general, white cells with five neighbours change to
black, but:
 Some “white” cells change to black if there are only four
“black” neighbours
 Some “white” cells change to black only if there are six
“black” neighbours

Variation of individual difference

What happens in this case after 50 iterations and
500 iterations?
Key property of cellular spaces:
potential
POTENTIAL
What is the potential of a cell?

Potential refers to the capacity for change

Higher potential means higher chance of change

How can we compute potential?
People
Potential
Nature
Different models for calculating
potential

Brian Arthur’s model of increasing returns

Vicsek-Salay model: structure from randomness

Schelling’’s model: segregation as self-organization
The Brian Arthur model of increasing
returns


Create a cell space and fill it with random values
For example, take a 30 x 30 cell space and populate
with random values (1..1000)
The Brian Arthur model of increasing
returns

Think of this cellular space as the starting point for a
population
What happens if the rich get richer?

This model is called “increasing returns”

 This effect is well-known in the software industry
 Customer may become dependent on proprietary data
formats
 High switching costs might prevent the change to another
product
 Examples: QWERTY keyboard, and Microsoft Windows

Arthur, B. (1994). “Increasing Returns and Path
The Brian Arthur model of
increasing returns

Consider a situation where the potential grows
with a return factor  ( is a scale factor)
Pi (t  1)   Pi (t )



O <  < 1 - decreasing returns (increased
competition)
 = 1 – linear growth
 > 1 – increasing returns (rich get richer)
The Brian Arthur model of increasing
returns

Take the random 30 x 30 cell space and apply the
increasing returns model  = 2 – What happens?
The Vicsek-Szaly Model: Structure from Randomness

Consider a CA with a 4 x 4
neighbourhood

Establish a random initial
distribution
Pi (0)   i (noise)
 Historical
accident that set the
process in motion
 P (t )

Pure averaging model
Pi (t  1) 
j
j j
5
TerraME: defining a model
Model implementation in TerraME
Each Land Unit is an environment, nested in the Rondônia environment.
Global rate
G
+
Rsmall
+
Rlarge
+
Asmall
Land Unit1
Land Unit2
...
+
...
Rondônia
+
Rsmall
Alarge
...
+
Asmall
Land Unitn
Legend
Environment
Agent
(two types of agentes Rsmall and R large)
(two types of agentes Asmall and A large)
TerraME rules of behaviour
How can we define rules of behaviour?
theory-driven models
modelling
theor
y
2
model
input
results
laws
tn
tn+1
1
data-driven models
stats inference
input
analysis
1
modelling
model
2
results
tn
tn+1
Types of models

Theory-driven models
 General laws and rules
 Can deal with non-stationary phenomena

Data-driven models
 Rules derived from statistical inference
 Case-specific
 Stationary phenomena
Models of Computation
(von Neumann, 1966)
(Wooldbridge, 1995)
(Minsky, 1967)
(Pedrosa et al, 2003)
(Aguiar et al, 2004)
(Straatman et al, 2001)
(Rosenschein and Kaelbling, 1995)
Agent based models
Cellular automata models
Which Cellular Automata?

For realistic geographical models
 the basic CA principles too constrained to be useful

Extending the basic CA paradigm
 From binary (active/inactive) values to a set of
inhomogeneous local states
 From discrete to continuous values (30% cultivated land,
40% grassland and 30% forest)
 Transition rules: diverse combinations
 Neighborhood definitions from a stationary 8-cell to
generalized neighbourhood
 From system closure to external events to external output
during transitions
Spatial dynamic modeling
Demands
Requirements

Locations change due to
external forces

discretization of space in cells

Realistic representation of
landscape

generalization of CA

Elements of dynamic models

discrete and continous processes

Geographical space is
inhomogeneous

Flexible neighborhood definitions
Extensibility to include userdefined models

Different types of models

Hybrid Automata

Formalism developed by Tom Henzinger
(UC Berkeley)
 Applied to
embedded systems, robotics, process control,
and biological systems

Hybrid automaton
 Combines discrete transition graphs with continous
dynamical systems
 Infinite-state transition system
Traditional Cellular Automata

Discrete state transition system (e.g, Life)
 At each step in time, the following effects occur:
 Any live cell with fewer than two neighbors dies, as if by
loneliness.
 Any live cell with more than three neighbors dies, as if by
overcrowding.
 Any live cell with two or three neighbors lives, unchanged,
to the next generation.
 Any dead cell with exactly three neighbors comes to life.
2-3 neighbours
0,1 or 4+ neighbours
Alive
Dead
3 neighbours




Hybrid Automata
Variables
Control graph
Flow and Jump conditions
Events
Event
Event
Jump condition
Control Mode A
Control Mode B
Flow Condition
Flow Condition
Modelo Hidrológico Simples
A water balance Automata
input
input
DRY
soilwater=soilwater+pre-evap
soilwater>=infilcp
input
WET
Surplus=soilwater-infilcp
Soilwater=infilcp
discharge
TRANSPORTING
MOVE(LDD, surplus, infilcp)
Surplus>0
Control Mode
Flow Condition
Jump Condition
Event
Transition
DRY
Solwat=solwat+pre-evap
Solwat>=infcap
WET
Surplus=soilwater-infilcap
Surplus>0
discharge
TRANSP
TRANSP
MOVE(LDD,surplus, infilcap)
Surplus>0
input
DRY
WET
Agents and CA: Humans as ants
Identify different actors and try to model their
actions
Farms
Settlements
10 to 20 anos
Recent
Settlements
(less than 4
years)
Source: Escada, 2003
Old
Settlements
(more than
20 years)
Model hypothesis:

Actors and patterns
Occupation processes are different for Small and
Medium/Large farms.
62o 30’ W


62o W
oS
9Rate
of change is not distributed uniformly9oin
S
space and time: rate in each land unit is influenced
by settlement age and parcel size; for small farms,
rate of change in the first years is also influenced by
installation credit received.
Location of change: For small farms, deforestation
9o 30’ S
has a concentrated pattern that spreads along roads.
For large farmers, the pattern is not so clear.
9o 30’ S
10o S
10o S
10o 30’ S
10o 30’ S
Large farms
62o 30’ W
Medium farms
Urban areas
Small farms
Reserves
0
62o W
50
Km
Model overview
Deforestation Rate Distribution from 1985 to
2000 - Land Units Level:

Large/Medium Rate Distribution sub-model

Small Farms Distribution sub-model
Allocation of changes - Cellular space
level:

Large/Medium allocation sub-model

Small allocation sub-model
Global study
area rate
in time
Land unit 1 rate t
Land unit 2 rate t
Large farms
Medium farms
Urban areas
Small farms
Reserves
2.500 m (large
and
medium)
500 m (small)
Deforestation Rate Distribution Module
Small Units Agent
latency
> 6 years
Deforesting
Newly implanted
Deforestation >
80%
Year of
creation
Slowing down
Iddle
Factors affecting rate:


Deforestation =
100%


Large and Medium Units Agent
Deforesting
Deforestation >
80%
Year of
creation
Slowing down
Iddle
Deforestation =
100%
Global rate
Relation properties density speedy of change
Year of creation
Credit in the first years (small)
Allocation Module: different factors and
rules
Factors affecting location of changes:
Small Farmers (500 m resolution):
 Connection to opened areas
through roads network
 Proximity to urban areas
Medium/Large Farmers (2500 m
resolution):
 Connection to opened areas
through roads network
 Connection to opened areas in
the same line of ownerships
Allocation Module: different resolution, variables and neighborhoods
1985
Small farms environments:
500 m resolution
Categorical variable:
deforested or forest
One neighborhood relation:
•connection through roads
Large farm environments:
2500 m resolution
1997
Continuous variable:
% deforested
Two alternative neighborhood
relations:
•connection through roads
• farm limits proximity
1997
Model implementation in TerraME
Each Land Unit is a scale, nested in the Rondônia scale.
Global rate
G
+
Rsmall
+
Rlarge
+
Asmall
Land Unit1
Land Unit2
...
+
...
Rondônia
+
Rsmall
Alarge
...
+
Asmall
Land Unitn
Legend
Environment
Agent
(two types of agents Rsmall and R large)
(two types of agents Asmall and A large)
Defining a model – part 3:
TerraME temporal model
Asynchronous Processes
Multiple Temporal Resolutions
The TerraME Timer
1. Get first pair
2. Execute the ACTION
3. Timer =EVENT
1.
1:32:00
Mens. 1
Execute an agent over the cellular space regions
2.
1:32:10
Mens. 3
Save the spatial data
3.
1:38:07
Mens. 2
Draw cellular spaces and agents states
4.
1:42:00
Mens.4
Carrie out the comunication between agents
...
return value
true
4. timeToHappen += period
TerraME Timer Object
Neighborhood based rules & Time
Rule:
General rule form:
cell.soilWater= cell. soilWater + 2;
if ( all neighbors = 1 ) then 0
Temporal
inconsistency
one copy
of the
cellular
space
1t 1 1t 1 1t 1 
 t 1 t 1 t 1 
1
1 
1
1t 1 1t 1 1t 1 


past
present
t 1
t 1
1º step
1t 1 1t 1 1t 1 
 t 1 t 1 t 1 
1
1 
1
1t 1 1t 1 1t 1 


0t 1t 1t 
 t
t
t
1 1 1 
1t 1t 1t 


2º step
2º step
 0t 1t 1 1t 1 
 t 1 t 1 t 1 
1
1 
1
1t 1 1t 1 1t 1 


1t 1 1t 1 1t 1 
 t 1 t 1 t 1 
1
1 
1
1t 1 1t 1 1t 1 


0 t
 t
1
1t

0t 1t 

1t 1t 
1t 1t 
update
1
1
1 
 t 1 t 1 t 1 
1
1 
1
1t 1 1t 1 1t 1 


1t 1t 1t 
 t t t
1 1 1 
1t 1t 1t 


t 1
1º step
 0t 1t 1 1t 1 
 t 1 t 1 t 1 
1
1 
1
t

1
t

1
t 1 
1
1
1


Runtime Rule Activity
tn
tn+1
rule
count = 0 ;
for i, cell ipairs( csValeDoAnary ) do
if ( cell.past.cover == “forest” ) then
cell.cover = “deforested”;
count = count + 1 ;
end
end
cell.synchronize( );
?
print(“Number of deforested cells: ”.. count);
TerraME Synchronization Schemes
Processes
Might Be
Sequential in Time
Parallel in Time
Sequential in Space
execute(globalAutomaton1);
synchronize( );
execute(globalAutomaton2);
synchronize( );
execute(globalAutomaton1);
execute(globalAutomaton2);
synchronize( );
Parallel in Space
execute(localAutomaton1);
synchronize( );
execute(localAutomaton2);
synchronize( );
execute(localAutomaton1);
execute(localAutomaton2);
synchronize( );
What is a Cell-Space?

Raster spatial data structure where each cell can
handle one or more types of attribute.

Cell spaces were used in some of the very early GIS
implementations and have been since discarded in
most GIS implementations in favor of one-attribute
raster data structures.

Cell spaces allow easier integrated modelling in a GIS
environment
Cell Spaces
(a) land_cover equals deforested in 1985
(a) land_cover equals deforested in 1985
attr_id
object_id
initial_time
final_time
C34L181985-01-0100:00:001985-12-3123:59:59
C34L18
01/01/1985
31/12/1985
C34L181988-01-0100:00:001988-12-3123:59:59
C34L18
01/01/1988
31/12/1988
C34L181991-01-0100:00:001991-12-3123:59:59
C34L18
01/01/1991
31/12/1991
C34L181994-01-0100:00:001994-12-3123:59:59
C34L18
01/01/1994
31/12/1994
C34L181997-01-0100:00:001997-12-3123:59:59
C34L18
01/01/1997
31/12/1997
C34L182000-01-0100:00:002000-12-3123:59:59
C34L18
01/01/2000
31/12/2000
C34L191985-01-0100:00:001985-12-3123:59:59
C34L19
01/01/1985
31/12/1985
C34L191988-01-0100:00:001988-12-3123:59:59
C34L19
01/01/1988
31/12/1988
C34L191991-01-0100:00:001991-12-3123:59:59
C34L19
01/01/1991
31/12/1991
C34L191994-01-0100:00:001994-12-3123:59:59
C34L19
01/01/1994
31/12/1994
C34L191997-01-0100:00:001997-12-3123:59:59
C34L19
01/01/1997
31/12/1997
C34L192000-01-0100:00:002000-12-3123:59:59
C34L19
01/01/2000
31/12/2000
land_cover
forest
forest
forest
deforested
deforested
deforested
forest
deforested
deforested
deforested
deforested
deforested
dist_primary_road
dist_secondary_road
7068.90
669.22
7068.90
669.22
7068.90
669.22
7068.90
669.22
7068.90
669.22
7068.90
669.22
7087.29
269.24
7087.29
269.24
7087.29
269.24
7087.29
269.24
7087.29
269.24
7087.29
269.24
Cell-space x Cellular Automata

CA
 Homogeneous, isotropic space
 Local action
 One attribute per cell (discrete values)
 Finite space state

Cell-space
 Non-homogeneous space
 Action-at-a-distance
 Many attributes per cell
 Infinite space state
Hybrid Automata

Formalism developed by Tom Henzinger
(UC Berkeley)
 Applied to
embedded systems, robotics, process control,
and biological systems

Hybrid automaton
 Combines discrete transition graphs with continous
dynamical systems
 Infinite-state transition system
Hybrid Automata




Variables
Control graph
Flow and Jump conditions
Events
Event
Control Mode
A
Flow Condition
Event
Jump condition
Control Mode B
Flow Condition
Neighborhood Definition

Traditional CA
 Isotropic space
 Local neighborhood definition (e.g. Moore)

Real-world
 Anisotropic space
 Action-at-a-distance

TerraME
 Generalized calculation of proximity matrix
Space is Anisotropic
Spaces of fixed location and spaces of fluxes in Amazonia
Motivation
Which objects are NEAR each other?
Motivation
Which objects are NEAR each other?
Using Generalized Proximity Matrices
Consolidated area
Emergent area
Computational Modelling with Cell Spaces
Cell Spaces

Components

Cell Spaces

Generalizes Proximity Matriz – GPM

Hybrid Automata model

Nested enviroment
TerraME basic concepts
An environment on the Earth could be modeled as a synthetic
environment in the computer representation world…
… which has three dimensions:
 Space, time and behavior.
Environment: A Key Concept in TerraME
An environment has 3 kinds of sub models:
 Spatial Model: cellular space + region + GPM (Generalized
Proximity Matrix)
 Behavioral Model: hybrid automata + situated agents
 Temporal Model: discrete event simulator
The spatio-temporal structure is shared by several
communicating agents
Support for Nested Environments
U
U
U
Environments can be nested
Multiscale modelling
Space can be modelled in different resolutions
Behavioural Model

Agents:
 Local
 Global
Software Architecture
RondôniaModel
São Felix Model
Amazon Model
Hydro Model
TerraME Language
TerraME Compiler
TerraME Virtual Machine
TerraLib
TerraME Framework
C++ Signal
Processing
librarys
C++
Mathematical
librarys
C++
Statistical
librarys
TerraLib
http://www.terralib.org/
Introduction: Rondônia modeling
exercise study area
Projetos antigos
Novos projetos
Projetos planejados
10
8
Projetos de
Colonização
13
15
14
16
km
Deforestation Map – 2000
(INPE/PRODES Project)
Deforestation
Forest
Non-forest
Federal Government induced
colonization area (since the 70s):

Small, medium and large farms.
 Mosaic of land use patterns.

Definition of land units and typology
of actors based on multi-temporal
images (85-00) and colonization
projects information (Escada, 2003).
Actors and patterns
Model hypothesis:

Occupation processes are different for
Small and Medium/Large farms.
62o 30’ W
62o W

9o S

Location of change: For small farms,
deforestation has a concentrated pattern that
spreads along roads. For large farmers, the
pattern is not so clear.
o
o
o
9 S
Rate of change is not distributed uniformly
in space and time: rate in each land unit is
influenced by settlement age and parcel size;
for small farms, rate of change in the first
years is also influenced by installation credit
received.
9o 30’ S
9o 30’ S
10 S
10 S
10o 30’ S
10o 30’ S
Large farms
62o 30’ W
Medium farms
Urban areas
Small farms
Reserves
0
62o W
50
Km
Model overview
Deforestation Rate Distribution from
1985 to 2000 - Land Units Level:

Large/Medium Rate Distribution submodel

Small Farms Distribution sub-model
Allocation of changes - Cellular
space level:

Large/Medium allocation submodel

Small allocation sub-model
Global study
area rate
in time
Land unit 1 rate t
Land unit 2 rate t
Large farms
Medium farms
Urban areas
Small farms
Reserves
2.500 m (large
and
medium)
500 m (small)
Model implementation in TerraME
Each Land Unit is an environment, nested in the Rondônia environment.
Global rate
G
+
Rsmall
+
Rlarge
+
Asmall
Land Unit1
Land Unit2
...
+
...
Rondônia
+
Rsmall
Alarge
...
+
Asmall
Land Unitn
Legend
Environment
Agent
(two types of agentes Rsmall and R large)
(two types of agentes Asmall and A l
Deforestation Rate Distribution Module
Small Units Agent
latency
> 6 years
Deforesting
Newly implanted
Deforestation >
80%
Year of
creation
Slowing down
Iddle
Deforestation =
100%
Large and Medium Units Agent
Deforesting
Deforestation >
80%
Year of
creation
Slowing down
Iddle
Deforestation =
100%
Factors affecting rate:

Global rate

Relation properties density speedy of change

Year of creation

Credit in the first years
(small)
Allocation Module: different factors and
rules
Factors affecting location of
changes:
Small Farmers (500 m resolution):
 Connection to opened
areas through roads
network
 Proximity to urban areas
Medium/Large Farmers (2500 m
resolution):
 Connection to opened
areas through roads
network
 Connection to opened
areas in the same line of
ownerships
Allocation Module: different resolution,
variables and neighborhoods
1985
Small farms
environments:
500 m resolution
Categorical variable:
deforested or forest
One neighborhood
relation:
Large
farm environments:
•connection
through
roads
1997
2500 m resolution
Continuous variable:
% deforested
Two alternative neighborhood
relations:
•connection through roads
• farm limits proximity
1997
Simulation Results
1985
1988
1994
1997
1991
Simulation Results
1985 to 1997
Contributions

TerraME models many aspects of spatial and temporal
Rondônia study area complexity combining:
 Multiple scales
 Multiple actors and behaviors
 Multiple time events and assynchronous processes
 Alternative neighborhood relationships
 Continuous and discrete behavior
Calibration and Validation
dados simulados
M
M
M
t1990
t2000
Ajustou?
Ajustou?
calibração
t2010
validação
dados reais
t1980
t1990
t2000
t2010
?
Data Coherence
Distancia a centros urbanos
Data Coherence
Processo de
desflorestamento
1985
1988
1991
1994
1997
2000
Conclusions

Computational modelling on cellular spaces is an
emerging trend in land use modelling

Realistic assumptions are built in TerraME
 We have tried to avoid the five orders of ignorance

TerraME is an evolving project
 We hope to learn more as we do further experiments
Spatial
Dynamical
Modeling with TerraME
Tiago Garcia de Senna Carneiro
Antônio Miguel Vieira Monteiro
Gilberto Câmara
TerraME Concepts: An Earth’s
environment …
can be represented as a synthetic environment…
… where analytical entities (rules) change the space
properties in time.
Several interacting entities share the same spatiotemporal
structure.
myModel = Enviroment
{
id = "myModel",
-- Add cellular spaces (spatial dimension)
cs1 = CellularSpace{ … },
-- Add rules (behaviour)
rul1 = Automata{ … },…
-- Add timer (temporal dimension)
t1 = Timer{ … }, -- glue rules to spaces
}
myModel.execute();
myModel = Enviroment
{
id = "myModel",
-- Add cellular spaces (spatial dimension)
cs1 = CellularSpace{ … },
cs2 = CellularSpace{ … },
-- Add rules (behaviour)
rul1 = Automata{ … },…
rulN = Automata{ … },
-- Add timers (temporal dimension)
t1 = Timer{ … },
tN = Timer{ … },
}
myModel = Enviroment
{
id = "myModel",
-- Add cellular spaces (spatial dimension)
cs1 = CellularSpace{ … },
-- Add rules to this CA (behaviour)
rul1 = Automata{ … },…
-- Add timers to this CA (temporal dimension)
t1 = Timer{ … },
-- Add CA to this CA (nested-CAs)
model1 = Environment{ … } …
model2 = Environment{ … },
}
myModel.execute();
Simulation of Physical
Processes
- rain drainage in a terrain -
O Brasil “from the space”
2000
Espinhaço Range
Minas Gerais State
“from the space”
2000
Lobo’s Range
Itacolomi
do Itambé Peak
Lobo’s Range
Itacolomi
do Itambé Peak
rain
rain
Itacolomi do Itambé
Peak
N
rain
Lobo’s Range
Picture direction
Itacolomi
do Itambé Peak
Lobo’s Range
Simulation
Result
(36 min.)
TerraME Advanced:
Non- isotropic spaces
Isotropic neighbourhoods in cell spaces
Von Neumann
Neighborhood
Moore Neighborhood
Neighborhood Definition

Traditional CA
 Isotropic space
 Local neighborhood definition (e.g. Moore)

Real-world
 Anisotropic space
 Action-at-a-distance

TerraME
 Generalized calculation of proximity matrix
Space is anisotropic
Spaces of fixed location and spaces of fluxes in Amazonia
Motivation
Which objects are NEAR each other?
Motivation
Which objects are NEAR each other?
Geographical space is
multidimensional

Spaces of absolute locations


Spaces of relative locations


Determined by cartesian coordinates of
objects
Determined by connectivity properties of
objects
Challenge to GIS applications

Capture spatial relations in absolute and
relative spaces
How do we capture nearness relations?

Traditional spatial analysis
techniques
P2

Operate in absolute space
 Two objects are near if...
 They are close in euclidian
distance OR
 They “touch” each other

Spatial weights matrix

P3
 w11
w
W   21
 w31

 w41
wij  1, if Oi touch O j
Constructed from pairwise
spatial relations
 Example – using “touch”
wij  1, otherwise
w12 w13 w14 
w22 w23 w24 
w32 w33 w34 

w42 w43 w44 
Generalized Proximity Matrix (GPM)


In a cell-space, each cell has a different
neighbourhood
Defined by a NxN matrix
 w11
w
W   21
 w31

w41
w12 w13 w14 
w22 w23 w24 
w32 w33 w34 

w42 w43 w44 
One simple example



Consider a 5x 5 cell-space
For each cell, a different matrix
The neighbours of a cell (the (2,3) cell are):
0
0
1
1
0
0
0
*
1
0
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
Using Generalized Proximity Matrices
Consolidated area
Emergent area
TerraME





O que é TerraME?
Quais os requisitos?
Quais as principais características?
Arquitetura e componentes
Onde obter?
TerraME: quais as principais
características?



Acesso direto a um banco de dados celular espaçotemporal
Espaço pode ser não isotrópico: relações de
vizinhança convencionais e por rede
Conceito de Ambientes aninhados:
 Diferentes comportamentos no espaço e tempo no mesmo
modelo
 Diferentes escalas temporais e espaciais no mesmo
modelo
 Diferentes relações de vizinhança no mesmo modelo
 Multiplas abordagens de modelagem no mesmo modelo:
agentes, automatos celulares, modelos de simulação, etc.
Características: Integração com Banco
de dados geográfico
Espaço celular em ambiente
Terralib/TerraView
fonte: Carneiro (2006)
Características: Relações de proximidade
através de redes
Transamazônica
Forest
Deforested
No data
Non-forest
Water
Br 163
Roads
100 km
Redes físicas ou lógicas: estradas,
linhas de transmissão, comunicão,
mercado
Fontes: Aguiar et al., 2003
Prodes/INPE
São Felix do Xingu
-
Características: Conceito de
Ambiente em TerraME
Cellular space
Um ambiente tem três sub-modelos

Espacial: espaço celular, relações de proximidade
 Comportamental: modelos celulares, autômatos, agentes situados,etc.
 Temporal:
Características: Ambientes podem ser
aninhados
Cada ambiente aninhado
tem seu próprio modelo temporal,
comportamental e espacial
Prodes/INPE 2000-2001
Ambientes aninhados: possibilitam modelos de
comportamento, espaço e tempo heterogêneos
Landsat 1988–96
Agriculture to urban
Agriculture/natural vegetation to water
Natural vegetation/water to urban
Water to agriculture
(K. Seto, Boston U.)
Ambientes aninhados: possibilitam
modelos de comportamento, espaço e
tempo heterogêneos
Ambientes aninhados: possibilitam modelos
de comportamento, espaço e tempo
heterogêneos
Exemplo: múltiplas resoluções espaciais para modelar áreas de pequeno e grandes
2500 m
Carneiro et al., 2004 (Amsterdam LUCC WS)
2.500 m e 500 m
Exemplo de modelo de alocação de desflorestamento
em Rondônia:
resoluções diferentes, variáveis, fatores e relações de
vizinhança
Small farms environments:
1985
500 m resolution
Categorical variable:
deforested or forest
One neighborhood relation:
•connection through roads
Large farm environments:
2500 m resolution
1997
Continuous variable:
% deforested
Two alternative neighborhood
relations:
•connection through roads
• farm limits proximity
Carneiro et al., 2004 (Amsterdam LUCC WS)
1997
Simulation Results
1985 to 1997
Ambientes aninhados: modelagem
multi-escala
Prodes/INPE 2000-2001
TerraME





O que é TerraME?
Quais os requisitos?
Quais as principais características?
Arquitetura e componentes
Onde obter?
TerraME: arquitetura e aplicações
Amazonia
RunoffModel
SãoFelixAgentsModel
TROLLModel
Prata
CLUE
TerraME Language
TerraME Compiler
TerraME Virtual Machine
TerraLib Enviromental
Modeling Framework
C++ Signal
Processing
librarys
TerraLib
fonte: Carneiro (2006)
C++
Mathematical
librarys
C++
Statistical
librarys
TerraME: componentes
TerraME INTERPRETER
• model syntax semantic checking
• model execution
TerraView
• data acquisition
• data visualization
• data management
• data analysis
LUA interpreter
TerraME/LUA interface
model
data
model
TerraME framework
MODEL DATA
Model
source code
fonte: Carneiro (2006)
TerraLib
database
data
Eclipse & LUA plugin
• model description
• model highlight syntax