Fundamental Collective Behaviors in Swarm Robotics

Abstract

In this chapter, we present and discuss a number of types of fundamental collective behaviors studied within the swarm robotics domain. Swarm robotics is a particular approach to the design and study of multi-robot systems, which emphasizes decentralized and self-organizing behavior that deals with limited individual abilities, local sensing, and local communication. The desired features for a swarm robotics system are flexibility to variable environmental conditions, robustness to failure, and scalability to large groups. These can be achieved thanks to well-designed collective behavior – often obtained via some sort of bio-inspired approach – that relies on cooperation among redundant components. In this chapter, we discuss the solutions proposed for a limited number of problems common to many swarm robotics systems – namely aggregation, synchronization, coordinated motion, collective exploration, and decision making. We believe that many real-word applications subsume one or more of these problems, and tailored solutions can be developed starting from the studies we review in this chapter. Finally, we propose possible directions for future research and discuss the relevant challenges to be addressed in order to push forward the study and the applications of swarm robotics systems.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Designing Swarm Behaviours

Imagine the following scenario: in a large area there are multiple items that must be reached, and possibly moved elsewhere or processed in some particular way. There is no map of the area to be searched, and the area is rather unknown, unstructured, and possibly dangerous for the intervention of humans or any valuable asset. The items must be reached and processed as quickly as possible, as a timely intervention would correspond to a higher overall performance. This is the typical scenario to be tackled with swarm robotics. It contains all the properties and complexity issues that make a swarm robotics solution particularly appropriate. Parallelism, scalability, robustness, flexibility, and adaptability to unknown conditions are features that are required from a system confronted with such a scenario, and exactly those features are sought in swarm robotics research.

Put in other terms, swarm robotics promises the solution of complex problems through robotic systems made up of multiple cooperating robots. With respect to other approaches in which multiple robots are exploited at the same time, swarm robotics emphasizes aspects like decentralization of control, limited individual abilities, lack of global knowledge, and scalability to large groups.

One important aspect that characterizes a swarm robotics system concerns the robotic units, which are unable to solve the given problem individually. The limitation is given either by physical constraints that would prevent the single robot to individually tackle the problem (e. g., the robot has to move some items that are too heavy), or by time constraints that would make a solitary action very inefficient (e. g., there are too many items to be collected in a limited time). Another source of limitation for the individual robot comes from its inability to acquire a global picture of the problem, having only access to partial (local) information about the environment and about the collective activity. These limitations imply the need for cooperation to ensure task achievement and better efficiency. Groups of autonomous cooperating robots can be exploited to synergistically achieve a complex task, by joining forces and sharing information, and to distributedly undertake the given task and achieve higher efficiency through parallelism.

The second important aspect in swarm robotics is redundancy in the system, which is intimately connected with robustness and scalability. Swarm robotics systems are made by homogeneous robots (or by relatively few heterogeneous groups of homogeneous robots). This means that the failure of a single or a few robots is not a relevant fact for the system as a whole, because the failing robot can easily be replaced by another teammate. Differently from a centralized system, in a swarm robotics system there is no single point of failure, and every component is interchangeable with other components. Redundancy, distributed control, and local interactions also allow for scalability, enabling the robotic system to seamlessly adapt to varying group sizes. This is a significant advantage with respect to centralized systems, which would present an exponential increase in complexity for larger group sizes.

Because all the above features are desiderata, the problem remains as to how to design and implement such a robotic system. The common starting point in swarm robotics is the biological metaphor, for which the fundamental mechanisms that govern the organization of animal societies can be distilled in simple rules to be implemented in the robotic swarm. This approach allowed us to extract the basic working principles for many types of collective behavior, and several examples will be presented in this chapter. However, it is worth noting that swarm robotics systems are not constrained to mimicking nature. Indeed, in many cases there is no biological example to be taken as reference, or the mechanisms observed in the natural system are too difficult to be implemented in the robotic swarm (e. g., odor perception is an open problem in robotics, preventing easy exploitation of pheromone-based mechanisms by using real chemicals). Still, even in those systems that have no natural counterpart, the relevant property that should be present is self-organization, for which group behavior is the emergent result of the numerous interactions among different individuals. Thanks to self-organization, simple control rules repeatedly executed by the individual robots may result in complex group behavior.

If we consider the scenario presented at the beginning of this chapter, it is possible to recognize a number of problems common to many swarm robotics systems, which need to be addressed in order to develop suitable controllers. One first problem in swarm robotics is having robots get together in some place, especially when the robotic system is composed by potentially many individuals. Getting together (i. e., aggregation) is the precondition for many types of collective behavior, and needs to be addressed according to the particular characteristics of the robotic system and of the environment in which it must take place. The aggregation problem is discussed in Sect. 71.2. Once groups are formed, robots need some mechanism to stay together and to keep a coherent organization while performing their task. A typical problem is, therefore, how to maintain such coherence, which corresponds to ensuring the synchronization of the group activities (Sect. 71.3), and to keep the group in coordinated motion when the swarm must move across the environment (Sect. 71.4). Another common problem in swarm robotics corresponds to searching together and processing some items in the environment. To this aim, different strategies can be adopted to cover the available space, and to identify relevant navigation routes without resorting to maps and global knowledge (Sect. 71.5). Finally, to maintain coherence and efficiency, the swarm robotics system is often confronted with the necessity to behave as a single whole. Therefore, it must be endowed with collective perception and collective decision mechanisms. Some examples are discussed in Sect. 71.6. For each of these problems, we describe some seminal work that produced solutions in a swarm robotics context. In each section, we describe the problem along with some possible variants, the biological inspiration and the theoretical background, the relevant studies in swarm robotics, and a number of other works that are relevant for some particular contribution given to the specific problem.

2 Getting Together: Aggregation

Aggregation is a task of fundamental importance in many biological systems. It is the basic behavior for the creation of functional groups of individuals, and therefore, supports the emergence of various forms of cooperation. Indeed, it can be considered a prerequisite for the accomplishment of many collective tasks. In swarm robotics too, aggregation has been widely studied, both as a standing-alone problem or within a broader context. Speaking in general terms, aggregation is a collective behavior that leads a group of agents to gather in some place. Therefore, from a (more or less) uniform distribution of agents in the available space, the system converges to a varied distribution, with the formation of well recognizable aggregates. In other words, during aggregation there is a transition from a homogeneous to a heterogeneous distribution of agents.

2.1 Variants of Aggregation Behavior

Aggregation can be achieved in many different ways. The main issue to be considered is whether or not the environment contains pre-existing heterogeneities that can be exploited for aggregation: light or humidity gradients (think of flies or sow bugs), corners, shelters, and so forth represent heterogeneities that can be easily exploited. Their presence can, therefore, be at the basis of a collective aggregation behavior, which, however, may not exploit interactions between different agents. Instead, whenever heterogeneities are not present (or cannot be exploited for the aggregation behavior), the problem is more complex. The agents must behave in order to create the heterogeneities that support the formation of aggregates. In this case, the basic mechanism of aggregation relies on a self-organizing process based on a positive feedback mechanism. Agents are sources of some small heterogeneity in the environment (e. g., being the source of some signal that can be chemical, tactile or visual). The more aggregated agents, the higher the probability to be attracted by the signal. This mechanism leads to amplification of small heterogeneities, leading to the formation of large aggregates.

2.2 Self-Organized Aggregation in Biological Systems

Several biological systems present self-organized aggregation behavior. One of the best studied examples is given by the cellular slime mold Dictyostelium discoideum, in which aggregation is enabled by self-generated biochemical signals that support the migration of cells and the formation of a multi-cellular body [1, 2]. A similar aggregation process can be observed in many other unicellular organisms [3]. Social and pre-social insects also present multiple forms of aggregation [4, 5]. In all these systems, it is possible to recognize two main variants of the aggregation process. On the one hand, the agents can emit a signal that creates an intensity gradient in the surrounding space. This gradient enables the aggregation process: agents react by moving in the direction of higher intensity, therefore aggregating with their neighbors (Fig. 71.1). On the other hand, aggregation may result from agents modulating their stopping time in response to social cues. Agents have a certain probability to stop and remain still for some time. The vicinity to other agents increases the probability of stopping and of remaining within the aggregate, eventually producing an aggregation process mediated by social influences (Fig. 71.2). In both cases, the same general principle is at work. Aggregation is dependent on two main probabilities: the probability to enter an aggregate, which increases with the aggregate size, and the probability to leave an aggregate, which decreases accordingly. This creates a positive feedback loop that makes larger aggregates more and more attractive with respect to small ones. Some randomness in the system helps in breaking the symmetry and reaching a stable configuration.

Fig. 71.1 a–d

Aggregation process based on a diffusing signal that creates an intensity gradient. (a) Agents individually emit a signal and move in the direction of higher concentration. (b) The individual signals sum up to form a stronger intensity gradient in correspondence with forming aggregates. (c) A positive feedback loop amplifies the aggregation process until all agents are in the same cluster (d)

2.3 Self-Organized Aggregation in Swarm Robotics

On the basis of the studies of aggregation in biological systems,

Fig. 71.2 a–d

Aggregation process based on variable probability of stopping within an aggregate. (a) Agents move randomly and may stop for some time (gray agent). (b) When encountering a stopped agent, other agents stop as well, therefore increasing the size of the aggregate. (c) The probability of meeting an aggregate increases with the aggregate size for geometric reasons. Social interactions modulate the probability of leaving the aggregate, which diminishes with the increasing number of individuals. (d) Eventually, all agents are in the same aggregate

various robotic implementations have been presented, based on either of the two behavioral models described above. Of particular interest is the work presented in [6], in which the robotic system was developed to accurately replicate the dynamics observed in the cockroach aggregation experiments presented in [5]. In this work, a group of Alice robots [7] was used and their controller was implemented by closely following the behavioral model derived from experiments with cockroaches. The behavioral model consists of four main conditions:

• i Moving in the arena center

• ii Moving in the arena periphery

• iii Stopping in the center

• iv Stopping in the periphery.

When stopping, the mean waiting time is influenced by the number of perceived neighbors (for more details, see [6]). The group behavior resulting from the interaction among Alice robots was analyzed with the same tools used for cockroaches [5, 6]. The comparison of the robotic system with the biological model shows a very good correspondence, demonstrating that the mechanisms identified by the behavioral model are sufficient to support aggregation in a group of robots, with dynamics that are comparable to that observed in the biological system. Additionally, the robotic model constitutes a constructive proof that the identified mechanisms really work as suggested.

This study demonstrates, in terms of simple rules, the approach of distilling the relevant mechanisms that produce a given self-organizing behavior. A different approach consists in exploiting artificial evolution to synthesize the controllers for the robotic swarm. This allows the user to simply define some performance metric for the group and let the evolutionary algorithm find the controllers capable of producing the desired behavior. This generic approach has been exploited to evolve various self-organizing behaviors, including aggregation [8]. In this case, robots were rewarded to minimize their distance from the geometric center of the group and to keep moving. The analysis of the evolved behavior revealed that in all cases robots are attracted by teammates and repelled by obstacles. When a small aggregate forms, robots keep on moving thanks to the delicate balance between attractive and repulsive forces. This makes the aggregate continuously expand and shrink, moving slightly across the arena. This slow motion of the aggregate makes it possible to attract other robots or other aggregates formed in the vicinity, and results in a very good scalability of the aggregation behavior with respect to the group size. This experiment revealed a possible alternative mechanism for aggregation, which is not dependent on the probability of joining or leaving an aggregate. In fact, robots here never quit an aggregate to which they are attracted. Rather, the aggregates themselves are dynamic structures capable of moving within the environment, and in doing so they can be attracted by neighboring aggregates, until all robots belong to the same group.

2.4 Other Studies

The seminal papers described above are representative of other studies, which either exploit a probabilistic approach [10, 9], or rely on artificial evolution [11]. Approaches grounded on mathematical models and control theory are also worth mentioning [12, 13]. Other variants of the aggregation behavior can be considered. The aggregate may be characterized by an internal structure, that is, agents in the aggregate are distributed on a regular lattice or form a specific shape. In such cases, we talk about pattern/shape formation [14]. Another possibility is given by the admissibility of multiple aggregates. In the studies mentioned so far, multiple aggregates may form at the beginning of the aggregation process, but as time goes by smaller aggregates are disbanded in favor of larger ones, eventually leading to a single aggregate for the whole swarm. However, it could be desirable to obtain multiple aggregates forming functional groups of a specific size. In this case, it is necessary to devise mechanisms for controlling the group size [15].

3 Acting Together: Synchronization

Synchronization is a common phenomenon observed both in the animate and inanimate world. In a synchronous system, the various components present a strong time coherence between the individual types of behavior. In robotics, synchronization can be exploited for the coordination of actions, both within a single or a multi-robot domain. In the latter case, synchronization may be particularly useful to enhance the system efficiency and/or to reduce the interferences among robots.

3.1 Variants of Synchronization Behavior

Synchronization in a multi-agent system can be of mainly two forms: loose and tight. In the case of loose synchronization, we observe a generic coordination in time of the activities brought forth by different agents. In this case, single individuals do not present a periodic behavior, but as a group it is possible to observe bursts of synchronized activities. Often in this case there are external cues that influence synchrony, such as the daylight rhythm. On the other hand, it is possible to observe tight synchronization when the individual actions are perfectly coherent. To ensure tight synchronization in a group, it is possible to rely on either a centralized or a distributed approach. In the former, one agent acts as a reference (e. g., a conductor for the orchestra or the music theme for a ballet) and drives the behavior of the other system components. In the latter, a self-organizing process is in place, and the system shows the ability to synchronize without an externally-imposed rhythm. It is worth noting that tight synchronization does not necessitate individual periodic behavior, neither in the centralized nor in the self-organized case. For instance, synchronization has also been studied between coupled chaotic systems [16]. In the following, we focus on self-organized synchronization of periodic behavior, which is the most studied phenomenon as it is commonly observed in many different systems.

3.2 Self-Organized Synchronization in Biology

Although synchronization has always been a well-known phenomenon [17], its study did not arouse much interest until the late 1960s, when Winfree began investigating the mechanisms underlying biological rhythms [18]. He observed that many systems in biology present periodic oscillations, which can get entrained when there is some coupling between the oscillators. A mathematical description of this phenomenon was first introduced by Kuramoto [19], who developed a very influential model that was afterwards refined and applied to various domains [17].

Similar mechanisms are at the base of the synchronous signaling behavior observed in various animal

species [3]. Chorusing is a term commonly used to refer to the coordinated emission of acoustic communication signals by large groups of animals. To cite a few examples, chorusing has been observed in frogs, crickets, and spiders. However, probably the most fascinating synchronous display is the synchronous flashing of fireflies from South-East Asia. This phenomenon was thoroughly studied until a self-organizing explanation was proposed to account for the emergence of synchrony [20].

A rather simple model describes the behavior of fireflies as the interactions between pulse-coupled oscillators [21]. In Fig. 71.3, the activity of two oscillators is represented as a function of time. Each oscillator is of the integrate-and-fire type, which well represents a biological oscillator such as the one of fireflies. The oscillator is characterized by a voltage-like variable that is integrated over time until a threshold is reached. At this point, a pulse is fired and the variable is reset to the base level (Fig. 71.3). Interactions between oscillators take the form of constant phase shifts induced by incoming pulses, which bring other oscillators close to the firing state, or make them directly fire. These simple interactions are sufficient for synchronization; in a group of similarly pulse-coupled oscillators, constant adjustments of the phase made by all the individuals lead to a global synchronization of pulses (for a detailed description of this model, see [21]).

Fig. 71.3

Synchronization between pulse-coupled oscillators. The oscillator emits pulses each time its state variable reaches the threshold level (corresponding to $1$ in the plot). When one oscillator emits a pulse, its state is reset while the state of the other oscillator is advanced by a constant amount, which corresponds to a phase shift, or to the oscillator firing if it overcomes the threshold

3.3 Self-Organized Synchronization in Swarm Robotics

The main purpose of synchronization in swarm robotics is the coordination of the activities in a group. This can be achieved in different ways, and mechanisms inspired by the behavior of pulse-coupled oscillators have been developed. In [15], synchronization is exploited to regulate the size of traveling robotic aggregates. Robots can emit a short sound signal (a chirp), and enter a refractory state for a short time after signaling. Then, robots enter an active state in which they may signal at any time, on the basis of a constant probability per time-step. Therefore, the chirping period is not constant and depends on the chirping probability. In this state, robots also listen to external signals and react by immediately emitting a chirp. This mechanism, similar to chorusing in frogs and crickets, leads to synchronized emission of signals. Thanks to this simple synchronization mechanism, the size of an aggregate can somehow be estimated. Given the probabilistic nature of chirping, a robot has a probability of independently initiating signaling that depends on the number of individuals in the group; estimating this probability by listening to own and others’ chirps allows an approximate group size estimation. Synchronization, therefore, ensures a mechanism to keep coherence in the group, which is the precondition for group size estimation.

In [22], synchronization is instead necessary to reduce the interferences between robots, which periodically perform foraging and homing movements in a cluttered environment. Without coordination, the physical interferences between robots going toward and away from the home location lead to a reduced overall performance. Therefore, a synchronization mechanism based on the firefly behavior was devised. Robots emit a signal in correspondence to the switch from foraging to homing. This signal can be perceived by neighboring robots within a limited radius and induces a reset of the internal rhythm that corresponds to a behavioral shift to homing. Despite the limited range of communication among robots, a global synchronization is quickly achieved, which leads the group to reduce interferences and increase the system performance [22].

A different approach to the study of synchronization is described in [23]. Here, artificial evolution is exploited to synthesize the behavior of a group of robots, with the objective of obtaining minimal communication strategies for synchronization. Robots were rewarded to present an individual periodic movement and to signal in order to synchronize the individual oscillations. The results obtained through artificial evolution are then analyzed to understand the mechanisms that can support synchronization, showing that two types of strategies are evolved: one is based on a modulation of the oscillation frequency, the other relies on a phase reset. These two strategies are also observed in biological oscillators: for instance, different species of fireflies present different synchronization mechanisms, based on delayed or advanced phase responses [20].

3.4 Other Studies

While self-organized synchronization is a well-known phenomenon, its application in collective and swarm robotics has not been largely exploited. The coupled-oscillator synchronization mechanism was applied to a cleaning task to be performed by a swarm of micro robots [24]. Another interesting implementation of the basic model can be found in [25]. Here, synchronization is exploited to detect and correct faults in a swarm robotics system. It is assumed that robots can synchronize a periodic flashing behavior while moving in the arena and accomplishing their task. If a robot incurs some fault, it will forcedly stop synchronizing. This fault can be detected and recovered by neighboring robots. Similar to the heartbeat in distributed computing, correct synchronization corresponds to a well-functioning system, while the lack of synchronization corresponds to a faulty condition.

Finally, synchronization behavior may emerge spontaneously in an evolutionary robotics setup, even if they are not explicitly rewarded. In [26], synchronization of group activities evolved spontaneously as a result of the need to limit the interferences among robots in a foraging task. In [27], robots were rewarded to maximize the mean mutual information between their motor actions. Mutual information is a statistical measure derived in information theory, and roughly corresponds to the correlation between the output of two stochastic processes. Evolution, therefore, produced synchronous movements among the robots, which could actually maximize the mutual information while maintaining a varied behavior.

4 Staying Together: Coordinated Motion

Another fundamental problem for a swarm is ensuring coherence in space. This means that the individuals in the swarm must display coordinated movement in order to maintain a consistent spatial structure. Coordinated motion is often observed in groups of animals. Flocks of birds or schools of fish are fascinating examples of self-organized behavior producing a collective motion of the group. Similar problems need to be tackled in robotics, for instance for moving in formation or for distributedly deciding a common direction of motion.

4.1 Variants of the Coordinated Motion Behavior

The coordinated motion of a group of agents can be achieved in different ways. Also in this case, we can distinguish mainly between a centralized and a distributed approach. In a centralized approach, one agent can be considered the leader and the other agents follow (e. g., the mother duck with her ducklings). In the distributed approach, instead, there is no single leader and some coordination mechanism must be found to let the group move in a common direction. Of particular interest for swarm robotics are the coordinated motion models based on self-organization. Such models consider multi-agent systems that are normally homogeneous and characterized by a uniform distribution of information: no agent is more informed than the others, and there exists no a priori preference for any direction of motion (i. e., agents start being uniformly distributed in space). However, through self-organization and amplification of shared information, the system can break the symmetry and converge to a common direction of motion. A possible variant of

the self-organized coordinated motion consists in having a non-uniform distribution of information, which corresponds to having some agents that are more informed than the others on a preferred direction of motion. In this case, a few informed agents may influence the motion of the entire group.

4.2 Coordinated Motion in Biology

Many animal species present coordinated motion behavior, ranging from bacteria to fish and birds. Not all animal species employ the same mechanisms, but in general it is possible to recognize various types of interactions among individuals that have a bearing on the choice of the motion direction. Coordinated motion has mainly been studied in various species of fish, in birds, and in insect swarms [29, 30]. The most influential model was introduced by Huth and Wissel to describe the behavior of various species of fish observed [28]. In this model, it is assumed that each fish is influenced solely by its nearest neighbor. Also, the movement of each fish is based on the same behavioral model, which also includes some inherent random fluctuation. According to the proposed behavioral model, each fish follows essentially three rules:

• i Approach a far away individual

• ii Get away from individuals that are too close

• iii Align with the neighbor direction (Fig. 71.4).

  Fig. 71.4 a–c

  

  Self-organized coordinated motion in a group of agents. In the bottom part, a group of agents is moving in roughly the same direction. According to the model presented in [28], agents react to the closest neighbor within their perception range and follow three main rules: (a) agents move toward a neighbor when it is too far; (b) agents move away from a neighbor when it is too close; (c) agents rotate and align with a neighbor situated at intermediate distances. The iterated application of these rules leads the group to move in a same direction

When the nearest neighbor is within the closest region, the fish reacts by moving away. When the nearest neighbor is in the farthest region, the fish reacts by approaching. Otherwise, if the neighbor is within the intermediate region, the fish reacts by aligning. These simple rules are sufficient to produce collective group motion, and the final direction emerges from the interactions among the individuals.

Starting from the above model, a number of variants have been proposed, which take into account different parameters and different numbers of individuals. In [31], a model including all individuals in the perceptual range was introduced, and a broad analysis of the parameters was performed, showing how minor differences at the individual level correspond to large differences at the group level. In [32], an experimental study on bird flocks in the field was performed, and position and velocity data were obtained for each bird in a real flock through stereo-photography and 3-D mapping. The data obtained data were used to verify the assumption about the number of individuals that each bird monitors during flocking, showing that this number is constant (and corresponds to about $7$ individuals) notwithstanding the varying density of the flock. Finally, in [33], a model was developed in which some of the group members have individual knowledge on a preferential direction. The model describes the outcome of a consensus decision in the flock as a result of the interaction between informed and uninformed individuals.

4.3 Coordinated Motion in Swarm Robotics

The models introduced for characterizing the self-organized behavior of fish schools or bird flocks have also inspired a number of interesting studies. The most influential work is definitely that of Reynolds, who developed virtual creatures called boids [34]. In this work, each creature executes three simple types of behavior:

• i Collision avoidance, to avoid crashing with nearby flockmates

• ii Velocity matching, to move in the same way of nearby flockmates

• iii Flock centering, to stay close to nearby flockmates.

Notice that the behavioral model corresponds to the models proposed in biological studies. The merit of this work is that it is the first implementation of the rules studied for real flocks in a virtual 3-D world, showing a close correspondence of the behavior of boids with that of flocks, herds, and schools. Reynolds’ research has been taken as inspiration by many other studies on coordinated motion, mainly in simulation. In [35], an implementation of the flocking behavioral model was proposed and tested on real robots. Robots use infrared proximity sensors to recognize the presence of other robots and their distance, which is necessary for collision avoidance and flock centering behavior. Additionally, a dedicated sensor to perceive the heading of neighbors was developed to support aligning behavior. This system, called the virtual heading system (GlossaryTerm

VHS

), is based on a digital compass and wireless communication. Despite the fact that a digital compass cannot reliably work in an indoor environment, it is assumed that neighboring robots have similar perceptions. The heading perceived with respect to the local north is communicated over the wireless channel, and it is exploited for alignment behavior. This system allowed testing the flocking behavior of small robotic groups in a physical setting and studying the dynamics of flocking with up to $1000$ simulated robots. This work was later extended in [36], by having a subgroup of informed individuals which could steer the whole flock, following the model presented in [33]. The dynamics of steered flocking have been studied by varying the percentage of informed robots in simulation, and tests with real robots have been performed as well.

4.4 Other Studies

As mentioned above, there exist numerous studies that were inspired by the schooling/flocking models. All these studies adopt some variants of the behavioral rules described above, or analyze the group dynamics under some particular perspective. A different approach to coordinated motion can be found in [37]. In this work, robots have to transport a heavy object and have imperfect knowledge of the direction of motion. They can, however, negotiate the goal direction by displaying their own preferred direction of motion and by adjusting it on the basis of the direction displayed by others. On the whole, this mechanism implements similar dynamics to the alignment behavior of the classical flocking model. Here, however, robots are connected together to the object to be transported, adding a further constraint to the system that obliges a good negotiation to allow motion. A similar constraint characterizes the coordinated motion studies with physically assembled robots presented in [38, 39]. Here, robots form a physical structure of varying shape and can rotate their chassis in order to match the direction of motion of the other robots. In this case, there is no direct detection of the motion direction of neighbors. Instead, robots can sense the pulling and pushing forces that are exerted by the other connected robots through the physical connections. These pulling/pushing forces are naturally averaged by the force sensor, which returns their resultant. Artificial evolution was exploited to synthesize an artificial neural network that could transform the forces sensed to motor commands. The results obtained show the impressive capability of self-organized coordination between the robots, as well as scalability and generalization to different size and shapes [38], and the ability to cope with obstacles and to avoid falling outside the borders of the arena [39].

5 Searching Together: Collective Exploration

Exploring and searching the environment is an important behavior for robot swarms. In many tasks, the swarm must interact with the environment, sometimes only to monitor it, but sometimes also to process materials or other kinds of resources. Usually, the swarm cannot completely perceive the environment, and the environment may also change during the operation of the robots. Hence, robots need to explore and search the environment to monitor for changes or in order to detect new resources.

To cope with its partial perception of the environment, a swarm can move, for instance using flocking, in order to explore new places (some locations may be unavailable, though). Hence, most of the environment can be perceived, but not at the same time. As in many other artificial systems, a tradeoff between exploration and exploitation exists and requires careful design choices.

5.1 Variants of Collective Exploration Behavior

There is no perfect exploration and search strategy because the structure of the environment in which the swarm is placed can take many different shapes. Strategies only perform more or less well as a function of the situation with which they are faced [40]. For instance, the swarm could be in a maze, in a open environment with few obstacles, or in an environment with many obstacles.

We identified a restricted number of environmental characteristics that play an important role in the choice of searching behavior in swarm robotics. These characteristics are commonly found in swarm robotics scenarios, and are the presence of a central place, the size of the environment, the presence of obstacles.

The central place is a specific location where robots must come back regularly, for instance for maintenance or to deposit foraged items. A scenario that involves a central place requires a swarm able to either remember or keep track of that location.

If the environment is closed (finite area) and not too large, the swarm may use random motion to explore, with fair chances to rapidly locate resources (or even the central place). In an open environment, robots can get lost very quickly. In this type of environment, it is necessary to use a behavior that allows robots to stay together and maintain connectivity.

Obstacles are environmental elements that constrain the motion of the swarm. If the configuration of the obstacles is known in advance, the swarm can move in the environment following appropriate patterns. In most cases, however, obstacles are unexpected or might be dynamic and may prevent the swarm from exploring parts of the environment.

5.2 Collective Exploration in Biology

In nature, animals are constantly looking for resources such as food, sexual partners, or nesting sites. Animals living in groups may use several types of behavior to explore their environment and locate these resources.

For instance, fish can take advantage of the number of individuals in a shoal to improve their capabilities to find food [41, 42, 43]. To do so, they move and maintain large interdistances between individuals. In this way, fish increase their perceptual coverage as well as their chances to find new resources.

Animals also heavily rely on random motion to explore their environment [44, 45, 46]. Usually the exploratory pattern is not fully random (that is, isotropic), because animals use all possible environmental cues at hand to guide themselves. Random motion can be biased towards a given direction, or it can be constrained in a specific area, for instance around a previously memorized location [47]. Some desert ants achieve high localization performance with odometry (counting their footsteps) and relying on gravity and the polarization of natural light. They may move randomly to look for resources but they are able to quickly return to their nest and also to return to an interesting location previously identified.

5.3 Collective Exploration in Swarm Robotics

One of the most common exploration strategies used in robotics is random exploration. In a typical implementation, robots wander in the environment until they perceive a feature of interest [48, 49, 50]. By doing this, robots possibly lose contact with each other and, therefore, their ability to work together. Hence this strategy is not suited for large or open environments. Due to the stochastic nature of the strategy, its performance can only be evaluated statistically. On average, the time to locate a feature is proportional to the squared distance with robots [44].

Systematic exploration strategies are very different. Robots use some a priori knowledge about the structure of the environment in order to methodically sweep it and find features. To ensure that robots do not repeatedly cover the same places, they may need to memorize which

places have already been explored. This is often implemented with localization techniques and mapping of the environment [51]. The advantage of this technique is that an answer will be found with certainty, and the time of exploration has a lower and upper bound if the environment is not open. However, memory requirements may be excessive, and the strategy is not suited for open environments.

Between the two extreme strategies reported in the previous paragraph lie a number of more specialized strategies that present advantages and drawbacks depending on the structure of the environment and the distribution of the resources.

Collective motion (which has already been detailed in Sect. 71.4) allows swarms to maintain their cohesion while moving through the environment. Flocking behavior can be employed in an open environment with a limited risk of losing contact between robots. The swarm behaves like a sort of physical mesh that covers part of the environment; to maximize the area covered during exploration robots can increase their interdistance during motion as much as possible.

Gas expansion behavior (Fig. 71.5) allows robots to quickly and exhaustively explore the surroundings of a central place [52, 53, 54, 55]. While one or several robots keep track of a central place, other robots try to move as far as possible from their neighbors, while still maintaining direct line of sight with at least one of them. The swarm behaves like a fluid or gas that penetrates the asperities of the environment. The exploration is very effective and any change or new resource within the perception range of the swarm is immediately perceived. However, since robots are bound to the central place, the area that they can explore is limited by the number of robots in the swarm. If robots do not stick to a central place, the resulting behavior shifts to a type of flocking or moving formation.

Fig. 71.5 a–d

Gas expansion behavior to monitor the surroundings of a central place. (a) The swarm starts aggregated around a central place (represented by a black spot). (b,c) Robots try to move as far as possible from their neighbors, while maintaining some visual or radio connection. (d) As a result, the whole swarm expands in the environment, like a gas, covering part of the environment

With chaining behavior, swarms can form a chain with one end that sticks to a central place and the other end that freely moves through the environment (Fig. 71.6). In [56], minimalistic behavior produces a static chain, but different types of chain motions can be imagined. In [57], for instance, chains can build up, move, and disaggregate until a resource is found. Contrary to gas expansion behavior, a chaining swarm may not immediately perceive changes in the environment because it has to constantly sweep the space. Chaining allows robots to cover a more important area than gas expansion behavior, ideally a disc of radius proportional to the number of robots.

Fig. 71.6 a–d

Chaining behavior in action with a central place represented by a large black dot, bottom left. (a) Robots start aggregated around the central place. (b) While maintaining visual or radio contact with neighbors, some robots change role and become part of a chain (grayed out). (c) Other robots move around the central place and encounter the early chain of robots. With some probability, they also turn into new parts of the chain. (d) At the end of the iterative process, robots form a long chain that spans through the environment and maintains a physical link to the central place

6 Deciding Together: Collective Decision Making

Decision making is a behavior used by any artificial system that must produce an adapted response when facing new or unexpected situations. Because the best action depends on the situation encountered, a swarm cannot rely on a pre-programmed and systematic reaction. Monolithic artificial systems make decisions all the time, by gathering information and then evaluating the different options at hand. However, when it comes to swarms, each group member might have its own opinion about the correct decision. If all individuals perceive the same information and process it in the same way, then they might independently make the same decision. However, in practice, the more common case is that individuals perceive partial and noisy information about the situation. Thus, if no coordination among group members occurs, a segregation based on differing opinions might take place, thereby removing the advantages of being a swarm. Therefore, the challenge is to have the whole group collaborate to make a collective decision and take action accordingly.

6.1 Variants of Collective Decision Making Behavior

There are mainly three mechanisms reported in the literature that allow swarms to make collective decisions. The first and most simple mechanism is based on opinion propagation. As soon as a group member has enough information about a situation to make up its mind, it propagates its opinion through the whole group.

The second mechanism is based on opinion averaging. All individuals constantly share their opinion with their neighbors and also adjust their own opinion in consequence. This iterative process leads to the emergence of a collective decision. The adjustment of the opinion is typically achieved with an average function, especially if opinions are about quantitative values such as a location, a distance, or a weight, for instance.

The third and last mechanism relies on amplification to produce a collective decision. In a nutshell, all individuals start with an opinion, and may decide to change their opinion to another one. The switch to a new opinion happens with a probability calculated on the basis of the frequency of this opinion in the swarm. Practically, this means that if an opinion is represented often in the group, it has also more chances of being adopted by an individual, which is why the term amplification is used.

Each of the three aforementioned mechanisms has some advantages over the others and may be preferred, depending on the situation faced. The factors that play an important role in collective decision processes include the speed and the accuracy needed to make the choice, the robustness of communication, and the reliability of individual information.

In terms of speed, opinion propagation allows fast collective decisions, in contrast with the two other mechanisms, which require numerous interactions among individuals. However, this speed generally comes at the cost of robustness or accuracy [58, 59, 60]. If communication is not robust enough, messages can be corrupted. The mechanism of opinion propagation is particularly sensitive to such effects, and a wrong or random collective decision might be made by a swarm in that case.

The averaging mechanism would produce a more robust decision because wrong information from erroneous messages is diluted in the larger amount of information present in the swarm [61]. However, opinion averaging works best if all individuals have roughly identical knowledge. If a small proportion of individuals have excellent knowledge to make the decision, while the remaining individuals have poor information, opinion propagation may produce better results than opinion averaging [33].

Lastly, the amplification mechanism is the main choice for a gradually emerging collective decision if opinions cannot be merged with some averaging function. Instead of adjusting opinions, individuals simply adopt new opinions with some probability. It is worth noting that this mechanism can produce good decisions even if individuals have poor information.

6.2 Collective Decision Making in Biology

The powerful possibilities of decision making in groups were already suggested by Galton back in 1905 [62]. In that paper, Galton reports the results of a weight-judging competition in which competitors had to estimate the weight of a fat ox. With slightly less than $800$ independent estimates, Galton observed that the average estimate was accurate to $1\%$ of the real weight of the ox. This early observation opened interesting perspectives about the accuracy of collective estimations, but it did not describe a collective decision mechanism, since Galton himself had to gather the estimates and apply some calculation to evaluate the estimate of the crowd.

More recent studies about group navigation have shown that groups of animals cohesively moving together towards a goal direction reach their objective faster than independent individuals [63, 64]. The mechanism of collective navigation not only allows the individuals to move and stay together, but it also acts as a distributed averaging function that locally fuses the opinions of individuals about the direction of motion, allowing them to improve their navigation performance.

In the last decades, the amplification mechanism has been identified as a source of collective decision in a broad range of animal species such as ants [65, 66], honeybees [67, 68], spiders [69], cockroaches [70], monkeys [71], and sheep [72].

Ants that choose one route to a resource probably constitute the most well-known example of the amplification mechanism. In [66], an ant colony is offered two paths to two identical resource sites. Initially, the two resources are exploited equally, but after a short time ants focus on a single resource. This collective choice happens because ants that have found the resource come back to the nest, marking the ground with a pheromone trail. The next ants that try to reach the resource are sensitive to this odor and have higher chances of following the path with higher pheromone concentration. As a result of this amplified response, a collective decision rapidly emerges. In addition, it was shown in [73] that when ants are presented two paths of different lengths to the same resource, the same pheromone-based mechanism allows them to choose the shortest path. This can be explained by the fact that ants using the shortest path need less time to make round trips, making the pheromone concentration on this path grow faster.

Quorum sensing is a special case of the amplification mechanism which has been notably used to explain nest site selection in ants and bees [74, 75, 76]. The most basic example of quorum sensing uses a threshold to dictate if individuals should change their opinion. If an individual perceives enough neighbors (above the threshold) that already share the opposite opinion, then it will in turn adopt this opinion. It has been shown that this threshold makes quorum sensing more robust to the propagation of erroneous information during the decision process. In addition, the accuracy of collective decisions made with quorum sensing may improve with group size, and cognitive capabilities of groups may outperform the ones of single individuals [77, 78]. In the case of nest site selection, cohesion is mandatory for the group. A cross inhibition mechanism complementing amplification was identified as a key feature to ensure that groups do not split [79].

6.3 Collective Decision Making in Swarm Robotics

In swarm robotics, opinion averaging has been used to improve the localization capabilities of robots. In [50], a swarm of robots carries out a foraging task between a central place and a resource site. The robots have to navigate back and forth between the two places and use odometry to estimate their location. As odometry provides noisy estimates, robots using solely this technique may quickly get lost. Here, robots can share and merge their localization opinions when they meet, by means of local infrared communication. By doing so, robots manage better localization and improve their performance in the foraging task. Moreover, robots associate a confidence level to their estimates, which is used to decide how information is merged. If a robot advertises an opinion with very high confidence, then the mechanism produces opinion propagation. Hence the two mechanisms of averaging and propagation are blended in a single behavior, and the balance between them is tuned by the user with a control parameter.

The aggregation behavior previously mentioned in Sect. 71.2.3 can be exploited to trigger collective decision making in situations where there are several environmental heterogeneities. In [80], the robots are presented two shelters and they choose one of them as a resting site by aggregating there. The behavior of the robots closely follows the one observed in cockroaches (Fig. 71.7). In [81], both robots and cockroaches are introduced in an arena with two shelters, demonstrating the influence of the two groups on each other when making the collective decision. The collective decision is the result of an amplification mechanism, implemented via the probability of a robot leaving an aggregate. This probability diminishes with the number of perceived neighbors, allowing larger aggregates to attract more robots.

Fig. 71.7 a–d

A swarm of robots is presented with two resource sites in its environment and must collectively choose one. (a) Initially, robots are randomly scattered. (b) Using a random walk, they move until a resource site is found. On average, the swarm is split in the two sites. (c) The more neighbors they perceive, the longer the robots stay. A competition between the two sites takes place and any random event may change the situation. Here a robot just left the top right site, further reducing the chances that other robots stay there. (d) The swarm has made a choice in favor of the bottom left site. The choice is stable, although some robots may frequently leave the site for exploration

6.4 Other Studies

The opinion averaging mechanism was deeply investigated with a general mathematical approach in [82, 83]. These studies demonstrate convergence of the mechanism and emphasize the importance of the topology of the communication network through which interactions take place.

Another amplification mechanism inspired from the behavior of honeybees was implemented in [84]. With this mechanism, it was shown that robots are able to make a collective decision and between two sites reliably choose the one offering the best illumination conditions.

The amplification mechanism based on pheromone trails, which is used by ants, has also inspired several swarm robotics studies. In [85, 86], the pheromone is replaced by light projected by a beamer. This implementation is limited to laboratory studies, but it allowed demonstrating path selection with robot swarms. In [87], the process is abstracted inside a network of robots that are deployed in the environment. Virtual ants hop from robots to robots and deposit pheromone inside them. Eventually, the shortest path to a resource is marked out by robots with high and sustained levels of pheromone.

7 Conclusions

In this chapter, we have presented a broad overview of the common problems faced in a swarm robotics context, and we pointed to possible approaches to obtain solutions based on a self-organizing process. We have discussed aggregation, synchronization, coordinated motion, collective exploration, and decision making, and we argued that many application scenarios could be solved by a mix of the above solutions. So, are we done with swarm robotics research? Definitely not.

First of all, the fact that possible solutions exist does not mean that they are the most suitable for any possible application scenario. Hardware constraints, miniaturization, environmental contingencies, and performance issues may require the design of different solutions, which may strongly depart from the examples given above. Still, the approaches we presented constitute a logical starting point, as well as a valid benchmark against which novel approaches can be compared.

Another important research direction consists in characterizing the self-organizing behavior we presented in terms of abstract properties, such as the time of convergence toward a stable state, sensitivity to parameter changes, robustness to failures, and so forth. From this perspective, the main problem is to ensure a certain functionality of the system with respect to the needs of the application and to predict the system features before actual development and testing. In many cases, a precise characterization of the system is not possible, and only a statistical description can be achieved. Still, such an enterprise would bring swarm robotics closer to an engineering practice, eventually allowing us to guarantee a certain performance of the developed system, as well as other properties that engineering commonly deals with.

The examples we presented all refer to homogeneous systems, in which all individuals are physically identical and follow exactly the same rules. This is, however, a strong simplification, which follows the tradition of biological modeling of self-organizing behavior. However, instead of being a limitation, heterogeneity is potentially a richness to be exploited in a swarm robotics system, which can lead to more complex group behavior. For instance, different individual reactions to features in the environment can be at the basis of optimal decision making at the group level [88]. Otherwise, heterogeneity between groups of individuals can be exploited for performing tasks that require specialized abilities, but maintaining an overall redundancy of the system that ensures robustness and scalability [89].

In conclusion, swarm robotics research still has many challenges to address, which range from the need for a more theoretical understanding of the relation between individual behavior and group dynamics, to the autonomy and adaptation to varied real-world conditions in order to face complex application scenarios (e. g., due to harsh environmental conditions such as planetary or underwater exploration, or to strong miniaturization down to the micro scale). Whatever the theoretical or practical driver is, we believe that the studies presented in this chapter constitute fundamental reference points that teach us how self-organization can be achieved in a swarm robotics system.