1 Introduction

Symmetry breaking in collective decisions is the phenomenon in which a system has at least two options to choose, which are all of equal value, and the system chooses one of them with a significant majority. The term “symmetry breaking” itself originates from physics. It describes the significant influence of fluctuations acting on a system and deciding which branch of a bifurcation the system takes (i.e., into which basin of attraction the system gets by fluctuations). In general, it transforms rather unordered system states into ordered states (e.g., spontaneous magnetization [1]). It is a complex phenomenon of extensive importance in a vast variety of fields. Symmetry breaking (in quantum mechanics) can be seen as an important example of emergent phenomena [2] and can even be seen as the origin of information [3].

The above notion of symmetry breaking also applies to other fields such as morphogenesis [4] or the behavior of multi-agent systems (MAS). In contrast to physical systems, MAS consist of agents that are autonomous in their decisions and in their energy supply (self-propelled). An example is pedestrian models, where symmetry breaking is detected as the formation of lanes or oscillations at narrow passages [5]. In this work we focus on swarm intelligence, especially, on social insects and swarm robotics.

In particular, we investigate symmetry breaking in aggregation processes. Aggregation behaviors of insects, as an example of simple natural swarm behavior, were frequently a subject of empirical research. Aggregation processes were investigated in several species, for example: bark beetles [6], ants [7, 8], cockroaches [7, 9–12], and honeybees [13, 14]. Some of these insects navigate by exploiting a gradient of odor [7], a gradient of population density [15], or by exploiting agent–agent encounters and a temperature gradient [14, 16].

A scenario that goes beyond mere aggregation is, for example, house-hunting in social insects. In addition to the mere task of aggregation without any preference for certain locations, the insects also have to choose an appropriate hive/nest site [17–19]. If two (or more) potential sites of equal utility exist, the swarm has to break this symmetry of the environment to prevent splitting the colony [20].

Explicit investigations of symmetry breaking in social insects include several works on y- and double bridge experiments with ants [21–23] and with social spiders [24]. The focus in these works is on decision processes showing symmetry breaking with binary choices (left branch vs. right branch). Symmetry breaking with several but discrete choices (sources, shelters) was investigated in foraging honeybees [25] and cockroaches [9, 10].

Furthermore, there are several studies elaborating on macroscopic models that describe collective decision making and symmetry breaking in social insects. For example, models of y-bridge experiments with ants [26–28] or aggregation behavior in cockroaches [9]. In all these works, the investigated insects operate on pheromones and take discrete decisions between several sources or shelters. A model of clustering of corpses in ant colonies is reported in [8]; a scenario, that is closer to the one proposed in this work due to the infinite number of possible choices (positions of potential corpse clusters). All these models are specialized for the respective scenarios. In this paper, we propose a generalized model of symmetry breaking in collective decision making.

Due to its generality, our model is also applicable to swarm robotics. The literature about aggregation experiments with robots is sparser compared to the number of studies about aggregation in biology. This is most likely due to the availability of global communication in standard robotic approaches that allow an easy implementation of aggregation behaviors. In nature-inspired minimalist swarm robotics [28] only local communication is available or allowed making aggregation a much harder task. Two approaches are distinguished: nature-inspired control algorithms [14, 16, 29, 30] and nature-mimicking applications of swarm robotics [31, 32]. Some of these robots navigate by exploiting agent–agent encounters and a temperature gradient [16, 30]. An explicit investigation of symmetry breaking in swarm robots does not seem to exist.

In addition to the above-mentioned studies with either insects or robots, aggregation experiments with heterogeneous swarms consisting of insects (cockroaches) and robots were reported in [12].

The purpose of this paper is two-folded. On the one hand, we want to analyze the behavior of young honeybees and an implementation of this behavior on swarm robots. Symmetry breaking is a good benchmark for these studies. On the other hand, we want to identify general properties of symmetry breaking in MAS independent of the underlying processes such as agent–agent interactions or mass recruitment.

In our own work, we have investigated the aggregation behavior of young honeybees (see Fig. 1) that search for areas of optimal temperature in the brood nest [14, 16]. Whether symmetry breaking can be observed in this behavior is an open question and is currently investigated in our lab. One aim of the work at hand is to lead to testable hypotheses of possible behavior models and parameters concerning the behavior of young honeybees. In reference to behavior models, symmetry breaking is a good benchmark to test their validity. In addition, we want to design a model that is able to give a measure of symmetry breaking ability and that might even predict the (possibly long-term) symmetry breaking behavior based on measurable quantities of the observed systems.

Fig. 1
figure 1

Infrared camera images of young honeybees in a temperature gradient. The areas below the heat lamps (left and right side) have about 36°C while the middle has about 32°C

Full size image

In previous works, we have developed a control algorithm for swarm robots based on the behavior models of young honeybees [14, 16]. The analysis reported in this paper also contributes insights that are applicable to swarms of robots. The general concept of this paper is to identify macroscopic and measurable quantities that can be used to model symmetry breaking in collective decisions in any kind of MAS.

By symmetry breaking, the system (e.g., swarm) focuses on one option (e.g., food source) and reaches a consensus. Typical explanations of this behavior are, for example: A single ant pheromone trail is easier to defend than two simultaneous trails; the exploitation of a single source is more efficient than the parallel exploitation of two sources (e.g., removal of obstacles); clusters of big sizes are important for the effectivity of successive collective tasks. Hence, the investigation of symmetry breaking might result in insights, that allow us to design more efficient artificial swarm systems, as well as in a better understanding of this emergent phenomenon.

Here, we investigate the ability of a MAS (which is also called ‘swarm’ in the following) moving in continuous space (simulated in floating point arithmetic) to break the symmetry imposed by the environment. The feature of symmetry breaking is not explicitly programmed into the agents; hence, we call it emergent symmetry breaking. We elaborate on the following questions: Why is the MAS able to break the symmetry? What are the key features for the effectivity of symmetry breaking in this MAS? On which parameters of the algorithm does it depend? What is the connection between the ability of the MAS to break symmetries and the ability to stay flexible in a dynamic environment?

2 Definitions and description of the scenario

In this section we define the phenomenon of symmetry breaking and several measures that allow to quantitatively compare systems concerning their symmetry breaking behavior. In addition, we give a detailed description of the investigated scenario.

2.1 Symmetry breaking

In order to clarify our understanding of symmetry breaking in the context of MAS, we define it formally:

Symmetry breaking: Say there are two possible options the swarm of agents can choose from: A and B (e.g., food sources). Both options are equal in their utility, reward, quality, etc. (e.g., quality and quantity of food). We say, a MAS with N agents shows symmetry breaking, if a significant majority M of the swarm (i.e., M ≥ (1 − δ)N of the agents, for a tolerance of 0 ≤ δ ≪ 0.5) chooses collectively either A or B, and this decision is not final and might be time-variant even though such a revision of the decision is unlikely.

In other words, the system shows symmetry breaking, if the agents reach a stable consensus that is revised only rarely (e.g., in a setting investigated in this paper we observed less than 1% revisions, see Sect. 3.1). This definition of symmetry breaking could also be called ‘weak symmetry breaking’ in contrast to a ‘strong symmetry breaking’ which is a time-invariant 100% decision (δ = 0). While breaking the symmetry, the MAS is still allowed to permanently explore the environment, which is the sine qua non for a MAS to be flexible and to change its behavior in case of a dynamical environment. For example, if the MAS chooses option A but after a while B becomes better than A, we would like to see the MAS to abandon A and to choose B (for example, cf. [26, 33]).

The question of which value should be chosen for the tolerance δ and a clearer definition of what is meant by “rare revisions” has to stay unanswered in the general case. Writing down a certain value independent of an application would be of little help because this decision is comparable to choosing a confidence interval. The actual value depends on the desired intensity of the symmetry breaking (i.e., the observer’s choice of what is considered a correct symmetry breaking), on the investigated scenario (e.g., variance in the behavior), and on the swarm size (that defines the granularity of the symmetry measure).

2.2 Investigated scenario: collision-based adaptive aggregation

We investigate a homogeneous MAS. The agents (or robots) move in 2-d space of rectangular shape (hereinafter referred to as arena) surrounded by a wall because we followed our previous experimental settings [ 30, 34]. They are equipped with sensors for distance measurements (e.g., based on IR) as well as a sensor that allows them to measure a special inhomogeneous property of the arena (e.g., light or temperature, hereinafter referred to as luminance distribution, see Fig. 3a). In addition, the agents are able to identify other agents as such (e.g., using their IR-sensors). The general task of the MAS is to aggregate at the brightest spot in the arena. To achieve this, all agents are controlled by the identical algorithm, which is called BEECLUST. It is inspired by the behavior of young honeybees, that typically aggregate at areas of a certain temperature, and was reported before [16, 30, 35, 36].

For the number of perceived neighbors necessary for a stop called stop threshold \(\sigma\in {\mathbb N}_1\) (in previous works we always set σ = 1) the algorithm BEECLUST is defined by:

  1. 1.

    Each agent moves straight until it perceives an obstacle \(\Upomega\) within sensor range.

  2. 2.

    If \(\Upomega\) is a wall, the agent turns away and continues with step 1.

  3. 3.

    If \(\Upomega\) is another agent, the agent counts the number of agents K it perceives. If K ≥ σ the agent measures the local luminance. The higher the luminance the longer the agent stays stopped. After the waiting has elapsed, the agent turns away from the other agent and continues with step 1.

The waiting time is determined by the local luminance: The occurring luminances on the interval [0lux, 1600lux] are linearly mapped to sensor values e ∈ [0, 180] (this definition is based on our experiments with real robots). The parameter w max is the maximum waiting time. The following equation is used to map the sensor values e to waiting times (for details see [30, 36]):

$$ w(e) = {{w_{\rm max}e^2}\over {e^2 + \theta}}, $$
(1)

where θ is an offset that was used to adapt Eq. 1 to the sensors of the robots [36, 16]. A plot of this function is shown in Fig. 2.

Fig. 2
figure 2

Waiting time in time steps depending on the local luminance that is linearly mapped on the interval [0, 180] of sensor values and then mapped according to Eq. 1

Full size image

The collective aggregation at the brightest spot is achieved via a positive feedback process: Clusters of σ + 1 stopped agents will form by chance anywhere in the arena. Agents in clusters at brighter spots have longer waiting times. These clusters will exist longer than clusters at darker spots. Hence, the chance of growing into a cluster of size σ + 2 is bigger for clusters at brighter spots. The area covered by clusters grows with the number of contained agents and clusters covering a bigger area are more likely to be approached by chance by moving agents. Hence, bigger clusters will grow faster. This process, typically, leads to just one big cluster at a rather bright spot as seen in Fig. 3b.

Fig. 3
figure 3

Luminance distribution and agent positions and trajectories a Luminance distribution in the arena. b positions of stopped agents (circles) and moving agents (triangles) with trajectories of the last 30 time steps, stopthreshold σ = 2, contours show luminance levels

Full size image

In contrast to previous works (e.g., see [16, 36]), we use a simple first-order geometric simulation with ‘continuous’ space (floating point arithmetic) and discrete time to investigate the MAS. The following simplifications were accepted as necessities to reduce the (particularly computational) complexity: Agents have no spatial extent and cannot collide, and the agents are simply reflected at walls (angle of incidence equals angle of reflection). The implemented noise model for the agent–agent recognition is very simple: Based on a predefined recognition probability γ, the success of a recognition process is probabilistic and uncorrelated in time. Note that the relation between the recognition probability and the velocity, which is kept constant in this work (see Table 1), define a ‘recognition success rate’.

Table 1 Used parameter setting in this work
Full size table

Initially, the agents have random headings, are in the state ‘moving’, and are random uniformly distributed in the whole arena (i.e., in average we have initially the same number of robots in the left as in the right half of the arena). The luminance distribution is bimodal with maxima of the exact same value and shape (see Fig. 3a) because we want to investigate the symmetry breaking behavior of the MAS between these two options (except for the experiment with a dynamic environment presented below). See Table 1 for the standard parameters used. A typical situation during a simulation run is shown for σ = 2 in Fig. 3b. A total of 19 agents (circles) have already formed a single cluster with a certain distance to the optimal spot while six others (triangles, two within the cluster) are still moving.

2.3 Symmetry measures

In the following, we need a measure of symmetry to investigate the chosen scenario. Two areas (one left and one right) of identical utility are provided to the agents. The first approach is clear: As there are two areas, we relate (directly or indirectly) the number of agents at one side to those at the other side. However, the agents have two states: stopped or moving. This allows the definition of state-dependent measures of symmetry. In this work, we focus on three measures.

As a first measure of symmetry we introduce a symmetry measure s all(t) that is state-independent. We call it state-independent symmetry measure. It is determined by identifying the number L all(t) of agents of any state at the left half of the arena (w.l.o.g.) and dividing it by the overall number of agents N. We get

$$ s_{\rm all}(t)=L_{\rm all}(t)/N. $$
(2)

Note the identity L all(t)/N = 1 − (R all(t)/N) due to state-independence (for R all(t) is the number of agents of any state at the right side). Total symmetry is indicated by s all = 0.5. Strong symmetry breaking is indicated by either ∀t > t 0:s all(t) = 0 or ∀t > t 0: s all(t) = 1. Weak symmetry breaking is indicated by values of s all(t) (mainly) oscillating either within 0 ≤ s all < δ or within 1 − δ < s all ≤ 1.

As we want to investigate the relevance of the two agent states to the symmetry breaking behavior, we introduce a second measure that is state-dependent and that is based on numbers of stopped agents only. We call it state-dependent symmetry measure. It is analog to the state-independent symmetry measure and is determined by the number L stop(t) of stopped agents at the left half of the arena (w.l.o.g.) divided by the overall number of stopped agents N stop(t):

$$ s_{\rm stop}(t)=\left\{ \begin{array}{ll} L_{\rm stop}(t)/N_{\rm stop}(t),& \hbox {if } N_{\rm stop}(t)\ne 0\\ \hbox {undefined},& \hbox {else}. \end{array} \right. $$
(3)

For N stop(t) = 0 this measure is not applicable.

The third measure we introduce is also state-dependent but involves also the overall number of agents in the arena. The idea is to have a measure that is, on the one hand, focused on the stopped agents, but that is, on the other hand, also scaled according to the fraction of stopped agents. Perfect symmetry breaking with low numbers of stopped agents is of less relevance compared to weaker symmetry breaking with high numbers of stopped agents. We call it scaled symmetry measure. The idea is to represent symmetry breaking in the stopped agents. This state-dependent symmetry measure is determined by:

  1. 1.

    identifying the number L stop(t) of stopped agents at the left half of the arena (w.l.o.g.),

  2. 2.

    dividing it by the overall number of stopped agents N stop(t),

  3. 3.

    mapping this intermediate result onto the interval [0, 1], where small values indicate low symmetry breaking,

  4. 4.

    and multiplying it by the fraction of stopped agents N stop(t)/N.

This is summarized by

$$ s_{\rm scaled}(t)=\left\{ \begin{array}{ll} 2\left|0.5-{{L_{\rm stop}(t)}\over {N_{\rm stop}(t)}}\right|{{N_{\rm stop}(t)}\over {N}},& \hbox {if}\, N_{\rm stop}(t)\ne 0\\ 0,& \hbox {else} \end{array} \right. $$
(4)

In addition, we use the median \(\tilde{s}_{\rm scaled}(t)\) of several sample runs of the simulation.

3 Observed behavior and analysis

3.1 Effectivity of symmetry breaking

In this work, we focus on the influence of the stop threshold σ on the ability of the MAS to break the symmetry. In a single simulation run we determine the evolution of the symmetry measure s all(t). See Fig. 4 for three samples (cf. similar figures in [9]). In reference to our definition of symmetry breaking and after observing the typical behavior of this system, a tolerance of about δ = 0.25 (which is in principle arbitrary) would introduce a reasonable discrimination between successful and unsuccessful symmetry breaking. Hence, we observe symmetry breaking for t > 125 for the upper and the lower curve while the middle curve would not represent symmetry breaking. In order to get statistically significant data, we sample such evolutions of s all(t) over many simulation runs and create histograms with N + 1 bins (s all(t) = 0/N, s all(t) = 1/N, etc.) for every 25th time step. The result is a sampled probability density of s all(t). See Fig. 5 for sampled probability densities with stop thresholds σ ∈ {1, 2, 3, 4} and agent–agent recognition probabilities γ ∈ {1.0, 0.7, 0.4, 0.2} for 500 time steps. Concerning symmetry breaking, the best result of the investigated parameter settings is achieved by setting agent–agent recognition γ = 1 and σ = 2 followed by σ = 3. Within this time period (t ≤ 500) no symmetry breaking is observed for σ = 1 and for σ = 4.

Fig. 4
figure 4

Evolution of the state-independent symmetry measure s all(t) for three samples (σ = 2)

Full size image
Fig. 5
figure 5

Measured probability density of the symmetry measure s all(t) for four stop thresholds σ ∈ {1, 2, 3, 4} (rows) and four different robot recognition probabilities γ ∈ {1.0, 0.7, 0.4, 0.2} (columns), 2 × 103 samples each, dark areas indicate low density

Full size image

For σ = 2 and σ = 3 the influence of the recognition probability γ is recognized. Symmetry breaking is handicapped, is achieved slower (if at all), and smaller majorities are achieved (for σ = 2 and γ = 0.7: high densities for values 0.04 < s all < 0.25 and 0.75 < s all < 0.96; for γ = 0.4: high densities for values 0.08 < s all < 0.28 and 0.72 < s all < 0.92), see Fig. 5e through Fig. 5g.

After having reached either s all(t 1) = 1 or s all(t 1) = 0 for time 0 < t 1 < 500, the MAS revised its decision (i.e., s all(t 2) < 0.5 or s all(t 2) > 0.5, respectively, for time t 1 < t 2 < 500) only in less than 1% of the cases (data not shown). This behavior agrees with our definition of symmetry breaking (a revision of the decision is unlikely).

The evolution of the median of the scaled state-dependent measure \(\tilde{s}_{\rm scaled}\) depending on the agent recognition probability γ for σ = 2 is shown in Fig. 6. The system shows little sensitivity to changes in the agent recognition probabilities for γ > 0.5. However, there is a clear breakdown at about γ = 0.225.

Fig. 6
figure 6

Evolution of the median of the scaled state-dependent measure \(\tilde{s}_{\rm scaled}\) depending on the agent recognition probability γ for σ = 2. Values close to 1 indicate high ability for symmetry breaking, values close to 0 indicate no ability for symmetry breaking. From top to bottom the values are: γ ∈ {1, 0.5, 0.3, 0.25, 0.225, 0.2}, 200 samples each, error-bars show 1st and 3rd quartiles

Full size image

In Fig. 7 we give histograms for the state-dependent symmetry measure s stop(t) for t = 500 (cf. similar histograms in [9]). The frequencies in Fig. 7 vary because in some final states of the MAS no agent was stopped, in which case s stop is not applicable according to Eq. 3. Hence, the histogram for σ = 3 (Fig. 7c) contains only 1,964 samples and the histogram for σ = 4 (Fig. 7d) only 129.

Fig. 7
figure 7

Histograms of the state-dependent symmetry measure s stop(t) for γ = 1 (2 × 103 samples)

Full size image

The most striking difference compared to Fig. 5 is that almost only the two extreme bins s stop(t) = 0 and s stop(t) = 1 are occupied for σ = {2, 3, 4}. For these cases, clusters form almost always at one side exclusively. In addition, the situation is slightly different in case of σ = 2 and σ = 3 since the histogram for σ = 3 shows higher frequencies in the outermost bins. Using the state-dependent symmetry measure, σ = 3 seems to show a slightly better symmetry breaking behavior.

We did longer simulation runs as well to test whether the stop threshold σ only influences the length of the transient and not the general ability of breaking the symmetry. The results are shown in Fig. 8. A fast and definite symmetry breaking is observed for σ ∈ {2, 3} already after t = 5 × 103 and t = 1 × 104 time steps, respectively. For σ = 4, a strong tendency toward symmetry breaking seems to be reached after many iterations (t = 7 × 104). For σ = 1, even after that many iterations a clear symmetry breaking is not observed. In Fig. 8a, the summation of the frequencies for 0.25 < s all < 0.75 (1028) is about the same compared to the sum of the frequencies for s all < 0.25 and s all > 0.75 (972). From these observations we infer that in case of σ ∈ {2, 3, 4} the stop threshold only influences the transient length but not the symmetry breaking effectivity. In case of σ = 1, it is possible that symmetry breaking cannot be observed but maybe the transient is just very long.

Fig. 8
figure 8

Histograms of the symmetry measure s all(t) for long runs of the simulation (2 × 103 samples)

Full size image

3.2 Dynamics of symmetry breaking

Now we focus on the changes \({\Updelta}s_{\rm all}\) of the symmetry measure s all(t) per time step to get a deeper understanding of the underlying processes. Figure 9 shows measurements of the symmetry measure changes \(\Updelta s_{\rm all}(s_{\rm all},t)\) depending on its current value for different stop thresholds. This means, the changes of s all are measured and averaged for each possible value of s all individually (which is possible because s all  ∈ {0, 1/N, 2/N, ..., 1}). Figure 9a shows the mean absolute changes

$$ \Updelta s_{\rm all}^{\rm abs}(s_{\rm all},t)={{1}\over {M}}\sum_i|s_{\rm all}^i(t)-s_{\rm all}^i(t-1)| $$
(5)

for the symmetry measure \(s_{\rm all}^i(t)\) of sample i, i ∈ 1, ..., M, and M = 2 × 103 samples. The changes are bigger for 0.125 < s all < 0.875 and especially for values close to s all = 0.5. For values close to s all = 0 or s all = 1 the changes are rather small. Figure 9b shows the mean relative changes

$$ \Updelta s_{\rm all}^{\rm rel} (s_{\rm all},t)={{1}\over {M}}\sum_i(s_{\rm all}^i(t)-s_{\rm all}^i(t-1)) $$
(6)

for M = 2 × 103 samples. The changes for s all = 0.5 average to \({\Updelta}s_{\rm all}^{\rm rel} =0\) independent of the stop threshold σ as expected and are rather big for 0.25 < s all < 0.5 and 0.5 < s all < 0.75. The main difference between the curves is the different number of zero-crossings. For σ ∈ {1, 2, 3} there are five crossings and for σ = 4 there is only one zero-crossing. However, the values for σ = 1 are very small (mostly less than 10−5) and partially insignificant. Hence, we exclude the case σ = 1 from further analysis. Both \({\Updelta}s_{\rm all}^{\rm abs}\) and \(\Updelta s_{\rm all}^{\rm rel}\) are time-variant. The shown results are only snapshots for t = 500. For example, the curve for σ = 4 changes over time and has also five zero-crossings for much bigger values of t which explains the long time behavior shown in Fig. 8d.

Fig. 9
figure 9

Absolute and relative change of the symmetry measure s all(t) depending on its current value for t = 500, 2 × 103 samples (confidence intervals are within symbols)

Full size image

The most significant qualitative difference between σ ∈ {2, 3} and σ ∈ {1, 4} is shown in Fig. 10 for the examples of σ ∈ {3, 4} (note that this diagram is a combination of two cropped log-scale diagrams for better readability). For σ = 3, intervals on the s-axis with values of \(\Updelta s_{\rm all}^{\rm rel}\), that lead toward s all = 0.5, are indicated by light gray areas with arrows pointing toward s all = 0.5; intervals on the s all-axis with values of \(\Updelta s_{\rm all}^{\rm rel}\), that lead away from s all = 0.5, are indicated by dark gray areas with arrows pointing toward s all = 0 or s all = 1, respectively. While the light gray areas are counterproductive for symmetry breaking the dark gray areas are productive. These areas are missing for σ = 4 (and t = 500) because \(\Updelta s_{\rm all}^{\rm rel}>0\)

Fig. 10
figure 10

Relative change of the symmetry measure depending on its current value for σ ∈ {3, 4} and t = 500 (same data as shown in Fig. 9). For σ = 3 areas that lead toward s all(t) = 0 are marked in light gray, areas that lead either to s all(t) = 0 or to s all(t) = 1 are marked in dark gray

Full size image

for s < 0.5 and \(\Updelta s_{\rm rel}<0\) for s all > 0.5. The two regions 0.1 < s all < 0.3 and 0.7 < s all < 0.9 are important for an efficient symmetry breaking. Only in case of σ = 2 and σ = 3 these regions have negative values for 0.07 < s all < 0.3 (i.e., s all(t) is decreased over time and tends toward s = 0) and positive values for 0.7 < s all < 0.9 (i.e., s all(t) is increased over time and tends toward s all = 1).

For a high number of samples (M→∞ in Eq. 6), \(\Updelta s_{\rm all}^{\rm rel}\) converges to the discrete derivative of s all and, hence, indicates in principle (stable/unstable) fixed points. However, the underlying processes are stochastic. Thus, neither the given fixed points nor the tendencies indicated by the arrows in Fig. 10 are strict and could be overridden by the system’s noise.

3.3 Flexibility in a dynamic environment

Finally, we investigate the connection between a high ability for symmetry breaking and the flexibility in a dynamic environment. These two properties of the swarm influence the ability for accurate selection and the ability to convergence to an equilibrium.

We compare the behavior of the MAS for σ = 2 as a representative for good symmetry breaking ability to σ = 1 (bad symmetry breaking ability). Now, the initial (t = 0) luminance distribution has a global maximum at the left side (bright light) and a local maximum at the right side (dimmed light). At t = 1 × 103 the two lights are switched (bright light right, dimmed light left). The simulation was stopped at t = 2 × 103.

The results are shown in Fig. 11. For σ = 1 the majority of the agents choose the global maximum (left side of the arena, marked in Fig. 11 by label ‘optimal’) in all runs for t < 1 × 103 (clearly indicated by the dark area for s all < 0.4 and t < 1 × 103). In a high percentage of the runs the majority of the agents quickly revise their initial decision and choose the new global maximum (right side of the arena) beginning at t = 1 × 103 (indicated by the dark area for s all > 0.75). During the whole time no significant majority forms neither at the left nor at the right half of the arena.

Fig. 11
figure 11

Dynamic environment, measured probability density of the state-independent symmetry measure s all(t) (2 × 103 samples). Values of greater than 0.5 indicate a majority of the swarm stays at the left half of the arena, values smaller than 0.5 indicate a majority of the swarm stays at the right half of the arena. For the time period 0 ≤ t < 103 the global maximum is at the left side, for 103 ≤ t < 2 × 103 it is at the right side of the arena

Full size image

For σ = 2 the situation is different. Almost during the whole period significant majorities of the swarm aggregate at one half of the arena (almost always stopped agents are found only in one half).

However, in many runs the system chose the right half with the dimmed light for t < 1 × 103 and after the switch the system did not revise its decision in almost 50% of the runs and stayed at the dimmed light in the left half of the arena.

4 Discussion and outlook

We have defined symmetry breaking and have reported the phenomenon of emergent (weak) symmetry breaking in a continuous-space MAS. It has been shown before that a simple behavior based on a single parameter is sufficient to generate collective decisions: This has been shown for resting times in ants and cockroaches [7]. In [9] the authors propose a model that describes the aggregation behavior of cockroaches based on resting times and the number of cockroaches at the concerned resting site. In the MAS described in this article, a certain number of neighboring agents (σ) is a precondition for stopping while the resting time is determined by the measured local luminance. Our measurements in the simulation show that at least the transient (until a state of symmetry breaking is reached) and possibly also the effectivity depends on the stop threshold σ. Our study shows that a high agent recognition probability γ is necessary for an effective aggregation and symmetry breaking behavior.

We think that the symmetry measures proposed in this paper will be applicable to experiments with both swarm robots and insects (see for example [31, 37]) as there is no need to use different methods.

Due to the idealized simulation (non-colliding agents, no noise on heading etc.) a direct transfer of our results to swarm robotic scenarios is not possible. Still, our results seem to have a general relevance which is supported by simulation runs with agent collisions (data not shown) that show the same qualitative behavior but with longer transients.

With the absolute and the relative symmetry measure change (\(\Updelta s_{\rm all}^{\rm abs}, \Updelta s_{\rm all}^{\rm rel}\)), we have identified two macroscopic features that are measurable in the simulation and that considerably influence the dynamics of the state-independent symmetry measure s all. We have determined a correlation between effective symmetry breaking and a qualitative property of \(\Updelta s_{\rm all}^{\rm rel}\) (number of zero-crossings).

In the limit (for many samples), \(\Updelta s_{\rm all}^{\rm rel}\) converges to the (discrete) derivative of s all. Hence, it indicates fixed points and predicts the evolution of s all to some extent. An investigation of the temporal evolution of \(\Updelta s_{\rm all}^{\rm rel}\) itself would in turn show, when symmetry breaking is actually reachable. We conjecture that the two features \(\Updelta s_{\rm all}^{\rm abs}\) and \(\Updelta s_{\rm all}^{\rm rel}\) might fully describe the process of symmetry breaking in this MAS on a macroscopic level.

Many works on symmetry breaking in swarm intelligence focus on mass recruitment with pheromones. The application of stigmergy introduces a certain degree of complexity accompanied with several assumptions (e.g., evaporation rate, odor detection threshold). Here, we focused on a system of lower complexity based on mere cluster formation. Hence, we have fewer assumptions. The most prominent difference compared to systems based on pheromones is the non-persistence of the clusters that are clues used for indirect communication. The probably mostly related example from swarm intelligence literature is the pattern formation in ant corpses [8]. There is also an infinite number of choices (cluster can form anywhere in space). Our system and this model of patterns in ant corpses become very similar, if we theoretically remove the living ants from the system. Then the corpses themselves travel from cluster to cluster with certain probabilities which is similar to our model.

Following [25], symmetry breaking in foraging honeybees does not seem to have much advantage for a honeybee colony in the absence of competitors and predators. It is also questionable whether situations of two (or more) equal options of food sources etc. do actually occur in nature. However, symmetry breaking situations show the differences in the ability of a swarm to reach consensus, although such situations themselves are more like an artifact. In fact, there seems to be a trade-off between the ability to break symmetries and the ability to be adaptive to dynamic environments (for a related work on speed vs. accuracy in collective decision making see [38]). This is supported by the work we presented in this article: While higher stop thresholds (σ > 1) lead to good symmetry breaking behavior, the variant with a low stop threshold σ = 1 is obviously less dependent on high agent recognition probabilities and shows higher flexibility to dynamic environments.

In natural swarm systems, the ability of breaking the symmetry between two targets can be seen as an indicator for variability of the animals’ ecological niche: In ants, most species that perform mass recruitment by pheromone trails, converge quickly to the first good foraging target and continue to exploit this food source massively, even after a better food source is established in the environment [26, 33]. For such a species, the quick convergence to one of two good solutions is a property that arises from the strong positive feedback loop enforced by the mass recruitment system (pheromone trails) in these species. It finally leads to symmetry breaking. The stronger this positive feedback is, the faster the emergence of symmetry breaking is assumed to happen. Also cockroach aggregation was found to exhibit symmetry breaking, thus we expect that aggregation spots do not change frequently for these species [12]. In contrast, the environmental conditions for honeybee nectar foragers change rapidly, even several times a day. In addition, only a limited amount of bees is supported by a given number of blossoms. The choice experiments described in [39] show, that even with two food sources of differing quality, the swarm never converges to just one foraging target. Comparable results have been shown in [22], who investigated saturation effects also with crowded ant trails. We currently investigate the dynamics of aggregation of young honeybees in temperature fields, where the model and the measurement criteria described in this article will be used to compare results and to make testable predictions. Despite that, a general measure of symmetry breaking strength is of big importance also in the field of swarm intelligence and swarm robotics, as symmetry breaking and choice performance are crucial key properties of any swarm intelligent system.

It will be part of our future work to check whether \(\Updelta s_{\rm all}^{\rm abs}\) and \(\Updelta s_{\rm all}^{\rm rel}\) fully describe the process of symmetry breaking in the reported MAS. Furthermore, we plan to analyze the connection between transient length and continuous values of σ obtained by a probabilistic stopping behavior of the agents and we will investigate the dynamics of \(\Updelta s_{\rm all}^{\rm abs}\) and \(\Updelta s_{\rm all}^{\rm rel}\) during simulation runs.