Self-propelled particles
Encyclopedia
Self-propelled particles (SPP), also referred to as self-driven particles or as the Couzin–Vicsek algorithm, is a concept used to model swarm behaviour. The concept was introduced in 1995 by Vicsek and Couzin et al. as a special case of the Boids
model introduced in 1986 by Reynolds
. A swarm is modelled in SPP by a collection of particles that move with a constant speed but respond to a random perturbation by adopting at each time increment the average direction of motion of the other particles in their local neighbourhood.
SPP models predict that swarming animals share certain properties at the group level, regardless of the type of animals in the swarm. Swarming systems give rise to emergent behaviours which occur at many different scales, some of which are turning out to be both universal and robust. It has become a challenge in theoretical physics to find minimal statistical models that capture these behaviours.
, and each following the same simple rules which govern their behaviour. The particles move in a plane with constant speed but in different directions. The direction of each particle is updated using a "nearest neighbor rule", a local rule which replaces the direction of each particle with the average of the particle's own direction plus the directions of its immediate neighbours.
Simulations demonstrate that a suitable "nearest neighbour rule" eventually results in all the particles swarming together, or moving in the same direction. This emerges, even though there is no centralised coordination, and even though the neighbours for each particle constantly change over time (see the interactive simulation in the box on the right).
Although more realistic swarming models have been explored, the SPP model remains important because of its simplicity and the strength and the variety of its emergent phenomena. The SPP model is an agent-based model based on a Lagrangian
viewpoint, which follows individual particles rather than working with the density of the swarm. It is a discrete-time switched linear system
which is stable
, even though no common quadratic Lyapunov function
exists. It is an analogue of the Ising model
in ferromagnetism
, where temperature corresponds to particle randomness and spin clusters correspond to particle clusters.
s are solitary and wingless nymphs
. If food is short they can gather together and start occupying neighbouring areas, recruiting more locusts. Eventually they can become a marching army extending over many kilometres. This can be the prelude to the development of the vast flying adult locust swarms which devastate vegetation on a continental scale.
One of the key predictions of the SPP model is that as the population density
of a group increases, an abrupt transition occurs from individuals moving in relatively disordered and independent ways within the group to the group moving as a highly aligned whole. Thus, in the case of young desert locusts, a trigger point should occur which turns disorganised and dispersed locusts into a coordinated marching army. When the critical population density is reached, the insects should start marching together in a stable way and in the same direction.
In 2006, a group of researchers examined how this model held up in the laboratory. Locusts were placed in a circular arena, and their movements were tracked with computer software. At low densities, below 18 locusts per square metre, the locusts mill about in a disordered way. At intermediate densities, they start falling into line and marching together, punctuated by abrupt but coordinated changes in direction. However, when densities reached a critical value at about 74 locusts/m2, the locusts ceased making rapid and spontaneous changes in direction, and instead marched steadily in the same direction for the full eight hours of the experiment (see video on the left). This confirmed the behaviour predicted by the SPP models.
In the field, according to the Food and Agriculture Organization of the United Nations, the average density of marching bands is 50 locusts/m2 (50 million locusts/km2), with a typical range from 20 to 120 locusts/m2. The research findings discussed above demonstrate the dynamic instability that is present at the lower locust densities typical in the field, where marching groups randomly switch direction without any external perturbation. Understanding this phenomenon, together with the switch to fully coordinated marching at higher densities, is essential if the swarming of desert locusts is to be controlled.
In 2010, Bhattacharya and Vicsek used an SPP model to analyse what is happening here. As a paradigm, they considered how flying birds arrive at a collective decision to make a sudden and synchronised change to land. The birds, such as the starlings in the image on the right, have no decision-making leader, yet the flock know exactly how to land in a unified way. The need for the group to land overrides deviating intentions by individual birds. The particle model found that the collective shift to landing depends on perturbations that apply to the individual birds, such as where the birds are in the flock. It is behaviour that can be compared with the way that sand avalanches, if it is piled up, before the point at which symmetric and carefully placed grains would avalanche, because the fluctuations become increasingly non-linear.
"Our main motivation was to better understand something which is puzzling and out there in nature, especially in cases involving the stopping or starting of a collective behavioural pattern in a group of people or animals ... We propose a simple model for a system whose members have the tendency to follow the others both in space and in their state of mind concerning a decision about stopping an activity. This is a very general model, which can be applied to similar situations." The model could also be applied to a swarm of unmanned drones
, to initiating a desired motion in a crowd of people, or to interpreting group patterns when stock market shares are bought or sold.
and the evolution of human trail
s in urban green spaces.
Boids
Boids is an artificial life program, developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds. His paper on this topic was published in 1987 in the proceedings of the ACM SIGGRAPH conference...
model introduced in 1986 by Reynolds
Craig Reynolds (computer graphics)
Craig W. Reynolds , is an artificial life and computer graphics expert, who created the Boids artificial life simulation in 1986. Reynolds worked on the film Tron as a scene programmer, and on Batman Returns as part of the video image crew. He is the author of the OpenSteer library.-External...
. A swarm is modelled in SPP by a collection of particles that move with a constant speed but respond to a random perturbation by adopting at each time increment the average direction of motion of the other particles in their local neighbourhood.
SPP models predict that swarming animals share certain properties at the group level, regardless of the type of animals in the swarm. Swarming systems give rise to emergent behaviours which occur at many different scales, some of which are turning out to be both universal and robust. It has become a challenge in theoretical physics to find minimal statistical models that capture these behaviours.
Overview
The SPP model is based on a collection of points or particles, each functioning individually as an autonomous agentAutonomous agent
An autonomous agent is an intelligent agent operating on an owner's behalf but without any interference of that ownership entity. An intelligent agent, however appears according to a multiply cited statement in a no longer accessible IBM white paper as follows:Intelligent agents are software...
, and each following the same simple rules which govern their behaviour. The particles move in a plane with constant speed but in different directions. The direction of each particle is updated using a "nearest neighbor rule", a local rule which replaces the direction of each particle with the average of the particle's own direction plus the directions of its immediate neighbours.
Simulations demonstrate that a suitable "nearest neighbour rule" eventually results in all the particles swarming together, or moving in the same direction. This emerges, even though there is no centralised coordination, and even though the neighbours for each particle constantly change over time (see the interactive simulation in the box on the right).
Although more realistic swarming models have been explored, the SPP model remains important because of its simplicity and the strength and the variety of its emergent phenomena. The SPP model is an agent-based model based on a Lagrangian
Lagrangian
The Lagrangian, L, of a dynamical system is a function that summarizes the dynamics of the system. It is named after Joseph Louis Lagrange. The concept of a Lagrangian was originally introduced in a reformulation of classical mechanics by Irish mathematician William Rowan Hamilton known as...
viewpoint, which follows individual particles rather than working with the density of the swarm. It is a discrete-time switched linear system
Linear system
A linear system is a mathematical model of a system based on the use of a linear operator.Linear systems typically exhibit features and properties that are much simpler than the general, nonlinear case....
which is stable
Stability theory
In mathematics, stability theory addresses the stability of solutions of differential equations and of trajectories of dynamical systems under small perturbations of initial conditions...
, even though no common quadratic Lyapunov function
Lyapunov function
In the theory of ordinary differential equations , Lyapunov functions are scalar functions that may be used to prove the stability of an equilibrium of an ODE. Named after the Russian mathematician Aleksandr Mikhailovich Lyapunov, Lyapunov functions are important to stability theory and control...
exists. It is an analogue of the Ising model
Ising model
The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
in ferromagnetism
Ferromagnetism
Ferromagnetism is the basic mechanism by which certain materials form permanent magnets, or are attracted to magnets. In physics, several different types of magnetism are distinguished...
, where temperature corresponds to particle randomness and spin clusters correspond to particle clusters.
Examples
Marching locusts
Young desert locustDesert locust
Plagues of the desert locust have threatened agricultural production in Africa, the Middle East, and Asia for centuries. The livelihood of at least one-tenth of the world’s human population can be affected by this voracious insect...
s are solitary and wingless nymphs
Nymph (biology)
In biology, a nymph is the immature form of some invertebrates, particularly insects, which undergoes gradual metamorphosis before reaching its adult stage. Unlike a typical larva, a nymph's overall form already resembles that of the adult. In addition, while a nymph moults it never enters a...
. If food is short they can gather together and start occupying neighbouring areas, recruiting more locusts. Eventually they can become a marching army extending over many kilometres. This can be the prelude to the development of the vast flying adult locust swarms which devastate vegetation on a continental scale.
One of the key predictions of the SPP model is that as the population density
Population density
Population density is a measurement of population per unit area or unit volume. It is frequently applied to living organisms, and particularly to humans...
of a group increases, an abrupt transition occurs from individuals moving in relatively disordered and independent ways within the group to the group moving as a highly aligned whole. Thus, in the case of young desert locusts, a trigger point should occur which turns disorganised and dispersed locusts into a coordinated marching army. When the critical population density is reached, the insects should start marching together in a stable way and in the same direction.
In 2006, a group of researchers examined how this model held up in the laboratory. Locusts were placed in a circular arena, and their movements were tracked with computer software. At low densities, below 18 locusts per square metre, the locusts mill about in a disordered way. At intermediate densities, they start falling into line and marching together, punctuated by abrupt but coordinated changes in direction. However, when densities reached a critical value at about 74 locusts/m2, the locusts ceased making rapid and spontaneous changes in direction, and instead marched steadily in the same direction for the full eight hours of the experiment (see video on the left). This confirmed the behaviour predicted by the SPP models.
In the field, according to the Food and Agriculture Organization of the United Nations, the average density of marching bands is 50 locusts/m2 (50 million locusts/km2), with a typical range from 20 to 120 locusts/m2. The research findings discussed above demonstrate the dynamic instability that is present at the lower locust densities typical in the field, where marching groups randomly switch direction without any external perturbation. Understanding this phenomenon, together with the switch to fully coordinated marching at higher densities, is essential if the swarming of desert locusts is to be controlled.
Bird landings
Swarming animals, such as ants, bees, fish and birds, are often observed suddenly switching from one state to another. For example, birds abruptly switch from a flying state to a landing state. Or fish switch from schooling in one direction to schooling in another direction. Such state switches can occur with astonishing speed and synchronicity, as though all the members in the group made a unanimous decision at the same moment. Phenomena like these have long puzzled researchers.In 2010, Bhattacharya and Vicsek used an SPP model to analyse what is happening here. As a paradigm, they considered how flying birds arrive at a collective decision to make a sudden and synchronised change to land. The birds, such as the starlings in the image on the right, have no decision-making leader, yet the flock know exactly how to land in a unified way. The need for the group to land overrides deviating intentions by individual birds. The particle model found that the collective shift to landing depends on perturbations that apply to the individual birds, such as where the birds are in the flock. It is behaviour that can be compared with the way that sand avalanches, if it is piled up, before the point at which symmetric and carefully placed grains would avalanche, because the fluctuations become increasingly non-linear.
"Our main motivation was to better understand something which is puzzling and out there in nature, especially in cases involving the stopping or starting of a collective behavioural pattern in a group of people or animals ... We propose a simple model for a system whose members have the tendency to follow the others both in space and in their state of mind concerning a decision about stopping an activity. This is a very general model, which can be applied to similar situations." The model could also be applied to a swarm of unmanned drones
Unmanned aerial vehicle
An unmanned aerial vehicle , also known as a unmanned aircraft system , remotely piloted aircraft or unmanned aircraft, is a machine which functions either by the remote control of a navigator or pilot or autonomously, that is, as a self-directing entity...
, to initiating a desired motion in a crowd of people, or to interpreting group patterns when stock market shares are bought or sold.
Other examples
SPP models have been applied in many other areas, such as schooling fish, robotic swarms, molecular motors, the development of human stampedesStampede
A stampede is an act of mass impulse among herd animals or a crowd of people in which the herd collectively begins running with no clear direction or purpose....
and the evolution of human trail
Trail
A trail is a path with a rough beaten or dirt/stone surface used for travel. Trails may be for use only by walkers and in some places are the main access route to remote settlements...
s in urban green spaces.
Further references
- Bertin, E.; Droz, M. & Grégoire, G. (2009) "Hydrodynamic equations for self-propelled particles: microscopic derivation and stability analysis" J. Phys. A, 42(44): paper 445001.
- Czirók, A.; Stanley, H.E. & Vicsek, T. (1997) "Spontaneously ordered motion of self-propelled particles" Journal of Physics A, 30(5): paper 1375.
- Czirók, A.; Barabási, A.L. & Vicsek, T. (1999) "Collective motion of self-propelled particles: Kinetic phase transition in one dimension" Phys Rev Lett, 82(1): 209–212.
- Czirók, A. & Vicsek, T. (2001) "Flocking: collective motion of self-propelled particles" In: Vicsek T Fluctuations and scaling in biology, Oxford University Press, pp. 177–209. ISBN 9780198507901.
- D'Orsogna, M.R.; Chuang, Y.L.; Bertozzi, A.L. & Chayes, L.S. (2006) "Self-propelled particles with soft-core interactions: patterns, stability, and collapse" Phys Rev Lett, 96(10): paper 104302.
- Levine, H.; Rappel, W.J. & Cohen, I. (2001) http://arxiv.org/pdf/cond-mat/0006477"Self-organization in Nott PR (2008) "The collective dynamics of self-propelled particles" Journal of Fluid Mechanics, 595: 239–264.
- Helbing, D. (2001) "The wonderful world of active many-particle systems" Advances in Solid State Physics, 41:357–368.
- Jadbabaie, A.; Lin, J. & Morse, A.S. (2003) "Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules" IEEE Transactions on Automatic Control, 48(6): 988–1001. – convergence proofs for the SPP model.
- Simha, R.A. & Ramaswamy, S. (2006) "Hydrodynamic fluctuations and instabilities in ordered suspensions of self-propelled particles" Phys Rev Lett, 89(5): paper 058101.
- Sumpter, D.J.T. (2010) Collective Animal Behavior Chapter 5: Moving together. Princeton University Press. ISBN 9780691129631.
- Vicsek, T. (2010) "Statistical physics: Closing in on evaders" Nature, 466: 43–44.
- Yates, C.A. (2007) "On the dynamics and evolution of self-propelled particle models" MSc thesis, Somerville College, University of Oxford.
- Yates, C.A.; Baker, R.E.; Erban, R. & Maini, P.K. (2010) "Refining self-propelled particle models for collective behaviour" Oxford Centre for Collaborative Applied Mathematics, Report Number 09/46.
External links
- Swarming desert locusts – Video clip from Planet EarthPlanet EarthPlanet Earth may refer to:* Earth, the third planet from the Sun* Planet Earth , a 2006 BBC documentary series* Planet Earth , a 1974 sci-fi TV movie...