Swarm Behavior

Since the beginning of life on earth, nature has developed a vast variety of collective behaviours. These behaviours include, for instance, thousands and thousands of fireflies flashing synchronously in summertime, covering entire grasslands with sallow light, as well as complex structures built by social insects that appear technically mature and allow for storage or even production of food, sophisticated ventilation mechanisms, breeding and defense against predators. Some of those structures are built to such perfection and precision that we have just started to learn how they actually work.

Swarm-like behaviours observed in biology, such as the instances named above, inspired a variety of research work in recent times. While, for instance, Meaterlinck 1927 described the life in a swarm of ants in a rather poetical way, later research tried to shed light on the mechanisms swarms exploit to solve their everyday-, but nevertheless nontrivial problems like localizing and exploiting food sources in an efficient way. Pursuing this research, it has surprisingly turned out that the complexity of the observed swarm behaviour is extremely contrary to the relative simplicity of its individuals (swarmers). The whole seems to be more than the sum of its parts. Whereas the swarmers are only capable of relatively simple forms of behaviour, the swarm as a whole shows highly sophisticated, yet flexible and robust behaviours – the term of swarm intelligence emerged. However, the appearance of complex phenomena that arise from local interactions of simple parts with each other and the environment is not limited to the fauna. Further works observe similar phenomena in the fields of physics and chemistry.

Enabled by continuously growing calculation capacity of up-to-date computers, swarm behaviours have not only been observed in nature, but have also been synthesized. Craig Reynolds' Boids, published in 1987, are a widely-known example for the traditional synthesis of swarm behaviour (figure on the left). Boids are synthetic, manually designed agents, whose individual-level locomotion behaviour consists of very few, simple rules. The movement of a swarm of boids, based on local interactions of the swarm-members, then causes a movement behaviour at the swarm-level that looks intriguingly similar to flocks of birds in nature. At the same time it shows in an impressive way how such complex behaviours, that appear to be steered by some central instance, can be organized in a simple, decentralized way. Recently, methods and techniques from the field of swarm intelligence inspired research in a variety of disciplines. From decentralized control of robot and agent swarms, over routing of traffic in communication networks to idealized synthesized swarm behaviour as a metaheuristic to solve complex optimization problems, the possibilities seem to be unlimited.

Popular scientific work in the field of swarm behaviour have then inspired authors to bestseller novels. Concerning the field of synthesized swarm behaviour, we want to cite Prey by Michael Crichton. The novel Der Schwarm (The Swarm) by Frank Schätzing is more oriented towards biology. The first one deals with the swarm behaviour of micro robots which gets out of control, the latter describes how a then unknown, marine life-form, organized as a swarm, poses a threat to and attacks the mankind.

Even further growing calculating capacity lastly allowed for the synthesis of swarm behaviour in an evolutionary way. Here, mechanisms of natural evolution are used to synthesize swarm behaviour, which enables new possibilities for research. However, the development of natural behaviours throughout synthetic evolutions has mostly been significantly narrowed due to certain constraints. Throughout my diploma thesis "distributed evolution of swarms", some of those constraints are both identified and eliminated to allow for less restricted, more extensive evolutions.

Regardless of the particular level of development from protozoa to mammals, the animal kingdom is pervaded by swarm-like behaviours whose complexities emerge due to local interactions not at the individual, but at the swarm-level.

An example of such behaviour at the level of micro-organisms is the freshwater alga (Volvox, figure on the left), which builds spherical multicellular colonies, whose surface is built from thousands of single cells, which are then able to swim in a coordinated manner. Moreover, the colony produces child colonies initially held within the interior of the parent colony in a specialized nutritious habitat, to be released when the parent colony disintegrates. Such “swarms of cells”, cell colonies, can be seen as an interstage between protozoa and multicellular animals.

The probably most well known forms of swarm behaviour are shown by social insects. The colony size of those is known to vary over many orders of magnitude. The cooperation and specialisation mechanisms in these swarms can reach a level, at which certain individuals of the swarm abandon their own survivability. For instance, colonies of the ant Myrmecocystus melliger may contain more than thousand honey pots: A special ant caste able to store so much honey in their bodies that their abdomen swells up to pea-size. As so swollen ants are unable move any more, they are hung below the ceiling of their nest by their swarm mates (Figure on the left)

– thus forming a living honey storage and preventing the honey from decay.

Even though such specialisations in a swarm penalize the survivability at the individual level, they enable the swarm as a super organism to solve complex tasks, such as rising large, most complex structures as habitats, as already sketched in the first paragraph of this paper. Given that the accomplishment of those tasks needs no centralized control, the swarm turns out to be flexible and tolerant to failures (some swarm individuals devoured by predators, etc).

However, not every membership in a swarm denotes individual lack of survivability. For instance, a school of fish (Figure on the right)does not penalize one member's ability to move or consume food; yet the probability for a lonely individual to be chosen as food by a predator increases.

Observations and documentations of swarm behaviours like those mentioned above have inspired further studies which aim for a synthesis of similar behaviours – and the induced advantages – in artificial systems. For this, individuals of a swarm are modelled as artificial agents. The following subsections are intended to provide a brief overview of several paths the named studies follow. We start with the synthesis of idealized swarm behaviour, where the individuals in a swarm have only very few behavioural base patterns at their disposal.

Algorithms based on idealized forms of swarm behaviour are applied as metaheuristics to find good solutions for complex optimization problems. Two of these Metaheuristics are explicitly named: Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO).

The PSO algorithm was already introduced throughout the articleoptimization strategies and design automation.

The ACO-Algorithm is inspired by ant colony foraging. Ants exploit food sources by creating pheromone trails from a food source, once found, back to the nest. Once the trail is laid, other foraging ants can follow it immediately without having to search for it. At the same time, due to random perturbations in pheromone laying and ant paths, the path to the food source is gradually optimized. Shorter paths to the food source are emphasized by heavier ant traffic – and therefore preferred in further runs. The described mechanisms are modelled by ACO to solve graph based optimization problems.

There are more specalized algorithms than metaheuristics also based on idealized swarm behaviour, such as swarm-based clustering procedures or algorithms in the field of graph partition.

In the context of theoretical biology, swarm behaviour is often synthesized manually according to archetypes observed in nature. From the observations of the living beings in nature, an individual behavioural model is designed and implemented on simulated or real artificial agents to check whether or not swarm behavioural patterns similar those observed in nature occur.

One field of interest, for example, is to model and simulate collective decisions among the swarm: How does a superorganism with only local interactions between individuals come to distinctive decisions, which food source should be exploited or where a new nest is built? An example of such behaviour is of ant colonies of Lasius niger, as well as honey bees.

Moreover, synthesized swarm behaviour offers the opportunity to place the observed behaviour in the context of its variations¹⁾ This allows to analyze, which of the observed individual behavioural patterns contribute to the efficiency of the entire swarm. As an example work for such an analysis we refer to the work of Krieger et al: The individuals of a swarm of robots were given the opportunity to recruit other individuals inspired by ant foraging, which increased the efficiency of the robot swarm.

Another approach to synthesize swarm behaviour is to evolve control structures for artificial agents using evolutionary optimization strategies, which already have been introduced troughout the preceding text, Optimization Strategies and Design Automation. Evolving solutions often produces unexpected, but less biased results. This approach is widely used in the relatively young fields of and design automation (evolutionary robotics, which also were introduced) and is transferable to swarm behaviour and swarm robotics. A further project in the field of evolutionary swarm robotics discussed on this web site is our project Beanbag Robotics.

Moreover, Dorigo et al. created a robot Swarm-Bot which consists of several smaller autonomous robots (s-Bots). The s-bots feature special actuators to attach themselves to each other and as a larger Swarm-Bot learn by evolution to solve various tasks more efficient than on the individual level.

Read in Distributed Evolution of Swarms how bio-oriented, free evolutions of swarm behavior are performed.