Modelling hierarchical flocking

Collective behavior is a very important aspect through which small or large groups of organisms optimize their living [1]. It involves collective decision making an various contexts, such as searching for food, navigating towards a distant target [2–5] or deciding when and where to go [4, 6–8]. Flocking is perhaps the most common and spectacular manifestation of collective behavior not only in nature since recently has gained attention in the context of collective robotics as well [9–11]. Most of the experimental and modeling approaches aimed at describing flocking by assuming egalitarian interactions among the members of a flock.

However, just as flocking is a widespread behavioral pattern of a collective, the hierarchical structure of the interactions among the members of groups is also very common [12]. Thus, starting with a trend-setting paper of Couzin et al [13] the question of leadership during flocking has attracted increasing interest. Early works assumed a two-level hierarchy while recent experimental observations involving some sophisticated animal groups such as pigeons or primates point towards the possibility of significantly more complex internal organization principles during group motion [2, 8, 14, 15]. In socially highly organized groups beyond a given size (dozens or so) the roles related to leadership do not seem to be simply binary, but several levels of hierarchy can be identified. In particular the available few experimental results indicate that many co-moving groups have an internal system of interactions which can be best interpreted in terms of pairwise hierarchical levels of interactions. Perhaps the best quantitatively evaluated hierarchical group motion was carried out for pigeon flocks [2, 16] in which a hierarchically distributed set of interactions was demonstrated using GPS tracks and a velocity correlation-delay method [2].

On the other hand, in spite of its relevance, there have been no realistic models proposed and studied devoted to the understanding of the conditions under which hierarchical flocking can be optimal. The only vaguely related original model is in a beautiful work by Shen [17], but the assumptions are quite arbitrary and the effect of the hierarchy on the performance of the flock is not investigated.

Therefore, our goal here is to design a general framework which allows the treatment of questions related to hierarchical leader-follower interactions in a general setting, when the flock is freely moving (in the present study in two dimensions). We also discuss the various variants allowed by our approach and characterize the efficiency of the behavioral rules by determining to what level a flock is stable against external perturbations. Hierarchy is thought to be prevalent because it can be shown to result in more efficient group performance [8, 12].

The present work is the first one in which a flexible and plausible framework is introduced to model hierarchical flocking. It turns out that introducing pairwise interactions satisfying a realistic hierarchical dynamics is far from being trivial. After introducing the model the main aspect we investigate is the stability of a flock moving freely in a border-less two-dimensional space. We shall associate with stability the tendency of a flock not to break into parts under external perturbations.

For an egalitarian system, every particle is believed to be the same, while for a hierarchical system, individual difference exists. Any complex multi-agent system can be classified as egalitarian or hierarchical according to the set of pairwise relationships between any two individuals. For each pair of particles in an egalitarian system, both of them have the same ability (referring to the same contribution strength and bidirectional information flow) when making decisions for the next time step. Meanwhile, for each pair of particles in a hierarchical system, when making a decision, they may have different level of contribution to the decision (weight) or have a directed information flow relationship, like the leader-follower mechanism (follower has no influence on the behavior of the leader).

Graphs/networks represent a useful tool for visualizing these pairwise interaction relationships of individuals belonging to one co-moving group. Therefore, we define several matrices to describe the internal properties of the hierarchical mechanisms from different points of view, for the purpose of characterizing the differences between the egalitarian and hierarchical systems clearly.

2.1. Contribution matrix

2.2. Dominance matrix

2.3. Egalitarian versus hierarchical systems

We consider in this paper N particles moving continuously (off lattice) in a free area without any boundary limitation. As shown in figure 1, the position and direction of N particles at the beginning are generated randomly, while over time these particles are expected to move coherently (ordered state). The figure is for the noiseless case.

Zoom In Zoom Out Reset image size

Suppose that the time interval between two updates of the directions and positions is Δt = 1. This assumption can be made without loosing generality since Δt occurs only in combination (being multiplied by it) with velocity terms At t = 0, N particles were randomly distributed within an area of a given size and have the same absolute velocity υ_d as well as randomly distributed directions θ. At each time step, the position of the ith particle is updated according to

$$\begin{eqnarray}&&{{\bf{x}}}_{i}(t+1)={{\bf{x}}}_{i}(t)+{{\bf{v}}}_{i}(t){\rm{\Delta }}t.\end{eqnarray} \tag{ 1 }$$

In each time step, the velocity of a particle v_i(t + 1) is updated according to the following equation

$$\begin{eqnarray}&&{{\bf{v}}}_{i}(t+1)={{\bf{v}}}_{i}^{{\rm{align}}}(t)+{{\bf{v}}}_{i}^{{\rm{rep}}}(t)+{{\bf{v}}}_{i}^{{\rm{adh}}}(t),\end{eqnarray} \tag{ 2 }$$

where ${{\bf{v}}}_{i}^{{\rm{align}}}(t)$ is the alignment term, ${{\bf{v}}}_{i}^{{\rm{rep}}}(t)$ is the repulsion term, and ${{\bf{v}}}_{i}^{{\rm{adh}}}(t)$ is the attraction term.

The alignment term was constructed to have an absolute value υ and a direction given by the angle ${\theta }_{i}^{{\rm{align}}}(t+1)$. The angle was obtained from the expression

$$\begin{eqnarray}&&{\theta }_{i}^{{\rm{align}}}(t+1)=\langle {\theta }_{i}(t)\rangle +{\rm{\Delta }}\theta (t),\end{eqnarray} \tag{ 3 }$$

where Δθ(t) represents noise, which is a random number chosen with a uniform probability from the interval [−η/2, η/2]. $\langle {\theta }_{i}(t)\rangle$ denotes the average direction of the velocities of neighbors of the given particle i. The average direction is given by the angle

$$\begin{eqnarray}&&\langle {\theta }_{i}(t)\rangle =\arctan \left(\displaystyle \frac{{\displaystyle \sum }_{j=1}^{N}{l}_{{ij}}(t)\sin ({\theta }_{j}(t))}{{\displaystyle \sum }_{j=1}^{N}{l}_{{ij}}(t)\cos ({\theta }_{j}(t))}\right).\end{eqnarray} \tag{ 4 }$$

Neighbor matrix ${L}_{N}(t)={[{l}_{{ij}}(t)]}_{N\times N}$ describes the neighbor relationships of particles at time t, where

$$\begin{eqnarray}&&{l}_{{ij}}(t)={c}_{{ij}}\ast {b}_{{ij}}\ast {a}_{{ij}}(t),\forall i,j=1,\cdots ,N.\end{eqnarray} \tag{ 5 }$$

The definition of adjacency matrix ${A}_{N}(t)={[{a}_{{ij}}(t)]}_{N\times N}$ is

$$\begin{eqnarray}&&{a}_{{ij}}(t)=\left\{\begin{array}{c}1,i=1,\cdots ,N,\ j\in {N}_{i}(t)\ \ \\ 0,{\rm{otherwise}}\end{array}\right.,\end{eqnarray} \tag{ 6 }$$

where ${N}_{i}(t)=\{j| \parallel {{\bf{x}}}_{i}(t)-{{\bf{x}}}_{j}(t)\parallel \leqslant r\}$. Here, r denotes the interaction radius. Using the above expressions the alignment term can be written as

$$\begin{eqnarray}&&{{\bf{v}}}_{i}^{{\rm{align}}}(t+1)={{c}}^{{\rm{align}}}\upsilon {{\bf{e}}}_{i}(t),\end{eqnarray} \tag{ 7 }$$

where c^align is the coefficient of the alignment term. e_i(t) is a unit vector with direction angle ${\theta }_{i}^{{\rm{align}}}(t)$.

The repulsion term exists only when the distance between any two particles is smaller than the repulsive radius r_rep. And the repulsion term is defined as

$$\begin{eqnarray}&&{{\bf{v}}}_{i}^{{\rm{rep}}}(t+1)={{c}}^{{\rm{rep}}}\displaystyle \sum _{j=1}^{N}{l}_{{ij}}(t)\left(\displaystyle \frac{{r}_{{\rm{rep}}}-\parallel {{\bf{x}}}_{{ij}}(t)\parallel }{{r}_{{\rm{rep}}}}\,\bullet \,\displaystyle \frac{{{\bf{x}}}_{{ij}}(t)}{\parallel {{\bf{x}}}_{{ij}}(t)\parallel }\right),\end{eqnarray} \tag{ 8 }$$

where $\parallel {{\bf{x}}}_{{ij}}(t)\parallel \lt {r}_{{\rm{rep}}}$ and ${{c}}^{{\rm{r}}{\rm{ep}}}$ is the coefficient of the repulsion term.

The attraction term is only considered for the boundary particles [18] of the whole system when the distance between two particles is between r_rep and r_adh.

$$\begin{eqnarray}&&{{\bf{v}}}_{i}^{{\rm{adh}}}(t+1)={{c}}^{{\rm{att}}}\displaystyle \sum _{j=1}^{N}{l}_{{ij}}(t)\left(\displaystyle \frac{{r}_{{\rm{rep}}}-\parallel {{\bf{x}}}_{{ij}}(t)\parallel }{{r}_{{\rm{att}}}-{r}_{{\rm{rep}}}}\,\bullet \,\displaystyle \frac{{{\bf{x}}}_{{ij}}(t)}{\parallel {{\bf{x}}}_{{ij}}(t)\parallel }\right),\end{eqnarray} \tag{ 9 }$$

where ${r}_{{\rm{rep}}}\leqslant \parallel {{\bf{x}}}_{{ij}}(t)\parallel \leqslant {r}_{{\rm{adh}}}$ and ${{c}}^{{\rm{a}}{\rm{dh}}}$ is the coefficient of the attraction term. This term is introduced in order to prevent the flock spreading (or, in other words, 'evaporating') due to perturbations.

Figure 2 shows the neighbour matrix of several variants of flocks mentioned in the last section. From figure 2, visualizes the differences between the egalitarian system from the typical hierarchical systems.

Zoom In Zoom Out Reset image size

The simulations were carried out in a free two-dimensional area. We considered groups of particles having various sizes ranging from 10 to 1280 particles. In order to keep the continuity and comparability of these simulation results of different group sizes, we chose the scale of the area for the random initial positions directly proportional to the scale of group size N, and generated the initial angle from the interval (−π, π]. Here, without loss of generality, the random initial positions are generated from a rectangle area with length L and width 0.6L. Then, the initial density of the system $\rho =N/(0.6{L}^{2})$, which is constant for various group sizes. We aimed at comparing the stability of egalitarian systems versus various hierarchical systems for varying levels of external disturbances (noise) and for different group sizes.

The alignment item of egalitarian flock model is much like the self propelled particle model proposed by Vicsek et al in 1995 [19], where the definition of neighbors of particle i includes itself and the contribution of the particles is the same. Thus, we call the egalitarian model as VEM (E for egalitarian, M for model). The contribution driven hierarchical model is called as CHM (C for contribution).

According to the definition of the strictly dominance matrix B_N, the neighbor matrix of a dominance-related strictly-hierarchical system has zero-value diagonal elements, that is, we have l_ii = 0, ∀ i = 1, ⋯, N for all dominance-related strictly-hierarchical systems. l_ii = 0 means that the neighbor set of particle i does not contain itself. In the following under hierarchy, we always mean hierarchical leader-follower kind of hierarchy. Therefore, we name the single-layer leader-follower hierarchical model (${l}_{{ii}}\ne 0,\forall i=1,\cdots ,N$) as SHM (S for single-layer leader-follower), and we call the single-layer leader-follower strictly-hierarchical model by SHMZ (S for single-layer leader-follower, and Z for l_ii = 0, ∀ i = 1, ⋯, N). Similarly, the double-layer leader-follower strictly-hierarchical flock model (l_ii = 0, ∀ i = 1, ⋯, N) is named as 'Double Hierarchical Model with Zero-s (DHMZ)', while when ${l}_{{ii}}\ne 0,\forall i=1,\cdots ,N$, we call it 'Double Hierarchical Model (DHM)'.

4.1. VEM versus CHM/SHM

In these simulations, we used $\rho =0.5,\upsilon =0.1,{r}_{{\rm{rep}}}=0.1,{r}_{{\rm{adh}}}=1.1,{{c}}^{{\rm{a}}{\rm{lign}}}=1,{{c}}^{{\rm{r}}{\rm{ep}}}=0.1,{{c}}^{{\rm{a}}{\rm{dh}}}=0.000\,2$, and interaction radius r = 1.1.

4.1.1. Order parameter

For this case we used the average normalized velocity as the order parameter, defined as

$$\begin{eqnarray}&&{\phi }^{{\rm{ave}}}=\displaystyle \frac{1}{T}\displaystyle \frac{1}{N}{\int }_{0}^{T}\parallel \displaystyle \sum _{i=1}^{N}{{\bf{v}}}_{i}(t)\parallel {\rm{d}}{t},\end{eqnarray} \tag{ 10 }$$

where T = 2000 is the simulation time for each experiment.

The error bar is defined as:

$$\begin{eqnarray}&&\sigma =\displaystyle \frac{1}{\sqrt{n}}\bar{\phi },\end{eqnarray} \tag{ 11 }$$

where $\bar{\phi }$ is the standard deviation of the order parameter values, and n > 0 is the number of simulations for a given system size. The typical values of n were chosen as follows:

$$\begin{eqnarray}&&n=\left\{\begin{array}{c}1000,{\rm{if}}\ \ N=10\\ 1000,{\rm{if}}\ \ N=20\\ 500,{\rm{if}}\ \ N=40\\ 200,{\rm{if}}\ \ N=80\\ 100,{\rm{if}}\ \ N=160\end{array}\right..\end{eqnarray} \tag{ 12 }$$

4.1.2. Results

First, we compared the stability of VEM and some simple hierarchical flocking systems, such as CHM and SHM. According to our results (see figures 3 and 4), a simple dominance-based system does not perform better than the much studied egalitarian flock. It should be noted that we did not compare VEM with CHM/SHM for larger group sizes than N = 160, because we guess CHM/SHM still do not perform better than VEM, but readers who are interested in size dependence are welcome to investigate it.

Zoom In Zoom Out Reset image size

Zoom In Zoom Out Reset image size

4.2. VEM versus DHM/DHMZ

In this simulation, we use $\rho =0.4,\upsilon =0.1,{{r}}_{{\rm{rep}}}=0.5,{{r}}_{{\rm{adh}}}=2.2,{{c}}^{{\rm{a}}{\rm{lign}}}=1,{{c}}^{{\rm{r}}{\rm{ep}}}=0.1,{{c}}^{{\rm{a}}{\rm{dh}}}=0.000\,06$, and interaction radius r = 2.2.

4.2.1. Order parameter

As mentioned above, we shall associate the stability with the tendency of a flock not to break into parts under external perturbations. In order to measure the stability of the particle group, we used the following velocity correlation as the order parameter

$$\begin{eqnarray}&&{\phi }^{{\rm{corr}}}=\displaystyle \frac{1}{T}\displaystyle \frac{1}{N(N-1)}{\int }_{0}^{T}\displaystyle \sum _{i=1}^{N}\displaystyle \sum _{j\in {N}_{i}(t)/i}\displaystyle \frac{{{\bf{v}}}_{i}(t){{\bf{v}}}_{j}(t)}{\parallel {{\bf{v}}}_{i}(t)\parallel \parallel {{\bf{v}}}_{j}(t)\parallel }{\rm{d}}{t},\end{eqnarray} \tag{ 13 }$$

where $j\in {N}_{i}(t)/i$ means $j\in {N}_{i}(t)$ and $j\ne i$. This expression indicates the stability of the flock under different conditions. We did not use the average velocity as the order parameter here, just because velocity correlation (as order parameter) could offer a more strictly stability description when the system is divided into two or more coherently moving subgroups.

4.2.2. Results

We compare VEM with DHM and DHMZ separately. figure 5 shows the comparison results of the VEM and DHM, while figure 6 shows the comparison results of VEM and DHMZ.

Zoom In Zoom Out Reset image size

Zoom In Zoom Out Reset image size

According to figure 5, we can see that VEM is a little bit better (better meaning that it is more ordered for the same amount of noise) than the DHM for different group size under lower noise, while it seems that DHM is a little better than VEM under larger noise. However, the advantage is so small that can be ignored. At the same time, it seems that there exists no relevant difference among the simulation results for various group sizes.

Figure 6 demonstrates that the DHMZ hierarchical model is significantly more stable than an egalitarian model for flocking, and the advantage is increasingly obvious as the size of the system increases. However, the stability gap between an egalitarian flock and a hierarchical flock stops increasing from 320 to 1280 particles. That is to say, the difference in the performances between the egalitarian system and the hierarchical system is increasing with system size, but only up to a given flock size and is not changing as the group size reaches a certain threshold. This is quite along the intuitive picture which suggests that hierarchy may play a relevant role only up to—at most—a few hundred of flock members.

At first, we were puzzled by the result that DHMZ performs much better than DHM. However there exists a plausible interpretation. The zero on the diagonal means that a unit does not consider its own decision (direction) when it decides about its direction at each time step. The element on the diagonal being not zero means that when a unit makes a decision, it will implement the average decision of both itself and its neighbors. In short, an interaction matrix with zeros along the diagonal means that the 'follow the leaders' principle is manifested in an enhanced way. Even if in other interactions the given unit is usually a leader (having a relatively large b_ij or c_ij values), when this leader decides how to proceed, it becomes a follower in relation with the others.

Let us consider twenty-eight particles, for example, figure 7 shows some important scenarios during the flocking process. The color bar reveals the weight of the contribution of the given particle. For example, the red particle is the strongest one, while the purple one is the weakest particle. The contribution values of these particles belonging to the DHMZ system satisfy log-normal distribution. That is, c_ij, i, j = 1, ⋯, N, i > j satisfy log-normal distribution, with mean value 0 and standard deviation 1. At the same time, the contribution value of each particle belonging to VEM system is equal, and the sum of the contribution values of VEM system is equal to the sum of the contribution values of the DHMZ system. The initial state of the twenty-eight particles in VEM is the same as that in DHMZ. In figure 7, the boundary particles are indicated by a bigger size than the inside particles. The first picture in figure 7 displays the state of all the particles at start. The left part of figure 7(b) depicts the structure of the VEM flock being less cohesive than the DHMZ (the right one) and a couple of particles are already separated from the VEM flock. Figures 7(c) and (d) show two key moments when VEM results in three separated groups while DHMZ results still in a single cluster. This can be taken as an important evidence to demonstrate that leader-follower hierarchical systems are more efficient regarding their stability against perturbations which the individual units are subject to.

Zoom In Zoom Out Reset image size

In conclusion, we have introduced an interpretation of the possible behaviors of interacting, collectively moving units (let it be birds, fish or people, etc) which is more general than any of the ones we are aware of. The main feature of our approach is that it unites into a single formalism the results and assumptions of the prior models and observations. Some of our results are plausible: a simple averaging of the direction of motion of neighbours (VEM) is quite efficient when the efficiency is measured as the level of stability against external/internal perturbations. The main points of our paper are concerned with the role of hierarchy among the co-moving units. We have located two non-trivial models: (i) the contribution during the averaging of the directions is weighted, (ii) the given unit is—when evaluating its direction in the net time step—in a fully 'follower mode' (DHMZ). At first, our numerical findings (i) is inefficient, (ii) performs the best, looked as ssurprising, but we provided the interpretations for these findings. Our formalismis general enough for using it to introduce a large family of more specific models.

This work was partly supported by the following grants: U.S. Air Force, Office of Scientific Research grant no. FA9550-17-1-0037; H2020, EU FP7 RED-Alert No: 740688 and the (Hungarian) National Research, Development and Innovation Office grant No K128780.