Jump to content

Flocking

From Wikipedia, the free encyclopedia
For the artistic technique, see Flocking (texture).
Two flocks of common cranes
A swarm-like flock of starlings

Flocking is the behavior exhibited when a group of birds, called a flock, are foraging or in flight. Sheep and goats also exhibit flocking behavior.

Computer simulations and mathematical models that have been developed to emulate the flocking behaviours of birds can also generally be applied to the "flocking" behaviour of other species. As a result, the term "flocking" is sometimes applied, in computer science, to species other than birds, to mean collective motion by a group of self-propelled entities, a collective animal behaviour exhibited by many living beings such as fish, bacteria, and insects.[1]

Flocking is considered an emergent behaviour arising from simple rules that are followed by individuals and does not involve any central coordination.

In nature

[edit]

There are parallels with the shoaling behaviour of fish, the swarming behaviour of insects, and herd behaviour of land animals. During the winter months, starlings are known for aggregating into huge flocks of hundreds to thousands of individuals, murmurations, which when they take flight altogether, render large displays of intriguing swirling patterns in the skies above observers.

Flocking behaviour was simulated on a computer in 1987 by Craig Reynolds with his simulation program, Boids.[2] This program simulates simple agents (boids) that are allowed to move according to a set of basic rules. The result is akin to a flock of birds, a school of fish, or a swarm of insects.

Measurement

[edit]

Measurements of bird flocking have been made[3] using high-speed cameras, and a computer analysis has been made to test the simple rules of flocking mentioned below. It is found that they generally hold true in the case of bird flocking, but the long range attraction rule (cohesion) applies to the nearest 5–10 neighbors of the flocking bird and is independent of the distance of these neighbors from the bird. In addition, there is an anisotropy with regard to this cohesive tendency, with more cohesion being exhibited towards neighbors to the sides of the bird, rather than in front or behind. This is likely due to the field of vision of the flying bird being directed to the sides rather than directly forward or backward.

Another recent study is based on an analysis of high speed camera footage of flocks above Rome, and uses a computer model assuming minimal behavioural rules.[4][5][6][7]

Algorithm

[edit]

Rules

[edit]

Basic models of flocking behaviour are controlled by three simple rules:

Separation
Avoid crowding neighbours (short range repulsion)
Alignment
Steer towards average heading of neighbours
Cohesion
Steer towards average position of neighbours (long range attraction)

With these three simple rules, the flock moves in an extremely realistic way, creating complex motion and interaction that would be extremely hard to create otherwise.

Rule variants

[edit]

The basic model has been extended in several different ways since Reynolds proposed it. For instance, Delgado-Mata et al.[8] extended the basic model to incorporate the effects of fear. Olfaction was used to transmit emotion between animals, through pheromones modelled as particles in a free expansion gas.

Hartman and Benes[9] introduced a complementary force to the alignment that they call the change of leadership. This steer defines the chance of the bird to become a leader and try to escape.

Hemelrijk and Hildenbrandt[10] used attraction, alignment, and avoidance, and extended this with a number of traits of real starlings:

  • birds fly according to fixed wing aerodynamics, while rolling when turning (thus losing lift);
  • they coordinate with a limited number of interaction neighbours of 7 (like real starlings);
  • they try to stay above a sleeping site (like starlings do at dawn), and when they happen to move outwards from the sleeping site, they return to it by turning; and
  • they move at relative fixed speed.

The authors showed that the specifics of flying behaviour as well as large flock size and low number of interaction partners were essential to the creation of the variable shape of flocks of starlings.

Complexity

[edit]

In flocking simulations, there is no central control; each bird behaves autonomously. In other words, each bird has to decide for itself which flocks to consider as its environment. Usually environment is defined as a circle (2D) or sphere (3D) with a certain radius (representing reach).[citation needed]

A basic implementation of a flocking algorithm has complexity – each bird searches through all other birds to find those which fall into its environment.[improper synthesis?]

Possible improvements:[citation needed]

  • bin-lattice spatial subdivision. The entire area the flock can move in is divided into multiple bins. Each bin stores which birds it contains. Each time a bird moves from one bin to another, lattice has to be updated.
    • Example: 2D(3D) grid in a 2D(3D) flocking simulation.
    • Complexity: , k is number of surrounding bins to consider; just when bird's bin is found in

Lee Spector, Jon Klein, Chris Perry and Mark Feinstein studied the emergence of collective behaviour in evolutionary computation systems.[11]

Bernard Chazelle proved that under the assumption that each bird adjusts its velocity and position to the other birds within a fixed radius, the time it takes to converge to a steady state is an iterated exponential of height logarithmic in the number of birds. This means that if the number of birds is large enough, the convergence time will be so great that it might as well be infinite.[12] This result applies only to convergence to a steady state. For example, arrows fired into the air at the edge of a flock will cause the whole flock to react more rapidly than can be explained by interactions with neighbors, which are slowed down by the time delay in the bird's central nervous systems—bird-to-bird-to-bird.

Applications

[edit]
Flock-like behaviour in humans may occur when people are drawn to a common focal point or when repelled, as below: a crowd fleeing from the sound of gunfire.

In Cologne, Germany, two biologists from the University of Leeds demonstrated a flock-like behaviour in humans. The group of people exhibited a very similar behavioural pattern to that of a flock, where if 5% of the flock would change direction the others would follow suit. When one person was designated as a predator and everyone else was to avoid him, the flock behaved very much like a school of fish.[13]

Flocking has also been considered as a means of controlling the behaviour of Unmanned Air Vehicles (UAVs).[14]

Flocking is a common technology in screensavers, and has found its use in animation. Flocking has been used in many films[15] to generate crowds which move more realistically. Tim Burton's Batman Returns (1992) featured flocking bats.[improper synthesis?]

Flocking behaviour has been used for other interesting applications. It has been applied to automatically program Internet multi-channel radio stations.[16] It has also been used for visualizing information[17] and for optimization tasks.[18]

See also

[edit]

References

[edit]
  1. ^ O'Loan, OJ; Evans, MR (1999). "Alternating steady state in one-dimensional flocking". Journal of Physics A: Mathematical and General. 32 (8). IOP Publishing: L99. arXiv:cond-mat/9811336. Bibcode:1999JPhA...32L..99O. doi:10.1088/0305-4470/32/8/002. S2CID 7642063.
  2. ^ Reynolds, Craig W. (1987). "Flocks, herds and schools: A distributed behavioural model.". ACM SIGGRAPH Computer Graphics. Vol. 21. pp. 25–34.
  3. ^ Feder, Toni (October 2007). "Statistical physics is for the birds". Physics Today. 60 (10): 28–30. Bibcode:2007PhT....60j..28F. doi:10.1063/1.2800090.
  4. ^ Hildenbrandt, H; Carere, C; Hemelrijk, CK (2010). "Self-organized aerial displays of thousands of starlings: a model". Behavioral Ecology. 21 (6): 1349–1359. arXiv:0908.2677. doi:10.1093/beheco/arq149.
  5. ^ Hemelrijk, CK; Hildenbrandt, H (2011). "Some causes of the variable shape of flocks of birds". PLOS ONE. 6 (8): e22479. Bibcode:2011PLoSO...622479H. doi:10.1371/journal.pone.0022479. PMC 3150374. PMID 21829627.
  6. ^ Project Starflag
  7. ^ Swarm behaviour model by University of Groningen
  8. ^ Delgado-Mata C, Ibanez J, Bee S, et al. (2007). "On the use of Virtual Animals with Artificial Fear in Virtual Environments". New Generation Computing. 25 (2): 145–169. doi:10.1007/s00354-007-0009-5. S2CID 26078361.
  9. ^ Hartman C, Benes B (2006). "Autonomous boids". Computer Animation and Virtual Worlds. 17 (3–4): 199–206. doi:10.1002/cav.123. S2CID 15720643.
  10. ^ Hemelrijk, C. K.; Hildenbrandt, H. (2011). "Some Causes of the Variable Shape of Flocks of Birds". PLOS ONE. 6 (8): e22479. Bibcode:2011PLoSO...622479H. doi:10.1371/journal.pone.0022479. PMC 3150374. PMID 21829627.
  11. ^ Spector, L.; Klein, J.; Perry, C.; Feinstein, M. (2003). "Emergence of Collective Behavior in Evolving Populations of Flying Agents". Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003). Springer-Verlag. Retrieved 2007-05-01.
  12. ^ Bernard Chazelle, The Convergence of Bird Flocking, J. ACM 61 (2014)
  13. ^ "http://psychcentral.com/news/2008/02/15/herd-mentality-explained/1922.html Archived 2014-11-29 at the Wayback Machine". Retrieved on October 31st 2008.
  14. ^ Senanayake, M., Senthooran, I., Barca, J. C., Chung, H., Kamruzzaman, J., & Murshed, M. "Search and tracking algorithms for swarms of robots: A survey."
  15. ^ Gabbai, J. M. E. (2005). Complexity and the Aerospace Industry: Understanding Emergence by Relating Structure to Performance using Multi-Agent Systems (Thesis). Manchester: University of Manchester Doctoral Thesis. Archived from the original on 2014-12-19. Retrieved 2007-02-21.
  16. ^ Ibanez J, Gomez-Skarmeta AF, Blat J (2003). "DJ-boids: emergent collective behaviour as multichannel radio station programming". Proceedings of the 8th international conference on Intelligent User Interfaces. pp. 248–250. doi:10.1145/604045.604089.
  17. ^ Moere A V (2004). "Time-Varying Data Visualization Using Information Flocking Boids" (PDF). Proceedings of the IEEE Symposium on Information Visualization. pp. 97–104. doi:10.1109/INFVIS.2004.65. Archived (PDF) from the original on 2022-10-09.
  18. ^ Cui Z, Shi Z (2009). "Boid particle swarm optimisation". International Journal of Innovative Computing and Applications. 2 (2): 77–85. doi:10.1504/IJICA.2009.031778.

Sources

[edit]
[edit]
Wikimedia Commons has media related to Swarming.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Flocking&oldid=1224687421"