Wednesday, July 03, 2013

Electro-Flock: Modelling Flocks using Simple Electro-Magnetism

Flocks are easy to model if you use physics instead of biology

Look - Its all done with magnets!
Electro-Flock is a simple flocking algorithm that relies only on Coulomb's Law, the single physical equation that describes how electrically charged particles interact. The project uses CoffeeScript, JQuery, HTML5 and Processing.js.

I started this project with the feeling that flocking algorithms were too specific. I wanted to see if I could write a really simply algorithm that didn't know it was meant to be a flocking algorithm. I had a feeling that electro-magnetism might just be the key to a really fundamental, self-organising flock. Was this feeling justified? -  Judge for yourself Play with the Electro-Flock Demo

What did you use to build Electro-Flock? 
For a complete description of the technology stack please see the prequel post:

Where can I see the demo and get the code?

Not another Flocking Algorithm surely?
It has been done before, many times, but something has always bothered me about the fluffy view of flocking. Being a firm advocate of evolutionary-biology I imagine Mother Nature as a cruel and selfish parent.

I think that apparent co-operation is most often an illusion created by constrained individualism, in other words individuals acting to serve their own goals in competition with others often end up acting in ways that just happen to look like they are co-operating and coordinating. In fact I had a feeling that the last thing most flock members would want to do is be part of a flock, or worse, part of a bait-ball! (see below for a definition and picture of a bait-ball)

All this pontificating finally led me to two interesting questions:
  1. What would happen if I were to create a selfish bot that actively spurns flocking, a bot that attempts to stay as far as possible from all other bots?
  2. What would happen if a collection of these selfish bots, an anti-flock, started to pursue their own selfish goals in competition with other identical bots?
The answer, as you can see from the demo, turns out to be amazing. Despite themselves the collection of entirely selfish individual bots magically cohere to form beautiful, fluid, dynamic flocks and tight little bait-balls.

Does it really need magic though?
Happily this anti-flock effect is simple to achieve without the aid of magic. Instead it relies on the single, prosaic principle of electro-magnetism. In fact the entire demo consists of nothing more than a combination of various types of magnet - yet the results are complex, very realistic and entirely emergent.

How do you make an anti-flock out of magnets?
The rest of this post will try to explain why anti-flocks work but before delving into any more theory you should definitely play with the demo. And remember - all the code is available from GitHub so you can see how to do it for yourself.

The Electro-Flock Demo - A Quick Start Guide

The top tool-bar

The top tool-bar allows you to set up your flocking environment. Choose the number of bots and, crucially, the number of attractors they will be chasing (see below for an explanation of why the attractors are important). You can also add some obstacles for the bots to avoid. All these things are just different types of magnets.

The bottom tool-bar

The bottom tool-bar allows you to switch off both the attractors and the obstacles. Switching off the attractors allows you to see the bots in their natural anti-flock state where they try their best to avoid flocking (see below for a picture of this). You can also reset the obstacles to mix things up. The Help link brings you back to this page.

Definitions and Discussion

A Flock
Normally a flock is defined as a number of birds that are feeding, resting or travelling together. I would say that a flock is a collection of individuals determined to achieve their own goals whilst avoiding others that are attempting to do the same.

A flock of birds

A Bait-Ball
A bait-ball occurs when small fish swarm in a tightly packed spherical formation about a common centre. It is commonly described as a last-ditch defensive measure adopted by small schooling fish when they are threatened by predators. I say this is wrong and that a bait-ball occurs when individual fish all selfishly attempt to get as far away as possible from a common set of predators.

The more predators, the tighter the ball

A constrained, two dimensional bait-ball

What is your Point?
Simple really. A flock is not a coordinated thing. A bait-ball is not a cooperative thing. These phenomenon emerge coincidentally whenever a collection of genetically similar actors find themselves selfishly pursuing their individual goals in the same location. Birds and fish are individualists, they are not members of a flock. The flock is simply a coincidence of time and space.

Yes, birds of a feather do flock together but not because they want to. Instead they flock simply because they all want the same things at the same time and so end up trying to occupy the same coordinates in space-time.

Clearly two things cannot occupy the same space-time coordinates so the individuals just do the best they can whilst selfishly optimising their individual trajectories - each chasing down whatever is attracting them or evading whatever is repulsing them whilst keeping the maximum distance from each other.

Therefore the effect that we pattern-seeking humans see as a flock or bait-ball does not require any form of co-operation, coordination or communication.  Instead it is simply the result of a group of individuals all trying to be in exactly the same place at the same time but failing. The only thing keeping the flock from imploding in a flurry of feathers or fish-scales is the mutual repulsion the individuals have for each other.

This is the opposite of the usual way we imagine flocks.

We normally think that the flock has some property of coherence, something that holds the flock together, but that is wrong. The flock is always trying to explode apart, the flock members want to be as far apart from each other as they can be, but since they are effectively identical (genetically) then they are all attracted and repulsed to the same degree by the same things.

This creates two opposing forces:
  1. The repulsion all bots feel for all other bots 
  2. The shared attraction bots feel to the things in the environment
And the critical, dynamic balance point between these two opposing forces is a flock.

Um .. OK. So why all this talk of magnets?
If I am correct then I should be able to model this all really easily. On the one hand I say that each bot should be repulsed by all other bots. On the other hand each bot should be attracted by elements of their environment. For a bird-flock that might be a positive attraction to a number of suitable roosting spots, for fish-bait-ball that might be a negative attraction to a number of predators.

All this attraction, both positive and negative, can be easily modelled using magnets, or more specifically using Coulomb's Law which is a law of physics that describes the electrostatic interaction between electrically charged particles.

Bots are magnets - right. So what happens when you try it out?
Unsurprisingly if you model the bots as magnets that simply repel each other you end up with a pure anti-flock, something like this:

The bots fly away from each other just as fast as they can

Until they are equally spaced as far as possible

You can see this for yourself if you switch the attractors off in the demo

The next step is to add some more magnets called attractors. The attractors positively attract bots to themselves causing the bots to chase them. And wouldn't you know it, as soon as you add attractors into the mix something amazing happens - the anti-flock turns into a beautiful, flowing dynamic flock and the more attractors you add the tighter and more coherent the flock becomes.

A loose flock created by two attractors

A tight bait-ball style flock created by twenty attractors

It works! That's great. But remind me - what is going on?
Its so simple - bots are repelled by bots and attracted to attractors - that's it.

This creates a system that seeks a balance point where the bots are as close as they can be to an attractor whilst being as far away as possible from each other. If the attractors were stationary then this balance point would be a static cloud of bots. However (and I didn't mention this before) the attractors are also repelled by the bots. So as the bots try to chase them down the attractors try to escape. Thus the balance point of the system is forever changing. Adding more than one attractor makes the balance point both dynamic and complex and the result is a beautiful flowing cloud of bots, in other words, a flock.

It looks like a flock sure but come on, birds and fish don't work like this do they?
Don't they? Maybe we have been making our explanations of flocking more complex and specific than they need to be because we have been thinking too much like biologists. Thinking like a physicist, that is thinking  in terms of electrically charged particles means we get the same (or better) results using a single incredibly simple formula - Coulomb's law. Occam's razor surely applies.

Go on then, tell me what you really think.
Thinking electrically then - birds flock not because they want to flock or try to flock but because each individual bird finds itself flying through a type of five dimensional Gauge Field. That's right - five dimensions. There are the four dimensions of space-time plus a bird-perceived fifth dimension of environmental attractiveness. Its just like flying through an electro-magnetic field with a compass.

At each point in space-time the bird experiences a greater or lesser degree of attraction to any given direction of flight and simply responds accordingly, like iron filings lining up in a magnetic field. The varying field strengths throughout four dimensional space-time are a product of everything in the bird's environment, for example the desirability of roosting spots, the presence of predators, the availability or otherwise of food sources, the wind direction - you name it, its an infinity of causes.

Birds of the same species will perceive and react to their attractor-field in essentially the same way and so they will end up trying to be in the same place at the same time. Since this is impossible it implies that birds must avoid each other, in other words that birds are repulsed by each other. Thus we have the tension between the two forces of attraction and repulsion - and a flock is the dynamically balanced result.

The same goes for a bait ball. The attractor field is in this case is negative. Instead of being positively attracted to elements in their environment a bait-ball is characterised by fish being repulsed by predators - but the direction of attraction does not matter as the effect is just the same. Lots of functionally identical fish all experiencing the same attractor-field all want to go to the same place at the same time but they can't because of all the other fish that are doing the exact same thing.

The bait ball is a pure and therefore very clear demonstration of the attractor field effect. Individually each fish acutely senses the varying degrees of repulsion as it travels through points in attractor-space-time. This has the effect of aligning the fish to the underlying attractor field lines and, in so doing, maximising the distance between the fish and the predators. With enough predators arranged around them in three dimensional space the least repulsive location becomes a perfect singularity, a point in five dimensional attractor-space-time around which all the fish align themselves with a precision that is distorted only by the presence of the other fish.

This bait-ball effect is exactly what we see happening with the demo when we add lots of attractors.

I sense a summary...
Don't think of a fluffy, co-operating  flock. Instead think of electrically charged particles moving through an electro-magnetic field. Swap the word 'magnetism' for 'environmental attractiveness' (both positive and negative) and just use the standard formula as described by Coulomb. What you get is flocking!

This strikes me as a beautiful and potentially useful simplification of the current descriptions of natural flocking behaviours and that, for me at least, serves to make this apparently complex but actually fundamentally simple phenomenon even more awe inspiring.