Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> This paper presents a series of experiments where a group of mobile robots gather 81 randomly distributed objects and cluster them into one pile. Coordination of the agents’ movements is achieved through stigmergy. This principle, originally developed for the description of termite building behaviour, allows indirect communication between agents through sensing and modification of the local environment which determines the agents’ behaviour. The efficiency of the work was measured for groups of one to five robots working together. Group size is a critical factor. The mean time to accomplish the task decreases for one, two, and three robots respectively, then increases again for groups of four and five agents, due to an exponential increase in the number of interactions between robots which are time consuming and may eventually result in the destruction of existing clusters. We compare our results with those reported by Deneubourg et al. (1990) where similar clusters are observed in ant colonies, generated by the probabilistic behaviour of workers. <s> BIB001 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> We study the problem of construction by autonomous mobile robots focusing on the coordination strategy employed by the robots to solve a simple construction problem efficiently. In particular we address the problem of constructing a linear 2D structure in a planar bounded environment. A "minimalist" single-robot solution to the problem is given, as well as two multi-robot solutions, which are natural extensions to the single-robot approach, with varying degrees of inter-robot communication. Results show that with minimal inter-robot communication (1 bit of state), there is a significant improvement in the system performance. This improvement is invariant with respect to the size of the environment. <s> BIB002 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> This paper investigates coherent collective motion, collective decision-making and behaviour transitions in networks of wireless connected mobile robots. Emergent global behaviour is achieved through the multiple interactions of locally communicating agents. Collectively, the robots hunt a moving target, immobilise that target and then hunt the next target. Using explicit communication over limited local range, the robots exchange their internal state vectors with neighbouring robots and update their internal states using deterministic transition rules. Configurations of a robot’s internal states and local sensor information are then translated into motion. The results demonstrate that the developed swarming algorithm is scalable and by exploiting the distributedness of the swarm shows an increasing success rate for increasing swarm sizes in domains of high noise. We have begun to validate our findings from simulation with real-robot experiments. <s> BIB003 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Workers of the Argentine ant, Iridomyrmex humilis,start to explore a chemically unmarked territory randomly. As the exploratory front advances, other explorers are recruited and a trail extends from it to the nest. Whereas recruitment trails are generally constructed between two points, these exploratory trails have no fixed destination, and strongly resemble the foraging patterns of army ants. A minimal model shows how the exploratory pattern may be generated by the individual workers' simple trail-laying and -following behavior, illustrating how complex collective structures in insect colonies may be based on self-organization. <s> BIB004 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Moving groups of animals, including fish, ungulates, birds and honeybee swarms seem able to take complex decisions in the absence of signalling mechanisms, and when group members cannot establish who has or has not got information. A numerical simulation shows how such groups can make accurate consensus decisions, and that the larger the group, the smaller the proportion of informed individuals needed to guide the group. A very small proportion of informed individuals is sufficient for near maximal accuracy. This has implications for our understanding of the evolution of information transfer in groups, and also suggests a new design protocol for the guidance of grouping robots. Cover photo, by Phillip Colla Natural History Photography ( ::: http://www.OceanLight.com ::: ), shows schooling jack mackerel. For animals that forage or travel in groups, making movement decisions often depends on social interactions among group members1,2. However, in many cases, few individuals have pertinent information, such as knowledge about the location of a food source3,4, or of a migration route5,6,7,8,9. Using a simple model we show how information can be transferred within groups both without signalling and when group members do not know which individuals, if any, have information. We reveal that the larger the group the smaller the proportion of informed individuals needed to guide the group, and that only a very small proportion of informed individuals is required to achieve great accuracy. We also demonstrate how groups can make consensus decisions, even though informed individuals do not know whether they are in a majority or minority, how the quality of their information compares with that of others, or even whether there are any other informed individuals. Our model provides new insights into the mechanisms of effective leadership and decision-making in biological systems. <s> BIB005 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> In group-living animals, aggregation favours interactions and information exchanges between individuals, and thus allows the emergence of complex collective behaviors. In previous works, a model of a self-enhanced aggregation was deduced from experiments with the cockroach Blattella germanica. In the present work, this model was implemented in micro-robots Alice and successfully reproduced the agregation dynamics observed in a group of cockroaches. We showed that this aggregation process, based on a small set of simple behavioral rules of interaction, can be used by the group of robots to select collectively an aggregation site among two identical or different shelters. Moreover, we showed that the aggregation mechanism allows the robots as a group to “estimate” the size of each shelter during the collective decision-making process, a capacity which is not explicitly coded at the individual level. <s> BIB006 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Nest construction is an impressive achievement for social insects. They employ templates (or pat terns) in the environment to guide construction tasks and robot swarms can use similar mechanisms. Early work examined how a spatio-temporal varying template can be utilized by a swarm of minimalist robots to build the framework for a linear wall. From this, it became clear that a method for regulating construction in a variable environment was needed. To this end, a social insect inspired distributed feedback mechanism is proposed and verified. Direct and indirect transfer of information between individuals, through the use of signals and cues, is shown to facilitate closure of a feedback loop allowing the system to operate close to optimally. Perturbation experiments demonstrate the robotic swarm's ability to adapt to environmental changes. The work described in this paper provides the basis for a distributed robotic system capable of constructing any given planar structure--a goal implicit in many of the suggested applications for collective construction. <s> BIB007 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Group-living animals are often faced with choosing between one or more alternative resource sites. A central question in such collective decision making includes determining which individuals induce the decision and when. This experimental and theoretical study of shelter selection by cockroach groups demonstrates that choices can emerge through nonlinear interaction dynamics between equal individuals without perfect knowledge or leadership. We identify a simple mechanism whereby a decision is taken on the move with limited information and signaling and without comparison of available opportunities. This mechanism leads to optimal mean benefit for group individuals. Our model points to a generic self-organized collective decision-making process independent of animal species. <s> BIB008 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> We present two swarm intelligence control mechanisms used for distributed robot path formation. In the first, the robots form linear chains. We study three variants of robot chains, which vary in the degree of motion allowed to the chain structure. The second mechanism is called vectorfield. In this case, the robots form a pattern that globally indicates the direction towards a goal or home location. <s> BIB009 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> We model the dynamics of self-organized robot aggregation inspired by a study on aggregation of gregarious arthropods. In swarms of German cockroaches, aggregation into clusters emerges solely from local interactions between the individuals, whereas the probabilities to join or leave a cluster are a function of the cluster size. Rather than explicitly modeling the spatial distribution of robots in the environment, we propose a population dynamics model that keeps track of the number of robots in clusters of specific size. The model is able to quantitatively and qualitatively predict the dynamics observed in extensive realistic simulation. In particular, we show both by modeling and simulation that the emergence of a giant component requires a minimal communication distance between individuals, whereas the robots remain scattered in the environment otherwise. <s> BIB010 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> We present a decentralized algorithmic approach to automatically building user-specified three-dimensional structures from modular units. Our bipartite system comprises passive units (blocks), responsible for embodying the structure and determining where further units can legally be attached, and active units (robots), responsible for transporting passive units. The algorithmic issues are correspondingly decomposed into two parts: (1) deciding where passive units may be attached; and (2) getting them to those locations. For the first part, we give simple, scalable rules for attachment and prove that they will reliably lead to the construction of any desired structure from a large class of three-dimensional shapes. For the second part, we compare three approaches: random movement, systematic search and gradient-following; each approach is successively faster but requires more communication overhead and/or unit capabilities. The system we describe enables guaranteed construction of desired structures using very simple agent algorithms, taking a high-level specification as the only required input. The topic of collective construction is related to the problems of programmed self-assembly and self-reconfiguration in modular robots, and the rules governing block attachment presented here may be usefully applied to such systems. <s> BIB011 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Swarm robotics draws inspiration from decentralized self-organizing biological systems in general and from the collective behavior of social insects in particular. In social insect colonies, many tasks are performed by higher order group or team entities, whose task-solving capacities transcend those of the individual participants. In this paper, we investigate the emergence of such higher order entities. We report on an experimental study in which a team of physical robots performs a foraging task. The robots are "identical" in hardware and control. They make little use of memory and take actions purely on the basis of local information. Our study advances the current state of the art in swarm robotics with respect to the number of real-world robots engaging in teamwork (up to 12 robots in the most challenging experiment). To the best of our knowledge, in this paper we present the first self-organized system of robots that displays a dynamical hierarchy of teamwork (with cooperation also occurring among higher order entities). Our study shows that teamwork requires neither individual recognition nor differences between individuals. This result might also contribute to the ongoing debate on the role of these characteristics in the division of labor in social insects. <s> BIB012 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Abstract One important task in cooperative robotics is the self–organization of robotic chain formations in unknown environments. Surveillance and reconnaissance in sewers, ducts, tunnels, caves or narrow passageways, in general, are some of the applications for this type of formation. In Hettiarachchi et al. (2008) we provided simulation results for a novel chain formation algorithm that addresses this task. This paper presents the results of the chain formation algorithm implementation on five robots. <s> BIB013 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Self-amplification processes are at the origin of several collective decision phenomena in insect societies. Understanding these processes requires linking individual behavioral rules of insects to a choice dynamics at the colony level. In a homogeneous environment, the German cockroach Blattella germanica displays self-amplified aggregation behavior. In a heterogeneous environment where several shelters are present, groups of cockroaches collectively select one of them. In this article, we demonstrate that the restriction of the self-amplified aggregation behavior to distinct zones in the environment can explain the emergence of a collective decision at the level of the group. This hypothesis is tested with robotics experiments and dedicated computer simulations. We show that the collective decision is influenced by the available spaces to explore and to aggregate in, by the size of the population involved in the aggregation process and by the probability of encounter zones while the robots explore the environment. We finally discuss these results from both a biological and a robotics point of view. <s> BIB014 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> In this paper, we study the problem of exploration and navigation in an unknown environment from an evolutionary swarm robotics perspective. In other words, we search for an efficient exploration and navigation strategy for a swarm of robots, which exploits cooperation and self-organisation to cope with the limited abilities of the individual robots. The task faced by the robots consists in the exploration of an unknown environment in order to find a path between two distant target areas. The collective strategy is synthesised through evolutionary robotics techniques, and is based on the emergence of a dynamic structure formed by the robots moving back and forth between the two target areas. Due to this structure, each robot is able to maintain the right heading and to efficiently navigate between the two areas. The evolved behaviour proved to be effective in finding the shortest path, adaptable to new environmental conditions, scalable to larger groups and larger environment size, and robust to individual failures. <s> BIB015 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> We present a communication based navigation algorithm for robotic swarms. It lets robots guide each other's navigation by exchanging messages containing navigation information through the wireless network formed among the swarm. We study the use of this algorithm in two different scenarios. In the first scenario, the swarm guides a single robot to a target, while in the second, all robots of the swarm navigate back and forth between two targets. In both cases, the algorithm provides efficient navigation, while being robust to failures of robots in the swarm. Moreover, we show that in the latter case, the system lets the swarm self-organize into a robust dynamic structure. This self-organization further improves navigation efficiency, and is able to find shortest paths in cluttered environments. We test our system both in simulation and on real robots. <s> BIB016 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> When selecting a resource to exploit, an insect colony must take into account at least two constraints: the resource must be abundant enough to sustain the whole group, but not too large to limit exploitation costs, and risks of conflicts with other colonies. Following recent results on cockroaches and ants, we introduce here a behavioral mechanism that satisfies these two constraints. Individuals simply modulate their probability to switch to another resource as a function of the local density of conspecifics locally detected. As a result, the individuals gather at the smallest resource that can host the whole group, hence reducing competition and exploitation costs while fulfilling the overall group's needs. Our analysis reveals that the group becomes better at discriminating between similar resources as it grows in size. Also, the discrimination mechanism is flexible and the group readily switches to a better suited resource as it appears in the environment. The collective decision emerges through the self-organization of individuals, that is, in absence of any centralized control. It also requires a minimal individual cognitive investment, making the proposed mechanism likely to occur in other social species and suitable for the development of distributed decision making tools. <s> BIB017 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Intelligent entities must often make decisions by comparing several candidate alternatives and selecting the best one. This is just as true for autonomous swarms as it is for solitary robots, but to date there has been little work to propose efficient comparison behaviors for autonomous robotic swarms that are not tied to specific environments. In this work, we examine an elegant collective comparison strategy that is used by at least three different species of social insect and adapt it for artificial systems. The behavior is particularly attractive for robotic implementations because it relies only on short range explicit peer-to-peer communication, eliminating the need for chemical trails or other forms of stigmergy. The proposed comparison strategy is proven to converge, and a series of experiments using real robots with noisy sensors is presented that validates our theoretical analysis. Using the proposed behavior, a robotic swarm is able to compare alternatives collectively more accurately than its member robots would be able to individually. <s> BIB018 </s> Swarm robotics: a review from the swarm engineering perspective <s> Source of inspiration <s> Evolutionary robotics can be a powerful tool in studies on the evolutionary origins of self-organising behaviours in biological systems. However, these studies are viable only when the behaviour of the evolved artificial system closely corresponds to the one observed in biology, as described by available models. In this paper, we compare the behaviour evolved in a robotic system with the collegial decision making displayed by cockroaches in selecting a resting shelter. We show that artificial evolution can synthesise a simple self-organising behaviour for a swarm of robots, which presents dynamics that are comparable with the cockroaches behaviour. <s> BIB019
The chain formation behavior takes its inspiration from foraging ants. BIB004 studied and modeled the behavior of Argentine ants which form chains of individuals connecting their nest with foraging areas. Approaches Chains of robots can be obtained in multiple ways: the most used design approaches are probabilistic finite state machines (PFSMs), virtual physics-based design and artificial evolution. Results BIB009 BIB012 ) developed a behavior, based on PFSMs, in which the robots have two different exchangeable roles: explorer and chain member (see Fig. 6(a) ). In the explorer role, the robots are searching for chain members or for the goal area. When they find either a chain member or the goal, they switch to the chain member role and stop. Chain members can become explorer again according to a probability that increases over time if no other robots are perceived. Different configurations and approaches are analyzed and presented. BIB013 used virtual physics-based design to form chains of robots. Virtual forces are used to keep a specific distance between robots and between a robot and the walls of the environment. The developed behavior creates chains that are strongly based on the shape of the environment, which is assumed to be composed of narrow corridors. BIB015 used artificial evolution to obtain a chain formation behavior (see Fig. 6(b) ). In their work, the robots, by using communication through colored LEDs, are able to follow each other forming a double chain between two designated areas. Differently from other chain formation behaviors, in this work the obtained chain is composed of moving robots. BIB016 proposed a collective behavior based on PFSMs and network routing which was able to obtain a chain composed of moving robots. The details of this work are presented in Sect. 3.2.1. The object clustering and assembling behaviors are displayed by many social insects. For example, ants exhibit brood clustering  and termites are able to deposit mud to build complex nests  . Insects usually exploit natural occurring gradients, such as temperature gradients, or pheromones gradients to tackle this tasks. Approaches In swarm robotics, object clustering and assembling are usually approached using probabilistic finite state machines. The robots explore the environment at random and react in different ways to the discovery of available objects or of part of the cluster/assemble to create. In almost all analyzed works, robots group objects sequentially or quasi sequentially. In fact, parallelism could potentially create collisions and interference and thus is avoided. To avoid such problems, a robot usually prevents other robots from depositing objects at the same time, either by using communication or by physically blocking access to the cluster site. Object aggregates are usually obtained using blocks with some kind of self-alignment mechanism based, for instance, on magnets. Results One of the pioneering work in object clustering is the one by BIB001 . In this work, the robots follow a very simple behavior: they explore the environment at random and, when they find an object, they pick it up. A robot with an object moves at random in the environment and deposits the object with a probability proportional to the number of other objects observed. Following these simple rules, the robots are able to create clusters of objects.  presented a work in which robots create clusters of object roughly in the shape of a wall (see Fig. 8(a) ). In this work, disks are scattered around the environment and a specific area is marked for disk clustering. Such area is located half way between a light and a line on the ground. The robots measure the distance between the line on the ground and the light to recognize the clustering area. The robots follow simple reactive rules to cluster the objects roughly in the shape of a wall. In a following work, BIB007 developed a similar mechanism in which the position of the cluster is marked by a moving robot instead of a fixed light. BIB002 developed a behavior to create simple 2D walls made of blocks of alternating color. A robot performs random walk in search for a block. After collecting a block, the robot searches either for the seed block or for the partially constructed wall. When it finds the wall or the seed block, the robot checks if no other robot is already placing a block by using local communication, and then places the blocks. Werfel (2006) developed a method for creating arbitrary 2D structures with blocks placed over a virtual grid. In this work, all robots have knowledge of a matrix which encodes the final structure to create. Such plan is used by the robots also as a frame of reference. The idea is the following: when a robot finds part of the structure, it follows it counting the placed blocks. This block-counting behavior allows the robot to locate itself in the frame of reference of the structure to create. Once the robot knows its position with respect to the placed blocks, it can decide where to place the next block using its knowledge of the final structure. This approach was also extended to create 3D structures BIB011 and tested using real robots ) (see Fig. 8(b) ). Consensus achievement is displayed in many insect species. For example, ants are able to decide between the shortest of two paths using pheromones  . Bees have mechanisms to collectively decide which is the best foraging area or which is the best nest location among several possibilities BIB005 . These mechanisms work even if not all the individuals in the swarm have an opinion on the best choice. Cockroaches also display consensus achievement behaviors when performing aggregation BIB008 . Approaches In swarm robotics, the approaches used for consensus achievement can be divided into two categories according to how communication is used. In the first category, direct communication is used: each robot is able to communicate its preferred choice or some related information. In the second category, instead, indirect communication is used: the decision is performed through some indirect clues, such as the density of the robot population. Results BIB003 proposed a collective behavior in which robots "hunt" two moving targets. The robots decide which target to follow first, follow it and block it. They then do the same for the second target. Two consensus achievement behaviors are proposed: in the first, the robots simply follow the robot closest to a target, resulting in a decision based on the spatial distribution of the swarm; in the second, the robots vote, using a majority rule, to decide which target to follow. BIB006 BIB014 ) studied consensus achievement in cockroaches by using a swarm of robots to replicate the experiment by BIB008 (see Fig. 12(a) ). In their system, consensus achievement is obtained through indirect communication. The focus of this work is both on consensus achievement and aggregation. For this reason this work was presented also in Sect. 3.1.1. A mathematical model of the same behavior was developed by BIB010 . In a similar work, BIB017 presented a collective behavior in which the swarm aggregates on the smallest resource that can host the whole group. A further extension was proposed by BIB019 . The authors used evolutionary robotics to replicate the results obtained by BIB008 comparing the two works also using a macroscopic model.  developed a strategy for consensus achievement through direct communication in a swarm of robots performing foraging. The robots are able to decide between two foraging areas. When two robots get close, they exchange their measured distances between the nest and the latest visited goal. Each robot performs an average of its measured distance with the one received from the other robots. In this way, the robots are able to agree on which area is the closest to the nest and discard the other one even when the measured distances are noisy. BIB018 proposed a consensus achievement behavior based on quorum sensing. The algorithm is inspired by how ants and bees choose the best nest over N alternatives BIB005 . When a robot finds a new alternative, it evaluates its quality and sends recruiting messages to other robots to advertise it. The frequency of these messages is proportional to the perceived quality of the alternative. Thanks to the different message frequencies associated with the different alternatives, over time all robots converge on the best alternative. The behavior is implemented as a probabilistic finite state machine. Montes de  focused on consensus achievement in a system where robots are performing multiple parallel executions of collective transport in groups of three from a nest area to a goal area. The robots need to reach consensus between two possible paths, one longer than the other (see Fig. 12(b) ). Each individual robot has a preferred path. When a group of three robots is formed in the nest, the robots choose the path that is preferred by the majority of them. The chosen path becomes the preferred one for all the robots in the group. Since the robots choosing the short path take less time to complete the execution, they are more often in the nest. This results in more groups formed by robots preferring the short path than those preferring the long path. This asymmetry eventually makes the robots use the shortest path. A mathematical model of this system was presented by . In this work, consensus is achieved both through direct and indirect communication, as the robots use direct communication at group level, and indirect communication at the swarm level.