Motion Captured: The Equation of Murmuration

May 1, 2015

Share this pageShare on FacebookTweet about this on TwitterShare on LinkedInGoogle+







sortsol

Sort sol (black sun) is a spectacular phenomenon that happens every spring and autumn as hundreds of thousands of starlings gather in the marshes of south-western Jutland, a way station between their winter grounds in the south and their Scandanavian summer homes. At sunset the birds take flight to search for a roost, creating immense flocks that darken the sky and blot out the sunset.

Above is a simple model, which we will describe, of a flock of birds. They start out flying in random directions and, by obeying some simple rules, they align and all fly in a co-ordinated way. Use the slider to control the number of arrows. We can simulate the effect of a falcon swooping in to attack the flock. Clicking on the box generates a dot (you can generate up to 20 by repeated clicking) the arrows avoid the dot while still trying to align with one another.

We talked last month about complexity and collective behaviour emerging from simple local rules. Flocks of starlings, herds of zebra or shoals of fish are spectacular natural examples of this. There is no co-ordinating starling directing the aerial ballet and the starlings don’t meet to discuss the evening flight plan. The order emerges spontaneously from each starling’s personal decisions. The first and best known attempt to model flock behaviour was Reynold’s boids. Boids is short for “bird-oid object” or, if you like, think of Tony Soprano saying “birds”. In 1986 when the model was proposed the way in which collective dynamics could emerge from local rules was not well known and Reynold’s model was a huge step forward for computer animation and was taken up enthusiastically by the artifical life community.

Briefly, a boid is a little triangle in a computer simulation. Each boid has a position and a heading. Reynold’s rules for each boid are to

  • Steer to avoid crowding neighbours.
  • Steer towards the average heading of neighbours.
  • Steer towards the average position of neighbours.

The exact implementation of the steering rules leads to realistic looking flocks, see Reynold’s own implementation. If you don’t like running applets try this or look out for the bat swarms in Batman Returns (1992) which were animated using boid rules.

Physicists, becoming interested in collective dynamics themselves, also took up modelling flocks. Naturally for physicists they based their models on previous successful models of collective dynamics, namely our old friend the Ising model. The Vicsek model is specified by the following rules. Each bird, drawn as an arrow, has a velocity vector $v_n(t) = v e^{i\theta_n(t)}$. That is, they all travel at the same speed but in different directions. Given a radius $r$ let $N(n)$ be the list of birds less than the distance $r$ from the $n^{th}$ bird. So $N(n)$ are the nearest neighbours of $n$. The average velocity in the neighbourhood of $n$ is
\[
V_n = \frac{1}{|N(n)|} \sum_{j \in N(n)} v_j \propto e^{i \phi_n}
\]
The updating rules are
\[
\theta_n(t + \delta t) = \phi_n + \eta_n \\
v_n(t + \delta t) = v e^{ i \theta_n(t + \delta t) } \\
x_n(t + \delta t) = x_n(t) + v_n(t + \delta t) \delta t
\]
Where $\eta$ is a random noise term. The noise term is interesting, too high and there is no order. The phase transition of order to disorder is very different depending on the type of noise, ‘intrinsic’ or ‘extrinsic’ which in turn should tell us about the forces in real flocks as they form and break up. See this for more details. In our simulation the magnitude of the noise is very low, as in real flocks.

The simulation above looks real. The Vicsek model and especially Boids were aimed at reproducing realistic looking flock behaviour. When a predator approaches the Vicsek arrows turn and wheel in what seems a reasonable way. But it is possible nowadays to measure huge flocks and turn what has been an art into an experimental science. This brings us to a remarkable paper: Super fluid transport of information in turning flocks of starlings. By filming flocks with multiple cameras they were able to study turning motions made by real flocks and discover three key facts:

  • Turns are initiated by a few individuals.
  • This information is propagated through the flock without attenuation.
  • The distance traveled by the information is proportional to the time $x(t) = c_s t$.

These are the key reasons why a flock can remain coherent during and after a turn. If information travelled any slower or was dissipated, distant parts of the flock would decouple. The Vicsek model, ignoring noise, with $J$ a normalization factor, predicts:
\[
v_n(t+\delta t) = v_n(t) + J \sum_{j} v_j(t)
\]
We have talked about discrete versions of continuous models before, now we go the other way. This is nothing more than a discrete version of
\[
\frac{dv_n}{dt} = -\frac{\partial H}{\partial v_n}
\]
with
\[
H = -J \sum_{\langle nj \rangle} v_n v_j
\]
Each bird updates its velocity in response to a ‘social force’ $F^n = \frac{\partial H}{\partial v_n}$. In fact this model is exactly the same as a ferromagnet with velocity playing the role of spin.

Now that we have gone from discrete time to continuous time we also go from discrete space to continuous space. Think of the flock as a fluid or a field instead of thinking about all birds individually. The angle for each bird becomes
\[
\theta_n(t) \rightarrow \theta(x,t)
\]
a function of position and time. With some not too tricky manipulations the $H$ function becomes
\[
H = \frac{1}{2} a^2 J \int d^3x [\nabla \theta(x,t)]^2 / a^3
\]
here $a$ is the average nearest neighbour distance, like a lattice spacing in a ferromagnet model. The relevant equation is now
\[
\frac{d\theta}{dt} = -\frac{\partial H}{\partial \theta} = a^2 J \nabla^2 \theta(x,t)
\]
This is just the well known diffusion equation. The diffusion equation describes things like heat propagating through a conductor (or option pricing) and has been studied extensively since the 18${}^{th}$ century. Thus we know a good deal about it. In a diffusive system information travels like $x(t) \sim \sqrt{t}$ and dissipates. So the Vicsek model, despite looking good, doesn’t work for real flocks.

The first step towards improving the model is the realisation that the system has a gauge symmetry! Making a uniform rotation of all the birds doesn’t affect the behaviour of the flock. Symmetries imply conservation laws but above we found dissipation, so something is missing. The function $H$ was given its suggestive name to remind us of Hamiltonian mechanics. In Hamiltonian mechanics every variable has a ‘conjugate’, like position and its conjugate: momentum. We need something like momentum to be conjugate to velocity. In gruesome detail, we add a conjugate momentum called $s$ to the Hamiltonian
\[
H = \int d^3x \frac{1}{2} \rho \nabla \theta(x,t)^2 + \frac{s^2}{2 \chi}
\]
So that now it looks like kinetic plus potential energy, $\chi$ is like a mass or inertia (the birds can’t turn infinitely fast) and $\rho$ is like a spring constant or stiffness. The physical interpretation of $s$ is as the inverse radius of curvature of the trajectory. Turning the crank, the machinery of Hamiltonian mechanics gives
\[
\frac{\partial \theta}{\partial t} = \frac{s}{\chi} \\
\frac{\partial s}{\partial t} = \rho \nabla^2 \theta
\]
Together these imply a conserved current, $j = \rho \nabla \theta$, and a conservation law
\[
\frac{\partial s}{\partial t} – \nabla j = 0
\]
This is familiar from electromagnetism, disturbances can’t be dissipated they must be transported away. Finally combining the two equations gives
\[
\frac{\partial^2 \theta}{\partial t^2} = \frac{\rho}{\chi} \nabla^2 \theta.
\]
This is the wave equation! This gives us exactly what we found experimentally, a linear relation between information transport and time $x(t) = c t$ with $c^2 = \frac{\rho}{\chi}$. These same equations are used to study the phenomenon of second sound in superfluid helium.

We sketched above a beautiful theory of bird motion showing surprising connections between what appear to be fundamentally different domains. Boids and Vicsek models are simple and produce something realistic looking, but are not the full story. The beautiful wheeling and turning


occur due to the decisions of a few individuals propagating through the flock. Interestingly, in the real sort sol when a predator approaches, the starlings unleash a deluge of vomit and droppings until the encroaching hunter is obliged to land. Which is why I generally try to stay away from field work and stick to modelling.