Flocks of birds can be modeled with boids

Boids 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 at Craig Reynold's Boids page.

Boids

The Boids program consists of a group of objects (birds) that each have their own position, velocity, and orientation. There are only 3 rules which specify the behavior of each bird:

Separation

Each bird attempts to maintain a reasonable amount of distance between itself and any nearby birds, to prevent overcrowding.

Alignment

Birds try to change their position so that it corresponds with the average alignment of other nearby birds.

Cohesion

Every bird attempts to move towards the average position of other nearby birds.

A "pseudocode" explanation of the Boids algorithm can be seen here.

As in the Game of Life, 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 here.

Boids is only one of many experiments in what is known as the field of "swarm intelligence". A key aspect of swarm intelligence systems is the lack of a centralized control agent--instead each individual unit in the swarm follows its own defined rules, sometimes resulting in surprising overall behavior for the group as a whole.

Swarm intelligence as exhibited by an ant colony

In ant colony optimization, 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 traveling salesman problem and other similar problems.

Video demonstrations of AntSim, a program implementing ant colony optimization, are available here and here.

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 "swarm robotics". 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.

Timm[ie] Wong, September 2008