Home > BE-410

BE-410


Hiroki Sayama

sayama@binghamton.edu 

2nd Annual French Complex Systems Summer School 
Continuous Space, Lattices and Swarms: 
Pattern Formation in Complex Systems 
 
Swarm Models


2  

Collective behavior of swarms 

  • Particle/cell aggregation, fish schools, bird flocks, insect swarms, ped. flows
  • Creates macroscopic behavior out of autonomous individual motion and local kinetic interaction
      • Acceleration
      • Alignment
      • Collision avoidance
      • Attraction to neighbors
  • Modeled using ��agents��
 

© Iain Couzin


3  

Agent-based modeling 

  • One of the most generalized frameworks for modeling/simulation of complex systems
  • You construct many virtual individuals, or ��agents��, and simulate their behaviors explicitly in a computer

4  

Agents 

  • Have internal properties
  • Spatially localized
  • Perceive the environment
  • Locally interact with other agents and behave based on predefined rules
  • No central supervisor
  • May learn autonomously
  • May produce non-trivial ��collective behavior�� as a whole
 

{ {x, y},

gender,

age,

mood, �� }


5  

Implementing agent-based models in Mathematica 

  1. Decide what kind of data format you will use to represent the properties of each agent
  2. Create a population of agents following that format
  3. Write a code to visualize the current states of agents (and any other observation/analysis tools you may need)
  4. Write a code to update the state of each agent based on the assumption of your model

Models with Fixed Number of Agents


7  

Example: Random walk and diffusion 

  • A small random vector                      is added to the location                 of each particle at                      every time step
  • Each particle shows a              Brownian motion
  • The collection of random-walking particles show ��diffusion�� at a macroscopic scale

8  

Exercise 

  • Modify the ��random walk�� simulator code so that:
    • Each particle has its own velocity
    • Each particle is accelerated by the attractive force toward the ��center of mass�� of the population of particles

      This should create a simple  swarming behavior


9  

Example: Diffusion limited aggregation (DLA) 

  • Two types of particles,          ��free�� and ��fixed��; only         free ones can move
  • When colliding into a          fixed one, a free       particle becomes fixed         and loses mobility
  • Starting with only one fixed particle, a complex self-similar pattern emerges (called ��spatial fractal��)

10  

Exercise 

  • Carry out the DLA simulation runs with multiple ��seeds�� randomly positioned in the space
  • Modify the simulator code so that (1) initially no ��fixed�� particles exist, but (2) the particles that touched the bottom edge of the space turn to ��fixed�� 

Models with Agent-Environment Interaction


12  

Example: Garbage collection by ants 

  • Ants are wandering in a space        where lots of garbage pieces            are scattered
  • When an ant finds garbage:
    • If the ant holds nothing, pick up a piece of garbage from there
    • If the ant already holds garbage, drop it off there

13  

Exercise 

  • Modify the ants�� garbage collection model so that:
    • Each ant produces pheromone where it is
    • Pheromone diffuses and evaporates at a constant rate
    • Ants are stochastically attracted toward places where there are greater amount of pheromone

Models with Agent Replacement


15  

Models with birth/death of agents 

  • The updating function determines whether or not each of the current agents can survive to the next step
    • If yes, it will be added to the ��next agent population�� list
    • If no, it will be simply disregarded
  • The updating function also simulates the birth of new agents, which will be added to the list as well

16  

  • Rabbits and foxes wander        and reproduce in a space
    • Foxes move faster than            rabbits
    • A rabbit will survive if it is       not caught by foxes
    • A fox will survive if it ate rabbits not long ago
    • Foxes�� reproduction is possible only when they eat rabbits
 

Example: Predator-prey model


17  

Exercise 

  • Modify the simulator code so that it outputs the time series plots of rabbit and fox populations in addition to the visual image of simulation
  • See if you actually have oscillatory behavior in these plots

18  

Exercise: Evolutionary adaptation 

  • Make the range of motion (motility) a heritable individual property of agents
  • Introduce mutations of the agent motility in both foxes and rabbits
  • See how the agent motilities spontaneously evolve in simulation 

19  

Exercise: Evolutionary adaptation 

  • Make the reproduction of agent density-dependent
    • Too few neighbors / too many neighbors will result in failure of reproduction
  • See how the agent motilities spontaneously evolve in simulation 

 


Pattern Formation in Heterogeneous Particle Swarms: ��Swarm Chemistry��


21  

Models of swarm behavior (1) 

  • Continuous-time dynamical models
    • Suzuki & Sakai (1973), Okubo (1977), Shimoyama et al. (1996), Chuang et al. (2006) etc.
    • Described by ODEs that include terms for
      • Self-propulsion
      • Friction
      • Pairwise kinetic          interaction

22  

Models of swarm behavior (2) 

  • Discrete-time kinematic models
    • Reynolds (1987), Viscek et al. (1995), Couzin et al. (2002), Kunz & Hemelrijk (2003, 2004) etc.
    • Each agent steers to 
      • Approach local center of mass
      • Align with local average velocity
      • Avoid collisions
      • Then add updated velocity to its position

23  

Diversity of swarm behavior 

  • Distinct classes of behaviors
    • Stationary clustering
    • Random swarming
    • Coherent linear motion
    • Amoeba-like structure
    • Milling
    • Dispersal

        etc.

  • Phase transitions between them
 

© Yao Li Chung


24  

A question 

  • Earlier studies were largely focused on homogeneous particle swarms only
    • Some considered small intra-population variations, but not kinetically distinct types
  • What would happen if two or more types of self-propelled particles are mixed together? 

25  

Swarm Chemistry 

  • A novel artificial chemistry research project where artificial swarm populations are used as chemical reactants
 

http://bingweb.binghamton.edu/~sayama/SwarmChemistry/


26  

Model assumptions 

  • Kinematics partly based on Reynolds�� Boids
  • Simple semi-autonomous particles moving in a continuous open 2-D space
    • Well-defined boundary of local perception
    • Kinetic interactions with local neighbors
    • No capability to distinguish different types

27  

Behavioral rules 

  • If no particles are found within local perception range, steer randomly (Straying)
  • Otherwise:
    • Steer to move toward the average position of local neighbors (Cohesion)
    • Steer towards the average velocity of local neighbors (Alignment)
    • Steer to avoid collision with neighbors (Separation)
    • Steer randomly with a given probability (Randomness)
  • Approximate its speed to its normal speed (Self-propulsion)

28  

Kinetic parameters 

    (Assigned to each particle individually)

29  

Behavior of homogeneous swarms 

  • Basic behavior of our model is similar to that of earlier models when a population is homogeneous
 

Stationary clustering 

Coherent linear motion 

Amoeba-like structure 

Dispersal 

[simulation]


30  

Dependence on kinetic parameters 

  • A couple of distinct phase transitions observed
  • Not-so-significant dependence on c3
 

c1: strength of cohesion 

c2: strength of alignment 
 

c1: strength of cohesion 

c1: strength of cohesion 

c2: strength of alignment 
 

c2: strength of alignment 
 

<|v|> : av. absolute vel. 

<r>: av. distance from CoM 

(Results with c3 ~ 50 �� 5) 

<v>: average velocity 

Coherent linear motion 

Random swarming 

Oscill-

ation 

Dispersal


31  

Exploring pairwise interactions 

  • Monte Carlo simulations (> 50,000 runs)
  • Fixed parameters:
    • N=300, R=200, Vn=10, Vm=40, c4=0, c5=0.5
  • Varied parameters:
    • c1, c2, c3 (cohesion, alignment, separation)
    • Two types (A, B) of particles randomly created; simulate each in isolation as well as in mixture
  • Initial conditions:
    • Randomly positioned and oriented in a 300x300 space
  • Quantities measured after 200 time steps:
    • Average linear/angular velocities, average distance from center of mass, local homogeneity
 

[simulation]


32  

Local homogeneity 

  • Measured by averaging over all particles the probability of the same type of particles within 6 nearest neighbors
 

Local homogeneity for this particle = 4/6 = 0.67 

H ~ 1.0 Separated 

H ~ 0.5 Well mixed


33  

Spontaneous separation 

  • Commonly seen in heterogeneous swarms
  • Often creates multilayer structures
 

(results with 4 types)


34  

Spontaneous separation 

  • Blending is possible if two types share the same cohesion-separation ratio (c1/c3)
 

(c1 / c3)A – (c1 / c3)B 

Local homogeneity H 

  • Alignment (c2) doesn��t play much role
  • Ratio c1/c3 determines pairwise equilibrium distance: req = (c1/c3)–1/2            (if c2 is ignored)

      Spontaneous separation is caused by the difference of ��personal space��


35  

Emergent motion 

  • Mixing two types may generate new behavior not present in either of them
 

Linear motion 

Rotation 

Oscillation


36  

Interactions between >2 types? 

  • Possibility space explodes exponentially with # of types involved
    • Exhaustive parameter sweep not feasible
    • Monte Carlo may not give enough resolution
  • It is no longer clear what kind of quantities should be measured to characterize resulting patterns
    • We don��t know what to expect

37  

Interactive evolutionary method 

  • An alternative, more exploratory approach
  • Heterogeneous swarms are represented by lists of multiple parameter sets (recipes) which are evolved over many iterations
  • A human participates in       evolutionary processes of         swarms by subjectively       selecting and varying             their recipes

38  

Recipe 

  • A list of kinetic parameter sets of different types in a swarm
    • Format: # of particles * (R, Vn, Vm, c1, c2, c3, c4, c5)
    • Each row represents one type
 
 

97 * (226.76, 3.11, 9.61, 0.15, 0.88, 43.35, 0.44, 1.0)

38 * (57.47, 9.99, 35.18, 0.15, 0.37, 30.96, 0.05, 0.31)

56 * (15.25, 13.58, 3.82, 0.3, 0.8, 39.51, 0.43, 0.65)

31 * (113.21, 18.25, 38.21, 0.62, 0.46, 15.78, 0.49, 0.61)


[simulation]


40  

Evolutionary operators (1) 
 

  • Perturbation to relative frequencies of different parameter sets within a recipe
  • Mixing of two swarms physically 

41  

Evolutionary operators (2) 

  • Duplication of parameter sets
  • Deletion of parameter sets 
  • Insertion of new parameter sets 
  • Point mutation of parameter values 

 


42  

Complex structures/behaviors 

  • More complex structures/behaviors possible by mixing several types of swarms

43  

Summary 

  • Many physical/biological/ecological systems can be modeled as swarms using agent-based modeling
    • Can include local interaction, heterogeneity, interaction with environment, birth/death of agents, etc.
  • Heterogeneous swarms may self-organize and robustly produce complex patterns (structures and behaviors)
Search more related documents:BE-410
Download Document:BE-410

Recent Documents:

Set Home | Add to Favorites

All Rights Reserved Powered by Free Document Search and Download

Copyright © 2011
This site does not host pdf,doc,ppt,xls,rtf,txt files all document are the property of their respective owners. complaint#nuokui.com
TOP