View source for Flocking

{{Short description|Swarming behaviour of birds when flying or foraging}}
{{for|the artistic technique|Flocking (texture)}}
[[Image:Grus grus flocks.jpg|thumb|Two flocks of [[common crane]]s]][[Image:The flock of starlings acting as a swarm. - geograph.org.uk - 124593.jpg|thumb|A swarm-like flock of [[starling]]s]]

'''Flocking''' is the behavior exhibited when a group of birds, called a [[Flock (birds)|flock]], are [[foraging]] or in flight. Sheep and goats also exhibit flocking behavior. Flocking by birds and mammals is similar to [[Shoaling and schooling|schooling]] in fish and these are often studied together.

Flocking is generally believed to arise from the need for cover and protection from predators in animal behavior.<ref>{{cite journal | last=Hamilton |first=W.D. |title=Geometry of the Selfish Herd | url=https://www.sciencedirect.com/science/article/abs/pii/0022519371901895 | journal=Journal of Theoretical Biology | volume=31 | issue=2 | year=1971 | pages=295–311 |doi=10.1016/0022-5193(71)90189-5|pmid=5104951 |bibcode=1971JThBi..31..295H | url-access=subscription }}</ref> This is an [[emergence|emergent]] behaviour governed by local rules that are followed by individuals and does not involve any central coordination.

== In nature ==

There are parallels with the [[Shoaling and schooling|shoaling]] behaviour of fish, the [[swarm]]ing behaviour of insects, and [[herd behaviour]] of land animals. During the winter months, [[starling]]s are known for aggregating into huge flocks of hundreds to thousands of individuals, [[Starling#Behaviour|murmurations]], which when they take flight altogether, render large displays of intriguing swirling patterns in the skies above observers.

=== Measurement ===
Measurements of bird flocking have been made<ref>{{ cite journal | last =Feder | first =Toni |date=October 2007 | title =Statistical physics is for the birds | journal = Physics Today| volume =60 | issue =10 | pages =28–30 | doi =10.1063/1.2800090 | doi-access =free | bibcode = 2007PhT....60j..28F }}</ref> 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.<ref>{{cite journal | last1 = Hildenbrandt | first1 = H | last2 = Carere | first2 = C | last3 = Hemelrijk | first3 = CK | year = 2010 | title = Self-organized aerial displays of thousands of starlings: a model | journal = Behavioral Ecology | volume = 21 | issue = 6| pages = 1349–1359 | doi = 10.1093/beheco/arq149 | doi-access = free | arxiv = 0908.2677 }}</ref><ref>{{cite journal | last1 = Hemelrijk | first1 = CK | last2 = Hildenbrandt | first2 = H | year = 2011 | title = Some causes of the variable shape of flocks of birds | journal = PLOS ONE | volume = 6 | issue = 8| article-number = e22479 | doi = 10.1371/journal.pone.0022479 | pmid=21829627 | pmc=3150374| bibcode = 2011PLoSO...622479H | doi-access = free }}</ref><ref>[http://www.rug.nl/sciencelinx/exhibits/swarming/index Project Starflag]</ref><ref>[http://www.rug.nl/fmns-research/beso/_people/hemelrijk Swarm behaviour model by University of Groningen]</ref>

== Algorithms ==

Various algorithms have been introduced to aid in the study of biological flocking. These algorithms have different origins, from computer graphics to physics, each offering a unique perspective on the real phenomena.

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  [[insect]]s.<ref>{{cite journal |last1= O'Loan |first1= OJ |last2= Evans |first2= MR |year= 1999|title= Alternating steady state in one-dimensional flocking |journal= Journal of Physics A: Mathematical and General |publisher= IOP Publishing |volume= 32 |issue= 8 |pages= L99 |doi= 10.1088/0305-4470/32/8/002|arxiv = cond-mat/9811336|bibcode= 1999JPhA...32L..99O |s2cid= 7642063 }}</ref>

=== Reynolds' Models ===
Flocking behaviour was simulated on a computer in 1987 by [[Craig Reynolds (computer graphics)|Craig Reynolds]] with the program [[Boids]].<ref>{{cite conference
|author= Reynolds, Craig W.
|title= Flocks, herds and schools: A distributed behavioural model.
|book-title= ACM SIGGRAPH Computer Graphics
|volume=21 |issue=4 |pages= 25–34
|year=1987
}}</ref> This program simulates simple agents (boids) that move according to a set of three basic rules: separation, alignment and cohesion. The result, akin to a [[Flock (birds)|flock]] of [[bird]]s, a [[Shoaling and schooling|school]] of [[fish]], or a [[swarm]] of [[insects]], was developed for motion picture visual effects.

==== Rules ====
[[File:Rule cohesion.gif|thumb|The "cohesion" behavior of the Boids flocking model]]

Reynolds' 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 ====

The basic model has been extended in several different ways since Reynolds proposed it. For instance, Delgado-Mata et al.<ref>{{Cite journal |display-authors=etal |vauthors=Delgado-Mata C, Ibanez J, Bee S |year=2007 |title=On the use of Virtual Animals with Artificial Fear in Virtual Environments |journal=New Generation Computing |volume=25 |issue=2 |pages=145–169 |doi=10.1007/s00354-007-0009-5 |s2cid=26078361}}</ref> 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<ref>{{Cite journal |vauthors=Hartman C, Benes B |year=2006 |title=Autonomous boids | journal=Computer Animation and Virtual Worlds |volume=17 |issue=3–4 |pages=199–206 |doi=10.1002/cav.123 |s2cid=15720643}}</ref> 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.

=== Vicsek Models ===
An early model from the domain of physics, the Vicsek model <ref>{{Citation 
 | last1=Vicsek, T. | last2=Czirok, A. | last3=Ben-Jacob, E. | last4=Cohen, Inon | last5=Shochet, O | year=1995 | title=Novel Type of Phase Transition in a System of Self-Driven Particles | journal=Physical Review Letters | volume=75 | issue=6 | pages=1226–1229 | doi=10.1103/PhysRevLett.75.1226 | arxiv=cond-mat/0611743 | bibcode=1995PhRvL..75.1226V }}</ref> gained attention in the study of flocking as a form active matter, a system where energy is continually added (unlike thermodynamic models).

Applied to collective motion and swarming, Vicsek models demonstrate that a simpler set of rules with just fixed speed, self-propelled particles, and neighbor alignment, are able to achieve sub-group flocking and milling (vortex structures). These models are attractive in physics due to their simplicity and universality.

Such models however, do not exhibit speed changes due to climbing and diving in flight, or complex phenomena such as orientation waves due to perceptual vision.

=== Aerodynamic Models ===

Hemelrijk and Hildenbrandt<ref>{{Cite journal |last1=Hemelrijk, C. K. |last2=Hildenbrandt, H. |year=2011 |title=Some Causes of the Variable Shape of Flocks of Birds |journal=PLOS ONE |volume=6 |issue=8 |article-number=e22479 |bibcode=2011PLoSO...622479H |doi=10.1371/journal.pone.0022479 |pmc=3150374 |pmid=21829627 |doi-access=free}}</ref> 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.

=== Orientation Models ===

Hoetzlein<ref>{{Cite journal |last=Hoetzlein, R. C. | year=2024 | title=Flock2: A model for orientation-based social flocking | journal=Journal of Theoretical Biology | volume=593 | article-number=111880 | doi=10.1016/j.jtbi.2024.111880 | pmid=38972569 | doi-access=free| arxiv=2404.17804 | bibcode=2024JTBio.59311880H }}</ref> introduced the orientation-model in 2024 which separates the perceptual aspects of bird flight from the underlying aerodynamic model, linking these two control systems only by a heading target similar to real flight control. The perceptual model of each bird is orientation-based, mapped to a sphere, which more closely matches the biological vision system. The output of perception is a target heading angle (not a vector), which is used to control an aerodynamic model much like a flight simulator. Energy and frequency analysis in this work bridge the study of real bird kinetics with simulation models. This model demonstrates emergent, spontaneous orientation waves for the first time, a key feature in flocking murmurations.

== Complexity ==
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.

A basic implementation of a flocking algorithm has complexity <math>O(n^2)</math> – each bird could potentially interact and respond to every other bird. To limit complexity, it is assumed that birds only interact with a limited number of neighbors spatially in 2D or 3D. This was proven empirically in 2008 by Ballerini et al.,<ref>{{Citation | last1=Ballerini M. | last2 = Cabibbo N. | last3=Candelier R. | last4=Cavagna A. | last5=Cisbani E. | last6=Giardina I. | last7=Lecomte V. | last8=Orlandi A. | last9=Parisi G. | last10=Procaccini A. | last11=Viale M. | last12= Zdravkovic V. | title=Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study | publisher=Proc. Natl. Acad. Sci. | volume=105 | issue=4 |year=2008 | pages=1232–1237 }}</ref> where it was shown that Starlings typically interact with at most seven topological neighbors.

Improvements: 
* Spatial Subdivision.<ref>{{Citation | last=Hoetzlein, R. | title=Fast Fixed-Radius Nearest Neighbors: Interactive Million-Particles Fluids | year=2014 | publisher=GPU Technology Conference}}</ref> The entire area/volume of the flock is divided uniformly. Each bin stores which birds it contains. Each time a bird moves from one bin to another, bin contents are updated. 
** Complexity: <math>O(n k)</math>, k is number of surrounding bins to consider.

Lee Spector, Jon Klein, Chris Perry and [[Mark Feinstein]] studied the emergence of collective behaviour in evolutionary computation systems.<ref>{{cite web | url=http://hampshire.edu/lspector/gecco2003-collective.html | author=Spector, L. |author2=Klein, J. |author3=Perry, C. |author4= Feinstein, M.  | year=2003 | title=Emergence of Collective Behavior in Evolving Populations of Flying Agents | work=Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003) | publisher=Springer-Verlag | access-date=2007-05-01}}</ref>

[[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.<ref>Bernard Chazelle, ''The Convergence of Bird Flocking'', J. ACM 61 (2014)</ref> 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==
 {{multiple image
 | direction = vertical
 | width = 220
 | footer = 
 | image1 = Human shields greeted crossing border into Iraq.jpg
 | alt1 = 
 | caption1 = 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.
 | image2 = Crowd fleeing sounds of gunfire near Westgate.jpg
 | alt2 =  | caption2 = 
 }}
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.<ref>"http://psychcentral.com/news/2008/02/15/herd-mentality-explained/1922.html {{Webarchive|url=https://web.archive.org/web/20141129010932/http://psychcentral.com/news/2008/02/15/herd-mentality-explained/1922.html |date=2014-11-29 }}". Retrieved on October 31st 2008.</ref>

Flocking has also been considered as a means of controlling the behaviour of Unmanned Air Vehicles (UAVs).<ref>Senanayake, M., Senthooran, I., Barca, J. C., Chung, H., Kamruzzaman, J., & Murshed, M. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.714.6323&rep=rep1&type=pdf "Search and tracking algorithms for swarms of robots: A survey."]</ref>

Flocking is a common technology in [[screensaver]]s, and has found its use in animation. Flocking has been used in many films<ref>{{cite thesis | last = Gabbai | first = J. M. E. | author-link = Jonathan Gabbai | title = Complexity and the Aerospace Industry: Understanding Emergence by Relating Structure to Performance using Multi-Agent Systems | year = 2005 | publisher = University of Manchester Doctoral Thesis | place = Manchester | url = http://www.gabbai.com/academic/complexity-and-the-aerospace-industry-understanding-emergence-by-relating-structure-to-performance-using-multi-agent-systems/ | access-date = 2007-02-21 | archive-date = 2014-12-19 | archive-url = https://web.archive.org/web/20141219110658/http://gabbai.com/academic/complexity-and-the-aerospace-industry-understanding-emergence-by-relating-structure-to-performance-using-multi-agent-systems }}</ref> to generate crowds which move more realistically. 
[[Tim Burton]]'s ''[[Batman Returns]]'' (1992)  featured flocking bats.{{synthesis inline|date=March 2018}}

Flocking behaviour has been used for other interesting applications. It has been applied to automatically program Internet multi-channel radio stations.<ref>{{cite conference
| title         = DJ-boids: emergent collective behaviour as multichannel radio station programming
|vauthors = Ibanez J, Gomez-Skarmeta AF, Blat J | year          = 2003
| book-title     = Proceedings of the 8th international conference on Intelligent User Interfaces
| pages         = 248–250
| doi           = 10.1145/604045.604089
}}</ref>
It has also been used for visualizing information<ref>{{cite conference
| title         = Time-Varying Data Visualization Using Information Flocking Boids
| author        = Moere A V
| year          = 2004
| book-title     = Proceedings of the IEEE Symposium on Information Visualization
| pages         = 97–104
| doi           = 10.1109/INFVIS.2004.65
| url= http://vis.computer.org/vis2004/DVD/infovis/papers/moere.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://vis.computer.org/vis2004/DVD/infovis/papers/moere.pdf |archive-date=2022-10-09 |url-status=live
}}</ref>
and for optimization tasks.<ref>{{cite journal
|vauthors=Cui Z, Shi Z |title= Boid particle swarm optimisation 
|journal= International Journal of Innovative Computing and Applications
|volume=2 |issue=2 |pages= 77–85
|year=2009
|article-number= 31778 
|doi= 10.1504/IJICA.2009.031778}}</ref>

==See also==
*[[Crowd]]
*[[Peloton]] (road bicycle racing)

==References==
{{Reflist}}

==Sources==
* {{cite book |last1=Bouffanais |first1=Roland |title=Design and Control of Swarm Dynamics |date=2016 |publisher=Springer Singapore |isbn=978-981-287-750-5 |url=https://www.springer.com/gp/book/9789812877505 |doi=10.1007/978-981-287-751-2|series=SpringerBriefs in Complexity }}
* {{ cite journal | last =Cucker | first =Felipe |author2=Steve Smale |author-link2=Stephen Smale  | year =2007 | title =The Mathematics of Emergence | journal = Japanese Journal of Mathematics | volume = 2| pages = 197–227| url =http://ttic.uchicago.edu/~smale/papers/math-of-emergence.pdf | access-date = 2008-06-09 | doi =10.1007/s11537-007-0647-x | s2cid =2637067 }}
* {{ cite journal | last =Shen | first =Jackie (Jianhong) | year =2008 | title =Cucker–Smale Flocking under Hierarchical Leadership | journal =SIAM J. Appl. Math. | volume =68 | issue =3 | pages = 694–719| url =http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJMAP000068000003000694000001&idtype=cvips&gifs=yes | access-date = 2008-06-09 | doi =10.1137/060673254 | arxiv =q-bio/0610048 | s2cid =14655317 }}
* {{ cite journal
|last = Fine|first=B.T.|author2=D.A. Shell|title=Unifying microscopic flocking motion models for virtual, robotic, and biological flock members.|journal=Auton. Robots|volume=35|issue=2–3|pages=195–219|year=2013|doi=10.1007/s10514-013-9338-z|s2cid=14091388}}
* {{ cite journal
|last =Vásárhelyi |first =G.|author2=C. Virágh|author3=G. Somorjai|author4=T. Nepusz|author5=A.E. Eiben|author6=T. Vicsek|year =2018 | title =Optimized flocking of autonomous drones in confined environments | journal=Science Robotics |volume =3|issue =20|article-number =eaat3536| publication-date= 18 July 2018|doi =10.1126/scirobotics.aat3536|pmid =33141727|doi-access =free|hdl =1871.1/87dd0889-cb66-4699-a27b-fc34f75e9b6d|hdl-access =free}}

==External links==
{{Commons category|Swarming}}
*[http://www.red3d.com/cwr/boids/ Craig Reynolds' Boids page]
*[http://lrss.fri.uni-lj.si/people/ilbajec/publications.htm Iztok Lebar Bajec's fuzzy logic based flocking publications]
*[https://www.bbc.com/news/av/uk-england-leeds-55221885 Murmurations of starlings (BBC videos)]
*[https://www.bbc.com/news/av/uk-england-norfolk-55870828 Drone flight captures Norfolk starlings murmuration (BBC videos)]
{{collective animal behaviour}}
{{Authority control}}

{{DEFAULTSORT:Flocking (Behaviour)}}
[[Category:Bird flight]]
[[Category:Group processes]]