- Self-propelled particles
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.
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.
External videos SPP model interactive simulation
– 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).
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.
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. 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.: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.
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, to initiating a desired motion in a crowd of people, or to interpreting group patterns when stock market shares are bought or sold.
SPP models have been applied in many other areas, such as schooling fish, robotic swarms, molecular motors, the development of human stampedes and the evolution of human trails in urban green spaces.
- ^ Degond, P.; & Motsch, S. (2007) "Continuum limit of self-driven particles with orientation interaction" SIAM J Appl Math, arXiv:0710.0293.
- ^ Setekera, R. (2009) "Numerical simulation of herding and flocking models" Masters' thesis, supervisor A Klar, Technische Universiteit Eindhoven.
- ^ 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
- ^ Reynolds, C.W. (1987) "Flocks, herds and schools: A distributed behavioral model" Computer Graphics, 21(4), 25–34. doi:10.1145/37401.37406
- ^ 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
- ^ 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
- ^ Toner, J.; Tu, Y. & Ramaswamy, S. (2005) "Hydrodynamics and phases of flocks" Annals Of Physics, 318(170)
- ^ 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
- ^ 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
- ^ 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.
- ^ Self driven particle model Interactive simulations, 2005, University of Colorado. Retrieved 10 April 2011.
- ^ 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
- ^ Uvarov, B.P. (1977) "Grasshopper and locust: a handbook of general acridology". Vol II: Behaviour, ecology, biogeography, population dynamics, Cambridge University Press.
- ^ a b Symmons, P.M.; Cressman, K. (2001) "Desert locust guidelines: Biology and behaviour" FAO, Rome.
- ^ 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
- ^ a b c Bhattacharya, K. & Vicsek, T. (2010) "Collective decision making in cohesive flocks"
- ^ Self-Propelled Particle System Improves Understanding Of Behavioral Patterns 2010.
- ^ 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
- ^ Bird flock decision-making revealed 2010.
- ^ Gautrais, J.; Jost, C. & Theraulaz, G. (2008) "Key behavioural factors in a self-organised fish school model" Annales Zoologici Fennici, 45: 415–428.
- ^ 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
- ^ 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
- ^ Helbing, D.; Farkas, I. & Vicsek, T. (2000) "Simulating dynamical features of escape panic" Nature, 407: 487–490. doi:10.1038/35035023
- ^ Helbing, D.; Keltsch, J. & Molnar, P. (1997) "Modelling the evolution of human trail systems" Nature, 388:47–50.
- 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.
Swarming Swarm algorithms Biological swarming
- Agent-based model in biology
- Bait ball
- Collective animal behavior
- Feeding frenzy
- Herd behavior
- Mixed-species foraging flock
- Mobbing behavior
- Pack hunter
- Patterns of self-organization in ants
- Sardine run
- Shoaling and schooling
- Sort sol
- Swarming behaviour
- Swarming (honey bee)
- Swarming motility
Animal migration Swarm robotics Related topics
Wikimedia Foundation. 2010.
Look at other dictionaries:
Collective animal behavior — Sort sol. Starling flock at sunset in Denmark Collective animal behavior describes the coordinated behavior of large groups of similar animals and the emergent properties of these groups. Facets of this topic include the costs and benefits of… … Wikipedia
Theoretical ecology — Mathematical models developed in theoretical ecology predict complex food webs are less stable than simple webs.:75–77:64 … Wikipedia
Crowd simulation — is the process of simulating the movement of a large number of objects or characters, now often appearing in 3D computer graphics for film. While simulating these crowds, observed human behavior interaction is taken into account, to replicate the … Wikipedia
Diel vertical migration — Diel vertical migration, also known as diurnal vertical migration, is a pattern of movement that some organisms living in the ocean and in lakes undertake each day. Usually organisms move up to the epipelagic zone at night and return to the… … Wikipedia
Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… … Wikipedia
Eusociality — Insect queen redirects here. For the comics characters, see Insect Queen. A swarming Meat Eater ant colony. Eusociality (Greek eu: good/real + social ) is a term used for the highest level of social organization in a hierarchical classification.… … Wikipedia
Collective intelligence — Types of collective intelligence Collective intelligence is a shared or group intelligence that emerges from the collaboration and competition of many individuals and appears in consensus decision making in bacteria, animals, humans and computer… … Wikipedia
Agent-based model — An agent based model (ABM) (also sometimes related to the term multi agent system or multi agent simulation) is a class of computational models for simulating the actions and interactions of autonomous agents (both individual or collective… … Wikipedia
Stigmergy — is a mechanism of indirect coordination between agents or actions. The principle is that the trace left in the environment by an action stimulates the performance of a next action, by the same or a different agent. In that way, subsequent actions … Wikipedia
Fish migration — Many species of salmon are anadromous and migrate long distances up rivers and streams to spawn. Many types of fish migrate on a regular basis, on time scales ranging from daily to annually or longer, and over distances ranging from a few metres… … Wikipedia