Time-variant feedback processes in collective decision-making systems: influence and effect of dynamic neighborhood sizes

Abstract

Self-organizing systems rely on positive feedback (amplification of perturbations). In particular, in swarm systems, positive feedback builds up in a transient phase until maximal positive feedback is reached and the system converges temporarily on a state close to consensus. We investigate two examples of swarm systems showing time-variant positive feedback: alignment in locust swarms and adaptive aggregation of swarms. We identify an influencing bias in the spatial distribution of agents compared to a well-mixed distribution and two features, percentage of aligned swarm members and neighborhood size, that allow us to model the time variance of feedbacks. We report an urn model that is capable of qualitatively representing all these relevant features. The increase in neighborhood sizes over time enables the swarm to lock in a highly aligned state but also allows for infrequent switching between lock-in states. We report similar occurrences of time-variant feedback in a second collective system to indicate the potential for generality of this phenomenon. Our study is concluded by applications of methods from renormalization group theory that allow us to focus on the neighborhood dynamics as scale transformations. Correlation lengths and critical exponents are determined empirically.

1 Introduction

Many systems showing pattern formation, such as animal coloration (Camazine et al. 2001), embryogenesis (Crick 1970), and grazing systems (Noy-Meir 1975), are examples of self-organizing systems. In a self-organizing system, numerous sub-components interact with each other and with the environment with simple and local interaction rules. These local interactions result either in positive feedback (also called amplification or activation) or in negative feedback (also called inhibition) effects, respectively, when interactions drive the system toward or away from an ordered state. General features of self-organizing systems are the interplay between positive feedback and random fluctuations as well as the interplay between positive and negative feedbacks (Bonabeau et al. 1999). Typically the system is initialized to an unordered state, that is, it is not showing any patterns in the beginning and it is far from an attractor. Fluctuations generate local deviations that are amplified, propagated through space and time by positive feedback until a spatiotemporal pattern forms. Negative feedback might prevent the system from reaching extreme states (e.g., 100% ordered, extinction). Due to this stochastic process, random dynamical attractors form and characterize especially the long-term dynamics of the system features (Arnold 2003).

Swarm systems are another example of self-organizing systems. A frequent setting in the case of swarms is that several stable ordered states exist (multistability) that are symmetrical to each other—a typical situation in collective decision-making systems (Valentini et al. 2014; Hamann 2013b; Montes de Oca et al. 2011; Dussutour et al. 2009; Nicolis and Dussutour 2008). For example, in flocking there are many directions in which the swarm could move and depending on the situation many directions might be of equal utility. Collective systems rely on consensus formation to be efficient and to prevent splitting the swarm (Jeanson et al. 2004; Couzin et al. 2005). Although the swarm may approach a consensus state and a large majority may share a common opinion, the swarm typically does not reach the extreme state of a 100% consensus (due to negative feedback as discussed above). The asymptotic behavior of the system is characterized by attractors that we call lock-in following the notion of Arthur (1989) who discusses economical processes such as the formation of standards. These lock-in states are random dynamical attractors, and due to stochasticity, the system always has nonzero probability to switch between lock-in states (Arnold 2003).

A swarm is a distributed agent system where each agent autonomously decides on its actions. With the global knowledge of an external observer, we can classify at least a subset of the agents’ actions as positive or negative feedback events that drive the system toward an ordered state or drive it away from a too ordered state (Hamann 2012, 2013a, b). These events can also be viewed as ‘frozen accidents’ (Hamann et al. 2013), that is, due to random events an agent increases the system’s order slightly (e.g., by approaching another agent in an aggregation scenario or by aligning with an agent that happens to be close-by in a flocking scenario) and subsequently tries to conserve that new state (e.g., by staying stopped or by following the other agent). By counting these positive and negative feedback events, we are able to calculate the ratio of positive feedback events

$$\begin{aligned} f^+ = \frac{F^+}{F^++F^-}, \end{aligned}$$

(1)

for the number of positive feedback events $0\leqslant F^+ \leqslant N$ within a limited time interval for swarm size N ($F^-$ accordingly). If $f^+>0.5$ (respectively, $f^+<0.5$), we say that positive feedback (negative feedback) is predominant and we know that the system is generally approaching (departing from) an ordered state.

As an extension, we can measure positive and negative feedback events for each possible system state L and average over many independent runs. We obtain a function of ratios $f^+(L)$. The ratios can be interpreted as probabilities of positive feedback. Hence, a Markov chain whose transition probabilities are defined by function $f^+(L)$ is a simple and abstract model of such systems, see Fig. 1 for swarm size $N=4$. In its simplest form, the system state L would just count the number of agents in a certain state s. High degrees of order (patterns) would be reached for $L=0$ (no agent in state s) and $L=N$ (all agents in state s). The transition probabilities are defined by $f^+(L)$. For example, $p_{3,2}=f^+(3)$ and $p_{3,4}=1-f^+(3)$ in Fig. 1.

Fig. 1

Example of a Markov chain for swarm size $N=4$. $p_{\mathrm{{i}}, \mathrm {j}}$ provides the transition probability to move from state i to state j

For several swarm systems, such as density classification (Hamann et al. 2010; Hamann 2012, 2013b), aggregation controlled by BEECLUST (Schmickl and Hamann 2011; Schmickl et al. 2008; Kernbach et al. 2009), and alignment in locust swarms (Yates et al. 2009; Buhl et al. 2006), it was found that negative feedback is initially predominant while positive feedback builds up only over time and not merely depending on the order of the current system state (Hamann 2012, 2013a, b). The time variance of feedbacks can be reflected, for example, in the above Markov chain model by time-dependent transition probabilities $p_{i+2,i+1}(t)=f^+(i,t)$. This dependency on time needs to be modeled and requires a defined property that determines the time dependency. Consequently, there exists a second feature and/or a mechanism besides the order of the system that controls the increase in positive feedback over time. This feature is very likely a spatial property. That fact is determined by the method of elimination due to the simplicity of the investigated systems. The agents of the investigated systems have only two properties, their (internal) state (e.g., opinion, direction of motion) and their position. This two dimensionality allows for two conceptually independent definitions of order. These systems can be ordered in terms of agent positions¹ and/or in terms of their states. Figure 2 shows all four possible combinations in a setting similar to a locust system that we investigate in this paper primarily.

Fig. 2

The four examples of un-/ordered positions and states of agents. Agents have positions on a circle (cf. locust scenario) and have one of two states: gray or black. a Ordered positions, ordered states. b Unordered positions, ordered states. c Ordered positions, unordered states. d Unordered positions, unordered states

Our first objective is to determine the above-mentioned second feature. Once determined, we aim at defining a mathematical model that is capable to (1) cover the interplay between positive and negative feedbacks and (2) to identify the increase in positive feedback over time. We continue the work reported in earlier publications (Hamann 2012, 2013b), where research questions investigated here were raised. We extend the recently published study (Hamann and Valentini 2014) where we provided preliminary results. Our main concept is to consider spatial features—specifically, relative agent positions. We find that the investigated system maximizes both types of order (see Fig. 2) although its primary purpose is to maximize the order in the motion direction. In the case of the locust system, we identify the second feature to be its neighborhood. That is, the local density of agents within perception range of a different agent. In the aggregation scenario, we have also analyzed the influence of the average neighborhood size and we have derived an appropriate model (Hamann et al. 2014). Another related work is that of Huepe et al. (2011) based on ‘adaptive networks.’ They also find that spatial feature is relevant and that can be modeled in an abstract way.

Most of the following experiments are based on a swarm model inspired by swarm alignment of locusts. These swarms switch between different aligned states even after having reached high degrees of alignment (lock-in states). This special property is necessary to stay adaptive to dynamic changes in the environment and is subject to the following investigations. First, we follow our hypothesis that spatial features are relevant in these systems and empirically analyze the disparity in the dynamics of locust alignment between well-mixed and biased spatial distributions of agents. We measure the probability of positive feedback based on transition probabilities and the bias in the agents’ neighborhoods toward agents of the current majority. Based on that statistical evidence collected in our preliminary analysis, we detect a crucial feature that summarizes these spatial effects, the average neighborhood size of agents. We define a two-dimensional Markov chain that depends on the current degree of alignment in the system and the average neighborhood size of agents. A vector field representation of the transition probabilities obtained from the Markov chain model provides a clear picture of what we call the ‘fly-bottle effect.’² We develop an urn model of the locust dynamics capable to represent the primary features of the system but at a lower computational complexity. After validating the urn model against agent-based simulations of the locust system, we derive an analytical description of its simplified dynamics that allow us to obtain insights into the causes of time-variant positive feedback as a function of the neighborhood size. Finally, we apply methods from physics, in particular the theory of renormalization group. This is done with the purpose of giving a different perspective on the system’s neighborhood size dependency, namely the perspective of scale transformation dynamics instead of temporal dynamics. This is followed by techniques to determine the propagation of correlations between agents through space.

2 Locust scenario

In the growth stage of a wingless nymph, swarms of desert locusts (Schistocerca gregaria) show a self-organizing collective motion behavior that is often referred to as ‘marching bands’ (Buhl et al. 2006). The collective motion is expressed in the directional alignment of a majority of locusts, it is density dependent, and individuals seem to change their direction as a response to local interactions with neighbors (Buhl et al. 2006). In experiments, the complexity of the collective motion is reduced to a pseudo-1-d setting by using a ring-shaped arena. Microscopic (Czirók et al. 1999) and macroscopic models (Yates et al. 2009; Hamann 2012, 2013a, b) of this behavior have been reported. Here, we use the microscopic model of self-propelled particles by Czirók et al. (Czirók et al. 1999) as our reference model (henceforth ‘Czirók model’).

The system is defined in 1-d space. A particle i has coordinate $x_\mathrm{i}\in [0,C)$ and dimensionless velocity $u_\mathrm{i}\in [-1,1]$. We refer to particles with velocity $u_\mathrm{i}<0$ as ‘left-goers’ (respectively, ‘right-goers’ for $u_\mathrm{i}>0$). The dynamics of a particle is defined by

$$\begin{aligned} x_\mathrm{i}(t+1) = x_i(t) +\mathrm{v} u_\mathrm{i}(t) \end{aligned}$$

(2)

where $\mathrm{v}$ is the nominal particle velocity and

$$\begin{aligned} u_\mathrm{i}(t+1) = G(\langle u(t)\rangle _\mathrm{i})+\xi _i \end{aligned}$$

(3)

considers the particle’s interaction with neighbors (subject to noise $\xi _\mathrm{i}$ uniformly distributed over $[-\eta /2,\eta /2]$). The local average velocity $\langle u(t)\rangle _\mathrm{i}$ for the ith particle is calculated over all neighbors located in the interval $[x_\mathrm{i}-\varDelta r,x_\mathrm{i}+\varDelta r]$ for perception range $\varDelta r$ (see Table 1 for the parameter settings). G describes both propulsion and friction forces

$$\begin{aligned} G(u) = {\left\{ \begin{array}{ll} (u+1)/2, &{} \text {for }u>0\\ (u-1)/2, &{} \text {for }u\leqslant 0 \end{array}\right. }. \end{aligned}$$

(4)

Table 1 Used parameters for the Czirók model

Equations 3 and 4 implement a variant of a local majority rule because each particle i aligns to the local average velocity $\langle u(t)\rangle _\mathrm{i}$. However, unlike the standard case in opinion dynamics, the contribution of each particle is weighted by its absolute velocity |u(t)| while the actual opinion is the sign of the velocity. The initial condition is a random uniform distribution for both the particles’ coordinates $x_\mathrm{i}\in [0,C)$ and their velocities $u_\mathrm{i}\in [-1,1]$. The number of particles is a constant that we call swarm size N. Throughout the paper, we prefer to use odd swarm sizes to avoid fluctuations at N / 2 (also see Table 1).

In the locust system, the spatial distribution of particles is biased and undergoes a nontrivial evolution. Next, we present already a measurement using the Czirók model to highlight these spatial distributions of particles which point to the dynamic neighborhood sizes and the main subject of this study. Figure 3 gives a simplified picture of the spatial correlations generated by the Czirók model in the form of the pair correlation function. In statistical physics, the pair correlation function (or radial distribution function) describes how the density of particles varies depending on the distance from a reference particle (this concept is also used later in Sect. 4.3.2). For a given left-goer ratio, we measure the density of left-goers as a function of the distance from a left-goer at times $t_1=30$ and $t_2=90$. We consider swarms with $N=41$ particles and system states with 25 left-goers and 16 right-goers only. The shown results are averaged over many independent runs. The two horizontal dashed lines give the expected distribution under the assumption of a uniform distribution of particles. Early in the simulation, at $t_1=30$, a left-goer has an increased density for nearby left-goers (within distances of about 2.6) in comparison with an assumed uniform distribution. Accordingly, right-goers have a decreased density for nearby right-goers due to symmetry. Later in the simulation, at $t_2=90$, left-goers have an increased density of nearby left-goers for even longer distances of up to about 6.0 and as a consequence a decreased density for the remaining arena (accordingly for right-goers). These spatial correlations in the particle distributions are discussed next, and we also study and interpret the temporal evolution of these correlations throughout the paper.

Fig. 3

Pair correlation function: measured density of left-/right-goers at distances from a particle of the same kind

3 Models

In this section, we describe the foundations and we define the tools underlying our mathematical modeling approach. We define two metrics, the probability of positive feedback events and the left-goer edge ratio. We present an experimental methodology to analyze the effects of biased spatial distributions in comparison with the canonical assumption of a well-mixed distribution of agents in the space. Next, we provide a Markov chain model capable to catch the dynamics of the locust system including spatial features. Using this Markov model, we show and explain what we call the fly-bottle effect and its correlations with both local (i.e., neighborhood size) and global (i.e., swarm size) density of agents in space. In addition, we present an urn model that is capable to qualitatively represent all the relevant spatial features. Finally, we give a mathematical model of the underlying feedback processes to indicate what can be done analytically.

3.1 Well-mixed and biased spatial distributions

In the following, we investigate the impact of biased spatial distributions of agents in the locust system. Often uniform distributions are assumed in models of collective systems, and we want to determine the difference in the swarm behavior between uniform and biased distributions. We model the collective decision-making process using Markov chains. A simple model for collective decision making with only one state variable was reported before (Hamann 2012, 2013b) and also above in Fig. 1. In the locust scenario, we count left-goers L (without loss of generality) and get a set of $N+1$ states: $\{0,1,\dots ,N\}$. As simplifying assumptions, we ignore that the system might stay within the current state (i.e., no self-loops) and that we might have changes in the left-goer number of more than one particle within a small time interval. By excluding self-loops, we only loose the capability to model temporal effects quantitatively while not influencing the qualitative behavior and steady states. Limiting the model to one state transition at a time has no major effects because we can always observe the system behavior on sufficiently small time intervals. Without loss of generality, we focus exclusively on transitions that are increasing the number of left-goers: $L\rightarrow L+1$. They occur with probability $P(L\rightarrow L+1)$ and due to the symmetry we have $P(L\rightarrow L+1)=1-P(L\rightarrow L-1)$ for $L\in \{1,2,\dots ,N-1\}$. These transition probabilities are easily measured for all system states L using the Czirók model. The initial agent positions are sampled from a random uniform distribution. Next, we simulate the evolution of the system according to the Czirók model for 2000 time steps. This time is sufficient for the system to exhibit spatial correlations characteristic of the Czirók model. The state transitions are measured and averaged over the whole time interval. The resulting values for all probabilities $P(L\rightarrow L+1)$ are shown in Fig. 4a (agent density $N/C=0.3$).

Fig. 4

Transition probabilities $P(L\rightarrow L+1)$ and left-goer edge ratio $\varepsilon$ using the Czirók model and two methods of initially positioning agents following a random uniform distribution or a special biased distribution($N=21$). a Czirók model, transition probabilities (average over time). b Czirók model, left-goer edge ratio (average over time). c Well-mixed variant of Czirók model, transition probabilities for different agent densities (average over one-time-step executions of the simulation). d Well-mixed variant of Czirók model, left-goer edge ratio (average over one-time-step executions of the simulation). e Bias variant of Czirók model, transition probabilities (average over one-time-step executions of the simulation). f Bias variant of Czirók model, left-goer edge ratio (average over one-time-step executions of the simulation)

An abstract model that only counts left-goers is not representing spatial features and therefore implicitly assumes for the agents a well-mixed distribution in space independent of their internal state (e.g., heading, opinion). However, swarm systems typically rely on spatial features and show non-homogeneous distributions of agents (Hamann 2010; Huepe et al. 2011). In the locust scenario, the first priority for the swarm is to achieve alignment, which is generally independent of agents’ positions. However, locusts seem to depend heavily on spatial features such as the number of neighbors (Hamann 2013a). In the following, we briefly investigate the difference between a well-mixed locust system and a locust system whose agents’ spatial distributions are biased by the time-dependent evolution of both positions and headings of agents. Our aim is to qualitatively analyze these differences and obtain insights into their origins. For the following experiment, we initially place the agents by sampling from a uniform distribution and calculate the updates in agent directions $u_\mathrm{i}$ according to the Czirók model. In contrast to our measurements presented in Fig. 4a, each simulation lasts for only one time step. In this way, we sample the system before its agent spatial distribution is affected by the Czirók model. Figure 4c shows the resulting transition probabilities for two agent densities ($N/C\in \{0.3, 1.0\}$) based on $2\times 10^5$ independent simulation samples each. We note that the density of agents influences the transition probabilities considerably. In addition, we note qualitative differences in the shapes of the curves compared to Fig. 4a.

Next, we define a measure capable to represent an important spatial feature, the left-goer edge ratio. The spatial distribution of agents induces a graph. The existence of an edge is simply determined by checking whether two agents are mutually within their perception range $\varDelta r$. At the beginning of the simulation, the induced graph corresponds to a (one-dimensional) random geometric graph. As time flows, the dynamics of the Czirók model bias the spatial distribution of agents. The set of agents with whom an agent shares an edge defines also its neighborhood, the size of this set is its neighborhood size, and the average neighborhood size is defined by (remember, $x_\mathrm{i}$ gives position of agent i)

$$\begin{aligned} \mathcal {N} = \frac{1}{N}\sum _{1\leqslant i \leqslant N}|\{1\leqslant j \leqslant N\text {: }|x_\mathrm{i}-x_\mathrm{j}|<\varDelta r\}|. \end{aligned}$$

(5)

To define our measure, we count ‘left-goer edges’ which are edges that connect at least one left-goer with another agent. The set of left-goer edges $E_L$ is defined by

$$\begin{aligned} E_L=\{e|e=(e_1,e_2)\text { with }e_1\text { and/or }e_2\text { is left-goer}\}. \end{aligned}$$

(6)

The definition of the set of right-goer edges $E_r$ is symmetrical. Our measure is the left-goer-edge ratio $\varepsilon$, which is calculated based on the set sizes:

$$\begin{aligned} \varepsilon =|E_\mathrm{L}|/(|E_\mathrm{L}|+|E_\mathrm{R}|). \end{aligned}$$

(7)

The edge ratio $\varepsilon \in [0,1]$ can be interpreted as an indicator of how the neighborhood sizes (i.e., node degrees) are distributed between left-goers and right-goers. If the neighborhood size averaged over all left-goers equals that averaged over all right-goers, then we have edge ratio $\varepsilon =0.5$. If the average neighborhood size of left-goers is bigger than that of right-goers, then we have edge ratio $\varepsilon >0.5$. If right-goer neighborhoods are bigger, then $\varepsilon <0.5$. We measure the edge ratio using the Czirók model by averaging over $2\times 10^5$ samples. Figure 4b shows the presence of bigger neighborhood sizes for left-goers in case of a global majority of left-goers ($L>N/2$, for swarm size $N=21$) and of smaller neighborhood sizes when left-goers are outnumbered ($L<N/2$). We do the same measurements for the well-mixed simulation as shown in Fig. 4d. In contrast to the Czirók model, the edge ratio scales linearly ($\varepsilon (L)=L/N$) for both the tested densities (see Fig. 4b). This result is in agreement with our expectations based on the well-mixed assumption. Hence, when we assume a well-mixed distribution, we ignore the correlations in space and time due to earlier dynamics of the locust system. We have shown the relevance of spatial effects in this system. This spatial effects are generated by positive feedback and establish a dependence on the system’s history which, in turn, influences the positive feedback itself.

Next, we investigate how the well-mixed distribution needs to be manipulated to obtain a similar spatial bias as in the locust system. The motivation is to better understand the relevant microscopic spatial features of the locust system. The aim is to gather information that will be useful in the definition of mathematical models, which represent relevant spatial features. We investigate how the well-mixed simulation can be modified to introduce a spatial bias that results in a nonlinear edge ratio $\varepsilon (L)$. We follow a simple constructive approach to influence the edge ratio: First, agents are positioned according to a uniform distribution; second, agents belonging to the current majority are paired to form clusters of two agents each. This is obtained by moving an agent of the current majority to the same position of a different agent of the current majority. Agents are initially positioned according to this procedure, and their directions $u_\mathrm{i}$ are updated for one time step. Averaging over many samples gives the resulting transition probabilities and edge ratios which are shown in Fig. 4e and 4f for two densities ($N/C\in \{0.3, 1.0\}$). The biased positioning of agents influences both the edge ratio and transition probabilities. The increased density from 0.3 to 1.0 almost only introduces a downscaling of the edge bias by a factor of about 0.45. Hence, we learn that the spatial bias of the locust system can be emulated by introducing a bias to their neighborhood. This finding is also in agreement with the measured pair correlation function shown in Fig. 3.

3.2 Markov chain model for two system variables

We extend the Markov chain model reported before (Hamann 2012, 2013b) and shown in Fig. 1 which relies on only one state variable, that is, it only counts the number of left-goers L. We consider as second state variable the average neighborhood size over all agents that we round to the nearest integer $\mathcal {N} \in \{1, \dots , N\}$. Figure 5 shows an example of the resulting chain for swarm size $N=3$. We get $(N+1)N$ states. For simplicity, we ignore again that the system might stay within the current state (no self-loops), that a concurrent change of both features might occur (no ‘diagonal’ transitions), and we also ignore that we might have changes in the left-goer number or neighborhood size of more than one within a small time interval (no transitions across several states). For any given state $(L,\mathcal {N})$, we measure the probability of observing a transition that increases/decreases the number of left-goers, $P(L\rightarrow L\pm 1|(L,\mathcal {N}))$, and the probability of observing a transition that increases/decreases the neighborhood size, $P(\mathcal {N}\rightarrow \mathcal {N}\pm 1|(L, \mathcal {N}))$. Throughout the paper, we reuse the concept that each system state of the locust system (or other collective decision-making systems) can be mapped onto this two-dimensional Markov chain and that the system’s dynamics is qualitatively well modeled by state transitions on this Markov chain.

Fig. 5

Markov chain for two state variables: number of left-goers L (say, horizontally) and the average neighborhood size $\mathcal {N}$ (say, vertically); swarm size $N=3$

In the following, we use the two-dimensional Markov chain model (i) to show and explain the origins of the fly-bottle effect and (ii) to highlight the correlation between the swarm size and the mean time to switch between lock-in states. The analysis of the Markov chain model is focused mostly on the computation of the asymptotic behavior of the collective decision-making process. However, due to the lack of self-loops in the chain, we obtain a periodic Markov chain of period two. This kind of Markov chains does not converge to a unique stationary distribution but repeatedly jumps between two stationary distributions: one for odd time steps and one for even time steps. Nonetheless, we can calculate a unique limiting distribution of the process by taking the mean of the two steady-state distributions of the chain. The analysis presented at the end of Sect. 4.1 is based on the computation of such limiting distributions.

3.3 Urn model

The idea of a Markov chain that depends on a pair of states $(L,\mathcal {N})$, namely the number of left-goers L and the average neighborhood size $\mathcal {N}$, provides a substrate for the following model. In addition, the considerations about the spatial bias discussed in Sect. 3.1 need to be integrated into one model.

We define an urn model that represents most of the relevant features of the locust system, especially those that are due to spatial biases. Our aim is to develop a model that is simpler and faster to simulate than the Czirók model but still represents the qualitative key features of this system. In the urn model, marbles represent agents and colors of marbles represent the states of the agents (here, left- and right-goers). The urn model consists of 3 urns: main, edges, and resource. Urn main represents the number of left- and right-goers in the swarm and contains a constant number of N marbles. Urn edges represents an average neighborhood and contains a variable number of marbles E. The number of marbles in edges represents the neighborhood size, and the ratio of left-goers within edges represents the edge ratio. Urn resource provides additional marbles to increase the neighborhood size E and therefore also holds a variable number of marbles. The underlying idea is that we want to model the increasing neighborhood size as observed in the locust system. The number of marbles in edges is allowed to increase and resource provides the required marbles. At the same time, the number of provided marbles in resource is limited which models the saturation effect in the increase in neighborhood sizes. At each round, the drawing process follows four stochastic rules. See Table 2 for used parameters. The parameters were chosen for good qualitative agreement with the Czirók model but without intensive parameter optimization.

Table 2 Used parameters for the urn model

Rule 1 We draw E times from edges with replacement (if E is even we do $E+1$ draws to avoid treatment of tie-breakers) and count the left-goers $\uplambda$ and right-goers $\rho$ that we draw. Next, we draw one marble from main. If $\uplambda > \rho$ and we have drawn a right-goer from main, then we put a left-goer back to main. If $\uplambda < \rho$ and we have drawn a left-goer from main, then we put a right-goer back to main. Otherwise, that is, $\uplambda < \rho$ and we have drawn a right-goer, we do not exchange the marble and put it back in main (accordingly for $\uplambda > \rho$ and left-goer). This first drawing rule represents the actual decision process of an agent based on counting neighboring agents and a majority rule.

Rule 2 This second drawing rule is executed at each round only with a probability of $P_\text {nsize}$. We draw E times from edges with replacement (if E is even we do $E+1$ draws) and count the left-goers $\uplambda$ and right-goers $\rho$ that we draw. Next, we do $\min (\uplambda ,\rho )+1$ random experiments: With probability $P_\text {incr}$, we move a left-goer or a right-goer (with equal probability) from resource to edges if possible. Finally, we do $E(\max (\uplambda ,\rho )/N-c_\text {decr})$ random experiments where $c_\text {decr}$ is a parameter to fine-tune the model. In each experiment, we first move with probability $P_\text {decr}$ a left-goer from edges to resource if possible. Then, we apply the same procedure for a right-goer. This rule models the dynamics of the neighborhood size. Big neighborhoods increase their size faster than small neighborhoods in situations in which the number of left- and right-goers is approximately the same. For unbalanced distributions, neighborhoods tend to decrease their size.

Rule 3 We draw one marble from main. If it is a left-goer, we replace a right-goer in edges with a left-goer (if possible) or vice versa in the case of a right-goer (positive feedback). This third drawing rule is executed in each round only with a probability of $P_\text {noise}$. The effect of this rule is to create a left-goer ratio in the urn edges similar to that in the urn main (in average replacements of marbles in edges follow the frequency of left-/right-goer draws from main which directly reflect the left-goer ratio in main).

Rule 4 We draw one marble from main. If it is a left-goer, we replace a left-goer in main with a right-goer (if possible) or vice versa in the case of a right-goer (negative feedback). This fourth drawing rule is executed in each round only with a probability of $P_\text {noise}$. These two last rules implement noise. They are executed with the same probability, but the positive feedback operates on edges and negative feedback operates on main.

Although these four drawing rules seem rather complex, they are simple to implement. This urn model is of low computational complexity and allows for a fast simulation of the locust system (e.g., in contrast to the Czirók model no distances between agents need to be checked). It is capable of simulating the spatial bias despite its simplicity. The Czirók model and the urn model are compared in Sect. 4.1.

3.4 Mathematical model of feedbacks

In the following, we analyze the feedback processes generated by the urn model and we relate the results of our analysis to those of previous works (Hamann 2012, 2013b). We follow the idea that, in the locust system, the time-variant behavior of positive feedback can be explained by the dynamics of neighborhood sizes. Hence, our aim is to find a causal relation between the dynamics of neighborhood sizes and the increase in positive feedback over time. We build on the approach of defining two different equations that model the change of the left-goer ratio $m=L/N$ over time. Specifically, one equation depends on the positive feedback probability $P_\mathrm{FB}$ (Hamann 2012, 2013b), while the other equation is independent. We then conclude the analysis by deriving an analytic expression for the positive feedback probability as a function of the neighborhood size.

We define a mathematical description of the above urn model. A detailed model would not allow for concise equations; therefore, we restrict our attention to the main features. We ignore the dynamics of urn edges except for the total number of marbles E which gives the average neighborhood size $\mathcal {N}$. Our main focus is to model the dynamics of urn main. We assume that the ratio of left-goers in the neighborhood (edges) is identical to the ratio of left-goers $m=L/N$ in main. This assumption implies a well-mixed system. Furthermore, we assume that $E=\mathcal {N}$ is odd. The dynamics of the urn model as defined by rule 1 is based on a majority rule for the draws from urn edges combined with a single draw from urn main. For $\mathcal {N}$ marbles, of which $m\mathcal {N}$ are left-goers and $(1-m)\mathcal {N}$ are right-goers, the probability to draw a majority of left-goers is

$$\begin{aligned} P_\text {maj}^\text {left}=\sum _{n\in \{\lceil \frac{\mathcal {N}}{2}\rceil ,\dots ,\mathcal {N}\}}\left( {\begin{array}{c}\mathcal {N}\\ n\end{array}}\right) m^n(1-m)^{\mathcal {N}-n} \end{aligned}$$

(8)

and the probability to draw a majority of right-goers is

$$\begin{aligned} P_\text {maj}^\text {right}=\sum _{n\in \{\lceil \frac{\mathcal {N}}{2}\rceil ,\dots ,\mathcal {N}\}}\left( {\begin{array}{c}\mathcal {N}\\ n\end{array}}\right) (1-m)^nm^{\mathcal {N}-n}. \end{aligned}$$

(9)

Following a heuristic approach, the average change $\varDelta m$ of left-goers within one time step is modeled as

$$\begin{aligned} \varDelta m^h(\mathcal {N},m)=(1-m)P_\text {maj}^\text {left}-mP_\text {maj}^\text {right}-P_\text {noise}(2m-1), \end{aligned}$$

(10)

whereas the first two terms model the positive feedback effect implemented by rule 1. An increase in the number of left-goers results from drawing a right-goer while having a majority of left-goers (and vice versa). The third term models the negative feedback effect of rule 4 (see Hamann et al. (2014) for details).

As a second alternative, we model the average change $\varDelta m$ of left-goers with a feedback-based approach as reported in (Hamann 2012, 2013b). That is, we neglect the actual processes causing positive and negative feedback in the urn model and we focus instead on the probability of positive feedback $P_\mathrm{FB}(\mathcal {N},m)$. We get

$$\begin{aligned} \varDelta m^\mathrm{FB}(\mathcal {N},m)=1-2\left( (1-P_\mathrm{FB}(\mathcal {N},m))P_\text {maj}^\text {left}+P_\mathrm{FB}(\mathcal {N},m)P_\text {maj}^\text {right}\right) . \end{aligned}$$

(11)

Now, we are in a position that allows us to define the probability of positive feedback as a function of the neighborhood size. This is achieved by equating and solving the right-hand sides of Eqs. 10 and 11 which yields

$$\begin{aligned} P_\mathrm{FB}(\mathcal {N},m)=-\left( 2m - 15P_\text {maj}^\text {left} + 5mP_\text {maj}^\text {left} + 5mP_\text {maj}^\text {right} + 4\right) \Bigg /\left( 10P_\text {maj}^\text {left} - 10P_\text {maj}^\text {right}\right) . \end{aligned}$$

(12)

With increasing neighborhood size $\mathcal {N}$, we obtain polynomials of increasing degree. For example, the first three polynomials are

$$\begin{aligned} P_\mathrm{FB}(\mathcal {N}=1,m)&=\frac{2}{5}, \end{aligned}$$

(13)

$$\begin{aligned} P_\mathrm{FB}(\mathcal {N}=3,m)&=\frac{3}{4} - \frac{7}{20(- 2m^2 + 2m + 1)}, \end{aligned}$$

(14)

$$\begin{aligned} P_\mathrm{FB}(\mathcal {N}=5,m)&=\frac{3}{4} - \frac{7}{20(6m^4 - 12m^3 + 4m^2 + 2m + 1)}. \end{aligned}$$

(15)

Figure 6 shows plots of Eq. 12 for $\mathcal {N}\in \{1,3,\dots ,27\}$. An exponential increase in positive feedback of the form $1-\exp (-\mathcal {N})$ with increasing neighborhood size $\mathcal {N}$ is clearly visible. Positive feedback gets more likely with increasing neighborhood size and independently from the current system state m. That means, the system is driven stronger to the two fixed points ($m\approx 0.15$ and $m\approx 0.85$) with increasing neighborhood size. A similar empirical result was reported in (Hamann 2013b, Fig. 8b) for a different swarm experiment showing temporal dependency. In the locust scenario, the neighborhood size also increases over time (see Section 4). Hence, the model given by Eq. 12 confirms the time-variant positive feedback in swarm systems as reported in (Hamann 2012, 2013b).

Fig. 6

Analytically obtained probabilities of positive feedback (Eq. 12) for neighborhood sizes $\mathcal {N}\in \{1,3,\dots ,27\}$

4 Results

In the following, we validate the urn model against simulations of the Czirók model. Our aim is to investigate whether the urn model is capable to reproduce the spatial bias that characterizes the locust system as well as other system features. We interpret the results of simulations using the two-dimensional Markov chain model introduced in Sect. 3.2. Additionally, we use a fitted Markov chain model to analyze the stability of lock-in states as a function of the size of the swarm by looking at the mean switching times between lock-in states. We report a result for another collective decision-making systems to show the potential for generality of this approach. Finally, we apply methods from renormalization group which allow us to provide novel perspectives on understanding the neighborhood size dynamics and the growing correlation lengths.

4.1 Urn model, edge bias, and neighborhood size

We investigate the Czirók model and the urn model with focus on the key findings that the average neighborhood size and the edge ratio are relevant features of the locust scenario. In particular, we investigate measured transition probabilities $P(L\rightarrow L\pm 1|(L,\mathcal {N}))$ and $P(\mathcal {N}\rightarrow \mathcal {N}\pm 1|(L, \mathcal {N}))$ by interpreting both models as Markov chains (Sect. 3.2). An overview of the complete system dynamics is given by vector fields in Fig. 7a, b for $N=41$ ($10^6$ samples for Czirók model and $5\times 10^6$ for urn model). These plots are based on the transition probabilities which are put in relation to each other. Furthermore, the horizontal and the vertical lengths of the arrows were normalized individually to maximize readability (i.e., vector field plots are qualitative; the quantitative data are given in Fig. 7c–f). In the case of the Czirók model, as a consequence of the initial random uniform distribution of agents over the whole ring, the neighborhood size $\mathcal {N}$ is initially small ($2\varDelta rN/C\approx 1.2$). Similarly, urn edges initially holds one left-goer and one right-goer. In the initial unordered state, there are approximately the same number of left-goers and right-goers ($L\approx N-L$). Hence, both systems start in the area at the lower middle of the vector field. First, the neighborhood size increases. Only later, once a bigger neighborhood size is formed, the system either increases or decreases in the number of left-goers L until reaching a stable state, respectively, $(L,\mathcal {N})\approx (35,8)$ or $(L,\mathcal {N})\approx (6,8)$.

Fig. 7

Vector fields, transition probabilities, and edge ratio for the Czirók and urn model ($N=41$, $10^6$ samples for Czirók model and $5\times 10^6$ for urn model). a Czirók model, vector field. b Urn model, vector field. c Czirók model, transition probabilities number of left-goers L (alignment). d Urn model, transition probabilities number of left-goers L (alignment). e Czirók model, transition probabilities neighborhood size $\mathcal {N}$. f Urn model, transition probabilities neighborhood size $\mathcal {N}$. g Czirók model, left-goer edge ratio $\varepsilon$. h Urn model, left-goer edge ratio $\varepsilon$

The vector fields depicted in Fig. 7a, b provide a clear picture of what we call the ‘fly-bottle effect.’ The swarm system is initialized with $L/N\approx 0.5$ and $\mathcal {N}<5$. At first, there is no positive feedback concerning the number of left-goers L (Fig. 7c, d) but the average neighborhood size $\mathcal {N}$ increases (in analogy to the fly bottle: ‘entering from below,’ Fig. 7e and f). Once $\mathcal {N}\approx 10$ or bigger, a strong positive feedback emerges that easily breaks the symmetry given by $L/N\approx 0.5$ and drives the system toward $L/N\approx 0.12$ or $L/N\approx 0.88$ (fly-bottle analogy: phototaxis behavior). For these values, however, there is negative feedback on $\mathcal {N}$ which decreases to $\mathcal {N}\approx 8$. Finally, positive and negative feedbacks balance out and the system converges to either $L/N\approx 0.15$ or $L/N\approx 0.85$ generating a lock-in effect (‘the fly is trapped’). This lock-in effect is only temporary because the positive feedback operating on L for $\mathcal {N}\approx 8$ is much weaker than that for $\mathcal {N}>8$ (cf. Fig 7c, thick line gives values for $\mathcal {N}=8$). As a consequence, when $\mathcal {N}\leqslant 8$ the system switches more frequently between a majority of left-goers ($L>20$) and a majority of right-goers ($L<20$). In contrast, when the neighborhood size is bigger ($\mathcal {N}> 8$), the system would transit from a symmetrical scenario with $L\approx 20$ to either $L\ll 20$ or $L\gg 20$ without switching between different majorities. In the long run, the system shows a switching behavior between the two lock-ins. However, such a change in majority becomes more infrequent with increasing swarm size N (see below) as also seen in natural locusts (Buhl et al. 2006). Projections of the data given in Fig. 7a, b are given in diagrams c–f.

Figure 7c, d shows the transition probabilities for an increase in L for all relevant values of the neighborhood size $\mathcal {N}$, respectively, for the Czirók and urn models. Another comparison is shown in Fig. 7e, f which give the transition probabilities for an increase in $\mathcal {N}$ for all relevant values of $\mathcal {N}$. Some curves are noisy because the corresponding configurations occur very rarely. We ignore statistical significance within this qualitative study (big quantitative differences between the two models are obvious). Positive feedback is found within approximately the same intervals in Fig. 7e, f (similarly for negative feedback). An extreme positive feedback in the Czirók model is noticeable in Fig. 7c, e. This can be seen in the interval $12<L<29$ of Fig. 7e, where transition probabilities toward bigger neighborhood sizes increase with increasing neighborhood sizes. In the intervals $6<L<18$ and $23<L<35$ of Fig. 7c, we can see that positive feedback boosts transition probabilities that push the system toward lock-in states. Figure 7g, h gives the left-goer edge ratio $\varepsilon$ for different times. The edge ratio of the urn model is more dynamic because the urn model is always started with one left-goer and one right-goer, that is, an edge ratio of $\varepsilon =0.5$. The initial edge ratio for the Czirók model, in turn, is the direct result of the uniform distribution of agents which gives $\varepsilon (L)=L/N$.

Finally, we investigate the effects of increasing the swarm size on the stability of lock-in states. We analyze the mean time $\tau _N$ necessary to move from a selected initial set of states with a majority of right-goers to a selected final set of states where left-goers are the majority in the system. In particular, these two sets approximately group all configurations of the locust system where positive and negative feedback balance each other, that is, they are close to one of the fixed points. We consider swarm systems whose transient dynamics have already vanished and thus settled down to their limiting behavior. We define the set of initial (respectively, final) states looking at the limiting distribution $P_{\infty }(L,\mathcal {N})$ of the process (computed from the Markov chain defined in Sect. 3.2 and shown in Fig. 8a). We select states with a majority of right-goers (respectively, left-goers) in descending order of probability up to an overall joint probability of the set of 0.1 (see patterned areas in Fig. 8a). This corresponds to a majority of right-goers where $L/N \approx 0.15$ and a majority of left-goers with $L/N \approx 0.85$, while $\mathcal {N} \in [5.8,14.2]$ for the urn model and $\mathcal {N} \in [4,10.6]$ for the Czirók model. To compute the mean switching time $\tau _N$, we first lump together all final states with majority of left-goers in a single state, and then, we make this state absorbing. We obtain in this way a Markov chain with a single absorbing state. An absorbing state is a state that, once entered, cannot be left by the Markov process (no outgoing transitions). The mean switching time of our original chain corresponds to the absorption time of a process in the modified chain that starts with an initial distribution proportional to the limiting probabilities of the initial states selected so far. Figure 8b shows the mean switching time $\tau _N$ when the swarm size N increases. The urn model’s qualitative behavior is similar to that of the Czirók model for all swarm sizes, with the latter experiencing shorter switching times. For both models, the mean switching time scales approximately exponentially with swarm size (notice the logarithmic scale of the horizontal axis in Fig. 8b), thus showing that bigger swarms form more stable majorities. Hence, the urn model preserves this important temporal feature of the Czirók model qualitatively.

Fig. 8

Illustrations of a limiting distribution $P_{\infty }(L,\mathcal {N})$ for the Czirók model, size $N=41$, patterned areas represent lock-in states; b mean first passage time $\tau _N$ over swarm size N for both models fitted to $a\exp (cx)x^b$, error bars give standard deviation (note logarithmic scale on vertical axis)

4.2 Generalization to another collective decision-making system

It seems a general phenomenon in swarm systems that negative feedback is initially predominant while positive feedback builds up only over time. The generality is supported by the following finding in an adaptive aggregation scenario.

The BEECLUST algorithm is a model algorithm for swarm aggregation. It is based on observations of young honeybees (Szopek et al. 2008, 2013). The behavioral model of these bees was transferred to a control algorithm for swarms of robots (Schmickl and Hamann 2011; Schmickl et al. 2008; Kernbach et al. 2009). The BEECLUST approach was analyzed in many models (Hereford 2011; Schmickl et al. 2009; Hamann et al. 2012, 2010; Bodi et al. 2011) and was also extended to be more efficient (Arvin et al. 2014, 2012). The BEECLUST algorithm controls a swarm to aggregate at a certain spot that is indicated by an environmental feature (e.g., temperature, light, and sound). If two options of equal utility are provided to the swarm, then it has to break this symmetry by collective decision making and aggregate only at one of the two options (Hamann et al. 2012). When driven by the BEECLUST algorithm, robots in the swarm repeatedly form clusters of aggregated robots. For the feedback processes, both the cluster size and the number of clusters seem important features. Small clusters tend to dissolve while big clusters tend to grow. In addition, the growth rate scales nonlinearly with the cluster size because, for example, robots in big clusters remain physically trapped by neighbors while in small clusters such geometrical constraints are unlikely to have an impact.

In our simulation, the swarm particles move in a rectangular arena, which has appropriate aggregation sites at both short sides. We separate the arena logically into two halves containing an aggregation site each. As the order parameter, we define the number of robots in the left half L without loss of generality. As the secondary feature, we choose the average neighborhood size $\mathcal {N}$ again, because it also gives an estimate of the average cluster size. For a small swarm of size $N=25$ that is successfully aggregating at one side, the measurements are shown in a vector field, see Fig. 9, similar to the measurements for in the Czirók model (Fig. 7a). Swarms initialized with a uniform distribution of positions have small neighborhood sizes and a balanced L (i.e., $L\approx N/2$). Initially, the neighborhood size increases as clusters start to form. However, negative feedback is still predominant and prevents the system to break the symmetry between the two aggregation spots, that is, $L=N/2$ is initially a stable fixed point. Later, the swarm achieves bigger neighborhood sizes ($\mathcal {N}>4$) and collectively decides for one side as positive feedback prevails over negative feedback. Although bigger clusters are more likely to persist than small clusters, a preferred neighborhood size of $\mathcal {N}=6$ is established. The dynamics described by the vector field in Fig. 9 resembles that of the locust system and, at some extent, supports our claims of generality concerning the fly-bottle effect.

Fig. 9

Vector field for the BEECLUST system, $2\times 10^6$ samples

4.3 Renormalization group theory, correlation length, and critical exponent

In the following, we discuss the potential of applying methods from renormalization group theory to the study of spatial dynamics in collective decision-making system. These methods provide, on the one hand, an additional point of view over the dynamics of neighborhood size which can interestingly be seen as a time-independent scale transformation dynamics inherent to majority decision-making processes. On the other hand, they allow to define and detect the structure formation and criticality of these systems depending on the measure of correlation lengths.

Renormalization group is a generally applicable method from physics (Fisher 1998). The leading idea is to view systems at different scales and to define transformations that map the system from scale to scale. Renormalization group can be seen as a divide-and-conquer approach to decrease a system’s degrees of freedom (Sornette 2006, p. 53) in a sequence of scale transformations. The underlying concept is that all (physical) systems are recursively defined on sub-systems of lower scale. It is a valid approach for situations where scale invariance and self-similarity are appropriate assumptions for the investigated system. Although renormalization group is mostly used in fields, such as particle physics, that are seemingly unrelated to systems relevant for swarm intelligence, there are also applications in closer fields, such as percolation and spin systems (Galam 1997). Sornette (2006, p. 291) even assigns to renormalization group potential for designing large-scale systems:

renormalization group can be thought of as a construction scheme or ‘bottom-up’ approach to the understanding and even to the design of large-scale hierarchical structures.

Similar to our approach, Galam (2000) applies methods of renormalization group to analyze a hierarchical decision-making system that is based on a local majority rule. However, in his case the scale transformation is used to model the explicit scale structure of the investigated system (voting in hierarchical structures). Here, we want to point to two ways of applying renormalization group to the analysis of the locust system in the context of dynamic neighborhood sizes. First, the dynamics of renormalization group for site percolation models shows similarities to the dynamics generated by majority rules in systems from swarm intelligence. Second, we apply methods of renormalization group to calculate critical exponents for the correlation lengths of the investigated locust system.

Next, we follow the example of applying renormalization group methods to a site percolation model by Sornette (2006, p. 299) because it has a direct connection to our locust system. The problem of site percolation is generally defined on a graph where each node has a certain probability p to be occupied. The question to answer is whether there is a path of occupied nodes that extends through the whole graph (spanning cluster). The different scales are defined recursively by grouping certain nodes in a set which forms supersites.

The above-mentioned sequence of scale transformations is based on the so-called renormalization group flow map $\varphi$, which is repeatedly applied to the transformed system feature x: $x'=\varphi (x)$, $x''=\varphi (x')$, etc. Renormalization group requires the discretization of space. Hence, one has to choose and define a lattice (triangular, square, pentagonal, etc.) which in turn defines static neighborhoods. In the case of percolation, the lattice cells are either occupied or unoccupied which is given by a probability p.

The next step is to define a flow map $\varphi$ that implements the scale transformation. The flow map has a crucial requirement as it has to preserve the key property under investigation. In the case of percolation, we are interested in spanning clusters (i.e., a path from occupied cells to neighboring occupied cells through the whole area). Our flow map needs to define a mapping $\varphi (p)=p'$ that gives the true probability $p'$ that a spanning cluster exists within the supersite (a supersite is the complement to a cell on the next scale level).

For site percolation on a triangular lattice, we can define supersites as composites of three cells. We have a spanning cluster either if all three cells are occupied or if two cells are occupied. Based on simple probability theory and combinatorics, we get

$$\begin{aligned} \varphi (p)=p'=p^3+3p^2(1-p). \end{aligned}$$

(16)

Writing it as change of p (i.e., $\varphi (p)=p+\varDelta p$), we get

$$\begin{aligned} \varDelta p=\varphi (p)-p=p^3+3p^2(1-p)-p. \end{aligned}$$

(17)

See Fig. 10 for plots of Eqs. 16 and 17. $\varphi (p)$ has three fixed points: unstable in $p=0.5$ and two stable points for $p=0$ and $p=1$. Therefore, the interpretation of the iterative scale transformation process is that for larger scales the lattice gets either sparser (toward $p=0$) or denser (toward $p=1$). Similar results with polynomials of higher degrees are obtained for square and pentagonal lattices, etc.

Fig. 10

Plots of flow maps, a site percolation on a triangular lattice (Eq. 16) and b flow map as change in p (Eq. 17)

4.3.1 Collective decision making as scale transformation

The connection between renormalization group and the locust system is the possibility to decrease the system’s degrees of freedom by grouping agents in clusters. On the next higher scale, these clusters are treated as if they were single agents. The idea is to group the agents usefully such that clusters of agents form an analogy to supersites. On the next scale, we ignore a number of details, such as distances between agents or noise, because we are averaging agent properties over spatial intervals. Self-similarity is achieved by treating clusters as if they were agents and by ignoring effects of noise.

A difference between the locust system and site percolation is that the topology matters in site percolation because it is defined on paths. In contrast, the topology is irrelevant for the locust system once the considered agents are mutually within perception range. This difference between these two systems is, however, meaningless in the following because the scale transformations for site percolation are typically defined in a way that allows to ignore complex considerations about the underlying topology. Hence, the two systems can be accessed via the same combinatorial approach, which is shown in the following.

In the case of the locust system, an agent is either a left-goer or a right-goer with the current ratio or probability $p=L/N$ and $1-p=1-L/N$, respectively. The flow map implements the majority decision, that is, we calculate the probability $p'$ of having a left-goer majority in the considered agent cluster with left-goer ratio p. If we consider a cluster size of $\mathcal {N}=3$, then we get Eq. 16 which is identical to Eq. 8. For the change of p, we get Eq.17 which gives a curve that corresponds to our measurements shown in Figs. 4a and 7c but for a noise-free, absorbing system ($\varDelta p=0$ for $p=0$ and $p=1$, see Fig. 10b). This allows for an intriguing interpretation of the locust system as a dynamic scale transformation system. The idea is to abstract away time and to substitute it with a stepwise scale transformation. This approach is in line with another interpretation of renormalization group by Sornette (2006, p. 287): ‘renormalization group is nothing but a kind of dynamical system in which time is replaced by scale.’ Our interpretation here is that the flow map for percolation systems implements actually a majority decision rule. Hence, the dynamics in scales of the iterative scale transformation and the dynamics in time of our locust system show interesting similarities. In fact, they share their primary interpretation that the pressure toward the two extremes ($p=0$ and $p=1$) is increased with increasing number of neighbors (in the case of renormalization group, one can compare triangular lattices to square lattices, square lattices to pentagonal lattices, etc.) and that the system considerably depends on neighborhood sizes, which is also the major statement of this paper.

4.3.2 Critical exponents and correlation length in collective decision making

In physics, the theory of critical phenomena investigates systems that approach ‘a state at which the scale of correlations becomes unbounded’ (Amit 1984). A key insight of this theory is that certain thermodynamic quantities across a number of different systems (e.g., solid-state magnetism and percolation) diverge following power laws. The corresponding critical exponents are determined, for example, by methods from renormalization group theory and allow to compare properties of different systems. The definition of a critical temperature $T_c$ is common which defines the boundary between an unordered ($T>T_\mathrm{c}$) and an ordered phase ($T<T_\mathrm{c}$).

In the following, we make use of the concept of correlation lengths from statistical physics. It is based on the definition of statistical correlations between random variables X. A pair correlation function $\gamma$ gives the correlation between spatially separated system features depending on a distance r and a considered position R

$$\begin{aligned} \gamma (r) = \text {corr}(X(R),X(R+r)). \end{aligned}$$

(18)

For many relevant systems, the correlation function can be approximated by

$$\begin{aligned} \gamma (r) \approx c_1+c_0\exp (-r/\xi ), \end{aligned}$$

(19)

for constants $c_0$, $c_1$ and correlation length scale $\xi$ that normalizes the distance r. Using the critical temperature, the corresponding power law for correlation length $\xi$ and critical exponent $\nu$ is defined by $\xi \propto |T-T_\text {c}|^{-\nu }$, that is, the correlation length $\xi$ is proportional to the power of the temperature difference (the ‘distance’ to the critical temperature).

In most physical systems investigated with methods from renormalization group, the topology is static or it is at least a valid simplification to assume a static topology. Examples are bond percolation (Young and Stinchcombe 1975) and the Ising model (Kadanoff 1966). In statistical mechanics, the correlation function is typically defined either directly on a regular lattice or, in the case of real space, on a regular lattice that is introduced as a modeling assumption. For the latter case, note a statement by Sornette (2006, p. 299): ‘there is no unique prescription for renormalizing in real space and a considerable number of approximate renormalization techniques have been developed, with varying degrees of success.’ Also for the real-space case, a static topology and homogeneous densities are assumed. The locust system, however, has inhomogeneous, dynamic densities and a dynamic topology in real space. Hence, we have to test different methods that are able to deal with dynamic topologies.

Similarly to renormalization approaches in real space, we have defined and tested a number of techniques to address the dynamic topologies. Three definitions of defining and measuring a correlation function were tested: real distances,³ hop-counts as distances (i.e., minimal number of required agents serving as relay stations for a supposed multi-hop communication), and lattices based on perception range (i.e., coarse-grained histogram in steps of multiples of perception ranges r, 2r, 3r, etc.). The coarse-grained histogram gave best results.

An example of measured correlations in the Czirók model is given in Fig. 11a (swarm size $N=351$, system state $L=57$, $10^6$ samples). We measure the correlation $\gamma$ between agent states (depending on particle velocity which is classified in $u\leqslant 0$ and $u>0$) and the distances r between them following Eq. 18 (agent states define the random variable X). A correlation function $\gamma$ is fitted following Eq. 19 and gives a correlation length of $\xi \approx 5.2$. However, finite-size effects of the ring-topology in the Czirók model introduce artifacts such that the functions of the form $\exp (-x)$ are not always easily fitted. These finite-size effects are reflected in the plots of the correlation length $\xi$ as shown in Fig. 11b for different swarm sizes (e.g., increased correlation length for $L/N=0.5$, local optimum for $L/N=0.175$ for $N=351$). In addition, rather big swarm sizes ($N>100$) are required to obtain exploitable data. The correlation length diverges for the critical system states $L/N\approx 0.15$ and $L/N\approx 0.85$ as expected (cf. $P(L\rightarrow L+1)=0.5$ in Fig. 7c). Hence, we can define, as analogy, two critical temperatures $T_c^1\approx 0.15$ and, in full symmetry, $T_c^2\approx 0.85$. For $T_c^1\approx 0.15$ and $T=L/N<0.5$, we find by fitting a critical exponent of $\nu \approx 0.49$ for the power law $\xi \propto |T-T_\text {c}|^{-\nu }$.

Fig. 11

Measured correlations in the Czirók model, fitted correlation function $\gamma$, and correlation length $\xi$ over left-goer ratio L / N ($10^6$ samples). a Fitted correlation function, swarm size $N = 351$, system state $L/N = 57/351 \approx 0.16$. b Correlation length $\xi$ over left-goer ratio L / N for swarm sizes $N \in \{101, 151, 251, 351\}$

These two critical points correspond to the left-goer ratios of the lock-in states. The critical exponent is an alternative method to the left-goer edge ratio that describes the influence of not-well-mixed agent distributions and the emerging correlations between agent positions and agent states. In particular, it gives a mathematically accessible representation of the qualitative difference between lock-in states and any other states.

5 Discussion and conclusion

This paper started from the finding of earlier publications (Hamann 2012, 2013b) that, in swarm systems, positive feedback builds up in a transient phase independently of the order parameter (here L) until maximal positive feedback is reached. The independence of this phenomenon from the order parameter indicates the existence of a second feature that controls the increase in positive feedback. In the case of the locust system, we identify the average size of agents’ neighborhoods as this second feature and, in addition, we detect the relevance of other spatial features such as the correlation length and the edge ratio. We extended the Markov chain approach introduced in (Hamann 2012, 2013b) to model the second state variable and therefore to count both left-goers (order parameter) and average neighborhood size (secondary feature). Although it was necessary to consider the original spatial features of the locust scenario, we extended the urn model concept (Hamann 2012, 2013b) to emulate spatiality, particularly, neighborhood size and edge ratio.

What we call the fly-bottle effect was introduced to describe the general dynamics in these two-dimensional models. The fly-bottle effect relies on a second feature that serves as a kick starter for the whole system by initiating short-range correlations first which can then be leveraged to increase the overall order in the system. The fly-bottle effect seems to have a certain generality in swarm systems. Indeed, the increase in positive feedback during a transient phase was also reported for other systems such as density classification and aggregation controlled by BEECLUST (Hamann 2012, 2013b). For the BEECLUST system, we have shown the respective vector field for neighborhood size as second feature. Indeed, it shows qualitatively similar dynamics as in the locust system.

An additional interpretation of the fly-bottle effect with reference to Fig. 3 is that the secondary feature is generating only short-ranged correlations early on but not global correlations. These short-ranged correlations seem to be side-effects, such as small clusters of agents in the investigated locust scenario. The long-range correlations seen later in the system are then an effect of the primary feature (here L) and probably could neither be generated by the one or the other feature alone. The qualitative difference between system states of low order (for the locust system: $0.25<L<0.75$) and of high order (for the locust system: $L<0.25$, $L>0.75$) is also proven by the measured correlation length using methods of renormalization group.

The similarities between a renormalization group approach to percolation and collective decision-making systems based on a local majority rule point to general concepts that are also contained in the fly-bottle effect. While the fly-bottle effect focuses on the temporal dynamics, the scale transformation of the percolation system establishes a time-independent hierarchy. On lower scales, small clusters of opinions are formed that help to establish order on higher scales by merging small clusters into bigger clusters. The influence of bigger neighborhood sizes can also be interpreted in the framework of renormalization group by comparing lattices of different node degrees (triangular, square, pentagonal, etc.).

Future research work will focus on the questions whether the fly-bottle effect is generally observed in swarm systems and, if so, whether it can be used to design swarm behaviors for artificial swarm systems.