# Flocking algorithms¶

a.k.a. collective motion, swarm dynamics, herd behaviour, particle systems...

A type of agent-based model where the emphasis is on motion in space.

Here’s a simple-but-entertaining one I’m working on at the moment : Vicsek’s “Self-Propelled-Particle” model [1]:

Vicsek’s simulation is a special case of the older but less-analytically-tractable “Boids” model, invented by Reynolds in the 80s. Reynolds wanted to model the flight of birds realistically, and his model had several rules to ensure, e.g. that his simulate birds did not collide in mid air.

Vicsek and colleagues stripped the model back to the its skeleton. Soon, circling physicists has joined him at the carcass (ahem), and now there’s a regular mini-research-field built around it. This model is about as simple as a classic Ising model, but covers moving things, which, motils creatures as we are, you might find easier to empathise with than abstract magnetic spins and such.

The formula, [2] in Vicsek’s words:

The only rule of the model is: at each time step a given particle driven with a constant absolute velocity assumes the average direction of motion of the particles in its neighborhood of radius $$r$$ with some random perturbation added.

I renamed “perturbation” to “noise”, “absolute velocity” to “speed” and “radius” to “range”, since this is a blog not a journal. Oh, and “neighborhood” to “neighbourhood”, because that’s how Australians spell.

Of key interest to the excitable creature who tends to become a working physicist, this model demonstrates classic “phase transition” behaviour. Sweep that “noise” slider from nought to maximum and you’ll see some radical changes in the behaviours of those little moving particles as they go from orderly marching through to fidgety jiggling. In the middle, somewhere, you’ll find a graceful, evolving, lifelike (if you squint) flocking behaviour, like birds or fish, if birds or fish had happened to evolve as translucent rust-coloured bricks. This is the “phase transition” region, where statmech folks can get overstimulated and use phrases like “self organised criticality”, or possibly “edge of chaos”, and might need to have a bit of a lie-down. And that’s what I’m investigating at the moment. (the phase transition and the lie-down.)

One thought this model fills me with, aside from the academic interest, is that it would make a really nice algorithm to drive a granular sampler. Has anyone done that yet? (edit: yes, e.g. Nicholas Mariette)

• Tamás Vicsek, András Czirók, Eshel Ben-Jacob, Inon Cohen, Ofer Shochet. 1995. Novel type of phase transition in a system of self-driven particles. Physical Review Letters. DOI. (Online)
• Boids inventor Craig Reynolds has a page dedicated to this algorithm with more than you could possibly need to know about his classic model, including other implementations, animations, and trainspotting of the algorithm at work in Hollywood blockbusters.
• Thomas Lux. 1995. Herd Behaviour, Bubbles and Crashes. The Economic Journal. (Online) — Nice paper on the relevance of this to human behaviour.
• Dion Harmon, Marcus A M de Aguiar, David D Chinellato, Dan Braha, Irving R Epstein, Yaneer Bar-Yam. 2010. Predicting economic market crises using measures of collective panic. (Online) (cf Wired’s heart-warmingly enthusiastic coverage of same.)
• Iain Couzin and colleagues have created some neat hacks in this area including exotica like mixing real animals with simulated ones in lab environments, and racetracks for locusts.
• Gama sutra’s diverting article on the intersection of the classic Reynolds Boids algorithm and human opinion dynamics. (Warning - human opinion dynamics are likely topologically very different to this kind of bloody-minded literalism. But the parallels are there to be drawn in some form, yes.)
 [1] You can view the source code for this page if you want to see how it’s done... I wrote the code in coffeescript originally, and the source for that is here. I haven’t tested this in Internet Explorer at all. My tests indicate it runs fast on Safari and Chrome, and sorta OK on Firefox. Patches welcome.
 [2] To nitpick - I’ve calculated angular perturbation by normalised vector sums rather than trigonometrically without first proving they are equivalent, and i use a lot fewer particles than they recommend.