The Swarm

Presentation

Lecture on 25.10.2007

A “flock” is a group of animals that move together in a more or less cohesive group. Although the behavior appears to be very complex, it is probably very simple and emerges from a few simple rules followed by each individual.

• Flock of starlings avoiding a predator
• A large flock of birds flying together

Craig Reynold developed a computer model of flocking behavior in 1986, which was later used in Hollywood in such films as Batman Returns. In his model, individuals follow the following three rules:

• Separation: steer to avoid crowding neighbors and to avoid predators
• Alignment: steer toward the average direction of neighbors
• Cohesion: steer towards the average position of the flock

Particle Swarm Optimization (PSO) is a continuous-value optimization algorithm that attempts to find the local minimum in the solution space by emulating flocking behavior. A population of candidate solutions “flies” around the solution space, at each time step steering towards its own personal best as well as the group personal best.

# Randomly generate population P with random positions and velocity vectors
# For each individual x from P,
  # Update velocity randomly towards Max-x and Max-group
  # Apply velocity vector to location
  # If f(x) is better than Max-x or Max-group, update them accordingly
# Goto 2

PSO Implementation by Kennon Ballou et al

What kinds of human flocking behavior do you see in real life? How are they like/unlike birds?

A very good example for human flocking behavoir you can see in the main field of a bicycle race. Each of the competitors keeps distance and pace to the guys arround him to have enough space for his own. This is the same like birds in a swarm.

(add some more answers)

Think of the ant, and don’t be lazy. Learn from the ant, and so be wise. It has no king, no general and no ruler.
Without any leadership, ants store food in the summer, and collect the harvest.
Proverbs 6:6-8

• provide 15-25% of the world’s biomass
• Very diverse - ~15,000 species; many species have radically different behaviors
• Communicate mostly via pheromones

• Great podcast with Deborah Gordon about ants and economics
• Brazilian Ants affecting their environment
• How the colony handles parasites and ill ants in their nest

Ants live in large colonies with millions of members not organised by a single ant. Colonies can live up to 30 years while single ants just live 30 days. Excapt of the queen all ants are male. Ants perform all cats over lifetime, so the jobs are just temporarily. The cast is choosen based on need / frequency of meeting other ants. There is no “soldiers” vs “workers” fight.

• Queen (just makes new ants)
• Males
  • Nest maintainers
  • Patrollers
  • Foragers

• Patrollers go out every morning, randomly search the area, return if they find food
• If foragers meet enough patrollers per minute, they leave the nest
• Foragers move randomly, but also tend to follow pheromone trails
• The shortest route will automatically be found and reinforced by even more traffic

Pheromones are a chemical substance which is produced by the ants and quickly evaporates. Each ant can produce different kinds of pheromones, each signal another information for example danger or food. The pheromones are produced continuously while moving. When a ant moves it moves randomly but tends to follow pheromone trails. The higher a concentration of pheromones is the higher the chance is that the ant will follow this trail. This makes it possible for ants to find the shortest way around obstacles.

These ants move along the road and follow the pheromone trail.

Lets put a obstacle in their way and see what happens. As you can imagine the ants need to find a way around the obstacle because they can't go over it and the pheromone trail is interrupted.

The ants now have a 50% chance to go left or right around the obstacle. While moving they produce pheromones.

After a while the shorter path becomes more and more established because pheromone concentration here is higher then on the longer path. On the longer path it takes more time to walk it so the pheromone can quickly evaporate. The shorter way is used by more ants in the same time, so the concentration of pheromones is much higher then in the longer way and more and more ants will choose the shorter way until its fully established.

This was just a short version of ant pheromone behavior, if you want more detailed information have a look at Ants finding shortest path

Ant Colony Optimization (ACO) is a combinatorial optimization algorithm developed by Marco Dorigo in 1992. It has been applied to problems such as TSP. Its major advantage is that it can be used continuously and in realtime. It works by having a population of “ants” which continuously explore the solution space and leave behind a virtual pheromone where they have already been, which evaporates over time. Ants tend to move towards detected pheromones in the solution space.

# Generation population of ants P # For each a in P

  # Move in a random direction, but prefer directions with pheromone
  # Leave behind some pheromone
  # If "food" found (i.e., a good solution), pick it up and return home
# Globally reduce the amount of pheromone
# Goto 2

In 1992 Loren Carpenter held a conference in Las Vegas where each of the 5000 viewers in the audience had a card with a red and a green side. Each of this cards represented one pixel on a big screen. By flipping the side the pixel represented by the card changed his color to the color shown on the card. After introducing the audience Carpenter loaded the famous game “PONG”. He divided the audience in two parts, one half controlling puncher one and the other controlling puncher 2. By showing the green side of the card the puncher moves down and when showing red it moves up. The color most shown on in the crowd is the direction the puncher moves. Now the audience played a good PONG game and also managed higher speed.

other experiments with this audience:

• building a number in a defined area
• flying a plane in a simulation software

longer and detailed description in Kevin Kelly's book "Out of Control"

• Cool swarm game a friend of mine showed me. It's a bit brutal but the swarm is nice :)
• This game is just sick! But great animation and what a beauty! Try to beat my 190 top velocity ;) — Bjoern 2007/10/30 19:12

• Raptors hunted in groups
• NYT Article on Swarm Behavior
• The Rules of the Swarm
• Honeybees Might Prompt Faster Internet Server Technology
• Bees' "waggle dance" may inspire better web server routing
• Scientists crack the Starling flocking code