Flocking (behavior)
Encyclopedia
Flocking behavior is the behavior exhibited when a group of birds, called a flock
, are foraging
or in flight. There are parallels with the shoaling
behavior of fish, the swarm
ing behavior of insects, and herd behavior
of land animals.
Computer simulations and mathematical models which have been developed to emulate the flocking behaviors of birds can generally be applied also to the "flocking" behavior of other species. As a result, the term "flocking" is sometimes applied, in computer science, to species other than birds.
This article is about the modelling of flocking behavior. From the perspective of the mathematical modeller, "flocking" is the collective motion of a large number of self-propelled entities and is a collective animal behavior
exhibited by many living beings such as bird
s, fish
, bacteria
, and insect
s. It is considered an emergent
behavior arising from simple rules that are followed by individuals and does not involve any central coordination.
Flocking behavior was first simulated on a computer in 1986 by Craig Reynolds
with his simulation program, Boids
. 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 bird
s, a school
of fish
, or a swarm
of insects.
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.
The basic model has been extended in several different ways since Reynolds proposed it. For instance, Delgado-Mata et al.
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
introduced a complementary force to the alignment that they call the change of leadership. This steer defines the chance of the boid to become a leader and try to escape.
Hemerlijk and Hildenbrandt
used attraction, alignment and avoidance and extended this with a numbet of traits of real starlings: first, birds fly according to fixed wing aerodynamics, while rolling when turning (thus losing lift), second they coordinate with a limited number of interaction neighbours of 7 (like in real starlings), third, they try to stay above a sleeping site (like starlings do at dawn) and when they happen to move outwards the sleeping site, they return to it by turning, fourth, they move at relative fixed speed. The authors showed that the specifics of flying behaviour as well as large flocksize and low number of interaction partners were essential to the creation of the variable shape of flocks of starlings.
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 no doubt due to the field of vision of the flying bird being directed to the sides rather than directly forward or backward.
A basic implementation of a flocking algorithm has complexity
- each bird searches through all other birds to find those who falls into his environment.
Possible improvements:
Lee Spector, Jon Klein, Chris Perry and Mark Feinstein studied the emergence of collective behavior in evolutionary computation systems.
Flocking has also been considered as a means of controlling the behavior of Unmanned Air Vehicles (UAVs).
Flocking is a common technology in screensaver
s, and has found its use in animation. Flocking has been used in many films to generate crowds which move more realistically. Tim Burton
's Batman Returns
(1992) featured flocking bats, and Disney
's The Lion King
(1994) included a wildebeest
stampede
.
Flocking behaviour has been used for other interesting applications. It has been applied to automatically program Internet multi-channel radio stations
. It has also been used for visualizing information
and for optimization tasks
.
Flock (birds)
A flock is a group of birds conducting flocking behavior in flight, or while foraging. The term is akin to the herd amongst mammals. The benefits of aggregating in flocks are varied and flocks will form explicitly for specific purposes...
, are foraging
Foraging
- Definitions and significance of foraging behavior :Foraging is the act of searching for and exploiting food resources. It affects an animal's fitness because it plays an important role in an animal's ability to survive and reproduce...
or in flight. There are parallels with the shoaling
Shoaling and schooling
In biology, any group of fish that stay together for social reasons are said to be shoaling , and if, in addition, the group is swimming in the same direction in a coordinated manner, they are said to be schooling . In common usage, the terms are sometimes used rather loosely...
behavior of fish, the swarm
Swarm
Swarm behaviour, or swarming, is a collective behaviour exhibited by animals of similar size which aggregate together, perhaps milling about the same spot or perhaps moving en masse or migrating in some direction. As a term, swarming is applied particularly to insects, but can also be applied to...
ing behavior of insects, and herd behavior
Herd behavior
Herd behavior describes how individuals in a group can act together without planned direction. The term pertains to the behavior of animals in herds, flocks and schools, and to human conduct during activities such as stock market bubbles and crashes, street demonstrations, sporting events,...
of land animals.
Computer simulations and mathematical models which have been developed to emulate the flocking behaviors of birds can generally be applied also to the "flocking" behavior of other species. As a result, the term "flocking" is sometimes applied, in computer science, to species other than birds.
This article is about the modelling of flocking behavior. From the perspective of the mathematical modeller, "flocking" is the collective motion of a large number of self-propelled entities and is a collective animal behavior
Collective animal behavior
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 group membership, the transfer of information across the group, the group decision-making process, and...
exhibited by many living beings such as bird
Flock (birds)
A flock is a group of birds conducting flocking behavior in flight, or while foraging. The term is akin to the herd amongst mammals. The benefits of aggregating in flocks are varied and flocks will form explicitly for specific purposes...
s, fish
Fish
Fish are a paraphyletic group of organisms that consist of all gill-bearing aquatic vertebrate animals that lack limbs with digits. Included in this definition are the living hagfish, lampreys, and cartilaginous and bony fish, as well as various extinct related groups...
, bacteria
Bacteria
Bacteria are a large domain of prokaryotic microorganisms. Typically a few micrometres in length, bacteria have a wide range of shapes, ranging from spheres to rods and spirals...
, and insect
Insect
Insects are a class of living creatures within the arthropods that have a chitinous exoskeleton, a three-part body , three pairs of jointed legs, compound eyes, and two antennae...
s. It is considered an emergent
Emergence
In philosophy, systems theory, science, and art, emergence is the way complex systems and patterns arise out of a multiplicity of relatively simple interactions. Emergence is central to the theories of integrative levels and of complex systems....
behavior arising from simple rules that are followed by individuals and does not involve any central coordination.
Flocking behavior was first simulated on a computer in 1986 by Craig 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...
with his simulation program, Boids
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...
. 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
Flock (birds)
A flock is a group of birds conducting flocking behavior in flight, or while foraging. The term is akin to the herd amongst mammals. The benefits of aggregating in flocks are varied and flocks will form explicitly for specific purposes...
of bird
Bird
Birds are feathered, winged, bipedal, endothermic , egg-laying, vertebrate animals. Around 10,000 living species and 188 families makes them the most speciose class of tetrapod vertebrates. They inhabit ecosystems across the globe, from the Arctic to the Antarctic. Extant birds range in size from...
s, a school
Shoaling and schooling
In biology, any group of fish that stay together for social reasons are said to be shoaling , and if, in addition, the group is swimming in the same direction in a coordinated manner, they are said to be schooling . In common usage, the terms are sometimes used rather loosely...
of fish
Fish
Fish are a paraphyletic group of organisms that consist of all gill-bearing aquatic vertebrate animals that lack limbs with digits. Included in this definition are the living hagfish, lampreys, and cartilaginous and bony fish, as well as various extinct related groups...
, or a swarm
Swarm
Swarm behaviour, or swarming, is a collective behaviour exhibited by animals of similar size which aggregate together, perhaps milling about the same spot or perhaps moving en masse or migrating in some direction. As a term, swarming is applied particularly to insects, but can also be applied to...
of insects.
Flocking rules
Basic models of flocking behavior are controlled by three simple rules:- Separation - avoid crowding neighbors (short range repulsion)
- Alignment - steer towards average heading of neighbors
- Cohesion - steer towards average position of neighbors (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.
The basic model has been extended in several different ways since Reynolds proposed it. For instance, Delgado-Mata et al.
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
introduced a complementary force to the alignment that they call the change of leadership. This steer defines the chance of the boid to become a leader and try to escape.
Hemerlijk and Hildenbrandt
used attraction, alignment and avoidance and extended this with a numbet of traits of real starlings: first, birds fly according to fixed wing aerodynamics, while rolling when turning (thus losing lift), second they coordinate with a limited number of interaction neighbours of 7 (like in real starlings), third, they try to stay above a sleeping site (like starlings do at dawn) and when they happen to move outwards the sleeping site, they return to it by turning, fourth, they move at relative fixed speed. The authors showed that the specifics of flying behaviour as well as large flocksize and low number of interaction partners were essential to the creation of the variable shape of flocks of starlings.
Measurement
Measurements of bird flocking have been made using high-speed cameras, and a computer analysis has been made to test the simple rules of flocking mentioned above. 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 anisotropyAnisotropy
Anisotropy is the property of being directionally dependent, as opposed to isotropy, which implies identical properties in all directions. It can be defined as a difference, when measured along different axes, in a material's physical or mechanical properties An example of anisotropy is the light...
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 no doubt due to the field of vision of the flying bird being directed to the sides rather than directly forward or backward.
Algorithmic 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. Usually environment is defined as a circle (2D) or sphere (3D) with a certain radius (representing reach).A basic implementation of a flocking algorithm has complexity
- each bird searches through all other birds to find those who falls into his environment.Possible improvements:
- bin-latticeSquare latticeIn mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice. It is one of the five types of two-dimensional lattices as classified by their symmetry groups; its symmetry group is known symbolically as p4m.Two...
spatial subdivision. Entire area the flock can move in is divided into a large number of 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 behavior in evolutionary computation systems.
Applications
In Cologne, Germany, two biologists from the University of Leeds demonstrated a flock like behavior in humans. The group of people exhibited a very similar behavioral 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.Flocking has also been considered as a means of controlling the behavior of Unmanned Air Vehicles (UAVs).
Flocking is a common technology in screensaver
Screensaver
A screensaver is a type of computer program initially designed to prevent phosphor burn-in on CRT and plasma computer monitors by blanking the screen or filling it with moving images or patterns when the computer is not in use...
s, and has found its use in animation. Flocking has been used in many films to generate crowds which move more realistically. Tim Burton
Tim Burton
Timothy William "Tim" Burton is an American film director, film producer, writer and artist. He is famous for dark, quirky-themed movies such as Beetlejuice, Edward Scissorhands, The Nightmare Before Christmas, Ed Wood, Sleepy Hollow, Corpse Bride and Sweeney Todd: The Demon Barber of Fleet...
's Batman Returns
Batman Returns
Batman Returns is a 1992 American superhero film directed by Tim Burton. Based on the DC Comics character Batman, it is the sequel to Burton's Batman , and features Michael Keaton reprising the title role, with Danny DeVito as the Penguin and Michelle Pfeiffer as Catwoman.Burton originally did not...
(1992) featured flocking bats, and Disney
Walt Disney Pictures
Walt Disney Pictures is an American film studio owned by The Walt Disney Company. Walt Disney Pictures and Television, a subsidiary of the Walt Disney Studios and the main production company for live-action feature films within the Walt Disney Motion Pictures Group, based at the Walt Disney...
's The Lion King
The Lion King
The Lion King is a 1994 American animated film produced by Walt Disney Feature Animation and released by Walt Disney Pictures. It is the 32nd feature in the Walt Disney Animated Classics series...
(1994) included a wildebeest
Wildebeest
The wildebeest , also called the gnu is an antelope of the genus Connochaetes. It is a hooved mammal...
stampede
Stampede
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....
.
Flocking behaviour has been used for other interesting applications. It has been applied to automatically program Internet multi-channel radio stations
. It has also been used for visualizing information
and for optimization tasks
.
External links
- Craig Reynolds' Boids page
- Iztok Lebar Bajec's fuzzy logic based flocking publications
- page on flocking maintained by T. Vicsek
- Flocking Simulator - A flocking behavior simulator in Java. Run online or free download. Includes multiple flocks, predators, obstacles and food.
- Another Flocking Simulator - A simple flocking applet which lets you control a number of parameters to create flocks that behave like birds, insects, bacteria, etc.
- NetLogo, a free software for multi-agent modeling, simulation, and the like, including a flocking simulation.
- VisualBots - Freeware multi-agent simulator in Microsoft Excel - Visual Basic syntax
- 3D Java Boids demonstrating bird flocking (Paul Richmond)