Flocking (behavior)

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 swarming 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 also generally be applied 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 birds, fish, bacteria, and insects.[1] 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 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.

Grus grus flocks
Two flocks of common cranes
The flock of starlings acting as a swarm. - geograph.org.uk - 124593
A swarm-like flock of starlings

Flocking rules

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

  1. Separation - avoid crowding neighbours (short range repulsion)
  2. Alignment - steer towards average heading of neighbours
  3. 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.

The basic model has been extended in several different ways since Reynolds proposed it. For instance, Delgado-Mata et al. [3] 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 [4] 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 [5] used attraction, alignment and avoidance and extended this with a number 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 real starlings); third, 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; 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[6] 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 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 no doubt 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.[7][8][9][10]

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 which fall into its environment.

Possible improvements:

  • bin-lattice 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.[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

Human shields greeted crossing border into Iraq
Flock-like behavior 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.
Crowd fleeing sounds of gunfire near Westgate

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.[13]

Flocking has also been considered as a means of controlling the behavior 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, 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.[16] It has also been used for visualizing information[17] and for optimization tasks.[18]

See also

References

  1. ^ O'Loan, OJ; Evans, MR (1999). "Alternating steady state in one-dimensional flocking". Journal of Physics A: Mathematical and General. IOP Publishing. 32 (8): L99. arXiv:cond-mat/9811336. Bibcode:1999JPhA...32L..99O. doi:10.1088/0305-4470/32/8/002.
  2. ^ Reynolds, Craig W. (1987). "Flocks, herds and schools: A distributed behavioral model.". ACM SIGGRAPH Computer Graphics. 21. pp. 25–34.
  3. ^ 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.
  4. ^ Hartman C, Benes B (2006). "Autonomous boids". Computer Animation and Virtual Worlds. 17 (3–4): 199–206. doi:10.1002/cav.123.
  5. ^ 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.
  6. ^ Feder, Toni (October 2007). "Statistical physics is for the birds". Physics Today. 60 (10): 28–30. doi:10.1063/1.2800090.
  7. ^ Hildenbrandt, H; Carere, C; Hemelrijk, CK (2010). "Self-organized aerial displays of thousands of starlings: a model". Behavioral Ecology. 21 (6): 1349–1359. doi:10.1093/beheco/arq149.
  8. ^ 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.
  9. ^ Project Starflag
  10. ^ Swarm behaviour model by University of Groningen
  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". 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". Manchester: University of Manchester Doctoral Thesis.
  16. ^ Ibanez J, Gomez-Skarmeta AF, Blat J (2003). "DJ-boids: emergent collective behavior 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.
  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.

Other sources

External links

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.

The name "boid" corresponds to a shortened version of "bird-oid object", which refers to a bird-like object. Incidentally, "boid" is also a New York Metropolitan dialect pronunciation for "bird".

As with most artificial life simulations, Boids is an example of emergent behavior; that is, the complexity of Boids arises from the interaction of individual agents (the boids, in this case) adhering to a set of simple rules. The rules applied in the simplest Boids world are as follows:

separation: steer to avoid crowding local flockmates

alignment: steer towards the average heading of local flockmates

cohesion: steer to move towards the average position (center of mass) of local flockmatesMore complex rules can be added, such as obstacle avoidance and goal seeking.

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.

The movement of Boids can be characterized as either chaotic (splitting groups and wild behaviour) or orderly. Unexpected behaviours, such as splitting flocks and reuniting after avoiding obstacles, can be considered emergent.

The boids framework is often used in computer graphics, providing realistic-looking representations of flocks of birds and other creatures, such as schools of fish or herds of animals. It was for instance used in the 1998 video game Half-Life for the flying bird-like creatures seen at the end of the game on Xen, named "boid" in the game files.

The Boids model can be used for direct control and stabilization of teams of simple Unmanned Ground Vehicles (UGV) or Micro Aerial Vehicles (MAV) in swarm robotics. For stabilization of heterogeneous UAV-UGV teams, the model was adapted for using onboard relative localization by Saska et al.At the time of proposal, Reynolds' approach represented a giant step forward compared to the traditional techniques used in computer animation for motion pictures. The first animation created with the model was Stanley and Stella in: Breaking the Ice (1987), followed by a feature film debut in Tim Burton's film Batman Returns (1992) with computer generated bat swarms and armies of penguins marching through the streets of Gotham City.The boids model 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.

Capricorn silvereye

The Capricorn silvereye (Zosterops lateralis chlorocephalus), also known as the Capricorn white-eye or green-headed white-eye, is a small greenish bird in the Zosteropidae or white-eye family. It is a subspecies of the silvereye that occurs on islands off the coast of Queensland in north-eastern Australia, and which is sometimes considered to be a full species.

Carolina parakeet

The Carolina parakeet (Conuropsis carolinensis) or Carolina conure is an extinct species of small green neotropical parrot with a bright yellow head, reddish orange face and pale beak native to the eastern, midwest and plains states of the United States. It was the only indigenous parrot within its range, as well as one of only two parrots native to the United States (the other being the thick-billed parrot). It was found from southern New York and Wisconsin to Kentucky, Tennessee and the Gulf of Mexico, from the Atlantic seaboard to as far west as eastern Colorado. It lived in old-growth forests along rivers and in swamps. It was called puzzi la née ("head of yellow") or pot pot chee by the Seminole and kelinky in Chickasaw. Though formerly prevalent within its range, the bird had become rare by the middle of the 19th century. The last confirmed sighting in the wild was of the ludovicianus subspecies in 1910. The last known specimen perished in captivity at the Cincinnati Zoo in 1918 and the species was declared extinct in 1939.

The earliest reference to these parrots was in 1583 in Florida reported by Sir George Peckham in A True Report of the Late Discoveries of the Newfound Lands of expeditions conducted by English explorer Sir Humphrey Gilbert who notes that explorers in North America "doe testifie that they have found in those countryes; ... parrots." They were first scientifically described in English naturalist Mark Catesby's two volume Natural History of Carolina, Florida and the Bahama Islands published in London in 1731 and 1743.

Carolina parakeets were probably poisonous—American naturalist and painter John J. Audubon noted that cats apparently died from eating them, and they are known to have eaten the toxic seeds of cockleburs.

Crowd

A crowd is a large group of people that are gathered or considered together. A crowd may be definable through a common purpose or set of emotions, such as at a political rally, a sports event, or during looting (this is known as a psychological crowd), or may simply be made up of many people going about their business in a busy area. The term "the crowd" may sometimes refer to the lower orders of people in general.

Fish School Search

Fish School Search (FSS), proposed by Bastos Filho and Lima Neto in 2007 is, in its basic version, an unimodal optimization algorithm inspired on the collective behavior of fish schools. The mechanisms of feeding and coordinated movement were used as inspiration to create the search operators. The core idea is to make the fishes “swim” toward the positive gradient in order to “eat” and “gain weight”. Collectively, the heavier fishes are more influent in the search process as a whole, what makes the barycenter of the fish school moves toward better places in the search space over the iterations.The FSS uses the following principles:

Simple computations in all individuals (i.e. fish)

Various means of storing information (i.e. weights of fish and school barycenter)

Local computations (i.e. swimming is composed of distinct components)

Low communications between neighboring individuals (i.e. fish are to think local but also be socially aware)

Minimum centralized control (mainly for self-controlling of the school radius)

Some distinct diversity mechanisms (this to avoid undesirable flocking behavior)

Scalability (in terms of complexity of the optimization/search tasks)

Autonomy (i.e. ability to self-control functioning)

Herding

Herding is the act of bringing individual animals together into a group (herd), maintaining the group, and moving the group from place to place—or any combination of those. Herding can refer either to the process of animals forming herds in the wild, or to human intervention forming herds for some purpose. While the layperson uses the term "herding" to describe this human intervention, most individuals involved in the process term it mustering, "working stock", or droving.

Some animals instinctively gather together as a herd. A group of animals fleeing a predator will demonstrate herd behavior for protection; while some predators, such as wolves and dogs have instinctive herding abilities derived from primitive hunting instincts. Instincts in herding dogs and trainability can be measured at noncompetitive herding tests. Dogs exhibiting basic herding instincts can be trained to aid in herding and to compete in herding and stock dog trials. Sperm whales have also been observed teaming up to herd prey in a coordinated feeding behavior.Herding is used in agriculture to manage domesticated animals. Herding can be performed by people or trained animals such as herding dogs that control the movement of livestock under the direction of a person. The people whose occupation it is to herd or control animals often have herd added to the name of the animal they are herding to describe their occupation (shepherd, goatherd, cowherd). A competitive sport has developed in some countries where the combined skill of man and herding dog is tested and judged in a "trial", such as a sheepdog trial. Animals such as sheep, camel, yak, and goats are mostly reared. They provide milk, meat and other products to the herders and their families.

History of computer animation

The history of computer animation began as early as the 1940s and 1950s, when people began to experiment with computer graphics - most notably by John Whitney. It was only by the early 1960s when digital computers had become widely established, that new avenues for innovative computer graphics blossomed. Initially, uses were mainly for scientific, engineering and other research purposes, but artistic experimentation began to make its appearance by the mid-1960s. By the mid-1970s, many such efforts were beginning to enter into public media. Much computer graphics at this time involved 2-dimensional imagery, though increasingly, as computer power improved, efforts to achieve 3-dimensional realism became the emphasis. By the late 1980s, photo-realistic 3D was beginning to appear in film movies, and by mid-1990s had developed to the point where 3D animation could be used for entire feature film production.

Okhlos

Okhlos is an action roguelike video game developed by Argentina-based independent video game developer Coffee Powered Machine and published by Devolver Digital. It was released on 18 August 2016.

Random International

Random International is a London-based art collective and collaborative studio, founded in 2005. The group shot to prominence with its interactive Rain Room art installation. Random International creates art installations that investigate notions of human consciousness, perception and instinct. Its work, which includes sculpture, performance and large-scale architectural installations, reflects the relationship between man and machine and centres on audience interaction. Two of its exhibition pieces have now become permanent installations, the first of which was the critically acclaimed and popular Rain Room, now permanently housed in Sharjah, United Arab Emirates (UAE).

The group was founded in 2005 by German artists Hannes Koch and Florian Ortkrass. Ortkrass graduated from the Royal College of Art in London in 2005, while Koch graduated in 2004. Its relentless experimentation with digital technologies and reflections of the human form has led it to collaborate with Harvard roboticists on creating 'point studies' that reduce representation of the human form in motion into 15 light points, as well as with architects to create large scale public displays that include covering a German train station with LED lights.

Rip-Off

Rip-Off is a vector shoot 'em up written by Tim Skelly and released in arcades by Cinematronics in 1980. It is the first shoot 'em up arcade game to feature cooperative gameplay and the first game to exhibit flocking behavior. Rip-Off was ported to the Vectrex home system in 1982.

The objective of Rip-Off is to prevent computer-controlled enemies from stealing eight canisters set in the center of the screen. One or two players control tank-like vehicles while game-controlled "pirate" tanks rush onto the field and attempt to drag the canisters off the edge of the screen. Enemies can be defeated by shooting or colliding with them. The game speed and difficulty increase with each successive wave until all the canisters have been taken ("ripped off").

Sheep

Domestic sheep (Ovis aries) are quadrupedal, ruminant mammals typically kept as livestock. Like most ruminants, sheep are members of the order Artiodactyla, the even-toed ungulates. Although the name sheep applies to many species in the genus Ovis, in everyday usage it almost always refers to Ovis aries. Numbering a little over one billion, domestic sheep are also the most numerous species of sheep. An adult female sheep is referred to as a ewe (), an intact male as a ram or occasionally a tup, a castrated male as a wether, and a younger sheep as a lamb.

Sheep are most likely descended from the wild mouflon of Europe and Asia. One of the earliest animals to be domesticated for agricultural purposes, sheep are raised for fleeces, meat (lamb, hogget or mutton) and milk. A sheep's wool is the most widely used animal fiber, and is usually harvested by shearing. Ovine meat is called lamb when from younger animals and mutton when from older ones in Commonwealth countries, and lamb in the United States (including from adults). Sheep continue to be important for wool and meat today, and are also occasionally raised for pelts, as dairy animals, or as model organisms for science.

Sheep husbandry is practised throughout the majority of the inhabited world, and has been fundamental to many civilizations. In the modern era, Australia, New Zealand, the southern and central South American nations, and the British Isles are most closely associated with sheep production.

Sheepraising has a large lexicon of unique terms which vary considerably by region and dialect. Use of the word sheep began in Middle English as a derivation of the Old English word scēap; it is both the singular and plural name for the animal. A group of sheep is called a flock, herd or mob. Many other specific terms for the various life stages of sheep exist, generally related to lambing, shearing, and age.

Being a key animal in the history of farming, sheep have a deeply entrenched place in human culture, and find representation in much modern language and symbology. As livestock, sheep are most often associated with pastoral, Arcadian imagery. Sheep figure in many mythologies—such as the Golden Fleece—and major religions, especially the Abrahamic traditions. In both ancient and modern religious ritual, sheep are used as sacrificial animals.

Swarm robotics

Swarm robotics is an approach to the coordination of multiple robots as a system which consist of large numbers of mostly simple physical robots. It is supposed that a desired collective behavior emerges from the interactions between the robots and interactions of robots with the environment. This approach emerged on the field of artificial swarm intelligence, as well as the biological studies of insects, ants and other fields in nature, where swarm behaviour occurs.

Symbolics

Symbolics refers to two companies: now-defunct computer manufacturer Symbolics, Inc., and a privately held company that acquired the assets of the former company and continues to sell and maintain the Open Genera Lisp system and the Macsyma computer algebra system.The symbolics.com domain was originally registered on March 15, 1985, making it the first .com-domain in the world. In August 2009, it was sold to napkin.com (formerly XF.com) Investments.

Biological swarming
Animal migration
Swarm algorithms
Collective motion
Swarm robotics
Related topics

Languages

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.