The Living Thing

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)

Why not read....


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.

blog comments powered by Disqus