SAPERE
Self-aware Pervasive Service Ecosystems
From Engineer to Alchemist, There and Back Again: An
Alchemist Tale
Danilo Pianini – [email protected]
Alma Mater Studiorum—Università di Bologna
Cesena, May 24th, 2013
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
1 / 46
Outline
1
Simulation
Definitions
Models
When it’s useful?
2
Alchemist
SAPERE background
Computational model
Engine and architecture
Case studies
Performance
3
Development
Development model
Contributors
Future activities
Danilo Pianini (UniBo)
Do or do not, there is no try.
An Alchemist Tale
Cesena, May 24th, 2013
2 / 46
Simulation
Simulation
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
3 / 46
Simulation
Definitions
Scientific Method
Traditional science workflow [Parisi, 2001]
Traditional scientific method
identification
direct observation
theories / hypothesis
empirical observation
quantitative analysis
validation / invalidation
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
4 / 46
Simulation
Definitions
Definition of Simulation
A new way for describing scientific theories
[Parisi, 2001]
Simulation is the process with which we can study the dynamic
evolution of a model system, usually through computational tools
[Banks, 1999]
Simulation is the imitation of the operation of a real-world process or
system over time
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
5 / 46
Simulation
Models
Simulation Requires a Model
M. Minsky – Models, Minds, Machines
A model (M) for a system (S), and an experiment (E) is anything to which
E can be applied in order to answer questions about S.
Representation / abstraction
Formalisation
Aggregation, Simplification, Omission
Building a model...
How complex should be the model?
Which assumptions should be done?
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
6 / 46
Simulation
Models
From Model to Simulation. . .
Computer simulation
Models are designed runnable processes
Simulation creates a virtual laboratory
controlled conditions
it’s easy to modify the experiment (variables, parameters, etc.)
Simulations imitate the operations of the modelled process
generation of an artificial evolution of the system
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
7 / 46
Simulation
Models
. . . and Back
Deductions on the real system represented
Evaluation of theories about the model
Model validation [Klugl and Norling, 2006]
if the data is reliable;
if prediction doesn’t match the observed behaviour do not match
⇒ the model must be revised
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
8 / 46
Simulation
When it’s useful?
Why do we Need Simulations?
[Parisi, 2001, Klugl and Norling, 2006]
The real system cannot actually be observed
The time scale of the real system is too small or too large for
observation
The original system doesn’t yet exist (or not anymore)
The system is too complex
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
9 / 46
Alchemist
Alchemist
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
10 / 46
Alchemist
SAPERE background
The SAPERE Project
http://www.sapere-project.eu/
SAPERE (Self-aware Pervasive Service Ecosystems) is an EU STREP
project under the FP7 FET Proactive Initiative: Self-Awareness in
Autonomic Systems (AWARENESS)
The objective of SAPERE is the development of a highly-innovative
theoretical and practical framework for the decentralized deployment
and execution of self-aware and adaptive services for future and
emerging pervasive network scenarios
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
11 / 46
Alchemist
SAPERE background
SAPERE World
SAPERE Node
eco-law
Engine
Software services
LSA Space
LSA
SAPERE
Node
SAPERE
Node
LSA
LSA
SAPERE
Node
LSA
eco-law activation
SAPERE
Node
SAPERE
Node
SAPERE
Node
SAPERE
Node
SAPERE
Node
Danilo Pianini (UniBo)
SAPERE
Node
An Alchemist Tale
SAPERE
Node
Cesena, May 24th, 2013
12 / 46
Alchemist
SAPERE background
Simulation of a SAPERE environment
The role of simulation
Emergence cannot be fully designed
It’s crazy to deploy a whole ecosystem without any test
Fist class abstractions
Dynamic environment
Different, mobile, communicating nodes
Programmability through a set of chemical-like laws
Continuous Time Markov Chain (CTMC) model
Autonomous agents
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
13 / 46
Alchemist
SAPERE background
Two approaches
Classic ABM modelling
High flexibility
Topology as first-class abstraction
Dynamics explicitly modelled
No native support for CTMC model
Chemical inspired modelling
Natively CTMC
Very fast and reliable algorithms exist in literature
Very limited topology: multicompartment at best
Only classic reactions can change the world status: limited flexibility
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
14 / 46
Alchemist
Computational model
Alchemist simulation approach
Base idea
Start from the existing work with stochastic chemical systems
simulation
Extend it as needed to reach desired flexibility
Goals
Full support for Continuous Time Markov Chains (CTMC)
Support for differently distributed events (e.g. Triggers)
Rich environments, with obstacles, mobile nodes, etc.
More expressive reactions
Fast and flexible SSA engine
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
15 / 46
Alchemist
Computational model
Enriching the environment description
Reactions
Environment
Molecules
Node
Alchemist world
The Environment contains and links together Nodes
Each Node is programmed with a set of Reactions
Nodes contain Molecules
Each Molecule in a node is described with a Concentration
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
16 / 46
Alchemist
Computational model
Extending the concept of reaction
From a set of reactants that combine themselves in a set of products to:
Reaction
Conditions
Actions
Probability distribution
Change
concentration
of something
Node
contains
something
Number of
neighbors<3
Rate equation: how conditions
influence the execution speed
Move a node
towards...
Any other
condition
about this
environment
Any other
action
on this
environment
In Alchemist, every event is an occurrence of a Reaction
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
17 / 46
Alchemist
Engine and architecture
SSA Algorithms
Several SSA exist, they follow the same base schema [Gillespie, 1977]:
1
Select next reaction using markovian rates
2
Execute it
3
Update the rates which may have changed
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
18 / 46
Alchemist
Engine and architecture
Do the math: reaction speed
Consider a chemical reaction in the form:
µ
A+B −
→C
The probability that this reaction will trigger depends on:
1
Number of molecules A and B: the higher, the higher the probability
those molecule will encounter and react
2
µ, a speed coefficient for the reaction
We define the propensity of a reaction as its speed in a precise instant of
time as
aµ = µ[A][B]
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
19 / 46
Alchemist
Engine and architecture
Do the math: next reaction choice
If we assume every reaction is a Poisson process, the probability for it to
be the next one is:
Z ∞
Z ∞
P
aµ
P(next = µ) =
P(µ, τ )dτ =
aµ e −τ j aj dτ = P
0
0
j aj
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
20 / 46
Alchemist
Engine and architecture
Do the math: next reaction time
We can also compute the next time of occurrence:


P
X
X
P(τ )dτ =
P(µ, τ )dτ = 
aj  e −τ j aj dτ
j
j
X
aj = λ −→ λe −λx
j
Z
t
F (x ≤ t) =
h
it
λe −λx dx = −e −λt
−∞
−∞
= e −λt
Now, given a uniformly distributed random r , it’s possible to compute it’s
equivalent for the desired distribution:
e −λt = r ⇒ t =
Danilo Pianini (UniBo)
− ln (r )
λ
An Alchemist Tale
Cesena, May 24th, 2013
21 / 46
Alchemist
Engine and architecture
Existing algorithms
Direct method
1 Compute propensity for each reaction
2
Select next reaction probabilistically
3
Execute it
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
22 / 46
Alchemist
Engine and architecture
Existing algorithms
A+B→C
B+C→D
E+G→A
D+E→E+F
F→D+G
Direct method + Dependency graph
1
Compute the dependencies among reactions
2
Compute propensity for each reaction
3
Select next reaction probabilistically
4
Execute it
5
Update propensities only for potentially involved reactions
6
Goto 3
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
23 / 46
Alchemist
Engine and architecture
Existing algorithms
Next Reaction
1 Compute a putative execution time for each reaction
2
Store reactions in a binary heap
3
Pick the next reaction
4
Execute it
5
Compute putative times only for potentially involved reactions
6
Goto 3
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
24 / 46
Alchemist
Engine and architecture
Existing algorithms
[Slepoy et al., 2008]
1
Compute propensities
2
Split the reactions in groups by their propensity
3
Throw randoms until a reaction in a group is selected
4
Execute it
5
Update propensities only for potentially involved reactions
6
Goto 3
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
25 / 46
Alchemist
Engine and architecture
More flexibility!
What they miss is what we added
Support for instantaneus events (∞ Markovian rate)
Reactions can be added and removed during the simulation
Support for non-exponential time distributed events (e.g. triggers)
Dependencies among reactions are evaluated considering their
“context”, speeding up the update phase
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
26 / 46
Alchemist
Engine and architecture
Smart data structures ⇒ bleeding edge performances
2.0
4
4
A+B→C
7.3
3.7
2
2
1
5.5
0
0
0
0
E+G→A
D+E→E+F
F→D+G
0
inf
10.1
0
0
1
0
B+C→D
9.1
8.9
4.2
0
1
1
0
Next Reaction efficient structures made dynamic
Dynamic Indexed Priority Queue
Allow to access the next reaction to execute in O(1) time
Worst case update in log2 (N) (average case a lot better)
Extended to ensure balancing with insertion and removal
Dynamic Dependency Graph
Allows to smartly update only a subset of all the reaction
Extended with the concept of input and output context
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
27 / 46
Alchemist
Engine and architecture
Modular structure
User Interface
Reporting System
Core Engine
Interactive UI
Reaction Manager
Alchemist language
Simulation Flow
Environment
Language Parser
Environment Instantiator
Dependency Graph
XML Bytecode
Incarnation-specific language
Application-specific Alchemist Bytecode Compiler
Environment description in application-specific language
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
28 / 46
Alchemist
Engine and architecture
Some Features in short
Parallel executor
Approximate Stochastic Model Checker
Parallelised engine
Alchemist2Blender
PVeStA integration
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
29 / 46
Alchemist
Case studies
Crowd evacuation
EXIT 1
EXIT 2
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
30 / 46
Alchemist
Case studies
Crowd steering
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
31 / 46
Alchemist
Case studies
Adaptive Displays
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
32 / 46
Alchemist
Case studies
Simple Morphogenesis proof of concept
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
33 / 46
Alchemist
Case studies
Morphogenesis of a Drosophila Melanogaster
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
34 / 46
Alchemist
Case studies
Anticipative adaptation
'datald.log' using 2:3:4
60
50
60
40
50
30
20
40
10
30
0
20
45
10
40
35
0
30
0
5
25
10
Danilo Pianini (UniBo)
15
20
20
25
15
30
10
35
40
5
45
An Alchemist Tale
0
Cesena, May 24th, 2013
35 / 46
Alchemist
Case studies
Realistic pedestrians
see the video...
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
36 / 46
Alchemist
Performance
Testbed
We realised the same crowd-steering application for both Alchemist
and RePast, in order to evaluate the performance gap (if any)
Source code for RePast and standalone Alchemist application
available at
http://www.apice.unibo.it/xwiki/bin/view/Alchemist/JOS
We choose a simplified use case which allows simulation in RePast
without any change in its engine
This actually cripples out the most important Alchemist optimization
for complex environment (the dependency graph)
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
37 / 46
Alchemist
Performance
Results
Performance comparison with Repast
500
450
Execution time [s]
400
350
300
250
200
150
100
50
0
50
100
150
200
250
300
350
400
450
500
Number of agents
Repast
Danilo Pianini (UniBo)
Alchemist
An Alchemist Tale
Cesena, May 24th, 2013
38 / 46
Development
Development
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
39 / 46
Development
Development model
Distributed development
Alchemist is a training ground for some good team development practices
Linux kernel-like development model
Java
XText
Mercurial DCVS
Bitbucket web-based code hosting
Maven
JUnit
Source is released under GPL
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
40 / 46
Development
Contributors
People involved
Michele Bombardi (Done)
Realistic pedestrians
Chiara Casalboni (Done)
Realistic pedestrians
Francesca Cioffi (Done)
Further experiments with Alchemist-SAPERE
Davide Ensini (Done)
Approximate Stochastic Model Checker improvement
Enrico Galassi (Done)
Alchemist-SAPERE high level language
Enrico Gualandi (Ongoing)
Alchemist-SAPERE languages review
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
41 / 46
Development
Contributors
People involved
Luca Mella (Done)
Tools for social network analysis
Alessandro Montalti (Done)
MS-BioNet to AlchemistXML translator
Luca Nenni (Done)
Alchemist2Blender
Enrico Polverelli (Done)
Gradient based patterns
Michele Pratiffi (Done)
Image importer for Alchemist
Giacomo Pronti (Done)
SAPERE incarnation main author
Luca Ricci (Ongoing)
Map importer for Alchemist
Andrea Vandin (IMT Lucca)
PVeStA integration
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
42 / 46
Development
Future activities
There is a lot of work to do!
MS-Bionet compatibility layer
AlcheGRID
Alchemist2Blender improvement
OpenStreet Map importer and Google Map importer
Blender Integration improvement
Gnuplot integration
CellML / SBML to AlchemistXML
Chemistry Incarnation review
Alchemist for Bio DSL
Realistic biological gradients
GPX tracks loader
RDF to Alchemist-SAPERE translator
These are examples, if you have something in mind, be proactive!
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
43 / 46
Development
Future activities
Bibliography I
Banks, J. (1999).
Introduction to simulation.
In Farrington, P., Nembhard, H. B., Sturrock, D. T., and Evans,
G. W., editors, Proceedings of the 1999 Winter Simulation
Conference, pages 7–13.
Gillespie, D. T. (1977).
Exact stochastic simulation of coupled chemical reactions.
Journal of Physical Chemistry, 81(25):2340–2361.
Klugl, F. and Norling, E. (2006).
Agent-based simulation: Social science simulation and beyond.
Technical report, The Eighth European Agent Systems Summer
School (EASSS 2006), Annecy.
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
44 / 46
Development
Future activities
Bibliography II
Parisi, D. (2001).
Simulazioni - La realtà rifatta al computer.
Società editrice il Mulino.
Slepoy, A., Thompson, A. P., and Plimpton, S. J. (2008).
A constant-time kinetic Monte Carlo algorithm for simulation of large
biochemical reaction networks.
The Journal of Chemical Physics, 128(20):205101+.
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
45 / 46
SAPERE
Self-aware Pervasive Service Ecosystems
From Engineer to Alchemist, There and Back Again: An
Alchemist Tale
Danilo Pianini – [email protected]
Alma Mater Studiorum—Università di Bologna
Cesena, May 24th, 2013
Danilo Pianini (UniBo)
An Alchemist Tale
Cesena, May 24th, 2013
46 / 46