Coherent collective behaviour emerging from decentralised balancing of social feedback and noise

Abstract

Decentralised systems composed of a large number of locally interacting agents often rely on coherent behaviour to execute coordinated tasks. Agents cooperate to reach a coherent collective behaviour by aligning their individual behaviour to the one of their neighbours. However, system noise, determined by factors such as individual exploration or errors, hampers and reduces collective coherence. The possibility to overcome noise and reach collective coherence is determined by the strength of social feedback, i.e. the number of communication links. On the one hand, scarce social feedback may lead to a noise-driven system and consequently incoherent behaviour within the group. On the other hand, excessively strong social feedback may require unnecessary computing by individual agents and/or may nullify the possible benefits of noise. In this study, we investigate the delicate balance between social feedback and noise, and its relationship with collective coherence. We perform our analysis through a locust-inspired case study of coherently marching agents, modelling the binary collective decision-making problem of symmetry breaking. For this case study, we analytically approximate the minimal number of communication links necessary to attain maximum collective coherence. To validate our findings, we simulate a 500-robot swarm and obtain good agreement between theoretical results and physics-based simulations. We illustrate through simulation experiments how the robot swarm, using a decentralised algorithm, can adaptively reach coherence for various noise levels by regulating the number of communication links. Moreover, we show that when the system is disrupted by increasing and decreasing the robot density, the robot swarm adaptively responds to these changes in real time. This decentralised adaptive behaviour indicates that the derived relationship between social feedback, noise and coherence is robust and swarm size independent.

1 Introduction

Several collective systems, in both natural and artificial swarms, rely on the mechanism of self-organisation to perform collective tasks. Self-organisation is driven by two main components: (i) random fluctuations caused by noise and individual factors and (ii) the presence of feedback in form of external information received from peers (social feedback) or the environment (environmental feedback) (Bonabeau et al. 1999; Camazine et al. 2003; Khaluf and Hamann 2016; Pinero and Sole 2019). Typically individuals receive these feedbacks from their local neighbourhood due to limited sensing and communication capabilities.

In tasks that aim to achieve an agreement within the group, often referred to as collective decision-making problems, the individual integrates the received social feedback to modify its own behaviour and align it with its peers’ behaviour (Castellano et al. 2009; Baronchelli 2018; Bose et al. 2017; Rausch et al. 2019). Therefore, in agreement tasks, social feedback is substantial to attain a stable coherent behaviour within the swarm. Conversely, random fluctuations may lead individuals to a behaviour contrary to the behaviour of the majority of the group that would reduce the swarm coherence.

The source of random fluctuations can be various, normally ascribed to noise in integrating/collecting feedback or to voluntary independent explorative behaviour of the individuals (Tsimring 2014). On the one hand, this spontaneous exploration may drive the system away from the consensus. On the other hand, it allows regular exploration of different behaviours which may enable the group to better adapt to changing conditions or dynamic swarm densities (Mayya et al. 2019; Wahby et al. 2019).

Ecological advantages of spontaneous exploration have been documented in many natural systems. For example, in ant colonies foragers may undertake individual explorations even if stable pheromone trails to food sources have already been established (Dussutour et al. 2009). However, to maximise benefits from coherence and adaptivity, the swarm needs to find and maintain a balance between peer agreement and exploration of new solutions, which is not a trivial task. This balance may be interpreted as an optimisation of the exploitation versus. exploration trade-off. On the one hand, the individuals exploit an option by aligning their behaviour with their peers and therefore maintaining coherence. On the other hand, the individuals explore other options through random misalignment. In the current study, we focus on the maximisation of exploitation in terms of group coherence, given a constant level of exploration. In particular, at the individual level, this trade-off optimisation translates in properly integrating the social feedback with noise. By noise we refer to any source of randomness or fluctuations, including sensor noise in robotic systems or, on a more abstract level, spontaneous exploration of new behaviours by individuals, as commonly used in the literature (Dussutour et al. 2009; Tsimring 2014; Hamann et al. 2014; Hamann 2018).

While in nature we can observe several self-organised systems that have evolved to maintain a balance between feedback and noise (Bonabeau et al. 1999; Camazine et al. 2003; Tsimring 2014), the problem of embedding this type of self-organised adaptivity in a decentralised artificial swarm is an open challenge. This challenge resides in identifying the individual rules that an agent must follow to allow the swarm to obtain the desired balancing in a fully distributed way. In the literature, this problem is often referred to as the micro–macro link as it aims to find a link between the macroscopic dynamics and the microscopic behaviour (Hamann and Wörn 2008; Lerman et al. 2004; Berman et al. 2009; Reina et al. 2015a, b). In collective decision-making systems, the interplay between social feedback and noise (e.g. individual exploration) has a crucial role in determining the collective coherence of the group (Khaluf et al. 2017b, 2018; Rausch et al. 2019). While a general solution to design any adaptive decision-making system is not yet in reach, our goal is to advance the understanding of the interplay between noise and social feedback in collective systems by taking a bottom-up approach and by using particular case studies as a starting point for the investigation of underlying fundamental properties.

Specifically, in the current work we focus on the prominent symmetry-breaking case study of locust marching. This case study represents a binary decision problem scenario where agents need to collectively decide to move in clockwise or counterclockwise direction in a ring-shaped arena that models a pseudo-one-dimensional environment (Vicsek et al. 1995; Buhl et al. 2006; Huepe et al. 2011; Ariel and Ayali 2015). This canonical scenario offers a suitable setting for our purposes because it focuses on the collective system’s ability to make a decision between two options of equal value. Thus, the decision-making process is not influenced by any environmental bias but only governed by the interplay of social feedback and noise. In this paper, noise is represented by spontaneous switching of an individual’s opinion independent of interactions with its neighbours. The agents cannot modify the noise level; however, we assume that they can estimate it and adapt their social feedback to counterbalance it. Through this approach, we do not intend to engineer an efficient noise-cancelling behaviour. On the contrary, we acknowledge the presence of noise as either unavoidable or favourable (e.g. to increase group adaptivity). Our goal is to study the link between noise and social feedback and how this relationship affects group coherence. To put this relationship into focus, we assume the agent not to be able to cancel noise but only to adapt its social feedback. The advantages of modulating the social feedback have been previously investigated in systems of collective motion (Torney et al. 2009; Shklarsh et al. 2011; Khaluf et al. 2018), foraging (Pagliara et al. 2018; Pitonakova et al. 2018; Talamali et al. 2019a; Rausch et al. 2019) and collective decision-making (Talamali et al. 2019b).

Other works focused indirectly on the importance of finding a proper balance between the social feedback and the noise in the system in order to move from undecided system to a decided one. For example, Khaluf et al. (2017b) studied the impact of the population density on the ability of the system to reach coherence. The density in this case is an indirect measure of the social feedback required to counterbalance the noise. Similarly, Buhl et al. (2006) investigated the impact of density in the locust-marching scenario; at low densities, locusts loose consensus on their motion direction because individuals do not receive enough social feedback. Valentini and Hamann (2015) modelled social feedback in terms of the number of communication links and studied how it influences the decision-making dynamics. Another parameter that was studied to investigate the influence of social feedback on collective decision-making was the networking model. For instance, in Huepe et al. (2011) and Chen et al. (2016) the authors considered dynamically changing building blocks of adaptive networks and analytically derived their influence on the swarm decision. Furthermore, network theoretic concepts were applied to analyse the impact of the number of interactions on flocking dynamics and collective response to an oscillating signal (Shang and Bouffanais 2014; Mateo et al. 2017, 2019). Similarly, Khaluf et al. (2017a, 2018) highlighted the role of different interaction models in enabling the system to restore a specific level of social feedback necessary for convergence to a collective decision.

Likewise, our locust-marching case study includes fluctuations in individual decision-making. However, differently from the previous works, we focus on the emergence and maintenance of maximum group coherence. In particular, we analytically derive an upper bound of the latter as well as the minimum social feedback needed to reach this upper bound. Thus, our results contribute to the domain of swarm robotics by presenting a fundamental link between communication, individual noise and global coherence. This link extends the understanding of coherent collective behaviour in the presence of fluctuations in individual decision-making. This understanding is particularly useful in low-density systems where robustness, scalability and flexibility are not guaranteed. We show that in such systems the maximum coherence can be recovered in a fully decentralised manner by individuals that are able to maintain their number of communication links.

We first introduce our locust-marching case study in Sect. 2 which includes a fixed level of noise in the individual decision-making process. We then find a reliable estimate of the maximum coherence degree as a function of this noise term in Sect. 3.1. From this result, we derive a mean-field model of the minimal number of communication links required for the social feedback to balance the noise level such that the maximum coherence degree emerges globally (Sect. 3.2). To validate our mean-field approximation, we compare the theoretical model with physics-based simulations of a robot swarm in collective locust-marching scenario (see implementation in Sect. 4). In Sect. 5, we first show the ability of the simulated robot swarm to adapt the social feedback to reach the maximum achievable coherence for various noise levels. Then, we demonstrate how a swarm could potentially use the feedback–noise balance to cope with time-varying swarm densities. We study this aspect by greatly varying the number of robots in the system and letting the individual robots adjust the amount of social feedback at runtime and in a fully decentralised manner. Investigating the dynamics caused by runtime variation of the swarm size is inspired by the studies of Czirók et al. (1999) and Buhl et al. (2006). In particular, they observed that the consensus reached by a dense locust population is lost when the density of this population drops. In our system, the robots react to this density drop by adjusting their communication range to reach the desired level of social feedback. As discussed in Sect. 6, the presented swarm robotics system does not allow direct implementation on a practical application but aims at validating through physics-based simulations that our analytically derived feedback-to-noise balance allows a generally robust, decentralised and swarm size-independent recovery of the maximum coherence.

2 Locust-inspired decision-making model

In this work, we propose a decentralised decision-making strategy that allows individual agents in a swarm to self-regulate their intake of information in order to autonomously balance the level of social feedback against noise. We design such a strategy for the binary decision problem in which a robot swarm must agree on the motion direction. The reference decision model of this study is the prominent natural system of the desert locust-marching bands (Buhl et al. 2006). By local interactions between the insects, the locust swarm converges to a consensus on the direction of motion. Previous work has shown that confining the locust swarm in a ring-shaped arena reduces the decision problem to a binary decision problem in which the two options are clockwise and counterclockwise marching directions (Buhl et al. 2006). Interpreting the ring as a one-dimensional space, we refer to the two marching directions for simplicity as left and right and analyse the collective decision in terms of the proportion of left-goers versus right-goers. Analyses by Buhl et al. (2006) have shown that the marching behaviour in this system can be modelled using the Czirók model (Czirók et al. 1999). This model has been later extended to the discrete Czirók model (Yates et al. 2009; Ariel and Ayali 2015), according to which after each time step $\varDelta t = 1$, both the position $x_{i}(t) \in \mathbb {R}$ and velocity $u_{i}(t) \in \mathbb {R}$ of the individual i are updated as follows¹:

$$\begin{aligned} x_{i}(t + 1)= & {} x_{i}(t) + \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)

where $\nu$ is a speed parameter and $\zeta _{i}(t) \in \left[ -1.0,1.0\right]$ is a uniformly distributed real random number (i.e. source of noise). Moreover, the propulsion and friction forces are given by the piecewise continuous function

$$\begin{aligned} G(\left\langle u_{i}(t) \right\rangle )= \frac{1}{2}\left[ \left\langle u_{i}(t) \right\rangle + \hbox {sgn}(\left\langle u_{i}(t) \right\rangle )\right] , \end{aligned}$$

(3)

where $\left\langle u_{i}(t) \right\rangle$ is the average over the set of velocities of i’s neighbours and $\hbox {sgn}\left( z\right)$ is a sign-function equal to +1 if $z>0$, $-\,1$ if $z<0$ and 0 if $z=0$. In the following, we refer to i’s neighbours (or i’s neighbourhood) as the agents with whom i established a communication connection at a given time t. Note that in Eq. (2), we modified the classical Czirók model by introducing the term $\delta _{s}$ which is $-1$ with probability $p_{s}$ and 1 otherwise, re-sampled at every time step for each agent individually. Adding $\delta _{s}$ allows us to include in the model the probability $p_{s}$ that an individual spontaneously switches its heading direction (i.e. the sign of $u_{i}(t)$),² inspired by previous studies on symmetry breaking (Huepe et al. 2011; Chen et al. 2016; Khaluf et al. 2018). This spontaneous switching directly contributes to spontaneous exploration by each agent. Hence, in a technical sense, $\zeta _{i}(t)$ can be interpreted as the individuals’ sensor noise and $\delta _{s}$ as the actuation noise (Huepe et al. 2011). However, on a more abstract level, $\zeta _{i}(t)$ represents fluctuations in communication while $\delta _{s}$ can be seen as an analogue to the spontaneous individual exploration. Therefore, combining $\zeta _{i}(t)$ and $\delta _{s}$ into one single term would be impractical and may obscure the role of individual exploration.

The sign of $u_{i}(t)$ indicates the marching direction and can be used to categorise each individual as a left-goer (for $u_{i}(t) < 0$) or right-goer (for $u_{i}(t) > 0$), respectively, and it represents the agent i’s opinion. Aggregating the opinions of the N agents composing the system, we can therefore compute the collective state of the system as:

$$\begin{aligned} \phi (t) = \frac{1}{N} \sum _{i}^N \hbox {sgn}\left( u_{i}(t)\right) . \end{aligned}$$

(4)

Note that Eq. (4) is different from Ariel and Ayali (2015) because, as in Khaluf et al. (2018), we are interested in measuring the coherence in the marching direction, i.e. either left or right. Therefore, we reduce the velocity $u_{i}(t)$ to the binary value $\hbox {sgn}\left( u_{i}(t)\right)$. We define the collective coherence degree$\vert \phi (t) \vert$ as the absolute value of the measure given in Eq. (4). A degree $\vert \phi (t) \vert =1$ indicates that $100\%$ of the individuals agreed on one direction and the system reached consensus.

3 Social feedback and noise

In our study, the social feedback perceived by agent i is the collection of velocities communicated by i’s neighbours, which i uses to calculate $\langle u_{i} \rangle$. Thus, social feedback scales with the number of neighbours, $n_{i}$, that i is communicating with. Additionally, from Eqs. (2) to (3), we can see that the agent dynamics are dictated by the combination of the social feedback from the neighbours and random noise from sensors ($\zeta _{i}$) and actuation ($\delta _{s}$). Each agent needs to rely on the neighbours’ feedback in order to achieve a global agreement. However, the feedback might be noisy either due to a sensing error of the agent acquiring the feedback (as modelled by $\zeta _{i}$), or due to an agent that spontaneously switched its opinion (with probability $p_{s}$).

Nevertheless, an agent i could mitigate the effect of such noise through averaging the feedback from a large enough number of neighbours $n_i$. In the trivial case, each agent would interact with all agents ($n_i=N-1$) in order to agree on a common direction. However, a complete interaction graph may be impossible to implement in either biological or artificial systems due to communication and/or computational limitations. In fact, communicating and processing large amount of information can be expensive and in certain systems even impossible. Therefore, the agent needs to rely on the feedback of a limited number of neighbours ($n_i \ll N-1$). In this case, the global agreement results from the sum of local coordination efforts. Conversely, relying on a too small neighbourhood makes the agent vulnerable to random fluctuations of its neighbours’ output, leading to a low degree of coherence (e.g. Czirók et al. 1999; Buhl et al. 2006). Thus, the agent faces a trade-off, and it needs to adjust the size of its neighbourhood to minimise communication cost while maintaining high coherence with the rest of the swarm. However, as we show in Sect. 3.2, coherence can be maximised even for $n_i \ll N-1$ for a wide range of $p_{s}$ values. To compute the lowest $n_{i}$ for which the highest possible coherence can emerge on the global scale, we follow a two-step approach.

First, in Sect. 3.1, we derive the maximum coherence degree that can be attained for a given noise level $p_{s}$. Second, in Sect. 3.2, we derive a steady-state approximation of the minimal neighbourhood size that an agent must maintain to reach this maximum coherence degree.

3.1 Maximum coherence degree $\vert \phi _{\mathrm{m}} \vert$

Consider a system in which the agent density is high enough for a stable coherent motion to emerge. Then, assuming that every agent’s velocity satisfies $\vert u_{i}(t)\vert \ne 0$ at every t, we can use $\hbox {sgn}(u_{i}) = \frac{u_{i}}{\vert u_{i} \vert }$ and reformulate Eq. (4) to

$$\begin{aligned} \begin{aligned} \phi (t)&= \frac{1}{N}\sum _{i}^N \frac{u_{i}(t)}{\vert u_{i}(t)\vert }\\&= \frac{1}{2N}\sum _{i}^{N}\frac{\delta _{s}}{\vert u_{i}(t)\vert }(\langle u_{i}(t) \rangle + \hbox {sgn}(\langle u_{i}(t) \rangle )) + \frac{1}{N}\sum _{i}^{N} \frac{\delta _{s}}{\vert u_{i}(t)\vert } \zeta _{i}. \end{aligned} \end{aligned}$$

(5)

Recall that $\langle u_{i}(t) \rangle$ is the average velocity of agent i’s neighbours. The second term on the right-hand side of Eq. (5) corresponds only to spontaneous switching and the sensor noise. Note that this term approaches zero for large N, such that

$$\begin{aligned} \lim _{N \rightarrow \infty } \frac{1}{N}\sum _{i}^{N} \frac{\delta _{s}}{\vert u_{i}(t)\vert } \zeta _{i} = 0. \end{aligned}$$

(6)

Thus, for large enough N we can simplify Eq. (5) to

$$\begin{aligned} \phi (t) = \frac{1}{2N}\sum _{i}^{N}\delta _{s}\left( \frac{\langle u_{i}(t) \rangle }{\vert u_{i}(t)\vert } + \frac{\hbox {sgn}(\langle u_{i}(t) \rangle )}{\vert u_{i}(t)\vert }\right) \;. \end{aligned}$$

(7)

At the steady state with maximum coherence $\vert \phi _{\mathrm{m}} \vert$, most agents march in the same direction and the fluctuations within an agent’s communication range become negligible, i.e. the collective state $\phi (t) \approx \phi _{\mathrm{m}}$ is time independent ($\phi _{\mathrm{m}}$ is the collective state at maximum coherence). In this case, the velocity $u_{i}$ of any agent i fluctuates around a constant value $u_{i}(t) \approx \pm 1$. Hence, we can rewrite Eq. (7) by replacing the first and second terms inside the brackets with the steady-state local collective state³ and its sign, i.e. $\frac{\langle u_{i}(t) \rangle }{\vert u_{i}(t)\vert } \approx \phi _{i} = \hbox {sgn}( \phi _{i} )\vert \phi _{i} \vert$ and $\frac{\hbox {sgn}(\langle u_{i}(t) \rangle )}{\vert u_{i}(t)\vert } \approx \hbox {sgn}( \phi _{i})$. This yields

$$\begin{aligned} \begin{aligned} \phi _{\mathrm{m}}&= \frac{1}{2N}\sum _{i}^{N}\delta _{s}(\phi _{i} + \hbox {sgn}( \phi _{i})) \\&= \frac{1}{2N}\sum _{i}^{N}\delta _{s}\hbox {sgn}( \phi _{i} )(\vert \phi _{i} \vert + 1). \end{aligned} \end{aligned}$$

(8)

Furthermore, at the steady state of maximum coherence local neighbourhoods are maximally aligned—i.e. the opinion of any randomly selected agent is likely to be reinforced by its neighbours. Therefore, at the steady state of maximum coherence the system stabilises and the direction switching occurs predominantly due to the spontaneous switching. As the probability for this switching, $p_{s}$, is equal for all agents, the local maximum coherence is equally limited for all neighbourhoods. Therefore, the value of the global collective state closely resembles the local collective state, i.e.

$$\begin{aligned} \phi _{i} \approx \phi _{\mathrm{m}} \end{aligned}$$

(9)

and therefore

$$\begin{aligned} \phi _{\mathrm{m}} = \hbox {sgn}(\phi _{\mathrm{m}})\frac{(\vert \phi _{\mathrm{m}} \vert + 1)}{2N}\sum _{i}^{N}\delta _{s}. \end{aligned}$$

(10)

As $\delta _{s}\in \lbrace -1,1\rbrace$ is a random variable sampled N times from

$$\begin{aligned} \delta _{s}= {\left\{ \begin{array}{ll} -1 ,&{}\quad \text {with } p_{s} \\ 1 ,&{}\quad \text {with } 1-p_{s}, \end{array}\right. } \end{aligned}$$

(11)

we can approximate the sum in Eq. (10) by the expected value of $\delta _{s}$ multiplied by N; this leads to

$$\begin{aligned} \phi _{\mathrm{m}} = \hbox {sgn}(\phi _{\mathrm{m}})(\vert \phi _{\mathrm{m}} \vert + 1)(0.5-p_{s}). \end{aligned}$$

(12)

Taking the absolute value of Eq. (12) and solving for $\vert \phi _{\mathrm{m}} \vert$ return the expression of the steady-state maximum coherence degree

$$\begin{aligned} \vert \phi _{\mathrm{m}} \vert = \frac{\vert 0.5-p_{s} \vert }{1-\vert 0.5-p_{s} \vert }, \end{aligned}$$

(13)

which is a function of only the time-independent noise term $p_{s}$.

3.2 Minimum communication degree for maximum coherence

To obtain Eq. (9), which is crucial for Eq. (13), one could assume that every agent receives maximum social feedback, i.e. the neighbourhood size of every agent i is $n_{i} \rightarrow N-1$. However, this assumption is a strong simplification that cannot be realised in most real systems due to physical constraints and/or communication and computational limitations. Additionally, asking every agent to process large quantity of information may not be necessary to attain consensus, or at least the maximum coherence degree $\vert \phi _{\mathrm{m}} \vert$, and consequently be a waste of energy. Therefore, finding the minimum neighbourhood size $n_{i}$—i.e. the social feedback strength—that guarantees the swarm to converge to $\vert \phi _{\mathrm{m}} \vert$ is of practical interest.

In general, the social feedback strength is determined by the agent density—i.e. the number of agents per space unit—and the communication range, with larger $n_{i}$ for increasing density or communication range. Previous work investigated how agent density influenced the collective coherence in symmetry breaking scenarios. In particular, it has been shown that the stability of the coherent state is proportional to the agent density (Buhl et al. 2006; Huepe et al. 2011; Ariel and Ayali 2015). Systems with low agent density either reached low collective coherence accompanied by frequent changes between the two collective states (where a state was given by the motion direction of the majority) (Buhl et al. 2006; Huepe et al. 2011), or remained undecided, unable to reach consensus (Khaluf et al. 2018); accordingly, highly dense systems reduced the number of transitions between coherent states and thus reduced their flexibility to switch between the available options.

Our goal is to preserve a communication degree that is sufficiently high for the maximum group coherence to emerge but not higher. Additionally, limiting communication to the lowest necessary value could allow the individuals to save energy and reduce unnecessary overload. In this section, we compute the minimal social feedback strength (in terms of the mean neighbourhood size $\langle n_{\mathrm{m}} \rangle$) to reach the maximum possible coherence degree $\vert \phi _{\mathrm{m}} \vert$ as a function of the spontaneous switch probability $p_{s}$.

Let $\rho$ and $\lambda = 1 - \rho$ be the dynamic global proportion of the right-goers and left-goers, respectively, and $\left\langle n \right\rangle$ the mean communication degree. Moreover, let us assume that the encountering probability per unit time is the same for all pairs of individuals. This assumption is a well-known random-mixing approximation (also known as well-mixed system approximation) widely applied in statistical physics to simplify the system modelling (Keeling and Eames 2005; Gross et al. 2006). For instance, applying this approximation, the rate $\omega _{\rho \lambda }$ of finding a communication link between a right-goer and a left-goer is given by

$$\begin{aligned} \omega _{\rho \lambda }=\langle n \rangle \rho \lambda . \end{aligned}$$

(14)

Next, consider an opinion-formation process for second-order homogeneous neighbourhood configurations (NC), where a focal agent i has two neighbours, both of which have the opposite opinion to i (see illustration in Fig. 1a).

Fig. 1

Illustration of homogeneous NCs; the circles represent the agents, the labels R and L represent right-goers and left-goers, respectively, and the arrows represent the bidirectional communication links. In this example, the focal agent is a right-goer (R) with the communication degree k. a Illustration of a second-order NC, i.e. the focal agent (R) has $k=2$ left-going neighbours (L). bk-order NC where the focal agent (R) is communicating with its $k=m+6$ left-going neighbours (L)

Similarly to Eq. (14), the rate for the second-order homogeneous NC illustrated in Fig. 1a is given by $\omega _{\lambda \rho \lambda }= \langle n \rangle \lambda \omega _{\rho \lambda } =\langle n \rangle ^2 \rho \lambda ^2$. Thus, although the time-dependent equation for $\rho$ is unknown and may be considerably complex, following Chen et al. (2016) we can apply the above assumptions to formulate the mean-field approximation for the time evolution of $\rho$

$$\begin{aligned} \begin{aligned} \dfrac{\hbox {d}\rho }{\hbox {d}t}&= p_{s} \left( \lambda - \rho \right) + \pi _{2}\, \left( \omega _{\rho \lambda \rho } - \omega _{\lambda \rho \lambda }\right) \\&= p_{s} \left( \lambda - \rho \right) + \pi _{2}\, \langle n \rangle ^{2} \left( \rho ^{2} \lambda - \rho \lambda ^{2}\right) \;, \end{aligned} \end{aligned}$$

(15)

where $\pi _{2}$ is the probability to adopt the neighbours’ opinion in a second-order homogeneous neighbourhood (i.e. two neighbours with the same opinion). The term $p_{s} \left( \lambda - \rho \right)$ takes into account that each agent may spontaneously switch its opinion with a probability $p_{s}$ per time step, as introduced in Sect. 2.

While Eq. (15) is a powerful tool for regular networks in which all interactions are only of second order, it is an oversimplification for systems with larger and more complex neighbourhood structures. In particular, the approximation in Eq. (14) neglects correlations of $\omega _{\rho \lambda }$ with the agent’s neighbourhood dynamics. For instance, $\omega _{\rho \lambda }$ is likely to be significantly influenced by links of higher order, i.e. communication with a higher number of agents. Thus, to increase the precision of the model, it would be reasonable to additionally consider $\dfrac{\hbox {d} \omega _{\rho \lambda }}{\hbox {d}t}$ as a function of higher-order link densities such as $\omega _{\rho \lambda \rho }$, $\omega _{\lambda \rho \rho }$, $\omega _{\lambda \lambda \rho }$, etc. This extension is well known as pairwise approximation, and there is a large body of literature investigating the validity of such models in the context of opinion-formation (Kimura and Hayakawa 2008; Böhme and Gross 2012) or spread of epidemics (House et al. 2009; Danon et al. 2011; Keeling et al. 2016). Similarly, considering higher-order approximations, i.e. $\dfrac{\hbox {d} \omega _{\lambda \rho \lambda }}{\hbox {d}t}$ or $\dfrac{\hbox {d} \omega _{\rho \lambda \rho }}{\hbox {d}t}$, would further improve the accuracy of the model. However, the cost of higher precision is increased mathematical complexity. Moreover, due to the nonlinearity of physical systems as well as the abundance of random fluctuations and unexpected events, the derivation of precise models may be impractical. Therefore, for the purposes of our study we choose a different approach, which relies on the random-mixing approximation but focuses on higher-order NCs in the limit of maximum global coherence. In particular, we extend Eq. (15) by considering the sum of probabilities of finding k-order homogeneous NCs (for $k \leqslant N-1$), i.e. NCs in which i has $k\geqslant 1$ neighbours which oppose i’s opinion (such as illustrated in Fig. 1b for a right-going focal agent). Similar to Eq. (15), we estimate

$$\begin{aligned} \dfrac{\hbox {d}\rho }{\hbox {d}t} = p_{s} \left( \lambda - \rho \right) + \sum _{k=1}^{N-1}\pi _{k}\, \langle n \rangle ^{k} \left( \rho ^{k} \lambda - \rho \lambda ^{k}\right) , \end{aligned}$$

(16)

where N is the total number of agents in the swarm. Note that, as Eq. (16) shows, we are simplifying the analysis by restricting our model only to NCs in which the neighbourhood of i is homogeneous, i.e. in which all k neighbours oppose i’s opinion. This restriction greatly reduces mathematical complexity while staying in good agreement with experimental observations, as shown in Sect. 5. Moreover, the assumption of homogeneous neighbourhoods appears valid in the limit of steady-state maximum coherence, i.e. where the deviation from local opinion homogeneity (i.e. from local consensus) is significantly reduced and dominated by spontaneous switching. To account for the frequency and significance of this deviation, we define the coefficient $\pi _{k}$ to be the probability that i adopts the opinion of its kth order homogeneous neighbourhood

$$\begin{aligned} \pi _{k} = (\alpha \vert \phi _{i} \vert )^{k}. \end{aligned}$$

(17)

First, the above definition of $\pi _{k}$ couples the neighbourhood coherence of i with the probability that i adopts the opinion of its neighbourhood. Second, it accommodates the fact that the likelihood of finding a k-order neighbourhood decreases with k. Additionally, the first factor in Eq. (17), $\alpha$, is an important ad hoc scaling parameter that includes several realistic nonlinear characteristics, such as finite-size effects due to interference within the communication range of an agent (i.e. limited line-of-sight propagation, e.g. when the communication between two agents cannot be established because the path is physically interrupted by other agents or obstacles), finite size of agents or bounds set by being confined within a finite space (i.e. a bounded finite area with non-periodic boundary conditions). We assume that $\alpha$ satisfies the condition $0 \leqslant \alpha \vert \phi _{i} \vert \langle n \rangle < 1$ which is necessary for the convergence of the sum in Eq. (16) and guarantees that $0 \leqslant \pi _{k} < 1$. As shown in supplementary material Sect. S1 and Fig. S1, this condition is indeed satisfied for the maximum coherence $\vert \phi _{\mathrm{m}} \vert$ after calibrating $\alpha$ with experiment data. In the limit of $N\rightarrow \infty$, Eq. (16) converges to

$$\begin{aligned} \dfrac{\hbox {d}\rho }{\hbox {d}t} = p_{s} \left( \lambda - \rho \right) + \frac{(\pi _{1} \langle n \rangle )^{2} \lambda \rho (\rho - \lambda )}{(1-\pi _{1}\langle n \rangle \lambda )(1-\pi _{1}\langle n \rangle \rho )}. \end{aligned}$$

(18)

Focusing on the decided state with maximum coherence, we consider the steady-state solution for which the left-hand side vanishes (i.e. for $\dfrac{\hbox {d}\rho }{\hbox {d}t} = 0$) and use $\phi = \rho - \lambda$, obtaining

$$\begin{aligned} p_{s} = \frac{(\pi _{1} \langle n \rangle )^{2} (1 - \phi ^{2})}{(2-\pi _{1}\langle n \rangle (1-\phi ))(2-\pi _{1}\langle n \rangle (1+\phi ))}. \end{aligned}$$

(19)

Finally, solving Eq. (19) yields two solutions for $\langle n \rangle$ from which only the one that returns positive values $\langle n \rangle > 0$ is meaningful in our context. Thus, with Eq. (17) and with substituting $\phi ^{2} =\vert \phi _{\mathrm{m}} \vert ^{2}$ we obtain

$$\begin{aligned} \langle n_{\mathrm{m}} \rangle (\vert \phi _{\mathrm{m}} \vert , p_{s}) = \frac{-p_{s} + \sqrt{p_{s} (1-\vert \phi _{\mathrm{m}}\vert ^2(1-p_{s}))}}{0.5(1-p_{s})(\vert \phi _{\mathrm{m}} \vert - \vert \phi _{\mathrm{m}}\vert ^3) \alpha }, \end{aligned}$$

(20)

which is the steady-state solution for the minimal average communication degree needed for the system to converge to the maximum coherence degree $\vert \phi _{\mathrm{m}} \vert$. Note that Eq. (20) is not defined for $p_{s} = 0.5$ which leads to $\phi = 0$, i.e. an entirely undecided collective state with $\rho =\lambda$ and zero coherence. By contrast, for $p_{s} \ne 0.5$ we can use Eq. (13) to reduce Eq. (20) to a function that is defined only in terms of the spontaneous switch probability $p_{s}$, such that $\langle n_{\mathrm{m}} \rangle (\vert \phi _{\mathrm{m}} \vert , p_{s}) = \langle n_{\mathrm{m}} \rangle (p_{s})$, shown in Fig. 2.

Fig. 2

Minimal average degree $\langle n_{\mathrm{m}} \rangle (p_{s})$ to enable emergence of maximum global coherence degree $\vert \phi _{\mathrm{m}} \vert$ (for $\alpha = 0.07$)

Fig. 3

Top views on the simulated robot swarm moving in a ring-shaped arena of 24 m diameter. White and black robots are left-goers and right-goers, respectively. The cyan lines represent communication links between robots

4 Validation with physics-based simulations

To validate the model introduced in Sect. 3, we implemented the locusts’ collective marching behaviour as described in Sect. 2 on a simulated robot swarm composed of $N=175{,}500$ and 1500 Footbot robots (Bonani et al. 2010). The chosen N was large enough to allow statistical reliability. We simulated the robot swarm through ARGoS (Pinciroli et al. 2012), which is a swarm robotics simulator that accurately reproduced physical interaction and the sensing/actuating capabilities of the Footbot.

The benefits of using physics-based simulations in our study were threefold. First, the simulation allowed us to test to what extent our abstract, networks-driven model is influenced by physical interference between robots, density fluctuations and communication correlation caused by spatial effects. Second, it allowed us to examine the behaviour of a swarm in which the robots were unaware of $p_{s}$. Third, the simulator provided a reliable platform for testing the effect of swarm size N on swarm dynamics. Additionally, the ARGoS simulator is programmed to simplify the transition from simulated swarm robotic experiments onto real robotic systems to close the reality gap.

The robot swarm operated in a ring-shaped arena that supported a circular motion of the robots; the outer and inner circles had diameters of 24 m and 4 m, respectively; accounting for the wall thickness of 0.5 m, the accessible environment had the size $A\sim 374~\hbox {m}^{2}$ (see simulator screenshots in Fig. 3). The resulting initial robot density (i.e. for $N=500$) was selected to initially have a minimal level of spatial interference among robots (Khaluf et al. 2016). For each experimental set-up, we performed 30 independent simulations, each with a different random seed.

4.1 Robot implementation

We programmed the robots to avoid unnecessary radial movement by always maintaining an angle of $(90\,\pm \,5)^{\circ }$ when moving in clockwise direction [or $(270\,\pm \,5)^{\circ }$, when moving in counterclockwise direction] to a light beacon located in the centre of the arena, unless collision avoidance was required. Robots sensed possible collision events using a set of 24 proximity sensors. Collision was avoided by performing a rotation with an angle that minimised the probability of a collision (calculated by the agent controller) without changing the sign of $u_{i}(t)$, before continuing marching. The initial position and orientation of the individuals were sampled uniformly from the available space within the arena and $\left[ 0,2\pi \right]$, respectively. The speed parameter $\nu$ [see Eq. (2)] was set to $\nu = 5~\hbox {m/ts}$, following the previous works that included the Czirók model (Czirók et al. 1999; Ariel and Ayali 2015). We use ts to refer to the simulation time step for more accurate phrasing; however, the relation of the simulation time to the simulated time was 1:1.

Robots communicated locally with their neighbours and exchanged their velocity $u_{i}$ (i.e. the speed $\vert u_{i} \vert \in \mathbb {R}^{+}$ and the sign, plus or minus, representing right or left, respectively) in order to reach agreement on a common direction of motion. For communication purposes, each robot was equipped with a range-and-bearing transceiver (Roberts et al. 2009) with a uniformly distributed sensor noise $\zeta _{i}(t) \in \left[ -1.0,1.0\right]$. Every agent was able to sense the number of its communication links by counting the number of distinct received messages. For this purpose, every time step, each robot i broadcast exactly one message with its id and its velocity value $u_{i}(t)$ from Eq. (2). Two robots could exchange information as soon as the discs defined by their communication range $r_i$ overlapped and both robots were in direct line-of-sight of each other. Communication was therefore always bidirectional. In robotic systems, direct communication is straightforward to implement and often preferred to indirect communication (e.g. observing neighbours’ state via a camera) (Bayındır 2016). The robot behaviour was built upon previous work (Khaluf et al. 2018) which has shown how the locust-marching behaviour can be implemented on directly communicating robots in order to qualitatively reproduce the dynamics observed in experiments with real locusts (Buhl et al. 2006) and the predictions of theoretical models (Yates et al. 2009; Ariel and Ayali 2015).

4.2 The scenario of sudden global disruptions

To implement severe external stimuli that considerably disrupt the balance between social feedback and noise, we simulated three sudden events, one breakdown and two influx events. During the breakdown the majority of robots ($65\% \;\text {of}\; N \;\text {i.e.}\; 325$ robots, randomly chosen) were removed from the arena so that their communication with the remaining active robots was entirely interrupted. Therefore, the breakdown led to a substantial decrease in interactions (social feedback intensity), causing a significant drop of the coherence degree $\vert \phi (t) \vert$. This event was used to investigate whether the group is able to recover the maximum level of coherence applying Eq. (20).

By contrast, the influx events significantly increased the agent density by moving a total of 1325 robots into the arena. At the first influx event, the number of robots was restored back to $N=500$ and the subsequent second influx event tripled the swarm size to $N=1500$. The influx events allowed to examine the group ability to maintain the maximum level of coherence while reducing the communication effort down to Eq. (20).

4.3 Range adjustment algorithm and parameters

In our study, the robots responded to the above-mentioned sudden global changes by dynamically adjusting the communication range. This response was efficiently distributed such that each individual i could find a communication range $r_i$ that is as high as necessary for global coherence to emerge but not higher. On the one hand, one could argue that keeping a large $r_i$ would grant the robot a strong social feedback and ease agreement. However, a downside to this approach would be the higher energy consumption associated with a higher number of communication links as well as higher computational cost. Furthermore, as argued in Sect. 3.1, there is a limit to the maximum value of coherence $\vert \phi _{\mathrm{m}} \vert$ which depends on $p_{s}$. Indiscriminately increasing $r_i$ would at most lead to a coherence degree of $\vert \phi _{\mathrm{m}} \vert$, therefore values of $r_i$ above the threshold necessary for $\vert \phi _{\mathrm{m}} \vert$ would be inefficient, leading to redundant computation and energy consumption, without additional coherence benefits. Finally, too high values of $r_{i}$ could lead to less local and more global information exchange, resulting in loss of scalability, robustness and flexibility of the collective system, as discussed in Sect. 3.2 and (Brambilla et al. 2013).

On the other hand, small $r_i$ would save energy while being sufficient to maintain agreement for limited noise levels (or high enough agent density). However, for sparse populations or higher noise levels, small $r_i$ would lead to low coherence levels. A further difficulty is given by the agent density fluctuations in space and time which, in case of small static values of $r_i$, would directly translate into coherence variations.

Consequently, to address all of the above challenges, we focused on finding a distributed algorithm that allowed every agent i, unaware of the global collective state, to individually and adaptively find a value of $r_i$ which was high enough to contribute to maximum global coherence but not unnecessarily higher. This requirement excluded the trivial solution in which all agents had a communication range larger than the swarm diameter. Consequently, as the intensity of the social feedback scaled with the communication degree $n_{i}$, each robot i adapted $n_{i}$ by dynamically tuning its interaction range $r_i$. The target communication degree was set to $n_{\mathrm{target}} = \langle n_{\mathrm{m}} \rangle$, which was calculated by the robot controller for a given $p_{s}$ using Eqs. (13) and (20). (The ad hoc parameter $\alpha$ was calibrated prior to the simulation, see Sect. S1 and Fig. S1a.) The latter two equations are the key contributions of our study and setting $n_{\mathrm{target}}$ equal to the output of Eq. (20) allowed us to realise the desired swarm behaviour. Through this decentralised approach, each robot i found the minimal communication range $r_i$ that led to the maximum global agreement and guaranteed an efficient balance between social feedback and noise.

In particular, each time step the robot increased (decreased) its $r_{i}$ by $\kappa$ if $n_{i}$ was below (above) $n_{\mathrm{target}}$, respectively (see the parameter values in Table 1). The upper limit of $r_{i}$ was assumed to be larger than the arena size to ensure that every agent was able to establish any number of communication links. Conversely, the robots could reduce the communication range to $r_{i} = 0.0$. Note that due to the decentralised nature of the swarm, the robot was not able to directly establish a connection to $n_{i}=n_{\mathrm{target}}$ neighbours but only indirectly through adjusting $r_{i}$. Tuning the communication range allowed the robot decision-making to be robust against agent density fluctuations. For instance, to reach the same target $n_{i}=n_{\mathrm{target}}$, the robot needed to set its $r_{i}$ to higher values when local distribution of robots was sparse and to lower values when local areas were crowded. In short, the communication range $r_i(t)$ of agent i with $n_i(t-1)$ neighbours was computed at each time step t as:

$$\begin{aligned} r_i(t)= {\left\{ \begin{array}{ll} r_i(t-1) + \kappa ,&{} \quad \text {if}\; n_i(t-1) < n_{\mathrm{target}}\\ r_i(t-1) ,&{} \quad \text {if}\; n_i(t-1) = n_{\mathrm{target}}\\ r_i(t-1) - \kappa ,&{} \quad \text {if}\; n_i(t-1) > n_{\mathrm{target}}.\\ \end{array}\right. } \end{aligned}$$

(21)

Table 1 Overview of parameters used in the simulation; ts is a unit referring to simulation time steps

The initial communication range was set to a minimal value, $r_{\mathrm{init}} = 0.3~\hbox {m}$, approximately the radius of a robot as measured from the centre of the robot. Due to Eq. (21), the robots rapidly increased the range and no physical contact was required for communication. Note that it was also possible to initialise the simulations with a communication range $r_{\mathrm{init}} \gg 0.3~\hbox {m}$. In this case, each agent adaptively reduced $r_{i}$ down to the value that is necessary to obtain $n_{i} = n_{\mathrm{target}}$. However, the differences in collective dynamics between high and low $r_{\mathrm{init}}$ were not significant to the purposes of the current study (see Figs. S2 and S3 in Sect. S2 for a more detailed discussion).

5 Simulation results

Using data from physics-based simulations, we validated Eq. (13) and Eq. (20). Additionally, we examined the performance of the range adjustment algorithm from Sect. 4.3 with respect to the swarm response to abrupt global changes such as agent breakdown and agent influx. For these purposes, we proceeded as follows:

• (i) In Sect. 5.1, we confirmed that Eq. (13) returns the maximum coherence degree $\vert \phi _{\mathrm{m}} \vert$ at significantly high values of communication degree. For this, we compared the theoretical prediction of Eq. (13) to data from simulations in which the communication range was constant and at high values. Here, the range was not dynamically adjusted. However, it was sufficiently high for each robot to obtain a communication degree $n_{i} > \langle n_{\mathrm{m}} \rangle$ [recall that the latter is given by Eq. (20)]. For this reason, we did not consider the influx events at this point.

• (ii) In Sect. 5.2, we validated Eq. (20) by comparing the results from (i) to simulations in which the agents applied the range adjustment given by Eq. (21) to maintain $n_{i} = \langle n_{\mathrm{m}} \rangle$. Note that here $n_{i}$ was on average three to four times lower than in (i).

• (iii) In Sect. 5.3, we tested the performance of (ii) in the event of an agent breakdown and compared it to the performance of a null behaviour. The null behaviour consisted of a swarm of robots with a constant communication range which was set equal to the pre-breakdown average range $\langle r \rangle$ from (ii). Consequently, the average communication degree was $\langle n \rangle \approx \langle n_{\mathrm{m}} \rangle$ before the breakdown and $\langle n \rangle < \langle n_{\mathrm{m}} \rangle$ after the breakdown. In addition, we considered two influx events occurring after the breakdown to validate the group ability to reduce communication cost without losing high coherence following Eq. (21).

5.1 Maximum coherence degree as a function of $p_{s}$

We quantified the agreement between theory [i.e. Eq. (13)] and experiment for a large set of $p_{s}$ values. For this purpose, we set the communication range to constant but high values to ensure a high average communication degree, $\langle n \rangle > \langle n_{\mathrm{m}} \rangle$, and measured the global coherence degree $\vert \phi (t) \vert$ for two robot densities. In particular, we kept the arena size constant and varied the swarm size $N \in \{500, 175\}$ through a breakdown, as described in Sect. 4.2. In each experiment, we tested a different value of $p_{s} \in (0,1)$ and simulated a breakdown at time step $t_{\mathrm{bd}}=2500~\hbox {ts}$ which changed the robot density from for $t < t_{\mathrm{bd}}=2500~\hbox {ts}$ to for $t > t_{\mathrm{bd}}=2500~\hbox {ts}$. Figure 4 shows the time averages $\overline{\vert \phi \vert }$ as a function of $p_{s}$ for $t < t_{\mathrm{bd}}=2500~\hbox {ts}$ in panel (a) and $t > t_{\mathrm{bd}}=2500~\hbox {ts}$ in panel (b), i.e. before and after the breakdown, respectively.

Fig. 4

Time-averaged maximum global coherence degree $\overline{\vert \phi \vert }$ as a function of the spontaneous switch probability $p_{s}$ before (a, triangles) and after (b, circles) the breakdown event. Each data point represents the average value and the error bars the standard deviation over 30 simulations. In the former (latter) case, $\overline{\vert \phi \vert }$ was averaged between $t=1000~\hbox {ts}$ and $t= 2500~\hbox {ts}$ ($t=3000~\hbox {ts}$ and $t= 5000~\hbox {ts}$), respectively, as illustrated in the inset for $p_{s}=0.2$. The average degrees were $\langle n \rangle \in \left[ 30,62\right]$ ($\langle n \rangle \in \left[ 21,42\right]$) for before (after) the breakdown, respectively, with higher $\langle n \rangle$ corresponding to simulations with $p_{s} > 0.2$. The maximum coherence predicted by Eq. (13) (blue solid line) nicely matches the swarm robotics simulations’ results for $\overline{\vert \phi \vert } > 0.3$ (Color figure online)

As Fig. 4 demonstrates, the theoretical model from Eq. (13) is in good agreement with the experimental observations.⁴ However, deviations occur for low values of $\overline{\vert \phi \vert }$. This is expected, given that in deriving Eq. (13) we assumed that the system is at the steady state of high coherence, with local coherence degree approaching the global one [Eq. (9)]. The assumption of Eq. (9) does not hold for low degrees of global coherence as it would in a well-mixed system. Nevertheless, its validity is evident in our spatial system for a considerable set of $p_{s}$ values for high and low robot densities. In particular, Fig. 4 shows a remarkably good agreement of the theoretical model with empirical data for $\overline{\vert \phi \vert } > 0.3$. For $p_{s} < 0.5$, $\overline{\vert \phi \vert }$ decreases as $p_{s}$ increases and vice versa for $p_{s}>0.5$. In the latter case, the global collective state $\phi (t)$ switches its sign at every time step, due to the discrete nature of the simulation time (see plots of $\phi (t)$ in Fig. S4 of Sect. S3). Moreover, as $p_{s}$ approaches 0.5, the agent motion decreases significantly—and is negligible for $p_{s} > 0.5$—because the time between the orientation switching approaches $\varDelta t = 1~\hbox {ts}$, zeroing out the distance travelled. Consequently, agent density fluctuations vanish and the neighbourhood sizes become static. Furthermore, as $p_{s}$ increases, so does the likelihood that the agent’s spontaneous opinion switch applies also to its neighbours. Therefore, at high $p_{s}$ an agent switches its opinion almost simultaneously with its neighbourhood, leading to the emergence of high coherence. Such high switching rates may be rather rare in animals or robots if they are attributed solely to individual failure. Nevertheless, spontaneous opinion switching with $p_{s} \geqslant 0.5$ may also occur due to contrarian behaviour (i.e. acting against the majority) (Zhong et al. 2005; Liang et al. 2013), malicious agents (Saldaña et al. 2017) or outsider attacks (Saulnier et al. 2017) and is therefore worth taking into consideration.

5.2 Minimum communication degree in relation to $p_{s}$ and $\vert \phi _{\mathrm{m}} \vert$

The results in Fig. 4 were obtained by setting $r_{i}$ to values that were considerably high and leading to $n_{i} > \langle n_{\mathrm{m}} \rangle$. As a successive analysis, we tested whether the theoretically derived minimal number of communication links $\langle n_{\mathrm{m}} \rangle$ [i.e. given by Eq. (20)] applied to the range adjustment behaviour (defined in Sect. 4.3) was allowing the swarm to reach $\vert \phi _{\mathrm{m}} \vert$. For this purpose, we selected the target communication degree $n_{\mathrm{target}}=\langle n_{\mathrm{m}} \rangle$. Figure 5a shows that, for $p_{s} \leqslant 0.3$ and $p_{s} \geqslant 0.7$, the simulation outcome is $\overline{\vert \phi \vert } \approx \vert \phi _{\mathrm{m}} \vert$, i.e. in very good agreement with the theoretical maximum. We limit our analysis to $p_{s} \leqslant 0.3$ and $p_{s} \geqslant 0.7$ because outside of this $p_{s}$ range the system approaches an undecided state, i.e. $\overline{\vert \phi \vert } \approx 0$ even for considerably large $\langle n \rangle$ (see Fig. 4).

The high standard deviations of $\overline{\vert \phi \vert }$ for $p_{s} > 0.85$ originated from particular simulation seeds for which the system remained undecided over the entire duration of the experiment. There are two possible reasons for this observation: (i) the duration of the warm-up period, i.e. the time period necessary to reach the steady state, was longer than the experiment or (ii) the system could not always escape the state in which $\vert \phi (t) \vert$ fluctuates around zero, even for very long simulation times. However, the number of simulations for which the steady state was not reached did not decrease significantly after extending the pre-breakdown period from 2500 to 12,500 ts. Both arguments indicate that the occurrence of a steady state with maximum coherence may be significantly influenced by the initial conditions (such as robot location and orientation). Another influencing factor may be the communication degree as for very high $\langle n \rangle$ the steady state was almost always reached (low standard deviations in Fig. 4) and for too low $\langle n \rangle$ the steady state was never reached (see supplementary material Sect. S4 and Fig. S5). Nevertheless, we believe that high values of $p_{s}$ may be considered as a pathological case of our system as the resulting behaviour is a continuous switch of direction every time step and it may have limited interest for a robotic implementation.

Additionally, we compared the range adjustment approach to a null behaviour where the communication range is constant but significantly shorter than in Sect. 5.1. Specifically, the communication range was configured to be equal to the pre-breakdown average range $\langle r \rangle$ of the adaptive model from Fig. 5a. On average, this created comparable conditions between the null behaviour and the adaptive behaviour outside of the breakdown or influx events. However, in contrast to the adaptive behaviour, in the case of the null behaviour local density fluctuations that arose due to robot motion significantly influenced the average degree (see Sect. S5 for more details). On the one hand, a robot i could have $n_i < \langle n_{\mathrm{m}} \rangle$ when the agent density is locally sparse. On the other hand, this communication degree loss was not always compensated in dense neighbourhoods due to interference (e.g. blocked line-of-sight). Therefore, before the breakdown, $\langle n \rangle$ was on average lower for the null behaviour than for the adaptive behaviour. Consequently, as shown in Fig. 5b, the coherence degree $\overline{\vert \phi \vert }$ for $p_{s} \leqslant 0.3$ was lower compared to the adaptive behaviour. This reasoning is further supported by the comparably higher $\overline{\vert \phi \vert }$ for $p_{s} \geqslant 0.7$. For these $p_{s}$ values, the system approached a state in which the distance travelled by the robots was zero due to the frequent opinion switches. Consequently, the local density fluctuations (e.g. temporary crowding) disappeared and $\overline{\vert \phi \vert }$ of the null behaviour was close to the adaptive behaviour.

Fig. 5

Time-averaged maximum global coherence degree $\overline{\vert \phi \vert }$ as a function of the spontaneous switch probability $p_{s}$ before the breakdown event (filled triangles). The continuous curve shows $\vert \phi _{\mathrm{m}} \vert$ from Eq. (13). a simulations with robots that adaptively adjust the communication range to reach $n_{i}=\langle n_{\mathrm{m}} \rangle$ given by Eq. (20) (with $\alpha =0.07$); b null behaviour, communication range is constant and equal to the average communication range of the range adjustment behaviour before the breakdown. $\overline{\vert \phi \vert }$ is averaged between $t= 1000~\hbox {ts}$ and $t= 2500~\hbox {ts}$ as illustrated in the inset of (b) for the null behaviour and $p_{s}=0.2$

5.3 Swarm response to global changes

In order to understand the collective decision-making under sudden global disruptions, we implemented the scenarios described in Sect. 4.2 and investigated the communication dynamics for a set of spontaneous switch probabilities $p_{s} \in \{0.01,0.05,0.1,0.2\}$. Figure 6 demonstrates the time evolution of the average degree $\langle n \rangle$. Directly after the breakdown event the communication degree of the remaining active robots was greatly reduced (implying lower social feedback intensity). However, in the case of the range adjustment behaviour, the robots responded by increasing their communication range $r_i$ (see bottom plots in Fig. 6) according to Eq. (21) and recovering $n_i\approx \langle n_{\mathrm{m}} \rangle$. As a result, the swarm was able to maintain the same average degree as before the breakdown and compensate for the removed links (see Fig. 6, squares). This behaviour was not observed for the null behaviour (see Fig. 6, diamonds). Furthermore, in the adaptive case, $\langle r \rangle$ was rapidly decreased to the pre-breakdown value after the first influx event and below the pre-breakdown value after the second, more severe, influx event (see bottom plots in Fig. 6). Despite the agent density increases, $\langle n \rangle$ was maintained at a constant level. As expected, the inverse dynamics was observed for the null behaviour.

Fig. 6

Average degree $\langle n \rangle$ for $p_{s} \in \{0.01,0.05,0.1,0.2\}$ and the corresponding average communication range $\langle r \rangle$ (top and bottom plot of each sub-figure, respectively). For the case of the null behaviour (orange lines), $\langle r \rangle$ was set equal to the pre-breakdown time-averaged values of the range adjustment approach (blue curves). The results are averages over 30 simulations; the shaded regions around the $\langle n \rangle$ curves show the 95% confidence interval. Grey dashed vertical lines indicate the time of the three events in which the robot density was changed: the breakdown at $t_{\mathrm{bd}}=2500~\hbox {ts}$, the first influx at $t_{if1}=5000~\hbox {ts}$ and the second influx at $t_{if2}=7500~\hbox {ts}$. For all four $p_{s}$, $\langle n \rangle$ was quickly recovered after both events in the adaptive behaviour, in contrast to the null behaviour (Color figure online)

Note that for the range adjustment behaviour, $\langle n \rangle \rightarrow \langle n_{\mathrm{m}} \rangle$ for all $p_{s}$, independent of the initial value of the communication range (see Fig. S2 in Sect. S2 for more details). By contrast, the average degree of the null behaviour approach demonstrates significant long-term variations. These variations are a consequence of the agents’ inability to adjust the communication range in response to agent density fluctuations as argued previously in Sect. 5.2.

Figure 7 reflects the influence of communication dynamics on the swarm ability to reach maximum coherence degree for the four tested values of $p_{s}$, averaged over 30 simulation runs (see Fig. S4 for the comparison of the time evolution of $\phi (t)$ between the two behaviour models for only one simulation seed). In general, in the adaptive approach the coherence degree agrees well with the theory [the horizontal grey dashed lines in Fig. 7 are computed from Eq. (13)]. By contrast, in the null behaviour the $\vert \phi (t) \vert$ mainly lies below $\vert \phi _{\mathrm{m}} \vert$ and is subject to significant long-term fluctuations caused by the inability to regulate communication degree (Fig. 6). Outside of the breakdown event, motion dynamics was primarily responsible for these variations, as discussed in the previous section and in Sect. S5. The breakdown event caused a significant drop of coherence $\vert \phi (t) \vert < \vert \phi _{\mathrm{m}} \vert$ due to the sudden decrease in social feedback (i.e. $\langle n \rangle < \langle n_{\mathrm{m}} \rangle$). Subsequently, the first influx event led to the increase in $\vert \phi (t) \vert$ back to the pre-breakdown value due to the increase in agent density. After the second influx event, the latter is particularly high, leading to the presence of strong social feedback and $\vert \phi (t) \vert \rightarrow \vert \phi _{\mathrm{m}} \vert$ for both behaviour models.

Fig. 7

Global coherence degree for $p_{s} \in \{0.01,0.05,0.1,0.2\}$. The results are averages of 30 simulations; the shaded regions around the curves show the 95% confidence interval. Grey dashed vertical lines indicate the time of the three events in which the robot density was changed: the breakdown event at $t_{\mathrm{bd}}=2500~\hbox {ts}$, the first influx event at $t_{if1}=5000~\hbox {ts}$ and the second influx event at $t_{if2}=7500~\hbox {ts}$. The grey dashed horizontal line indicates the $\vert \phi _{\mathrm{m}} \vert$ given by Eq. (13). For all four $p_{s}$, after the breakdown the group was able to rapidly recover coherence in the adaptive behaviour, in contrast to the null behaviour which suffered a significant drop in $\langle n \rangle$. After the influx events, both models showed recovery of the coherence level, as expected from our theoretical considerations due to the increase in $\langle n \rangle$ (in the null behaviour) and maintenance of $\langle n \rangle = \langle n_{\mathrm{m}} \rangle$ (in the adaptive behaviour)

For a more careful validation of Eqs. (13) and (20), we simulated the above behaviour for a larger set of spontaneous switch probabilities $p_{s}$. The results are presented in Fig. 8. The figure contrasts the swarm performance of the adaptive approach to the null behaviour with respect to reaching $\vert \phi _{\mathrm{m}} \vert$ after the breakdown and the first influx events. As Fig. 8 shows, applying Eq. (20) in the range adjustment behaviour enables the swarm to restore $\overline{\vert \phi \vert }$ close to the theoretical value of Eq. (13) after the breakdown (Fig. 8a) as well as to maintain $\overline{\vert \phi \vert } \approx \vert \phi _{\mathrm{m}} \vert$ after the first influx event (Fig. 8c). By contrast, in the null behaviour the swarm coherence approaches the theoretical limit only after the (first) influx (Fig. 8d), whereas after the breakdown (Fig. 8b) the swarm coherence is considerably below the $\overline{\vert \phi \vert } \approx \vert \phi _{\mathrm{m}} \vert$ reached in Fig. 8a. The large standard deviation values observed for $p_{s} > 0.8$ in the null behaviour can be explained using the same arguments as for the adaptive behaviour (see Sect. 5.2).

Fig. 8

Time-averaged maximum global coherence degree $\overline{\vert \phi \vert }$ as a function of the spontaneous switch probability $p_{s}$ after the breakdown event (top row, empty circles) as well as after the subsequent first influx (bottom row, filled circles). The continuous curve shows $\vert \phi _{\mathrm{m}} \vert$ from Eq. (13). Left column: simulations with robots that adaptively adjusted the communication range to reach $n_{i}=\langle n_{\mathrm{m}} \rangle$ given by Eq. (20) (with $\alpha =0.07$); right column: null behaviour, communication range is constant and equal to the average communication range of the range adjustment behaviour before the breakdown. After the breakdown, $\overline{\vert \phi \vert }$ is averaged between $t= 3000~\hbox {ts}$ and $t= 5000~\hbox {ts}$ as illustrated in the inset of (b) for the null behaviour and $p_{s}=0.2$; after the influx event, the $\overline{\vert \phi \vert }$ is averaged between $t= 5500~\hbox {ts}$ and $t= 7500~\hbox {ts}$ as illustrated in the inset of (d) for the null behaviour and $p_{s}=0.2$

The swarm coherence values after the second influx event (i.e. swarm size increasing to $N=1500$) are not shown because they are similar to the results in Fig. 4. For the null behaviour, the reason is the high agent density that leads to a high number of communication links and therefore high coherence (as expected from our considerations in Sect. 3). For the range adjustment behaviour, the maximum coherence is maintained together with the minimum degree similar to Fig. 8a, c.

6 Conclusion

In this paper, we have studied the relationship between noise—modelled as random fluctuations of agents’ opinion—and social feedback—which scales with the communication degree of an agent—as well as the influence of their relationship on the coherence of a collective system. As a case study, we have examined a collective symmetry-breaking problem inspired by locust-marching behaviour. In our system, the individuals selected one out of two options—marching either in the clockwise or in the counterclockwise direction—based on the input received from their neighbours. Additionally, any individual could spontaneously switch its opinion with probability $p_{s}$, modelling a form of noise. We have shown that this probability determines the maximum degree of coherence that the swarm can achieve (i.e. the maximum proportion of agents with the same opinion). Using mean-field approximations, we have derived a steady-state estimate of the minimum communication degree $\langle n_{\mathrm{m}} \rangle$ (i.e. the minimum average number of neighbours per agent) necessary to enable the collective system reach maximum coherence degree under a specific level of noise. Remarkably, we could formulate $\langle n_{\mathrm{m}} \rangle$ as a function of only the noise level $p_{s}$. As social feedback scales with the communication degree, the derived function of $\langle n_{\mathrm{m}} \rangle$ [i.e. Eq. (20)] represents the relationship between social feedback and noise that leads to a coherent collective behaviour. This minimum degree ensures that the communication between the individuals remains local as well as energetically and computationally efficient.

To test the validity of our theoretic findings, we implemented an algorithm which enabled an individual to adapt its communication range to reach the target communication degree $\langle n_{\mathrm{m}} \rangle$. Through this decentralised algorithm, the swarm was able to reach the maximum coherence degree and to online adapt to robot density changes. To test the ability of our algorithm to adapt to robot density changes, we simulated a breakdown in which the majority of the swarm was removed from the system and two influx events in which the swarm significantly increased (i.e. over a thousand individuals were added to the swarm). By applying our range adjustment algorithm, the swarm was able to implicitly sense the global changes and respond to them accordingly. The key component of our approach was the analytically derived minimum communication degree $\langle n_{\mathrm{m}} \rangle$ in terms of $p_{s}$.

Remarkably, although the formulation of $\langle n_{\mathrm{m}} \rangle$ included one ad hoc parameter, it did not explicitly require information about the environmental properties (such as size or shape of the arena) nor the physical configuration of an agent. In particular, the ability of the swarm to reach maximum coherence was independent of the swarm size as long the agents maintained $\langle n_{\mathrm{m}} \rangle$ individually, i.e. in a decentralised, fully distributed manner. Therefore, our results highlight the importance of the swarm density attribute in terms of feedback density—i.e. average number of communication links per agent—as opposed to the physical agent density—i.e. mean number of individuals per unit area (Khaluf et al. 2017b). Although the impact of swarm density on collective alignment has been intensively studied before in experiments with real locusts (Buhl et al. 2006) as well as related models (Vicsek et al. 1995; Yates et al. 2009; Huepe et al. 2011; Ariel and Ayali 2015), little emphasis was put on the distinction between feedback density and the agent density. One possible reason is that in natural systems this distinction is less relevant as individuals tend to receive feedback from all agents within their perception. However, in artificial systems it is common to distinguish between particle density (i.e. number of agents per unit area of the arena) and sensor coverage density (i.e. disc area covered by the agent’s sensor per unit area of the arena). The latter may be tuned in a decentralised manner by the individuals, as opposed to most natural systems.

The adaptive distributed tuning of communication is vital to reduce fluctuations in social feedback strength as a response to variations in agent density. Without the tuning of the communication range—the null behaviour in Sects. 5.2 and 5.3—agent density fluctuations in the agent’s local neighbourhood may lead to low levels of global coherence. Conversely, the adaptive approach allows individuals to reduce social feedback fluctuations and lead to a collective behaviour that is swarm size independent, robust to agent removal and scalable.

The key contribution of our study is the analytically derived $\langle n_{\mathrm{m}} \rangle$. However, to enable an adaptive behaviour in which all agents can reach $\langle n_{\mathrm{m}} \rangle$ we did not explicitly impose an upper bound $r_{\mathrm{max}}$ to the communication range of the agents. Instead, we assumed that $r_{\mathrm{max}}$ may be longer than the diameter of the arena (i.e. $r_{\mathrm{max}} > 25~\hbox {m}$). However, in some cases—particularly in real robotics implementations—a shorter $r_{\mathrm{max}}$ may be desirable, which creates a trade-off. On the one hand, a high communication range may be energetically or computationally costly and hard to realise on real robots. On the other hand, a low $r_{\mathrm{max}}$ can lead to substantial loss of coherence. The latter is confirmed by our simulations of a null behaviour in which, contrary to the adaptive behaviour, all agents had a constant $r = r_{\mathrm{max}} < 2.5~\hbox {m}$. Note that even if each agent could dynamically adjust the range up to this low $r_{\mathrm{max}}$ the resulting dynamics would be similar to our null behaviour. In particular, when $r_{\mathrm{max}}$ is low, the decrease in agent density directly leads to a decrease in group coherence. This indicates that when $r_{\mathrm{max}}$ is lower than what is necessary for an agent i to reach $n_{i} = \langle n_{\mathrm{m}} \rangle$, the robustness of collective decision-making is significantly reduced. By contrast, allowing the agents to reach the analytically derived $\langle n_{\mathrm{m}} \rangle$ maximises group agreement without imposing a higher than necessary communication cost. Therefore, our approach is a step towards an optimisation of the trade-off between high coherence and low communication cost.

Nevertheless, implementing our model on real robots may pose significant challenges such as the exclusion of environmental noise, the implementation of range adjustment behaviour and the estimation of the spontaneous switching rate. Although the technical realisation of a real robotic system is outside of the scope of the current study, we believe that meeting the challenges associated with translating our model onto real robots is not unrealistic. However, the main focus of the current study is rather dedicated to the more abstract definition of $\langle n_{\mathrm{m}} \rangle$. Consequently, for the purpose of validating our theoretical model under more realistic conditions our effort aimed not at thoroughly reproducing a real-world scenario but rather at implementing a collective system in an environment that is far from ideal. For instance, due to the implemented physical interference and line-of-sight blocking, the communication range of robots in crowded neighbourhoods was confined to the nearest neighbours even without an explicit definition of $r_{\mathrm{max}}$. By contrast, a predefined value of $r_{\mathrm{max}}$ that is lower than the size of the arena has the major disadvantage of forcefully limiting the agents’ ability to establish $\langle n_{\mathrm{m}} \rangle$ communication links. Therefore, it is not suitable for the purposes of validating a relationship between $\langle n_{\mathrm{m}} \rangle$ and the maximum global coherence. It is important to emphasise that, at its core, the range adjustment algorithm is a tool used to enable the robots to adapt the strength of social feedback through the number of communication links. An alternative technique could be the adjustment of the motion speed such that faster motion leads to more frequent communication. Nevertheless, we believe that extending our simulations to more practical and realistic scenarios is a promising direction for future research. These scenarios should consider realistic values of $r_{\mathrm{max}}$ as well as address other technical challenges associated with range adjustment by real robots.

In general, our results contribute to the domain of swarm robotics by revealing a fundamental link between coherent collective behaviour, fluctuations in individual decision-making and social interactions. Provided a robot is capable of dynamically adjusting its communication range, our findings can be applied to a wide range of swarm robotic decision-making processes. In the present study, our theoretical model was tested on the simulated case study of coordinated motion; however, other swarm robotic tasks such as navigation, path formation, flocking or foraging are also viable alternatives for further investigation and potential application. Thus, our results have far reaching implications for the research on collective symmetry breaking as they showcase the critical and fundamental relationship between social feedback, noise and coherence in collective systems, and demonstrate the ability of collective systems to reach maximum coherence after severe external interference.