Self-propelled particles

SPP models predict robust emergent behaviours occur in swarms independent of the type of animal that is in the swarm.

Self-propelled particles (SPP), also referred to as self-driven particles or as the Couzin–Vicsek algorithm,^[1][2] is a concept used to model swarm behaviour. The concept was introduced in 1995 by Vicsek and Couzin et al.^[3] as a special case of the Boids model introduced in 1986 by Reynolds.^[4] 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.^[5]

SPP models predict that swarming animals share certain properties at the group level, regardless of the type of animals in the swarm.^[6] 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.^[7][8][9]

Overview

The SPP model is based on a collection of points or particles, each functioning individually as an autonomous agent, 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.^[10]

External videos
	SPP model interactive simulation[11] – needs Java

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).^[3]

Although more realistic swarming models have been explored,^[12] the SPP model remains important because of its simplicity and the strength and the variety of its emergent phenomena.^[10] 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.^[9] It is a discrete-time switched linear system which is stable, even though no common quadratic Lyapunov function exists.^[10] It is an analogue of the Ising model in ferromagnetism, where temperature corresponds to particle randomness and spin clusters correspond to particle clusters.^[3]

Examples

Locust nymph

External videos
	Marching locusts – sped up 6-fold. When the density of locusts reaches a critical point, they march steadily together without direction reversals.

Marching locusts

Young desert locusts 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.^[13] This can be the prelude to the development of the vast flying adult locust swarms which devastate vegetation on a continental scale.^[14]

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.^[15] 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/m², 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.^[6]

In the field, according to the Food and Agriculture Organization of the United Nations, the average density of marching bands is 50 locusts/m² (50 million locusts/km²), with a typical range from 20 to 120 locusts/m².^[14]:29 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.^[6]

Bird landings

Flocks of birds can abruptly change their direction in unison, and then, just as suddenly, make a unanimous group decision to land^[16]

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.^[17]

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.^[16] 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.^[18]

"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."^[16] 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.^[19]

Other examples

SPP models have been applied in many other areas, such as schooling fish,^[20] robotic swarms,^[21] molecular motors,^[22] the development of human stampedes^[23] and the evolution of human trails in urban green spaces.^[24]

Notes

1. ^ Degond, P.; & Motsch, S. (2007) "Continuum limit of self-driven particles with orientation interaction" SIAM J Appl Math, arXiv:0710.0293.
2. ^ Setekera, R. (2009) "Numerical simulation of herding and flocking models" Masters' thesis, supervisor A Klar, Technische Universiteit Eindhoven.
3. ^ ^{a b c} Vicsek, T.; Czirok, A.; Ben-Jacob, E.; Cohen, I. & Shochet, O. (1995) "Novel type of phase transition in a system of self-driven particles" Physical review letters, 75:1226–1229. doi:10.1103/PhysRevLett.75.1226
4. ^ Reynolds, C.W. (1987) "Flocks, herds and schools: A distributed behavioral model" Computer Graphics, 21(4), 25–34. doi:10.1145/37401.37406
5. ^ Czirók, A. & Vicsek, T. (2006) "Collective behavior of interacting self-propelled particles" Physica A, 281: 17–29. doi:10.1016/S0378-4371(00)00013-3
6. ^ ^{a b c} Buhl, J.; Sumpter, D.J.T.; Couzin, D.; Hale, J.J.; Despland, E.; Miller, E.R. & Simpson, S.J. (2006) "From disorder to order in marching locusts Science, 312(5778): 1402–1406. doi:10.1126/science.1125142
7. ^ Toner, J.; Tu, Y. & Ramaswamy, S. (2005) "Hydrodynamics and phases of flocks" Annals Of Physics, 318(170)
8. ^ 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. doi:10.1088/1751-8113/42/44/445001
9. ^ ^{a b} Li, Y.X.; Lukeman, R. & Edelstein-Keshet, L. (2007) "Minimal mechanisms for school formation in self-propelled particles" Physica D: Nonlinear Phenomena, 237(5): 699–720. doi:10.1016/j.physd.2007.10.009
10. ^ ^{a b c} 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.
11. ^ Self driven particle model Interactive simulations, 2005, University of Colorado. Retrieved 10 April 2011.
12. ^ Helbing, D. (2001) "Traffic and related self-driven many-particle systems" Reviews of Modern Physics, 73(4), 1067–1141. doi:10.1103/RevModPhys.73.1067
13. ^ Uvarov, B.P. (1977) "Grasshopper and locust: a handbook of general acridology". Vol II: Behaviour, ecology, biogeography, population dynamics, Cambridge University Press.
14. ^ ^{a b} Symmons, P.M.; Cressman, K. (2001) "Desert locust guidelines: Biology and behaviour" FAO, Rome.
15. ^ Huepe, A. & Aldana, M. (2004) "Intermittency and clustering in a system of self-driven particles" Physical review letters, 92(168701): 1–4. doi:10.1103/PhysRevLett.92.168701
16. ^ ^{a b c} Bhattacharya, K. & Vicsek, T. (2010) "Collective decision making in cohesive flocks"
17. ^ Self-Propelled Particle System Improves Understanding Of Behavioral Patterns 2010.
18. ^ Somfai, E.; Czirok, A. & Vicsek, T. (1994) "Power-law distribution of landslides in an experiment on the erosion of a granular pile" Journal of Physics A, 27(20). doi:10.1088/0305-4470/27/20/001
19. ^ Bird flock decision-making revealed 2010.
20. ^ Gautrais, J.; Jost, C. & Theraulaz, G. (2008) "Key behavioural factors in a self-organised fish school model" Annales Zoologici Fennici, 45: 415–428.
21. ^ Sugawara, K.; Sano, M. & Watanabe, T. (2009) "Nature of the order-disorder transition in the Vicsek model for the collective motion of self-propelled particles" Phys. Rev. E, 80: 050103.1-4. doi:10.1103/PhysRevE.80.050103
22. ^ Chowdhury, D. (2006) "Collective effects in intra-cellular molecular motor transport: coordination, cooperation and competetion" Physica A, 372(1): 84–95. doi:10.1016/j.physa.2006.05.005
23. ^ Helbing, D.; Farkas, I. & Vicsek, T. (2000) "Simulating dynamical features of escape panic" Nature, 407: 487–490. doi:10.1038/35035023
24. ^ Helbing, D.; Keltsch, J. & Molnar, P. (1997) "Modelling the evolution of human trail systems" Nature, 388:47–50.

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. doi:10.1088/1751-8113/42/44/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. doi:10.1088/0305-4470/30/5/009
• 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) "Self-organization in Nott PR (2008) [http://arxiv.org/pdf/0707.1436 "The collective dynamics of self-propelled particles" Journal of Fluid Mechanics, 595: 239–264. doi:10.1017/S0022112007009184
• 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. doi:10.1103/PhysRevLett.89.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. doi:10.1038/466043a
• 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 Earth