Modelling the swarm: Analysing biological and engineered swarm systems

Abstract

In this article, we discuss the current research efforts on swarm systems and on the motivation of mathematical modelling of such distributed and self-organizing systems. Obviously, a special emphasis is given to those articles which were carefully selected for the special issue at hand. These articles demonstrate how mathematical models of different kinds – bottom-up agent models and top-down model approaches – increase the understanding of natural swarm systems, for example, by investigating the efficiency in the self-regulation of social insect colonies. A second group of articles illustrates how mathematical models are used to generate and optimize artificial swarm systems as engineered in the field of swarm robotics. We discuss the common problems of such modelling efforts and highlight the importance of models as generators of hypotheses that suggest novel empiric experiments as well as the importance of empiric experimentation that results in meaningful model parameterizations. In summary, the special issue at hand, which is introduced by this article, gives a significant overview about the lines of research that are followed in the research of swarm systems today.

Keywords:

• modelling
• multi-agent systems
• swarms
• swarm intelligence
• robotics

1. Motivation and background

Social insect colonies show an impressive level of collective intelligence that allows these colonies to select foraging sites [1–5] and nest sites [6,7] in a distributed and energetically efficient manner. These collective capabilities arise from inter-worker interaction and communication which allow for self-organization of the insect societies [8,9] and collective decision making performed by the workers. Most prominent examples of such collective capabilities are nectar foraging decision making in honeybees [3,10] and food-source selection by pheromone trails in ants [4]. However, also other aspects of self-regulation of these colonies are facilitated by self-organization via simple worker interactions: food allocation, task allocation and collective building [11–13], which were found to be based on simple rules of direct communication (e.g. honeybee dances [14,15], honeybee trophallaxis [16,17]). Also indirect communication by altering the environment of other workers was found to result in collective decision making in ants and termites (e.g. stigmergy [18–20]). In the last decade, these collective behaviours have been studied empirically [3,15,21], as well as by mathematical modelling and simulation [22–26]. While empirical studies showed the high levels of flexibility of these natural collective systems, theoretical studies by modelling and simulation suggest also high levels of robustness and scalability.

Simple motion principles of organisms like flocking, shoaling, herding or phenomena based on random motion can be reflected well enough in mathematical models derived from physics. In such models, organisms are treated like gas molecules and their motion is Brownian combined with attraction/repulsion forces. Several of the models we collected for this special issue picked up this approach. Also ‘mean-field’ approaches, mainly done in ordinary differential equation (ODE) models, might be useful to model some biological swarm systems, whenever the assumption of a ‘well mixed’ distribution may be applicable. However, organisms seldom move really randomly. Nor are they just simple particles. They pursue specific goals, aggregate or disperse in space, communicate and memorize. They have specific physiological states (e.g. energy-level) and morphologies (size, weights, etc.). These factors do not only affect their energetics, they also prominently affect the behaviours that they (choose to) perform. In addition to that, they frequently interact by direct and indirect communication and they tend to memorize past effects. Finally, also the environment in which they operate is highly structured and this heterogeneity is also dynamic. For example, the flower patches that honeybee foragers visit in the morning might already be gone in the afternoon, when other patches offer rich nectar supply. All these factors describe important discrepancies between biological life forms and atoms or molecules. Thus, it is likely that models, which were originally derived from physics and chemistry, might not hold well for biological swarm systems as soon as a certain level of abstraction has to be overcome. In these cases, individual-based models or even multi-agent models (see [27–30] for more information) might be a better choice. The faster and cheaper computer hardware becomes the more feasible these approaches get. In this special issue, we selected a variety of articles that have chosen this modelling approach, based on the arguments mentioned above. Of course, there is also a downside in multi-agent modelling: These models tend to grow rather complex. They are based on multi-agent modelling tools (libraries) which are sometimes black-boxes (discretization, random number generators, etc.) and depict just one out of many specific cases which would perhaps be summarized by a more general modelling approach (e.g. ODE models). However, as we try to demonstrate in this special issue, these models produce helpful results. Their predictions are actually testable hypotheses that suggest novel experiments that can be performed with the real animals. In contrast to very abstract models, the level of detail of these models allows to predict the outcome of experimental procedures quantitatively and not only qualitatively. We have tried to represent the two main methods (multi-agent system or robot system) and the two main objectives of the particular research (understanding natural systems or engineering of bio-inspired artificial systems) in Figure 1.

Figure 1. Classification of the articles (numbered as ordered in this issue) according to two criteria: method (multi-agent system or robot system) and objective (understanding natural systems or engineering of bio-inspired artificial systems); obviously this classification cannot be fully coherent.

Based on empirical findings and based on the understanding of biological swarm systems, which was derived from modelling and simulation, a variety of optimization algorithms and engineered applications have been reported which use natural collective systems as their main source of inspiration. The activities in this new scientific community have led to the emergence of the new field of science called ‘swarm intelligence’ [31–33]. Often seen as a subset of the older field of ‘artificial intelligence’, the methods of swarm intelligence are not based on sophisticated and complex engineered reasoning architectures. Instead, swarm intelligence exploits the emergent properties of self-organizing interaction networks operated by computationally inexpensive, reactive and individually often non-cognitive masses of agents [34–37]. In swarm intelligence, cognition arises, if at all, only on the collective level, thus potentially giving us a new approach to understand our own human cognition. Most prominent examples of ‘swarm intelligent’ algorithms are ‘ant colony optimization’ (ACO) [38], ‘particle swarm optimization’ (PSO) [33,39] and ‘bees algorithm’ [40].

Originally, the term ‘swarm’ was adopted by engineers and computer scientists mainly from flocks of birds and shoals of fish. However, their main source of inspiration was social insects, which are, in biology, correctly attributed with the term ‘colony’. Despite this obviously incorrect nomenclature, the aspects of collective intelligence in social insects are – in today's literature – classified as ‘swarm intelligence’ and not as ‘colony intelligence’. For the mechanisms involved in swarm intelligence of social insects, heterogeneity of the environment and heterogeneity of the animals itself (workers, soldiers, nurses, scouts, queens, etc.) are important aspects.

As was already mentioned above, ODE-based modelling has been around since decades, while agent-based models of social insect ecology have prospered more recently. These models support the creation of ‘virtual colonies’, incorporating the self-organized spatial ordering of the colony's inner space, as well as the non-random interaction patterns among the workers. Prominent examples of these multi-agent models have been produced for honeybees [41–53], ants [54,55] and wasps [56]. However, these multi-agent models usually incorporate the physical reality only partially (e.g. concerning friction and inertia). Thus, the constraints and capabilities of these agents still differ significantly from their real-world counterparts. One option to create physical agents is to use robotic systems, especially autonomous mobile robots, as a physical model. If these robots show a certain degree of similarity to the natural organisms that should be modelled (bio-mimicry) and if they are driven by the bio-inspired agent programs that were developed and refined in multi-agent simulation before, these robotic systems could act as excellent models of the real system.

One example of such systems is ‘swarm robotics’ [57–59], which has been on the stage since several years. This approach of robot engineering aims for picking up the advantages observed in natural swarm systems (flexibility, robustness, scalability and simplicity of individual agents). Swarm robotics wants to achieve the functionality of one singular large and complex robot by the joint efforts of a swarm of many simple and small agents. Inspired by their natural counterparts, it is self-organization, swarm intelligence and emergence that allows this swarm to achieve a complex task which cannot be achieved by one of the simple swarm members alone. Several swarm algorithms have been suggested and tested in swarm robotics, mainly inspired by the behaviour of ants [60–64], honeybees [65–70] and also slime-mould [71], cockroaches [72] and fish [73]. To understand the dynamics of these artificially created swarm systems, again mathematical modelling and simulation [58,74–79] becomes important. On the one hand, these models help to explore and to tune these swarm systems; on the other hand, they allow to monitor the extent at which the system was altered in the process of bio-inspiration, which always involves a ‘translation’ of mechanisms from the natural to the engineering domain. For both the original natural and the artificially created systems, mathematical models allow to depict the ‘core functionality’. Hence, these models allow comparisons of both types of systems.

2. Modelling biological swarms

The article of I. Karsai and A. Runciman (1) is an excellent example of how multi-agent modelling of a natural swarm system by multi-agent modelling can improve the understanding of this system. In an agent-based approach the authors demonstrate that a group of wasps on the nest, which seem to be inactive, play an important role in the self-regulatory capabilities of such wasp colonies. These inactive wasps serve as a collective ‘common stomach’ for the colony which spreads the information about the colonies' current status of water supply and water demand throughout the whole colony. This spread of information is achieved by wasp-to-wasp feeding–a behaviour that is well described by a small set of simple rules. For example, ‘the wasp that has more water donates a fraction of the surplus water to a wasp with a lower water content in her crop’. This common stomach allows all foragers (water foragers, pulp foragers, nest builders) to query the current situation and to adapt their individual task allocation in accordance to this information. In consequence, the colony shows adaptive collective behaviour as observed by shifts in division of labour and task partitioning in response to various perturbations of the system. The study investigates several worker-to-forager ratios and predicts the resulting working efficiency of the colony members. The article builds upon previous modelling work, based on an ODE model which studied the wasp system in a mean-field approach. The study at hand expands these insights by demonstrating that the observed collective behaviours can be observed also in a spatially explicit model that is based on simple behavioural rules of inter-adult worker interactions.

Also in the article of A. Dornhaus (2), the regulation of foraging activities in a social insect colony is the main focus of the study. Like the previously discussed article, this study adopts an agent-based approach to allow modelling of collective behaviour based on parallel execution of individual agent behaviours. The agent-based approach allows an easy incorporation of spatial aspects. Also the mechanisms of information processing/sharing, task allocation and recruitment mechanisms vary in the observed set of species. For example, honeybees are able to recruit other forager bees to their previously visited food source by communicating spatial information through the well-known ‘waggle dance’ [14]. In addition, the division of labour between nectar foragers and nectar storers is regulated by another dance, the ‘tremble dance’ [15]. In contrast to that, the foraging for nectar in bumblebees is less complex, as these dances and division of labour are missing. Besides foraging, also other tasks are performed by workers in these colonies. In most cases it is individual decision making that is performed in parallel by thousands or hundreds of workers that generates task-related subgroups of workers. How much work is then performed depends on how many workers decided to perform the specific tasks, at which place in the colony they decided to do so and at which intensity they perform these tasks. It is clear that, from a colony-level point of view, regulation of these decisions is beneficial for colony fitness, to let the appropriate number of workers choose the most needed tasks at the right locations in the colony. Natural selection has created a rich bouquet of worker-to-worker interactions and simple chemical/physical/behavioural cues that allows these regulations to happen in a decentralized but efficient manner. Besides the regulation of nectar foragers and nectar storers the most prominent examples are comb building, brood care (nursing) and thermo-regulation (fanning and heating). The use of multi-agent simulation allows to generate different sets of agent rules which allows for a certain level of detail creating a model that is biologically useful. Also spatial heterogeneity of food sources, of cues and of worker localization can easily be implemented by such models. The article of A. Dornhaus demonstrates and discusses the application of two of these models: one for making predictions about honeybee and bumblebee foraging decisions and another for predicting the efficiency of intra-colonial task selection based on different regulation mechanisms. The results found in these studies are biologically interesting and the predictions of these models produce several interesting hypotheses that have to be investigated empirically in future.

In the study of H. Hamann, T. Schmickl and K. Crailsheim (3) the collective motion principles of slime mould amoebas are modelled in an abstract agent-based approach. The emphasis of this study is on a dynamical systems interpretation of the collective behaviour. While the system almost always converges to simple patterns, the complexity during the transient (time period between initialization and steady state) is higher. The authors discuss the possibility of extending the transient and investigate its dependency on certain system parameters. From a modelling perspective this study raises the question whether investigations of transients in mathematical models of swarms should be considered to be of more importance.

3. Engineering artificial swarm systems

The contribution of M. Varga, S. Bogdan, M. Dragojevic and D. Miklic (4) is focused on a model of collective search and decision making. The authors develop a multi-agent system of a heterogeneous swarm of scouts and labourers with applications to swarm robotics. The task of the swarm is to localize a target of most relevance within a given time interval. The definition of the agents' equation of motion raises the question of how to model deterministic and non-deterministic parts of the behaviour. This is the typical combination of exploitation and exploration in social insect behaviour which is an interesting modelling challenge. In addition to a stochastic component, a heuristic component is added. It incorporates a simple form of memory in the system and introduces temporal correlations. In a second part of the article the decision-making process is analysed exhaustively.

In the article by M. Read, P.S. Andrews, J. Timmis and V. Kumar (5) the important methodological question of how to calibrate agent-based simulations in the presence of epistemic uncertainties is addressed. The authors relate their reasoning to their own background of application which is the modelling and simulation of the immune system. The idea there is to integrate knowledge that was acquired in wet-lab experiments into a model that might, in turn, indicate the areas where further experiments are necessary. The article addresses a sophisticated combination of uncertainty, sensitivity and robustness analysis and parameter perturbations. For example, the analysis might uncover that the predictions of the agent-based model rest on a highly influential parameter which has to be precisely specified possibly within a range more specific than backed by biological literature. Obviously the relevance of predictions by agent-based models can be overestimated, if they are not supported by a fine methodology. The article represents a great effort in increasing researchers' sensitivity for this fact and proposes solutions.

The article of M. Bodi, R. Thenius, T. Schmickl and K. Crailsheim (6) demonstrates how bio-inspiration can present more interesting (new) properties in an artificial system than it was observed in the inspiring natural system before. The artificial system might show extra characteristics and might behave even more swarm intelligent than the natural source of inspiration. The study presented here builds on a simulation study of the BEECLUST algorithm, which is derived originally from honeybees that aggregate in a temperature field. This algorithm was already ported to a robot swarm [67,69] and was also analysed by mathematical modelling [80,81]. As a result of these modelling efforts, the article at hand extends the concept of BEECLUST to allow the swarm-intelligent self-coordination of two coexisting robotic swarms that pursue different goals while running in parallel and while sharing the same environment. This simulation study investigates the importance of the swarm density concerning the success rate of individual swarm members. At low densities the rate of interactions within swarm members is too low to generate feedbacks that impose efficient governing forces on the swarm's collective behaviours. The original BEECLUST algorithm was altered in a way that each of the two swarms draws benefits from the presence of the members of the other swarm. Although both swarms pursue different goals they self-organize in a blended manner what finally yields a kind of ‘swarm-level symbiosis’ as an emergent property. Again here, multi-agent simulation allowed a decent study of parameters (swarm densities) and environmental conditions (gradient fields). Without a direct counterpart in nature and without extensive empirical experimentation with robots, a sophisticated new swarm algorithm was developed purely based on insights gained from prior modelling of singular swarms. Even bio-inspiration could not have suggested such an algorithm, as in the natural source of inspiration, comparable phenomena have not been reported so far. This clearly shows that bio-inspiration and modelling together can lead to creative generation of novel algorithms, even beyond the level that nature suggests.

The contribution of N. Bredeche, J.-M. Montanier, W. Liu and A.F.T. Winfield (7) bridges the wide field from models of evolutionary dynamics to the engineering question of how to produce intelligently acting robots. Having to go over everything from theory to practice is typical for evolutionary robotics studies of today. In their research they face the challenge of (semi-)automatically synthesizing control software for a swarm (or ‘population’) of autonomous robots possibly even without knowing important features of the environment beforehand. The approach of evolutionary robotics is to apply distributed online optimization algorithms that are inspired by natural evolution. This way their work can be interpreted as a computational model of evolutionary dynamics (in case of applying robot simulations) and even as an embodied model of evolutionary dynamics (in case of applying real robots). From the perspective of the engineer they are, however, also facing the problem of a missing objective function that could be used by the robots to evaluate the utility of their behaviour. In contrast to natural evolution the engineer has to solve a predefined task that should be performed by the robots. In addition, behaviour evaluations in the real world are typically also noisy which increases the complexity of the challenge. The authors mention a potential solution, the Selfish Gene metaphor, which can be summarized as ‘the best behaviour is the one which spreads its genes across the whole population’. At that point the setting can be viewed as a modelling problem again because one has to figure out how the system dynamics have to be designed in a way that the desired behaviour coincides with the best gene-spreading strategy. By addressing all theoretical challenges and by reporting the successful case study the article constitutes a remarkably advancement in evolutionary robotics.

In the article by S. Kernbach, V. A. Nepomnyashchikh, T. Kancheva and O. Kernbach (8) a swarm of Jasmine robots is studied in a ‘foraging for energy’ scenario. The same type of robots was also studied by the article of Bodi et al. mentioned above. Similar to that article, also Kernbach et al. find a critical and an optimal swarm density. Beyond the critical density, the robots block each others' movement, thus performance of the swarm diminishes. The optimal density is characterized by the fact that the number of robot-to-robot interactions in terms of IR-LED communication is maximized but physical motion of the robots is not impaired. In this configuration the swarm can – at least theoretically – maximize its benefit from any swarm algorithm. In the study presented here, the robots perform a general task that is to stay in contact with other robots while driving in the arena and avoiding obstacles. This task is usually called ‘ad-hoc sensor networking’, as the swarm of robots collectively collects sensor data which is routed through the swarm by the ever-changing but frequent robot-to-robot contacts. However, robots spend energy over time, thus they have to recharge similar to animals that have to eat from time to time. In the investigated scenario, these swarm robots have to find an energy source (socket), to plug themselves in there and to recharge. After that they have to leave the energy station as quickly as possible, to minimize blocking time of the energy source and to maximize their own working time. From a swarm-level perspective, the efficiency of the system can be measured by the following three swarm-level observables. For a high efficiency, the number of individual robots that ran out of energy should be minimized, the time fraction the average robot spends with the task ‘sensor-networking’ should be maximized and the total amount of energy that is harvested should be maximized to ensure robustness of the energy supply. Clearly, these efficiency criteria are non-independent from each other; the latter two are even contradictory. The more energy is harvested, the less likely the robots will run out of energy, but the less fraction of time can be spent for sensor networking. The swarm behaviour is constituted by the sum of all individual behaviours and might additionally show emergent phenomena. In this article, the resulting efficiency of several variants of individual behavioural programs, for example, ‘threshold-based task selection’ versus ‘inertia-based task selection’ is studied empirically. The fact that these empirical studies are accompanied with decent mathematical modelling of the swarm systems makes this article a prominent example of how ‘model-driven experimentation’ can enhance the output of empirical research and how it can deepen the understanding of empirically observed phenomena.

4. Conclusions

In this special issue of MCMDS, we collected a set of articles that, on the one hand, model natural swarm systems to achieve a better understanding of their self-regulating principles and of their mechanisms of collective decision making. These insights may help to improve the performance of existing swarm-intelligent optimization algorithms and swarm robotic behavioural algorithms. In addition, such insights into natural systems can even suggest novel classes of such algorithms, which have not been used so far. On the other hand, we collected articles that use mathematical models to analyse and predict the behaviour of artificial swarm systems. These mathematical analyses allow not only to tune the considered artificial swarm system, they can also highlight the core challenges and problem sets these systems have to deal with. These insights, expressed in mathematical form, may allow the community of theoretical biologists to investigate natural systems with a new set of research questions. The answers to these questions might then again push forward the level of knowledge about the natural system but might also provide new solutions for the community of swarm engineers in the fields of optimization and robot engineering.

The articles collected in this special issue clearly show how close empirical research is intertwined with mathematical modelling research. All models we collected have been parameterized by empirical measurements in the natural or engineered swarm system. In many of the collected articles, models were formulated and analysed in a way that these models suggest/predict interesting emergent phenomena in the swarm system. These predictions were then either immediately experimented in the real system and reported in the same article or they were presented as testable hypotheses suggesting future empirical research. Either way, the results of these empirical studies will lead to adaptations of the models and – in turn – will affect their predictions and characteristics. This ‘model driven empirical research’ is – in our opinion – the most important value of mathematical models and the following articles reflect this research paradigm.

In addition, these articles demonstrate that swarm systems are global phenomena. They occur on all size scales, from cosmology down to the atomic level, and they are not confined to a specific domain in science. However, every scientific community that deals with swarm systems is producing mathematical models of these systems which represent a common language for these scientists. But even more than that, these models allow to search for the ‘common core’ that all swarm systems share. This common core allows then to generalize results gained in one study to other domains, ‘infecting’ these scientific domains with new provoking ideas and with novel points of view. Thus, mathematical models are infectious, as they spread across scientific domains and ‘infect’ researchers in other domains with new hypotheses. This is due to their level of abstraction and the ‘common language’ of mathematics. Thus, they are not confined by the borders of language (domain-specific speak) and by blocking discussion about (mostly irrelevant) details. Mathematical models are mainly the manifestation of ideas and ideas tend to spread. However, ideas influence each other as they spread, thus, on some level of abstraction, they tend to swarm.

Acknowledgements

The editing of this special issue was supported by the Austrian Federal Ministry of Science and Research (BM.W_F) and by the European Commission (EC): EU-IST-FET project ‘SYMBRION, no. 216342; EU-ICT project ‘REPLICATOR’, no. 216240; EU-ICT project ‘CoCoRo’, no. 270382; as well as by the following Austrian Science Fund (FWF) research grants: P15961-B06 and P19478-B16.