F rank Sch w eitzer: Aktiv e Bro wnsche T eilchen: ein ph ysik

Aktive Brownsche Teilchen:
ein physikalisches Multi-Agenten-System
zur Modellierung interaktiver
Strukturbildung
Frank Schweitzer
http://summa.physik.hu-berlin.de/∼frank/
Institut für Physik der Humboldt-Universität zu Berlin
GMD Institut für Autonome intelligente Systeme - AiS, St. Augustin
Gliederung
1. Multi-Agenten-Systeme
2. Modell Aktiver Brownscher Teilchen
3. Aktive Brownsche Teilchen mit Energiedepot
4. Strukturbildung mit Aktiven Brownschen Teilchen
(1) Biologische Aggregation
(2) Simulation von Wegenetzen von Ameisen
5. Zusammenfassung
Slide 1
$
%
'
&
Universität Oldenburg, 6. Juli 1999
Complex Systems
Slide 2
New England Complex Systems Institute
“Complex systems are systems with multiple interacting
components whose behavior cannot be simply inferred from
the behavior of the components.
The study of complex systems spans all scales, from particle
fields to the universe. Among the most complex systems with
which we are familiar are biological and social systems –
including biological macromolecules, biological organisms,
ecosystems, and human social and economic structures.”
Journal “Advances in Complex Systems”
“By complex system, it is meant a system comprised of a
(usually large) number of (usually strongly) interacting
entities, processes, or agents, the understanding of which
requires the development, or the use of, new scientific tools,
nonlinear models, out-of equilibrium descriptions and
computer simulations.”
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
$
%
1
agent:
Multi-Agent Systems (MAS)
• subunit with “intermediate” complexity
⇒ may represent local processes, individuals, species,
agglomerates, components, ...
• large number / different types of agents
multi-agent system:
• interactions between agents:
– on different spatial and temporal scales
– local / direct interaction
– global / indirect interactions (coupling via resources)
• “bottom-up approach”: no universal equations
⇒ self-organization, emergence of system properties
• external influences (boundary conditions, in/outflux)
⇒ coevolution, circular causality
• possibly simplest set of rules ⇒ “sufficient” complexity
minimalistic agent:
• cooperative interaction instead of autonomous action
• no deliberative actions, no specialization, no internal memory
Slide 3
$
%
'
&
Universität Oldenburg, 6. Juli 1999
Active Brownian Particles
Slide 4
• external eigendynamics of the field
• interaction between particles via multicomponent field
• consideration of energetic aspects
• complete stochastic dynamics, based on Langevin equations
• particle-based approach to structure formation
advantages:
2. discrete internal states: θi(t)
– generation of different components of a self-consistent field
– sensitivity to different field components
→ non-linear feedback ⇒ interactive structure formation
on the macroscopic level
1. internal energy depot: ei(t)
– take-up, storage, conversion of internal energy
→ pumped Brownian particles, Brownian motors
internal degrees of freedom:
“Active Brownian particles are Brownian particles with
internal degrees of freedom. They have the ability to take up
energy from the environment, to store it in an internal depot
and to convert internal energy to perform different activities,
such as metabolism, motion, change of the environment, or
signal-response behavior.”
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
$
%
2
Α
10
Α
10
Ω
20
Ω
20
30
30
x
x
Observation of Brownian Motion
y
30
20
10
0
y
30
20
10
0
The position of the Brownian particle (radius 0.4 µm) is documented on a millimeter
grid in time intervals t0 = 30 seconds.
Slide 5
$
%
'
&
Universität Oldenburg, 6. Juli 1999
Equations for Brownian Particles
Slide 6
ξ(t): white noise, ξi(t) ξ j (t0 ) = δij δ(t − t0 ).
• overdamped limit: dv i/dt = 0, or γ0 → ∞
dri √
kB T
ε
= 2 Dn ξ(t) ; Dn =
=
dt
γ0
γ0
Dn: spatial diffusion coefficient of the particles
fluctuation-dissipation theorem: S = kB T γ0
hF stoch (t)i = 0 ; hF stoch (t) F stoch (t0 )i = 2S δ(t − t0)
F stoch: stochastic force
• stochastic approach ⇒ Langevin equation:
dv i
dri
= vi ; m
= −γ0v i + F stoch
dt
dt
γ0: friction coefficient of motion
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
$
%
3
Brownian Particle with Internal Energy Depot
Depot e(t) ⇒ internal storage of energy
d
dt e(t) = q(r) − c e(t) − d(v) e(t)
q(r): gain ⇒ space-dependent take-up of energy
c: loss ⇒ internal dissipation
d(v): conversion of internal into kinetic energy
simple ansatz: d(v) = d2v2; d2 > 0
Stochastic equation for Brownian particles with energy depot
mv̇ + γ0v + ∇U (r) = d2e(t)v + F (t)
Slide 7
$
%
'
&
⇒
8.0
γ0
zero: v02 =
dissipation
6.0
q0
c
−
γ0 d2
Universität Oldenburg, 6. Juli 1999
Non-linear Friction Function
γ(v) = γ0 − d2 e(t)
v
4.0
d(v) = d2v2 ;
q0
c + d2 v 2
q 0 d2
c + d2 v 2
2.0
γ0−(d2q0/c)
pumping
γ(v) = γ0 −
e0 =
assumptions: q(r) ≡ q0 ;
⇒
2.0
0.0
−2.0
−4.0
−6.0
0.0
Slide 8
ė(t) = 0
v̇ + γ0v + ∇U (r) = d2e(t)v + F (t)
d
e(t) = q(r) − c e(t) − d(v) e(t)
dt
equations of motion:
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
γ(v)
$
%
4
0.0
−1.0
−2.0
σ = 1 − dc γq0
2 0
x1
1.0
2.0
σ > 0 only if: q0 > q0crit =
• v approximated by the stationary velocity:
q0
c
−
v02 = v12 + v22 =
γ0 d2
⇒
Slide 9
γ0 c
d2
• efficiency ratio:
dEout/dt d2 e v2
=
σ=
dEin /dt
q0
q0
• energy depot in quasi-stationary equilibrium: e =
c + d2 v 2
−1.0
Critical Supply of Energy
0.0
−1.0
−2.0
−2.0
assumption: motion in two dimensions
a
U (x1 , x2) = (x12 + x22)
2
q(x1 , x2) = q0
2.0
2.0
1.0
q0 = 0.0: simple Brownian motion;
q0 = 1.0: motion on a stochastic limit cycle
x1
1.0
0.0
2.0
−1.0
1.0
−2.0
x2
Brownian particle as micro–motor:
0.0
$
%
'
&
2.0
0.0
−2.0
100
−2.0
Universität Oldenburg, 6. Juli 1999
Localized Energy Sources



200
t
x1
0.0
q(x1 , x2) = 

4.0
3.0
2.0
1.0
2.0
0.0
2.0
−2.0
0.0
−2.0
0
Slide 10
300
2.0
• increase in d2 abridges
the cycle ⇒ directed
motion more susceptible
to become Brownian
motion
• new cycles start with a
burst of energy
• intermittent type of
motion
⇒ oscillatory movement
with fixed direction
• motion into the energy
area becomes accelerated
• parabolic potential: U (x1 , x2) = a2 (x12 + x22)
• take-up of energy in a restricted area:
h
i
q0 if (x1 − b1)2 + (x2 − b2)2 ≤ R2
0 else
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
x2
e
x2
x1
x2
$
%
5
Active Brownian Particles Responding to a Field
active particles:
• characterized by an internal degree of freedom: θi(t),
which can be changed:
w(θi0 |θi)
• Langevin equation:
√
dr
∂he(r, t)
dv
i
i
= vi ;
= −γv i + αi
+ 2 εi γ ξ i(t)
dt
dt
∂r ri
overdamped limit:
v
u
u
α ∂he(r, t)
dr
i
i
u 2εi
+t
=
ξ (t)
dt
γ
∂r ri
γ i
he(r, t): effective field
• “individual” parameters (may depend on θi) :
αi: individual response to the field
– attraction: αi > 0, or repulsion: αi < 0
– threshold h0: αi = Θ[he(r, t) − h0], Θ[y] = 1, if y > 0
– internal value θ: αi = δ(θi − θ)
εi: individual intensity of noise
– measure of the sensitivity si of the particle: si ∝ 1/εi.
Slide 11
$
%
'
&
Universität Oldenburg, 6. Juli 1999
Effective Field
N
X
i=1
qi(θi , t) δ(θ − θi(t)) δ(r − ri(t))
Slide 12
spatio-temporal evolution of the field, hθ (r, t):
(i) decay with rate kθ
(ii) diffusion (coefficient Dθ )
(iii) production with individual rate qi(θi , t)
+
• particles with internal parameter θ generate a field hθ (r, t)
which obeys a reaction-diffusion equation:
dhθ (r, t)
= −kθ hθ (r, t) + Dθ ∆hθ (r, t)
dt
∇he(r, t) = ∇he( . . . , hθ(r, t), hθ0 (r, t), . . . )
• effective field: a specific function of the different field
components hθ (r, t):
• Langevin eq.: particles respond to the gradient of he(r, t)
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
$
%
6
Complete Dynamics for N Active Particles
• N active Brownian particles:
internal parameters θ1, ..., θN ; positions r 1, ...., rN
canonical N -particle distribution function:
P (r, θ, t) = P (r 1, θ1, . . . , rN , θN , t)
• changes:
(i) movement: ri → ri0
(ii) transition: θi → θi0 with probability w(θi0 |θi)
N
X
X
{w(θi|θi0 )P (θi0 , θ?, r, t)
• multivariate master equation:
limit of strong damping: γ0 → ∞, and αi = α, εi = ε:
N
∂
X
P (r, θ, t) = − {∇i ((α/γ0) ∇ihe(r, t) P (θ, r, t))
∂t
i=1
−Dn ∆iP (r, θ, t)}
+
i=1 θi0 6=θi
−w(θi0 |θi)P (θi , θ?, r, t)}
• dynamics of the effective field he(r, t)
Slide 13
$
%
'
&
C
$
%
δ(r − ri(t))
Universität Oldenburg, 6. Juli 1999
i=1
N
X
h(r,t)
Examples of Circular Causation
generates
influences
Slide 14
• track formation:
bacteria, pedestrians mark their track, which can be reinforced
by other individuals (ususally D0 = 0)
• biological aggregation:
cells, slime mold amoebae, myxobacteria generate a chemical
field to communicate
applications:
∇i he(r, t) = ∇i h(r, t)
dh(r, t)
= −k0 h(r, t) + D0 ∆hθ (r, t) + q0
dt
• one-component field:
• active particles are identical ⇒ no transitions
αi = α > 0, εi = ε, θi = 0, qi(θi, t) = q0 = const.
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
7
(d)
(c)
Aggregation of Larvae
(a)
(b)
Aggregation of larvae of the bark beetle Dendroctonus micans.
Total population 80 larvae, density 0.166 larvae/cm 2 .
Time in minutes: (a) t = 0, (b) t = 5, (c) t = 10, (d) t = 20.
Deneubourg, J. L.; Gregoire, J. C.; Le Fort, E.: Kinetics of Larval Gregarious Behavior
in the Bark Beetle Dendroctonus micans (Coleoptera: Scolytidae), J. Insect Behavior
3/2, 169-182 (1990)
Slide 15
$
%
'
&
Universität Oldenburg, 6. Juli 1999
(b)
(a)
(f)
(e)
(d)
Aggregation of Active Brownian Particles
(c)
Position of 100 active Brownian particles moving on a triangular
lattice (size: A = 100 × 100).
Time in simulation steps: (a) t = 100, (b) t = 1.000, (c) t = 5.000,
(d) t = 10.000, (e) t = 25.000, (f) t = 50.000.
Slide 16
Schweitzer, F.; Schimansky-Geier, L.: Clustering of Active Walkers in a Two-Component
System, Physica A 206, (1994) 359-379
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
$
%
8
(f)
(e)
(d)
Evolution of the Self-Consistent Field
(a)
(b)
(c)
Time in simulation steps. (left side) Growth regime: (a) t = 10, (b) t = 100,
(c) t = 1.000, (right side) Competition regime: (d) t = 1.000, (e) t = 5.000,
(f) t = 50.000. The scale of the right side is 10 times the scale of the left side.
Hence, Fig. (d) is the same as Fig. (c).
Schweitzer, F.; Schimansky-Geier, L.: Clustering of Active Walkers in a Two-Component
System, Physica A 206, (1994) 359-379
Slide 17
$
%
'
&
Universität Oldenburg, 6. Juli 1999
generates
influences
h-1(r,t)
h+1(r,t)
influences
generates
C+1
Examples of Circular Causation
C-1
applications:
• exploitation of food sources:
ants mark trails from food sources to the nest with additional
chemicals to guide nestmates to resources
• self-assembling of networks:
particles responding to two different fields, link nodes with
opposite potential
Slide 18
$
%
• state dependent production rate
θi
qi(θi, t) = [(1 + θi) qi (+1, t) − (1 − θi) qi(−1, t)−1]
2
• two-component field
θi
∇i he(r, t) =
[(1 + θi) ∇i h−1(r, t) − (1 − θi) ∇i h+1(r, t)]
2
N
dhθ (r, t)
X
= −kθ hθ (r, t) + qi(θi, t) δ(θ − θi(t)) δ(r − ri(t))
dt
i=1
• active particles with two different states θ ∈ {−1, +1},
transitions possible
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
9
Slide 19
Hölldobler, B. and Möglich, M.: The foraging system of Pheidole militicida (Hymenoptera:
Formicidae), Insectes Sociaux 27/3 (1980) 237-264
Schematic representation of the complete foraging route of Pheidole milicida, a harvesting ant of the southwestern U.S. deserts.
Each day tens of thousands of workers move out to the dendritic
trail system, disperse singly, and forage for food.
Foraging Route of Ants (Pheidole milicida)
$
%
'
&
Universität Oldenburg, 6. Juli 1999
b
a
f
e
d
Slide 20
Schweitzer, F.; Lao, K.; Family, F.: Active Random Walkers Simulate Trunk Trail Formation
by Ants, BioSystems 41 (1997) 153-166
Formation of trails from a nest (middle) to a line of food at the top and
the bottom of a lattice. (a-c) show the distribution of chemical component
(+1), and (d-f) show the distribution of chemical component (−1). Time in
simulation steps: (a), (d) t = 1.000, (b), (e) t = 5.000, (c), (f) t = 10.000.
c
Trunk Trail Formation to Extended Forage Areas
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
$
%
10
d
c
Trunk Trail Formation to Separate Food Items
a
b
Formation of trails from a nest (middle) to five randomly placed
food clusters. The distribution of chemical component (−1) is
shown after (a) 2000, (b) 4000, (c) 8500, and (d) 15000 simulation
time steps, respectively.
Schweitzer, F.; Lao, K.; Family, F.: Active Random Walkers Simulate Trunk Trail
Formation by Ants, BioSystems 41 (1997) 153-166
Slide 21
$
%
'
&
Universität Oldenburg, 6. Juli 1999
t = 50
Formation of Networks
t = 10
t = 200
t = 10.000
t = 100
t = 1.000
Slide 22
Time series of the evolution of a network (time in simulation steps). Lattice size
100 × 100, 5.000 particles, 40 nodes, z+ = 20, z− = 20. Parameters: q0 = 10.000,
kh = 0.03, β = 0.2.
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
&
$
%
11
$
%
'
&
Universität Oldenburg, 6. Juli 1999
Self-Organization
Slide 24
SFB 230 “Natural Constructions”, Stuttgart, 1984 - 1995
Self-organization is defined as spontaneous formation,
evolution and differentiation of complex order structures
forming in non-linear dynamic systems by way of feedback
mechanisms involving the elements of the systems, when
these systems have passed a critical distance from the statical
equilibrium as a result of the influx of unspecific energy,
matter or information.
Physico-Chemical and Life Sciences, EU Report 16546 (1995)
Biebricher, C. K.; Nicolis, G.; Schuster, P.: Self-Organization in the
Self-organization is the process by which individual subunits
achieve, through their cooperative interactions, states
characterized by new, emergent properties transcending the
properties of their constitutive parts.
Frank Schweitzer: Aktive Brownsche Teilchen: ein physikalisches Multi-Agenten-System
'
Conclusions
• particle-based model for interactive structure formation
1. Model of Active Brownian Particles:
• relation to biology:
(a) energy consumption for metabolism and motion
(b) interaction with the environment due to a self-consistent
multicomponent field ⇒ non-linear feedback
2. Conversion of Brownian Motion into Directed Motion:
(a) quasiperiodic movement of the particles between energy
sources and “home”
Slide 23
• applicable to systems where only small particle numbers
govern the system dynamics
• efficient and stable simulation algorithm: instead of integrating
PDE ⇒ simulation of the Langevin equation
• stochastic approach to directed movement and structure
formation
3. Advantage of the Active Brownian Particles Model:
(c) chemotactic response to a self-consistent chemical field
two-component field ⇒ directed forward / backward motion
(b) directed movement in a asymetric periodic potential
⇒ direction depends on conversion parameter d2 and noise D
&
$
%
12