Optimisation of Boids Swarm Model Based on Genetic Algorithm and Particle Swarm Optimisation Algorithm (Comparative Study). Paper about the boids model (Reynolds. Flocks of Boids. Original Boids, developed by Craig Reynolds, is an artificial life program, simulating the flocking behavior of birds. As with most artificial life.

1. Computer Science
2. Craig Reynolds Actor

Boids Background and Update by You need to be using an Java-enabled browser to see this demo. In 1986 I made a computer model of coordinated animal motion such as bird flocks and fish schools. It was based on three dimensional computational geometry of the sort normally used in computer animation or computer aided design. I called the generic simulated flocking creatures. The basic flocking model consists of three simple which describe how an individual boid maneuvers based on the positions and velocities its nearby flockmates: Separation: steer to avoid crowding local flockmates Alignment: steer towards the average heading of local flockmates Cohesion: steer to move toward the average position of local flockmates Each boid has direct access to the whole scene's geometric description, but flocking requires that it reacts only to flockmates within a certain small neighborhood around itself. The neighborhood is characterized by a distance (measured from the center of the boid) and an angle, measured from the boid's direction of flight.

Flockmates outside this local neighborhood are ignored. The neighborhood could be considered a model of limited perception (as by fish in murky water) but it is probably more correct to think of it as defining the region in which flockmates influence a boids steering.

Simulated boid flock avoiding cylindrical obstacles (1986) In cooperation with many coworkers at the Symbolics Graphics Division and Whitney / Demos Productions, we made an animated short featuring the boids model called Stanley and Stella in: Breaking the Ice. This film was first shown at the Electronic Theater at SIGGRAPH '87. There was a published at the same conference. In the course notes for SIGGRAPH '88 there was an Since 1987 there have been many other applications of the boids model in the realm of. The 1992 Tim Burton film was the first.

It contained computer simulated bat swarms and penguin flocks which were created with modified versions of the original boids software developed at Symbolics. (then at VIFX, which later merged with ) produced realistic imagery of bat swarms. Andrea Losch (then at Boss Films) and Paul Ashdown created animation of an 'army' of penguins marching through the streets of Gotham City. From Stanley and Stella in: Breaking the Ice (1987) As luck would have it, organized the original ground-breaking Workshop a few months after the boids paper was published in 1987. A helpful go-between got word to Chris and he let me give an informal presentation on boids at the.

The boids model has become an oft-cited example of principles of Artificial Life. Flocking is a particularly evocative example of emergence: where complex global behavior can arise from the interaction of simple local rules.

In the boids model (and related systems like the multi-agent ) interaction between simple behaviors of individuals produce complex yet organized group behavior. The component behaviors are inherently nonlinear, so mixing them gives the emergent group dynamics a chaotic aspect. At the same time, the negative feedback provided by the behavioral controllers tends to keep the group dynamics ordered. The result is life-like group behavior. A significant property of life-like behavior is unpredictability over moderate time scales.

For example at one moment, the boids in the applet above might be flying primarily from left to right. It would be all but impossible to predict which direction they will be moving (say) five minutes later.

At very short time scales the motion is quite predictable: one second from now a boid will be traveling in approximately the same direction. This property is unique to complex systems and contrasts with both chaotic behavior (which has neither short nor long term predictability) and ordered ( static or periodic) behavior. This fits with Langton's 1990 observation that life-like phenomena exist poised at the edge of chaos. The boids model is an example of an, a class of simulation used to capture the global behavior of a large number of interacting autonomous agents. Individual-based models are being used in biology, ecology, economics and other fields of study. Note that the straightforward implementation of the boids algorithm has an asymptotic complexity of O(n 2).

Each boid needs to consider each other boid, if only to determine if it is not a nearby flockmate. However it is possible to reduce this cost down to nearly O(n) by the use of a suitable spatial data structure which allows the boids to be kept sorted by their location. Finding the nearby flockmates of a given boid then requires examining only the portion of the flock which is within the general vicinity. Using such algorithmic speed-ups and modern fast hardware, large flocks can be simulated in real time, allowing for. new Online resources related to boids.

the SIGGRAPH '87 boids paper. An where I describe a little about how the boid model came about.

new. Another page about in a report about.

on the 1987 boids paper in a literature review. A summary of in the report on in in the project of the ACM SIGGRAPH Education Committee. Books and articles that describe boids. (1993) the book by.

(1995) in Zmagazine. (1994) in Cornell's SciTech Magazine by. part of an 'interactive essay on '. (in computer graphics). by. (specifically, chapter ) by. (1992) by from F&SF.

(1995) by. (1992) by. (1991) by. 'Scientists play god in a binary universe of their own making' (1998) by Curt Suplee new. by.

by. by.

(2000) by describes adaptive behavior, including boids, for a cognitive psychology audience. new.

(2000). This Amateur Scientist column discusses the role of software experiments as a tool in understanding biological phenomena. new. Articles on other topics that mention boids as example or metaphor:. in: Coevolution of classes of governance principles (1993) by new.: Nurturing the Hungry Mind (1995). (1996) by. (1996).

new. (1997) is an attempt to apply concepts of emergent behavior to problems of business management. (1997) by draws a parallel between complex adaptive systems and flexible software development practices. new. (1997) by Paul Plsek, Curt Lindberg, and Brenda Zimmerman.

new. (1998) by reports on the fifth Chaos in Manufacturing conference. The boids model is described (albeit incorrectly) on. new.: What HealthCare Organizations Can Learn from Complexity Science (2000). new Other computational models of group motion. Computer animation.

Eurythmy by Susan Amkraut and Michael Girard contained the first procedural animation of flocks when it was shown at the Film & Video Show of SIGGRAPH '85. It is available on SIGGRAPH Video review. Some imagery from the appear on this page from Ars Electronica 89. Amkraut and Girard also created flocking and herding in the 1993 VR production. and colleagues at Georgia Tech's GVU have created several physically-based models of such as herding one-legged hoppers and a pack of bicyclists. Disney's (1994) included a wildebeest stampede by Kiran Joshi, MJ Turner, et al.

Here are two stampede-related items from excellent:. (search for second occurrence of stampede). sequence (QuickTime Movie, 21.9 MB. Also available as (1.2 MB) and (28.7 MB)). implemented a realistic, physically-based model of fish schooling as part of her dissertation research on artificial animals. See also:.

and. ', ACM Computer Graphics, Proceedings of SIGGRAPH'94, July 1994. A non-technical article called, by Gene Levinson which appeared in The World & I Magazine. While at Santa Barbara Studios, used the Dynamation particle system software to create animation of flocking space creatures for an episode of.

Course at George Washington University includes an assignment to implement a Behavioral Motion Control System like boids. You can see some of the student's animations from:, and. new. Games, Interactive graphics and virtual reality. (1980) a video arcade game designed by featured a group of three autonomous 'enemy tanks' which exhibited coordinated group motion. They avoided collisions with each other and would seek the goal objects ('canisters'), or if they got too close, the player controlled vehicles.

The combination of goal seeking and collision avoidance produced a motion like flocking. For more details, read Tim Skelly's own.

See also this Rip-Off and this page about an. new. (1985) by, Robin Schaufler, et al., premiered at the SIGGRAPH 85 art show.

On at least one occasion, a school accidentally arose in this 'virtual fish tank'. (1993) by and Matthew White. Describes an implementation of boids using up to 50 parallel Transputer processors to simulate flocks of up to 100 boids at interactive rates (6 frames per second or better).

The simulation included obstacle avoidance. The full article is available in. new. introduces visitors to the sciences of complexity, artificial life and related fields.

It is an online version of a project that started as an at in Boston. Its goal is to introduce visitors to the sciences of complexity and artificial life. The original project was jointly developed by the (see their page) and (see their page).: A theoretical approach towards an evolving, interactive VR environment using a distributed DOME and CAVE System (1998) by, and in Proceedings of Virtual Worlds '98. Paris, France, July 1-3, 1998. Also available in. Robotics. heads at the University of Southern California which studies robotic.

See also Maja's and these of robots performing various group behaviors, including flocking. (Some press clippings from and. And see this delightful (the second paragraph)). by Y.

Uny Cao, Alex S. Fukunaga, and Andrew B. Kahng (UCLA 1996) surveys research in robot groups. Provides an interesting contrast to much of the work cited on this page: the flocking/herding involved is of natural animals while a robot plays a role similar to a sheepdog. As is done when training real sheepdogs, ducks are used here as a less challenging stand-in for sheep. Read the delightful for more detail. See also 's pages about the research related to robo-sheepdog.

(1997) by, examines algorithms to control multiple mobile robots, focuses on behaviors that can be obtained through local control, and demonstrates createing complex behaviours with simple algorithms. new.

(1993) by Describes the use of a homogeneous population of robots, an Army-ant swarm, for transportation of material. Investigates both spatial and behaviroal self-organization.

new. in a community of cubic-inch microrobots which form a capable of task such as clustering, following the leader, and playing tag. new. a collection of publication and resources by new. (1998) by of the. Includes papers and, a Java demonstation applet. new.

(2000) by (in ) discusses swarm intelligence, emergent computation and collective robotics. new. Aerospace (coordinated groups of aircraft or spacecraft). (1995) by discusses potential applications and designs for groups of reactive communicating satellites: 'design goals are embedded in the constellation rather than individual satellites, and the constellation exhibits emergent behavior.' new. (1996) describes early test of a potential fleet of solar-powered autonomous aircraft that fly at high altitude in 'V' formations like geese, and this of the test flight of a prototype.

(1999), US Air Force press release describing the US AFRL's 'Technology Satellite of the 21st Century' program, including plans for a system of 'formation-flying' satellites that can quickly adapt to rapidly changing mission requirements. new. Education (about distributed and complex systems). developed a programmable modeling environment for exploring the behaviors of such as bird flocks, traffic jams, and ant colonies. For more information see Mitchel's book. OK, while not strictly a ' computational model of group motion,' is a collection of participatory activities for young students to help them learn about group motion and complex systems.

Artificial life and Evolutionary computation. by Nahum Zaera, and. Published in. (1999) by investigates flocking (herding) under the influence of a predator. Specifically, it models a situation very much like the interaction between a sheep-dog and a flock of sheep, such as in a sheep-dog trial. See the applet, and the related applet. new.

(1997) by and uses as its example a group of butterflies navigating by olfactory sensors. Based on Zhang's 1996 Ph.D. See the full paper in. new. Art. As part of this MFA work, created a virtual reality art piece called which included a flock of swallows that would fly over to eat food dispensed from the user's 3d wand. At SIGGRAPH 93 's presented, a robotic art installation composed of reactive sculptural and musical elements.

( Environment for the Interactive Design of Emergent Art, by and ) is an art piece based on artificial life which includes a flock of birds. An art piece called by, Robert Rowe and, performed at NYU in 1995, and another version installed that same year in Bonn under the title. It was also presented at the venue. is the system underlying the 1997 and 1998 installations known as by et al. This interactive 3D world is full of autonomous objects and characters, including flock-like groups. Biology. Ornithologist and mathematician describe a model of flocking and roosting in A Stochastic Nonlinear Model for Coordinated Bird Flocks (1990) appearing in edited by Saul Krasner.

The project uses individual-based models to study animal behavior and ecological issues. Models of and have been created in EcoTools. There is also a simulation at this site. Physics. published an analysis of flocking particles in Physical Review Letters on August 7, 1995, which focused on transitions in collective behavior. (I will provide a more complete description here when I better understand Prof. Vicsek's work.).

implemented a cellular automata model of using his system based on work. by and published in Physical Review Letters (Volume 75, page 4326, December 4, 1995) includes a proof that motion of a flock or herd is essential to its collective ability to align.

That is, group alignment is not possible with local perception in the absence of motion. (0.7 MB gzipped Postscript) by presented at the 1996. by and in Physical Review E, October 1998, Volume 58, Issue 4, pp. See the AIP summary:, this summary from, and this article from.

Physics of Flocks ( and ) by, transcripts and audio recordings from on the Australian Broadcasting Corporation. Search, optimization and visualization techniques inspired by flocks and swarms. (and see the original by and ) searchs a multidimensional solution space.

Somewhat like a genetic algorithm, but the PSO's search points move as a swarm through the space with a velocity, altered by steering accelerations. See also this. (1998) by and, uses a flock model, with communication between boids, to better search for clusters in spacial datasets, just as a natural flock provides better foraging than individual birds could manage. See this demo. introduced in 1992 by '.studies artificial systems that take inspiration from the behavior of and which are used to solve function or combinatorial optimization problems.'

. (1994) by and, uses a school of fish metaphor to search the web. by Glenn Proctor is a data visualization technique that portrays datapoints as fish that school through a 3d space, revealing correlations in the data by their motion and clustering. See the paper (1998, PDF 91KB) by Glenn Proctor and Chris Winter. new. (1996) by,.

See also these related links: (1998) by Mark Ward in New Scientist, (1997) by Julia Flynn in BusinessWeek, and. new. Other emergent, collective behavior. a research group exploring the question: 'How do we obtain coherent behavior from the cooperation of large numbers of unreliable parts that are interconnected in unknown, irregular, and time-varying ways?' new.: 's page of links on emergent computation by swarms of simple agents. new.

Other topics. 's term report on software to.

has developed a system called to simulate the motion of large crowds of people. It can handle crowds of more than 100,000 people. See also these, and these articles by in from and. A page of by the Biological Model Simulation group at Keio University.

The demos are in 2d and include basic schooling, predation, interactive feeding, and schooling with two species. sells tools to model the motion of large crowds with their software, based on an efficient engine for. Daniel Bullok wrote a as a class project. An introduction called and a computational model of resource-deprived by. A for a programmable multi-agent shell by. page is the report from his Science Project - his 8th grade Science Project, mind you. Kids these days!).

by uses a simple spring-mass model of animal bodies and simulates herding on the plane. This report contains good diagrams and descriptions of the implementation of component steering behaviors.

is the web site for a book of the same name by (shop for the book ). He implemented boids and added another rule which cause the boids to attempt to maintain a clear view ahead of them.

This resulted in flocks which form the classic 'V' formations of migrating geese. In a class project called Leon Blackwell extends a boid-like model to include predator-prey interactions. a 1977 class project by Brian O'Connor. Includes source code and animations. (Although there seem to be access problems for some of the files.). (the January 1999 installment of ' column on Computing Science in ) talks about emergence using examples such as flocks, schools, herds, traffic jams, ant colonies, and forest fires.

by Harry Brignull, reports on a project to implement boids using the package. Includes diagrams of the resulting group motion and source code. This class project involved an interactive flock which plays the game of tag and allows the use to either ride along passively with a member of the flock, or take control and pilot the boid. new.

a study of flocking geese objects (1999) by Cathryn J Polinsky. Presentation slides for a Senior Project called 'Flight Simulation of Flocking Geese Using Particle Set Animation' new Natural flocks, herds, and schools. Some seminal papers from the (hardcopy) literature:. The Structure and Function of Fish Schools (1982) by Brian Partridge in, June 1982, pages 114-123. The Chorus Line Hypothesis of Manoeuvre Coordination in Avian Flocks (1984) by, in, Volume 309, May 24, 1984, pages 344-345. Animal Groups in Three Dimensions: How Species Aggregate (1997) edited by and William M. A collection of papers related to a 1991 workshop on measuring and modeling animal aggregations.

Use this link to for the book. A 22 second (160x120 pixels, in (1.1 Mb) and (1.8 Mb) formats) swimming in the Kelp Forest tank at the from a page of. See also the live view of this tank. Here are some other flock/herd/school pictures on the web:, (MPEG, 0.5 Mb), (MPEG, 1.0 Mb). interesting site on behavior of livestock and other subjects, contains a section on which covers topics such as:.

new. new each of which contain pictures and diagrams on geometrical relationships between herds of livestock, the shapes of their enclosures, and the positions of human handlers.

Calvin's book discusses the predation on herds of early humans in Chapter 8: (you may wish to search for the first occurance of herd).: on the structure of migratory goose flocks, and folksy thoughts on applying these ideas to groups of humans. V formations: at the bottom of 's page about the there is a discussion about the mixed evidence for an aerodynamic explanation of the 'V' formations often seen in migrating ducks and geese. See also the cited. A page by illustrating how individual fish in a school benefit from reduced predation due to.

An essay called by Tony J. Pritcher in his book describes research by into the effect he calls synchrokinesis whereby small movements of individuals copied through the shoal provide an accurate movement towards better conditions. (Contrast this with the work of (above) which suggests that individual errors are damped out by interaction with the rest of the group.). (1995) by a field ethology study of how the size and relative positioning of this bird affect the vigilance (scanning) behavior of individuals in the group.

new. Cutting horses and herding dogs: these two types of trained animal behaviors have evolved into modern sport competitions. Their origin was to assist humans raising stock animals, and they can still be found in this role today. Both are related to herding behavior in special ways.

The job of a herding dog (stockdog, sheepdog) is to help a shepherd contain and control a herd of stock animals (especially sheep, goats or cattle). A herding dog uses its understanding of the stock animal's herding behavior to be able to move the whole group as a unit. For more information see:, and new. The cutting horse derived from the American cowboy culture and is specifically trained to handle cattle.

A cutting horse's skill is in being able to defeat the cattle's herding instinct, allowing it to separate off (cut) one individual at a time. The site of the includes and of the sport. new. Some general information about these animals:. from the WWW Virtual Library. by. From Cornell's:.

From the in the at the:. From the: collections on and. From pictures of:, and.

new. Biomechanics:. by.

by. From the site on:. (1993) by new.

includes simulated swarms of prey, see below. from NASA (see also ). An exhibit on in the online of. very high speed photography by Ralph W. Scott.

A large collection of new Software (There is additional source code for Java implementations listed on the.) This is the original 1986-1988 implementation, written in Symbolics Common Lisp, and based on Symbolics' S-Geometry 3d modeling system and S-Dynamics animation system. (Modern versions of those applications are available from, see: and.

Your browser may not recognize this file as Lisp source code and try to reformat it as filled text. If so use View / Page Source or equivalent, or download the file.) This platform-independent boids implementation by includes C source code and an Inventor-based binary executable demo for SGI machines. These boids support both flocking and obstacle avoidance. An After Dark screen saver module for Macintosh computers. This very nice package implements a parameterized version of boids including several species of creatures (wasps, birds, fish, sheep.) based on altering the parameters. There are control panels that allow you to experiment with the parameters. For other sources of this software see Simon's.

Version 1.0 of a Windows application featuring three distinct species of flocking birds and nice control panels for adjusting their parameters. See the file for more information. This is a screen saver for NeXT computers by based on the boids model. C code and related files are available for FTP.

See the file for details. A screen saver for Windows.

A-Quarium is a fish tank simulator somewhat related to boids. '.a fish will try to swim with a close neighbour if it is of the same species, and will try to swim away if it is of a different species. The behaviour of the fish tank is an emergent property of all the individual fish actions.' There is an implementation of boids for, an interactive real-time graphic programming environment, from and. This Windows 3.1 software originally accompanied the book Artificial Life Lab by, Waite Group Press, 1993, now out of print. It includes an implementation of boids and related ALife models. A commercial ' for 3D Studio from.

This is an application for a PowerPC Macintosh using QD3D. Other versions exist for 68000 Macs with FPU, and as After Dark modules.

See the main page by (Ishihama Yoshiaki) for other alife-related Mac and Java software. Wrote this very nice 2D implementation of boids for Windows 95 or WindowsNT and provides both executable and source code.

A screen shot on the web page shows the interactive slider controls and a large flock flying around several obstacles. A boids implementation by Stephen Coy has been included in the sample code since version 5. Stephen suggests that better source code is included with the DirectMusic demo based on boids. A boids demo based on Christopher Kline's implementation (see above) is included in 's OpenGL/OpenInventor tool called Apprentice which is free for non-commercial, educational use. By, Cool School simulates a school of fish and predators using behavioral modeling. The O(n 2) cost of the naive boids algorithm is reduced by by subdividing the population into a hierarchy of 'subschools'. He reports running at interactive rates with 32 subschools each containing 33 fish on a 200MHz Pentium-class machine.

Cool School was developed as part of the project mentioned above. A 1997 class project at Stanford by Chris Quartetti and Eng-Shien Wu, includes a movie file showing flocking and collision avoidance, and C source code. (of University College London) developed the first two implementations to compare VRML and Java3D, and the third to test the DIVE multi-user VR system. Source is includes for all three. A commercial plug-in from for the animation system, creates herds and flocks of animated characters.

new and created these Mac applications to simulate extremely large swarm-like populations, using modifications of the basic boid algorithms. See also his applet. new Richard Lowe wrote this boids implementation in Visual Basic and provided the source code. (I have not seen it run but:) It apparently provides for interactive specification of obstacles. new wrote a boids implementation as a Windows application for a Final Year Project in college. The original version used Direct3D and he later rewrote it to use.

Binaries and source are available for download from his page. new wrote this 2d shooter game based on boids. It runs under Windows 95, 98, and NT and is available for free download. You can shot at the flocking birds, but watch out, because they can shoot back!

And since they are a flock, they can make coordinated group attacks. new developed these models of 'people moving in relation to other people and things' as part of a suite of (Windows PC based) demonstrations of his. Powers and his colleagues in the seek to model and understanding the purposeful behavior of living organisms. new wrote this ecological simulation of a three species system using individual-based local rules.

It is written as a Java application. This page contains links to a paper, the source code and both platform-independent and Windows-specific executables. new a StarLogoT implementation of flocking from ('Making Sense of Complex Phenomena Through Building Object-Based Parallel Models.' ) Includes links to a movie of the simulation and a page of. new wrote this flocking plug-in for in its scripting language MEL. It is available at the repository.

new wrote this boids code to use with the, the page contains links to the code, a movie, and some diagrams of the steering force vectors used in the boids model. new Lexicological note: in addition to common terms like flock, herd, and school, English has a rich history of specific words to describe groups of various animals, sometimes known as collective nouns or venereal terms.

Computer Science

These words were used more frequently when hunting wild animals was a major source of food. For an amusing discussion of these words see the book by James Lipton (Viking Penguin, 1993, ISBN ). Here are some web pages that provide similar information:. by.

in A Beastly Garden Of Wordy Delights by. by. and by.

by. See also by. by new. by new. from the new. by new.

by Janice Welsh new Send comments to visitors since June 29, 1995 Last update: September 6, 2001 (fixed the 'early motion tests' link December 6, 2006) (fixed links to Brian J. Mork's work July 30, 2007).

Overview is an artificial life simulation originally developed by Craig Reynolds. The aim of the simulation was to replicate the behavior of flocks of birds. Instead of controlling the interactions of an entire flock, however, the Boids simulation only specifies the behavior of each individual bird.

With only a few simple rules, the program manages to generate a result that is complex and realistic enough to be used as a framework for computer graphics applications such as computer generated behavioral animation in motion picture films. An applet visualizing the Boids simulation can be seen.

Emergent Behavior As in the, the simple rules of the Boids simulation sometimes gives rise to surprisingly complex behavior. Although the long-term behavior of an entire flock is difficult (if not impossible) to predict, its motion and arrangement is predictable and orderly over small periods of time. A slightly more complex model involving obstacle avoidance has been used to allow the Boids to travel through a simulated environment, avoiding obstacles and rejoining together as a single flock. A short video demonstration of these types of behavior is available. Swarm intelligence as exhibited by an ant colony In, the goal is for ants to explore and find the optimal path(s) from a central colony to one or more sources of food.

As with ants in real life, the simulated ants initially travel in random directions, but return to the colony once a food source is found. The key in the evolution of the simulation is the use of pheromone trails, which compel other ants to follow them.

Pheromone trails evaporate over time, so paths which are shorter end up being traveled more often. This results in a positive feedback mechanism which ensures that the entire group of ants will eventually converge on an optimal path. The problem-solving strategy of the ant colony can be applied to a number of different problems involving searches for optimal paths through graph structures.

For instance, ant colony optimization algorithms are suitable for use in the and other similar problems. Video demonstrations of, a program implementing ant colony optimization, are available and. Groups of small robots can be programmed with swarm intelligence algorithms One application of the ideas involved in Boids and other swarm intelligence simulations is in the field of '. Certain tasks such as mapping, nanorobotics/microbiotics, or foraging lend themselves well to being solved most efficiently by a group of many small robots. In such cases, each robot needs to be programmed with the principles of swarm intelligence in mind in order for the whole group to most efficiently complete the desired task. A key component in these systems is communication between individual robots in order to ensure that each is devoted to an appropriate task at hand.

Craig Reynolds Actor

Timmie Wong, September 2008.