1 Introduction

The move towards large-scale distributed systems promotes the field of collective decision-making as a fundamental area of research to address novel distributed control mechanisms. Collective decision-making encompasses (i) the decision mechanisms used at the individual level, and (ii) the emergent behavior at the system level. In this paper, we focus on binary decision-making processes, also known as symmetry-breaking [3], in which two choices of the same quality are available and the system needs to select one in a self-organized manner. For systems comprising only one individual, the solution is rather trivial (i.e., random). In contrast, in collective systems a mutual agreement (i.e., a consensus) needs to be achieved [11]. In order to enable such an agreement, the presence of noise is usually substantial. In particular, symmetry-breaking was mostly used to demonstrate the role of noise (i.e., random choices of the individuals) in pushing the system out of an equilibrium state [13]. Hence, it plays a key role in shifting the system towards one of the two options. This shift is then amplified [22] using interactions of a particular kind, referred to as positive feedback loops. While positive feedback is dominating, more individuals become in favor of the selected option and the coherence degree—represented by the fraction of individuals sharing the same opinion—increases until a consensus is achieved and \(100\%\) of individuals agree on the selected option [8, 16]. At this point, negative feedback helps the system to preserve its selected option by damping the noise at the individual level and demotivating the individuals to change their opinion. The specific balance between positive feedback, negative feedback, and noise defines if the system reaches a decided or undecided global state. For example, a high level of noise may exceed the influence of the feedback loops and hence keep the system in an undecided state. Similarly, applying a strong enough positive feedback around a particular option may push the system to decide in favor of that particular option even in cases of low system densities—i.e., low number of feedback loops [17].

In this paper, we show that the interaction model is a key parameter to tune the balance between feedback loops and noise such that the collective system becomes decided even under significant noise levels. The interaction model is exploited by the individuals to exchange their decisions (opinions). Individuals interact locally using proximity models [10, 20]. Local interactions allow collective systems to exhibit scalability, since the decisions at the individual level are made based on the personal preferences and on the influence of neighbors located in the immediate proximity. The latter is independent of the system size when the density is constant, hence, the functionality of the system is preserved at any scale (size). However, the implicit assumption of sufficient local interactions, [24], is only valid under moderate noise level e.g., moderate individual deficiency. Very limited research focuses on the impact of the interaction model on the robustness of collective systems against high level of noise [5].

In this study, we use coherence degree as a quality measure of collective behavior. Coherence degree is defined as the fraction of individuals adopting a common opinion/committing to a common option. In statistical physics, in a phase transition this measure is referred to as the order parameter. We use this measure to compare the efficiency of different interaction models in preserving the coherence of a collective behavior in a robot swarm under high levels of noise. The noise level is increased using one of the following two mechanisms: (i) reducing the impact of feedback loops through massive break-down of interaction links between the individuals by introducing robot breakdowns, and (ii) increasing the tendency to switch opinion randomly at the individual level. We go beyond the proximity (local) interaction model, and investigate scale-free [1], small-world [23], and regular models. As a case study, we use the locust marching behavior, in which individuals need to decide on their motion direction, and they have only two options of going right or left. Consequently, a consensus is achieved when all individuals select the same direction of motion. This corresponds to the highest degree of coherence in the collective behavior (\(100\%\) of the individuals agree).

The paper is organized as follows, in Sect. 2, we specify the decision-making model used by the individuals to select their direction and velocity of motion in a locust marching scenario. The different interaction models, which we investigate in this paper are explained in Sect. 3. In Sect. 4, we present both the robot and environment configurations used in our physics-based simulations. Subsequently, the results obtained from these simulations are demonstrated and discussed in Sect. 5, and the paper is concluded in Sect. 6.

2 Decision-Making Model

Our collective model, as mentioned above, is inspired by one of the prominent natural examples of self-organized behavior: the collective motion (referred to as the marching bands) of desert locust swarms (Schistocerca gregaria). It has been previously shown by Buhl et al. that the collective behavior of marching locusts is similar to the behavior of the particles described by the Czirók model [6]. The latter originates from the Vicsek model and describes self-propelled interacting particles moving in 1D [9, 21]. We adopt the Czirók model to define the individual decision-making processes, except that in our implementation locusts are simulated by a swarm of N homogeneous robots. Similar to Buhl et al., we consider a ring-shaped arena, where robots need to decide to go either left (i.e., the left-goers) or right (i.e., the right-goers), while avoiding collisions with other robots or the arena walls. The initial position and orientation of the robots are sampled from a uniform distribution. Following the discrete Czirók model [4, 26], position \(x_{i}(t)\) and velocity \(u_{i}(t) \in \mathrm{I\!R}\) of robot i are updated at every time step \(\varDelta t = 1\) according to

$$\begin{aligned} x_{i}(t + 1) = \nu u_{i}(t) \end{aligned}$$
(1)
$$\begin{aligned} u_{i}(t+1) = \delta _{s} \left[ G(\left\langle u_{i}(t) \right\rangle ) + \zeta _{i}(t)\right] , \end{aligned}$$
(2)

with \(\nu \) being a speed parameter and \(\zeta _{i}(t) \in \left[ -1.0,1.0\right] \) uniformly distributed noise. The propulsion and friction forces are given by the piece-wise continuous function

$$\begin{aligned} G(\left\langle u_{i}(t) \right\rangle )= {\left\{ \begin{array}{ll} \frac{1}{2}(\left\langle u_{i}(t) \right\rangle + 1), &{} \left\langle u_{i}(t) \right\rangle > 0 \\ \frac{1}{2}(\left\langle u_{i}(t) \right\rangle - 1), &{} \left\langle u_{i}(t) \right\rangle < 0\\ 0, &{} \text {otherwise,} \end{array}\right. } \end{aligned}$$
(3)

where \(\left\langle u_{i}(t) \right\rangle \) is the average over the set of velocities of i’s neighbors. Finally, in Eq. (2) we extended the discrete Czirok model by the factor \(\delta _{s}\), which is \(-1\) with probability \(p_{s}\), and 1 otherwise. Note that the originial Czirok model does not include \(\delta _{s}\), which we added to introduce the probability \(p_{s}\) to spontaneously switch the heading direction, i.e. the sign of \(u_{i}(t)\). This is the main extension of the Czirok model that allows to account for an additional noise on the individual decision-making process [12], while \(\zeta _{i}(t)\) represents the sensor noise, i.e. the uncertainty in the perception of the neighborhood opinion. From the sign of \(u_{i}(t)\) we can deduce the state of robot i: if \(u_{i}(t) > 0\) (\(u_{i}(t) < 0\)) then we denote i as a left-goer robot (right-goer robot), respectively. Therefore, the collective state or collective behavior of the system is given by:

$$\begin{aligned} \phi (t) = \frac{1}{N} \sum _{i}^N \frac{u_{i}(t)}{\vert u_{i}(t) \vert } \end{aligned}$$
(4)

The absolute value of this measure represents the degree of coherence in the collective behavior (system’s decision). When this degree is \(\vert \phi (t) \vert =1\), i.e., \(100\%\) of the individuals agree on one opinion, the system reaches consensus. Fluctuations that occur due to different sources of noise—i.e. sensor noise \(\zeta \) and spontaneous opinion switching \(p_{s}\)—affect directly the degree of coherence achieved at the system level.

3 Interaction Models

Four different types of interaction (network) models are considered in this paper: (i) proximity network (PN), (ii) regular network (RN), (iii) small-world (SW), and (iv) scale-free (SF). These models differ fundamentally in how individuals connect.

First, PN models describe topologies in which each robot interacts with those robots that are within its proximity communication radius. Therefore, the choice of the communication radius has a significant influence on the communication degree of the robot. Two extreme values of the communication radius are \(r_{c} = 0\) and \(r_{c} > d_{A}\), where \(d_{A}\) denotes the diameter of the arena. In former case, there are no interactions, i.e. the degree of every robot is zero and the collective behavior is the average over the opinions that are purely governed by noise. When \(r_{c} > d_{A}\), every robot interacts with every other robot in the arena which results in a complete network. For a swarm with an even number of individuals (majority is always available in the individual’s neighborhood) this will always lead to consensus. However, complete networks have no locality because every robot knows the state of the entire system at every time step. In contrast, we obtain PN models with local interactions over a limited communication radius \(r_{c}\) and an approximated average of communication degree \(\left\langle k \right\rangle \).

Second, RN models are topologies in which all robots have equal degree and in which neighbors are selected at random, irrespective of their physical distance. Consequently, robots might be connected to robots at larger physical distances.

Third, SW models originate by randomly rewiring RN networks such that the network distance (hop count) between two randomly chosen nodes grows proportionally to the logarithm of the total number of nodes [15, 23]. Following the Watts-Strogatz model [23], we generate SW models by starting from a RN model and replace random links with new links—between any two nodes irrespective of their physical distance—that are sampled from a uniform distribution with probability \(p_{sw}\). Differently from RN models, the latter process introduces a number of hubs, i.e. nodes with above-average degree.

Fourth, SF models are a special type of SW models, observed in a large number of natural and biological systems [15, 25]. They are characterized with a power-law distributed degree and a very short average distance, making these networks ultra-small [7]. On the one hand, this implies the presence of a few extraordinary hubs with degrees that are far higher than the network average. On the other hand, most nodes have a relatively low degree such that the removal of a random node is not likely to affect the system connectivity. Therefore, SF networks are known to be robust against random node failure. Following the Barabasi-Albert model [2], we generate scale-free networks by starting from a small complete network of 10 nodes (robots). Subsequently, each of the remaining \(N-10\) nodes (N denotes the size of the swarm) is iteratively added with a fixed degree. Each of the newly added nodes is connected to a node i with a probability proportional to i’s degree \(k_{i}\), a process also known as preferential-attachment [2]. The latter step increases \(k_{i}\) and at the end of the network growth process the resulting average network degree amounts to \(\left\langle k \right\rangle \) being the same as in the other interaction models.

4 Simulations

In this section we describe the physics-based simulations that we conducted using ARGoS [19] to analyze the global collective behavior of a homogeneous swarm of \(N=500\) simulated FootbotsFootnote 1. ARGoS allows us to perform our simulations with taking the robot’s physics into consideration, and hence facilitates the generation of more realistic results. In the following, we present the configurations adapted at both individual and environment levels.

4.1 Robot Configuration

In our simulations, robots move randomly with a linear speed of \(\nu =5\,m/ts\), and try to avoid collisions by halting either the left or the right wheel, depending on its orientation relative to the position of the nearby robot or wall. However, in cases when collision avoidance requires to turn more than 90\(^{\circ }\), the robot is programmed to maintain the sign of \(u_{i}(t)\). Therefore, collision avoidances do not constitute an additional source of spontaneous direction switching. Nevertheless, the density of robots used in our experiments—i.e., the number of robots over the area of the arena allows to account for a minimized level of spacial interferences [14]. Additionally, the rate of collision avoidances is greatly reduced when the swarm is in consensus because then robots move in the same direction and the possibility of a potential collision becomes negligible. While moving, each robot communicates and exchanges opinions with its neighbors. The opinion of robot i is given by the value of \(u_{i}(t)\) (Eq. (2)), for which the sensor noise is set as \(\zeta \in \left[ -1, 1 \right] \), and the spontaneous switching probability \(p_s\). The two types of implemented communications are proximity (short-range) communications and targeted long-range communications. To enable long-range communications over the whole arena area, we assume that the inner walls of the ring-shaped arena are lower than the level of the range-and-bearing sensors and actuators but high enough to be perceived by the robot as physical obstacles. This allows to include all communication models described in the previous section.

4.2 Environment Configuration

An important system property is the density of the swarm inside the arena [6, 9]. Therefore, apart from the size of the swarm, the shape and the area of the environment have a significant influence on the system dynamics. In our experiments, swarm robots are confined within a ring-shaped arena with a diameter of 4 m (24 m) for the inner (outer) walls, respectively. The form of the arena encourages the robots to move either clockwise or counter-clockwise, i.e. right or left. Because the arena has a finite radial width, we program the robots to avoid unnecessary radial movement by always maintaining an angle of \((90 \pm 5)^{\circ }\) to a light beacon located in the center of the arena (i.e. unless collision avoidance is required).

To simulate the event of a break-down, we deactivate the majority of robots at \(t=t_{d}\) randomly. When a robot i is deactivated, it stops moving, i.e. \(u_{i}(t_{d})=0\), and all its communication links are broken. The latter implies that the break-down leads to a substantial decrease of interactions, often followed by a loss of consensus or a significant drop in the degree of coherence. However, as we will demonstrate in the next section, certain interaction models allow the swarm to recover the degree of coherence to a higher level even if more than two thirds of the swarm individuals are deactivated. Table 1 summarizes the parameters settings over the different interaction models implemented in this paper. Note that the interaction models are all generated such that the average robot degree is the same over all models for a fair comparison. This is set to \(\left\langle k \right\rangle \approx 6\). Finally, the rewiring probability \(p_{sw}\) for the generation of the SW models is set to \(p_{sw}=0.5\) to guarantee the occurrence of nodes with above-average degree. In this regard, SW models represent a transition model between RN and SF models.

Table 1. Overview of implemented interaction models and the parameters used to generate them.
Full size table

Figure 1 depicts a top view of the ring-shaped arena, over which the locust swarm is performing collective marching. The screen-shots are taken after a severe loss of robots (i.e., break-down of \(65\%\) of the interaction links) for the three interaction models PN, SW, and SF.

Fig. 1.
figure 1

Top view on the locust swarm. Green (red) robots are left-goers (right-goers), respectively, and black robots are deactivated. (a) PN, (b) SW, and (c) SF, all after break-down. For a clearer picture of the dynamics, see the recordings [18]. (Color figure online)

Full size image

5 Results and Discussion

We launch different sets of physics-based simulations to analyze the influence of the interaction model on the degree of coherence achieved in a locust swarm that is exposed to a high level of noise. We first simulate a strong sudden occurrence of noise through a major break-down in the interaction links. The intensity of the break-down—represented by the number of deactivated robots—has the main influence on the achieved degree of coherence. Secondly, we use a new set of experiments to simulate the high level of noise through increasing the probability of the individual spontaneous switch, together with the incidence of robot break-down events.

We start with a robot locust swarm that suffers a major break-down after reaching a high degree of coherence (i.e. over \(75\%\) of the robots agree on the same direction). The individuals in this set of experiments are characterized with relatively low level of individual noise (i.e., spontaneous switch probability \(p_{s}=0.02\)). The individual noise is set low in order to focus on the robustness of the different interaction models against random break-down. The coherence degree is measured using the absolute value \(\vert \phi (t) \vert \)—i.e., the fraction of robots agreeing on the same opinion. We analyze the corresponding time average \(\bar{\vert \phi \vert }\) as a function of the percentage of deactivated robots to reveal the efficiency of each interaction model in preserving a high coherence degree.

In each experiment, and for all interaction models, we first let the swarm achieve a high coherence degree (over \(75\%\) of the robots). Subsequently, we deactivate a certain percentage of the robots. As mentioned above, for a fair comparison of the different interaction models, all simulations are configured such that the average robot degree before the break-down is the same, here set to \(\left\langle k \right\rangle \approx 6\). We analyze the time evolution of the coherence degree \(\vert \phi (t) \vert \) to study the efficiency of the applied interaction model in preserving a high \(\vert \phi (t) \vert \). The left part of Fig. 2 demonstrates the results, in which every data point represents the coherence degree \(\vert \phi (t) \vert \) averaged over the post break-down time—i.e., between the break-down event and the end of simulation at \(T=5000ts\). The time evolution of \(\vert \phi (t) \vert \) is illustrated in the inset, for the PN model and the deactivation of \(65\%\) of robots. The resulting value of \(\bar{\vert \phi \vert }\) shown in the inset corresponds to one data point in the major plot, other data points were obtained accordingly. As shown, \(\vert \phi (t) \vert \) drops for all interaction models with increasing percentages of deactivated robots. Nevertheless, there are significant differences among the interaction models. We can notice that all models except of the PN model were able to preserve a high coherence degree (\(\bar{\vert \phi \vert } >0.75\)) up to \(50\%\) of deactivationFootnote 2. Furthermore, the SF interaction model shows a pronounced tendency of achieving higher \(\bar{\vert \phi \vert }\) than the other models starting from \(65\%\) of deactivation. At this point, the performance of the SW and RN models demonstrate a clear drop. However, under the RN model \(\bar{\vert \phi \vert }\) drops faster than it does under the SW, as can be seen between the deactivation of \(65\%\) and \(75\%\). This can be explained by the fact that, for the same average degree, the SW model has a higher clustering coefficient than the RN model: it has a number of robots with higher connectivity degree. Beyond \(75\%\) deactivation, SW and RN models start to behave similarly and in agreement with the PN model. SF preserves its superior performance up to \(85\%\) of deactivation, due to the high robustness of its hubs.

We continue our experiments with the same low level of individual noise (\(p_{s}=0.02\)) and we fix the deactivating percentage to \(65\%\), at which the coherence degree drops for all models below \(\bar{\vert \phi \vert } < 0.5\). For this setting, we investigate the efficiency of each interaction model in recovering the coherence degree to a higher level. We analyze this efficiency for different robot average communication degree. For this purpose, we define \(\bar{\vert \phi \vert }\) as a function of the robot’s average communication degree \(\left\langle k \right\rangle \), aiming to determine the minimum rewiring threshold needed for the influence of the feedback loops to overcome the noise influence and hence increasing the degree of coherence in the collective behavior. In this set of simulations, the system starts with the PN model, followed by a break-down of \(65\%\) of interaction links at \(t_{d} = 10000 ts\). Next, we use targeted rewiring at \(t = 12500 ts\), to generate the different interaction models with the same average robot degree. The right side of Fig. 2 demonstrates the results of these experiments. The inset shows an example for the time evolution of \(\phi (t)\) for the PN model before the break-down event (the black dashed line), and PN (blue) or SF (orange) interactions for \(t > 12500 ts\). The latter period of time is used to compute \(\bar{\vert \phi \vert }\) which corresponds to one point in the major plot. This plot shows that SF, SW, and RN models are able to restore a high coherence degree \(\bar{\vert \phi \vert } > 80\%\) with an average robot degree of \(\left\langle k \right\rangle =4\), while the PN model requires \(\left\langle k \right\rangle \approx 7.5\) to restore a similar degree of coherence.

Fig. 2.
figure 2

Comparison of the average collective state \(\bar{\vert \phi \vert }\) as a function of the percentage of deactivated robots (left) and the average communication degree (right). Left inset: time evolution of \(\vert \phi (t) \vert \) after the break-down. Right inset: Time evolution of \(\phi (t)\) starting with PN model, break-down, targeted rewiring of interactions to a SF model (orange) or no rewiring (blue, continued). Data points were averaged over 30 runs. (Color figure online)

Full size image

As mentioned above, after examining the robustness of the interaction models against mere break-down events, we continue investigating their robustness against increasing the level of individual noise (i.e., the spontaneous switch \(p_{s}\)). For this purpose, we run a new set of experiments, in which we increase the level of individual noise, first, to \(p_{s}=0.05\). Results are illustrated on the left side of Fig. 3. In this figure, we can notice that despite low coherence degree \(\bar{\vert \phi \vert }<0.5\), the SF model outperforms other models significantly starting from the deactivation percentage of \(55\%\). Below this (critical) percentage of deactivations, all SF, SW and RN models were able to generate similar degree of coherence, which is significantly better compared to the PN model. A behavior similar to the one shown in Fig. 2 is observed, that is the SW model generating higher \(\bar{\vert \phi \vert }\) than the RN model for specific deactivation percentages before converging to a similar behavior that approaches the PN model. To better investigate the specific role of the individual noise, we start with a swarm of 175—i.e., \(35\%\) (\(65\%\) deactivation) of the total N = 500—and with an average robot degree of 4—i.e., the average degree at which all models (except for the PN model) are able to achieve \(\bar{\vert \phi \vert } > 80\%\) with a swarm of 175 in the previous experiments, see the right side of Fig. 2—and we analyze \(\bar{\vert \phi \vert }\) for different values of \(p_s\). Results are illustrated on the right side of Fig. 3. In this figure, we can notice the significantly higher robustness of all interaction models in comparison to the PN model in terms of the obtained \(\bar{\vert \phi \vert }\). The behavior of SF, SW, and RN models seems similar up to a certain noise level (here \(p_{s}=0.08\)), up which the SF model starts to clearly outperform other models (i.e., demonstrating higher coherence degree). This can be also deduced from the inset on the right side of Fig. 3, which corresponds to one data point and shows the phase transition of the coherent behavior generated by the SF model. Moreover, both SW and RN models demonstrate a behavior that is initially similar to the SF model and later approaches the PN model.

Fig. 3.
figure 3

Comparison of the average collective state \(\bar{\vert \phi \vert }\) as a function of the percentage of deactivated robots (left) and the spontaneous switching probability \(p_{s}\) (right). Left inset: time evolution of \(\vert \phi (t) \vert \) after the break-down. Right inset: Time evolution of \(\phi (t)\) at \(p_{s}=0.08\), after the break-down, with alternative targeted rewiring of interactions to a SF topology (orange) or no rewiring (blue, continued) and an average degree of \(\left\langle k \right\rangle \approx 4\). Data points were averaged over 30 runs. (Color figure online)

Full size image

In general, the data points at which the behavior of SW and RN models aligns with the behavior of the PN model (see Figs. 2 and 3) indicate that it is not merely the presence of long-range interactions that contributes to the increased degree of coherence. Nor is it the value of the network distance, as RN and SW models behave similarly in our experiments. Instead, our conjecture is that it is the fraction of well-connected individuals that significantly influences coherence and robustness of the collective system affected by severe noise levels. On the one hand, these well-connected individuals have access to a sufficiently large sample of the swarm to reliably estimate its collective state. On the other hand, they can reach and influence the opinion of a significant number of individuals. Both features allow the system to preserve sufficient feedback loops that counteract the effects of noise.

Finally, the ratio of positive feedback to noise also defines the level of adaptivity of a collective system. When this ratio is critical, phase transitions occur [6, 21] and the swarm is able to explore different options (in our case two options), making the swarm more adaptive to environmental changes. These phase transitions were observed in our systems as well, an example is shown in the right inset of Fig. 2 before the break-down (i.e., for \(t < 10000\) ts). However, in the same inset one can see that after rewiring the interactions to a SF model (orange data points at \(t > 12500\) ts), the presence of positive feedback outweighs the effects of noise. Thus, the increased coherence degree stabilized and the adaptivity decreased significantly such that no phase transitions occur until the end of the experiment. However, adaptivity can be restored by increasing the level of noise, as we can see by considering the right inset of Fig. 3 for comparison, demonstrating that the balance between positive feedback and noise is crucial to the collective system performance.

6 Conclusion

In this paper, we have investigated the impact of the interaction model used in collective system on the coherence degree of its decisions under high levels of noise. Beyond local interactions, we have investigated the coherence degree of a collective behavior under: SF, SW, and RN interaction models. The interaction models were analyzed using the case study of locust marching, which represents a symmetry-breaking decision-making problem. Our results have revealed a clear evidence of the significant role the interaction model plays in defining the coherence degree under different noise sources. SF has shown an outstanding performance over other models when the level of noise in the system exceeds a particular threshold. The influence of noise was increased either though introducing a break-down of a particular percentage of the interaction links or through increasing the probability to spontaneously switch of the opinion at the individual level (i.e., the individual noise). SW and RN models act similar to SF up to a specific level of noise, after which both demonstrate a drop in performance, however, a smaller drop of the SW model. Starting from a particular noise level, SW and RN show similar behavior that approaches the behavior of the PN model. Our findings can help as a preliminary step on the way to engineering artificial swarms with a robust coherence degree against high levels of noise from different sources.

In future work, we plan to compare the different interaction models in terms of the mean time required to achieve high coherence levels or even consensus. Furthermore, we plan to investigate the exact relation between the drop in the coherence degree and the connectivity measures of the collective system, such as the clustering coefficient and the fraction of hubs. Finally, it is worthwhile to examine the combination of PN and SF models that could additionally improve coherence degree of collective behavior as well as collective response to localized external stimuli.