Boids

Last updated

A Boids example created in OpenGL

Boids is an artificial life program, developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds, and related group motion. His paper on this topic was published in 1987 in the proceedings of the ACM SIGGRAPH conference. [1] The name "boid" corresponds to a shortened version of "bird-oid object", which refers to a bird-like object. [2] Reynolds' boid model is one example of a larger general concept, for which many other variations have been developed since. The closely related work of Ichiro Aoki is noteworthy because it was published in 1982 — five years before Reynolds' boids paper. [3]

Contents

Rules applied in simple Boids
Rule separation.gif
Separation
Rule alignment.gif
Alignment
Rule cohesion.gif
Cohesion

Model details

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:

More 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. [4] 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 [5] 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) [6] or micro aerial vehicles (MAV) [7] in swarm robotics. For stabilization of heterogeneous UAV-UGV teams, the model was adapted for using onboard relative localization by Saska et al. [8]

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

The boids model has been used for other interesting applications. It has been applied to automatically program Internet multi-channel radio stations. [10] It has also been used for visualizing information [11] and for optimization tasks. [12]

Biologist Richard Dawkins references the Boids model in his 2009 book The Greatest Show on Earth: The Evidence for Evolution . [13]

See also

Related Research Articles

<span class="mw-page-title-main">Flocking</span> Swarming behaviour of birds when flying or foraging

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.

<span class="mw-page-title-main">Swarm behaviour</span> Collective behaviour of a large number of (usually) self-propelled entities of similar size

Swarm behaviour, or swarming, is a collective behaviour exhibited by entities, particularly animals, of similar size which aggregate together, perhaps milling about the same spot or perhaps moving en masse or migrating in some direction. It is a highly interdisciplinary topic.

<span class="mw-page-title-main">Particle system</span> Technique in game physics, motion graphics and computer graphics

A particle system is a technique in game physics, motion graphics, and computer graphics that uses many minute sprites, 3D models, or other graphic objects to simulate certain kinds of "fuzzy" phenomena, which are otherwise very hard to reproduce with conventional rendering techniques – usually highly chaotic systems, natural phenomena, or processes caused by chemical reactions.

<span class="mw-page-title-main">Micro air vehicle</span> Class of very small unmanned aerial vehicle

A micro air vehicle (MAV), or micro aerial vehicle, is a class of man-portable miniature UAVs whose size enables them to be used in low altitude, close-in support operations. Modern MAVs can be as small as 5 centimeters. Development is driven by commercial, research, government, and military purposes; with insect-sized aircraft reportedly expected in the future. The small craft allows remote observation of hazardous environments inaccessible to ground vehicles. MAVs have been built for hobby purposes such as aerial robotics contests and aerial photography.

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 (1982) as a scene programmer, and on Batman Returns (1992) as part of the video image crew. Reynolds won the 1998 Academy Scientific and Technical Award in recognition of "his pioneering contributions to the development of three-dimensional computer animation for motion picture production." He is the author of the OpenSteer library.

Neuromorphic computing is an approach to computing that is inspired by the structure and function of the human brain. A neuromorphic computer/chip is any device that uses physical artificial neurons to do computations. In recent times, the term neuromorphic has been used to describe analog, digital, mixed-mode analog/digital VLSI, and software systems that implement models of neural systems. The implementation of neuromorphic computing on the hardware level can be realized by oxide-based memristors, spintronic memories, threshold switches, transistors, among others. Training software-based neuromorphic systems of spiking neural networks can be achieved using error backpropagation, e.g., using Python based frameworks such as snnTorch, or using canonical learning rules from the biological learning literature, e.g., using BindsNet.

<span class="mw-page-title-main">Ant colony optimization algorithms</span> Optimization algorithm

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

Swarm intelligence (SI) is the collective behavior of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence. The expression was introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellular robotic systems.

<span class="mw-page-title-main">Crowd simulation</span> Model of movement

Crowd simulation is the process of simulating the movement of a large number of entities or characters. It is commonly used to create virtual scenes for visual media like films and video games, and is also used in crisis training, architecture and urban planning, and evacuation simulation.

<span class="mw-page-title-main">Multi-agent system</span> Built of multiple interacting agents

A multi-agent system is a computerized system composed of multiple interacting intelligent agents. Multi-agent systems can solve problems that are difficult or impossible for an individual agent or a monolithic system to solve. Intelligence may include methodic, functional, procedural approaches, algorithmic search or reinforcement learning.

<span class="mw-page-title-main">Dario Floreano</span> Swiss-Italian roboticist and engineer

Dario Floreano is a Swiss-Italian roboticist and engineer. He is Director of the Laboratory of Intelligent System (LIS) at the École Polytechnique Fédérale de Lausanne in Switzerland and was the founding director of the Swiss National Centre of Competence in Research (NCCR) Robotics.

<span class="mw-page-title-main">Swarm robotics</span> Coordination of multiple robots as a system

Swarm robotics is an approach to the coordination of multiple robots as a system which consist of large numbers of mostly simple physical robots. ″In a robot swarm, the collective behavior of the robots results from local interactions between the robots and between the robots and the environment in which they act.″ 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.

Humans have considered and tried to create non-biological life for at least 3000 years. As seen in tales ranging from Pygmalion to Frankenstein, humanity has long been intrigued by the concept of artificial life.

Cultural algorithms (CA) are a branch of evolutionary computation where there is a knowledge component that is called the belief space in addition to the population component. In this sense, cultural algorithms can be seen as an extension to a conventional genetic algorithm. Cultural algorithms were introduced by Reynolds (see references).

Ant robotics is a special case of swarm robotics. Swarm robots are simple robots with limited sensing and computational capabilities. This makes it feasible to deploy teams of swarm robots and take advantage of the resulting fault tolerance and parallelism. Swarm robots cannot use conventional planning methods due to their limited sensing and computational capabilities. Thus, their behavior is often driven by local interactions. Ant robots are swarm robots that can communicate via markings, similar to ants that lay and follow pheromone trails. Some ant robots use long-lasting trails. Others use short-lasting trails including heat and alcohol. Others even use virtual trails.

<span class="mw-page-title-main">Self-propelled particles</span> Type of autonomous agent

Self-propelled particles (SPP), also referred to as self-driven particles, are terms used by physicists to describe autonomous agents, which convert energy from the environment into directed or persistent motion. Natural systems which have inspired the study and design of these particles include walking, swimming or flying animals. Other biological systems include bacteria, cells, algae and other micro-organisms. Generally, self-propelled particles often refer to artificial systems such as robots or specifically designed particles such as swimming Janus colloids, bimetallic nanorods, nanomotors and walking grains. In the case of directed propulsion, which is driven by a chemical gradient, this is referred to as chemotaxis, observed in biological systems, e.g. bacteria quorum sensing and ant pheromone detection, and in synthetic systems, e.g. enzyme molecule chemotaxis and enzyme powered hard and soft particles.

Physically based animation is an area of interest within computer graphics concerned with the simulation of physically plausible behaviors at interactive rates. Advances in physically based animation are often motivated by the need to include complex, physically inspired behaviors in video games, interactive simulations, and movies. Although off-line simulation methods exist to solve most all of the problems studied in physically-based animation, these methods are intended for applications that necessitate physical accuracy and slow, detailed computations. In contrast to methods common in offline simulation, techniques in physically based animation are concerned with physical plausibility, numerical stability, and visual appeal over physical accuracy. Physically based animation is often limited to loose approximations of physical behaviors because of the strict time constraints imposed by interactive applications. The target frame rate for interactive applications such as games and simulations is often 25-60 hertz, with only a small fraction of the time allotted to an individual frame remaining for physical simulation. Simplified models of physical behaviors are generally preferred if they are more efficient, easier to accelerate, or satisfy desirable mathematical properties. Fine details are not important when the overriding goal of a visualization is aesthetic appeal or the maintenance of player immersion since these details are often difficult for humans to notice or are otherwise impossible to distinguish at human scales.

Cloud robotics is a field of robotics that attempts to invoke cloud technologies such as cloud computing, cloud storage, and other Internet technologies centered on the benefits of converged infrastructure and shared services for robotics. When connected to the cloud, robots can benefit from the powerful computation, storage, and communication resources of modern data center in the cloud, which can process and share information from various robots or agent. Humans can also delegate tasks to robots remotely through networks. Cloud computing technologies enable robot systems to be endowed with powerful capability whilst reducing costs through cloud technologies. Thus, it is possible to build lightweight, low-cost, smarter robots with an intelligent "brain" in the cloud. The "brain" consists of data center, knowledge base, task planners, deep learning, information processing, environment models, communication support, etc.

Swarm robotic platforms apply swarm robotics in multi-robot collaboration. They take inspiration from nature. The main goal is to control a large number of robots to accomplish a common task/problem. Hardware limitation and cost of robot platforms limit current research in swarm robotics to mostly performed by simulation software. On the other hand, simulation of swarm scenarios that needs large numbers of agents is extremely complex and often inaccurate due to poor modelling of external conditions and limitation of computation.

<span class="mw-page-title-main">Lyle Norman Long</span> Academic and computational scientist

Lyle Norman Long is an academic, and computational scientist. He is a Professor Emeritus of Computational Science, Mathematics, and Engineering at The Pennsylvania State University, and is most known for developing algorithms and software for mathematical models, including neural networks, and robotics. His research has been focused in the fields of computational science, computational neuroscience, cognitive robotics, parallel computing, and software engineering.

References

  1. ↑ Reynolds, Craig (1987). "Flocks, herds and schools: A distributed behavioral model". Proceedings of the 14th annual conference on Computer graphics and interactive techniques. Association for Computing Machinery. pp. 25–34. CiteSeerX   10.1.1.103.7187 . doi:10.1145/37401.37406. ISBN   978-0-89791-227-3. S2CID   546350.
  2. ↑ Banks, Alec; Vincent, Jonathan; Anyakoha, Chukwudi (July 2007). "A review of particle swarm optimization. Part I: background and development". Natural Computing. 6 (4): 467–484. CiteSeerX   10.1.1.605.5879 . doi:10.1007/s11047-007-9049-5. S2CID   2344624.
  3. ↑ Aoki, Ichiro (August 25, 1982). "A Simulation Study on the Schooling Mechanism in Fish". Nippon Suisan Gakkaishi (Japanese Fisheries Academic Journal). 48 (8): 1081–1088. doi: 10.2331/suisan.48.1081 . Retrieved November 26, 2023.
  4. ↑ Delgado-Mata, Carlos; Martinez, Jesus Ibanez; Bee, Simon; Ruiz-Rodarte, Rocio; Aylett, Ruth (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.
  5. ↑ Hartman, Christopher; Beneš, Bedřich (July 2006). "Autonomous boids". Computer Animation and Virtual Worlds. 17 (3–4): 199–206. doi:10.1002/cav.123. S2CID   15720643.
  6. ↑ Min, Hongkyu; Wang, Zhidong (2011). Design and analysis of Group Escape Behavior for distributed autonomous mobile robots. IEEE International Conference on Robotics and Automation (ICRA). doi:10.1109/ICRA.2011.5980123.
  7. ↑ Saska, Martin; Jan, Vakula; Libor, Preucil (2014). Swarms of micro aerial vehicles stabilized under a visual relative localization. IEEE International Conference on Robotics and Automation (ICRA). doi:10.1109/ICRA.2014.6907374.
  8. ↑ Saska, Martin; Vojtech, Vonasek; Tomas, Krajnik; Libor, Preucil (2012). Coordination and Navigation of Heterogeneous UAVs-UGVs Teams Localized by a Hawk-Eye Approach (PDF). IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Archived from the original (PDF) on August 10, 2017. Retrieved August 11, 2019.
  9. ↑ Lebar Bajec, Iztok; Heppner, Frank H. (2009). "Organized flight in birds" (PDF). Animal Behaviour. 78 (4): 777–789. doi:10.1016/j.anbehav.2009.07.007. S2CID   53180059.
  10. ↑ Ibáñez, Jesús; Gómez-Skarmeta, Antonio F.; Blat, Josep (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.
  11. ↑ Moere, A V (2004). "Time-Varying Data Visualization Using Information Flocking Boids". Proceedings of the IEEE Symposium on Information Visualization. pp. 97–104. doi:10.1109/INFVIS.2004.65.
  12. ↑ Cui, Zhihua; Shi, Zhongzhi (2009). "Boid particle swarm optimisation". International Journal of Innovative Computing and Applications. 2 (2): 77–85. doi:10.1504/IJICA.2009.031778.
  13. ↑ Dawkins, Richard (2009). The Greatest Show on Earth: The Evidence for Evolution. Free Press. pp. 219–220. ISBN   978-1-61664-829-9.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.