Asymptotic flocking for the three-zone model

1.   Introduction

Flocking behavior is an intriguing phenomenon observed frequently in nature. However, it remains an open question how birds or fish are able to organize efficiently to form a coherent motion. Modeling has proved to be crucial in highlighting how such complex behaviors can be described by simple interaction rules. Among the different models proposed, the three-zone model has been particularly popular in biology ^[1,2,3,4,5]. In the three-zone model, agents representing birds or fish engage in three types of interactions: repulsion, alignment, and attraction, depending on the relative location of their neighboring agents. The goal of this manuscript is to provide sufficient conditions for the convergence of such a system towards a flock, which we define to occur when all agents approach a common velocity.

Analytical studies of flocking dynamics have mainly been inspired by the seminal work of Cucker and Smale ^[6,7]. In their research, they studied a simplified version of the so-called Vicsek model ^[8], where only the alignment force between agents is considered. They proved rigorously the convergence of the dynamics to a flock, given the condition that the alignment force is sufficiently strong. This work has been followed by many generalizations ^[9,10,11] and improvements ^[12,13,14].

One key element of proving the convergence of the Cucker-Smale model to a flock is the decay of the kinetic energy of the system due to the alignment rule, which acts as a source of friction. In the present manuscript, the dynamics combine the alignment rule with the additional forces of attraction and repulsion. Therefore, we have to define the energy of the system as the sum of its kinetic energy and potential energy. The attraction-repulsion term does not modify the total energy since it is Hamiltonian dynamics. However, the alignment term causes the kinetic energy, and consequently the total energy of the system, to decay with respect to time. As a result, if the attraction-repulsion force is such that the particle configuration remains spatially bounded, the influence of the alignment term will guarantee the system converges to a flock. Notice that we do not draw any conclusions about the spatial organization of the flock, though many analytic and numerical studies have studied this problem ^[15,16,17].

Since our proof is based mainly on an energy functional, it is possible to extend the method to the kinetic equation associated with the three-zone model. However, in this case, we have to define a weaker notion of flocking for the kinetic equation. There is additional difficulty in dealing with a kinetic equation: since we are working with a continuum distribution, there is no longer a maximum distance between two agents. Despite these obstacles, we manage to prove a $L^1$-type convergence result by using stochastic process theory.

So far, the sufficient condition for flocking requires that the attraction term is given by a confinement potential. However, this condition can be weakened by incorporating the effect of the alignment in the non-spatial dispersion of the agents. Here, the effects of attraction and alignment are treated separately.

It might be possible to improve the sufficient condition for flocking and/or to find a joint condition on the strength of attraction and alignment using commutator techniques ^[18,19]. Commutator may also help to prove that the dynamics converges exponentially fast toward equilibrium. Other perspectives will be to extend the proof to other types of interactions, such as non-symmetric interactions ^{[10,11,20,21]}, or those using the so-called topological distance ^[22,23,24].

The paper is organized as followed: in section 2, we introduce the three-zone model for agent-based dynamics. We prove the main result by finding a sufficient condition for the emergence of a flock and give several numerical illustrations. In section 3, we extend this result to the kinetic equation associated with the agent-based model. Finally, we draw a conclusion in section 4.

2.   Agent-based models

2.1.   Three-zone model

We consider the three-zone model, which describes agents moving according to three rules of interaction: repulsion (at short distance), alignment and attraction (long distance). A schematic representation of the model is given in Figure 1. Each agent $i$ is represented by a vector position ${\bf x}_i$ and a velocity ${\bf v}_i$ both belonging to $\mathbb{R}^d$ (with $d = 2$ or $3$). The evolution of the $N$ agents is governed by the following system:

Here, $\phi_{ij} = \phi(|{\bf x}_j-{\bf x}_i|)$ represents the strength of the alignment between agents $i$ and $j$. We suppose that the function $\phi$ is strictly positive. Similarly, $\nabla_{{\bf x}_i} V(|{\bf x}_j-{\bf x}_i|)$ represents the attraction or repulsion of agent $j$ on $i$. Indeed, developing the gradient gives:

Thus, agent $i$ is attracted to agent $j$ if $V' > 0$ and repulsed if $V' < 0$. In Figure 1, we illustrate two possible choices for $\phi$ and $V$.

2.2.   Flocking: rigorous results

The goal of this section is to prove conditions guaranteeing that the three-zone models (2.1) and (2.2) converges to a flock.

Definition 2.1. We say that a configuration $\{{\bf x}_i, {\bf v}_i\}_{i}$ converges to a flock if the following are satisfied:

(i) There exists ${\bf v}_{\infty}$ such that ${\bf v}_i \xrightarrow{t\rightarrow \infty} {\bf v}_{\infty}$ for all $i = 1, \dots, N$.

(ii) There exists $M$ such that $|{\bf x}_j-{\bf x}_i| \leq M$ for all $i, j = 1, \dots, N$ and for all $t\geq 0$.

In other words, in order to achieve a flock, agents should converge to a common velocity ${\bf v}_\infty$ and the distance between agents should remain (uniformly) bounded in time.

The key quantity for studying the emergence of a flock is the energy function, defined below:

We can interpret this value as a sum of the kinetic and potential energy of the system.

By itself, the attraction-repulsion terms (2.1) and (2.2) describes a Hamiltonian system and therefore preserves the total energy $\mathcal{E}$. However, the alignment term causes the total energy to decay with respect to time. That is, it plays the role of a 'friction term', making the system dissipative. More precisely, we can estimate the decay rate of the energy $\mathcal{E}$.

Lemma 2.2. Let $\{{\bf x}_i, {\bf v}_i\}_i$ be the solution of the $N$-bird systems (2.1) and (2.2). Then the energy $\mathcal{E}$ of Eq (2.3) satisfies:

Since $\phi$ is a positive function, the energy $\mathcal{E}$ is decaying along the solution trajectory.

Proof. Taking the derivative in time of the energy leads to:

By an argument of symmetry, we find:

Therefore, we can simplify:

Using now the symmetry $\phi_{ij} = \phi_{ji}$, we conclude

Since the energy $\mathcal{E}$ is decaying, we deduce that the potential energy is bounded uniformly.

Lemma 2.3. Take $\{{\bf x}_i, {\bf v}_i\}_i$ to be a solution of the three-zone models (2.1) and (2.2). There exists $C$ such that for any time $t \geq 0$:

Proof. Take $C_0 = \mathcal{E}(\{{\bf x}_i(0), {\bf v}_i(0)\}_i)$. Since $\mathcal{E}$ is decaying along the solution trajectory, we deduce that for all $t$:

Since the kinetic energy $\frac{1}{2}\sum_{i = 1}^N |{\bf v}_i|^2$ is always positive, we deduce:

Taking $C = 2C_0N^2$ yields the result.

To take advantage of the Lemma 2.3, we suppose that $V$ is a confinement potential ^[21]:

Roughly speaking, agents still experience an attraction force at long distances.

Under this assumption, we can prove the second part of flocking behavior, namely that the distances between agents are bounded.

Lemma 2.4. Suppose $V$ satisfies Eq (2.6). Then there exists $r_M$ such that:

Proof. From Lemma 2.3, we know that the potential energy is bounded, in particular:

Since $V$ satisfies Eq (2.6), we deduce that there exists $r_M$ such that:

Since $V(|{\bf x}_j(t)-{\bf x}_i(t)|)$ is bounded by $C$, we conclude that $|{\bf x}_j(t)-{\bf x}_i(t)|$ is bounded by $r_M$.

Remark 1. Similarly, if we suppose that $V$ diverges at $r = 0$, then there exists a minimal distance $r_m$ between agents:

We can now conclude by deriving sufficient conditions to guarantee flocking behavior for the three-zone model.

Theorem 2.5. Suppose $V$ satisfies Eq (2.6) and is bounded from below, $\phi$ is strictly positive and bounded. Moreover, assume that both $\phi$ and $V$ have bounded first-order derivative. Then the three-zone model converges to a flock.

Proof. Using Lemma 2.4, we know that the distance between agents remains bounded: $|{\bf x}_j(t)-{\bf x}_i(t)|\leq r_M$. Since $r_M$ is finite, we can take the minimum of $\phi$ on this interval:

Since $\phi$ is strictly positive, we deduce that $m > 0$. Therefore,

Since the energy $\mathcal{E}(\{{\bf x}_i, {\bf v}_i\}_i)$ is decaying and bounded from below we deduce that $\frac{d}{dt} \mathcal{E}(\{{\bf x}_i, {\bf v}_i\}_i) \stackrel{t \to \infty}{\longrightarrow} 0$ (if $\frac{d}{dt} \mathcal{E}$ is uniformly continuous). Therefore, using Lemma 2.2,

Since $\phi_{ij}\geq m > 0$, we conclude that $|{\bf v}_j-{\bf v}_i|\stackrel{t \to \infty}{\longrightarrow} 0$.

Moreover, the mean velocity, $\bar {\bf v} = \frac{1}{N} \sum_i {\bf v}_i$, is preserved by the dynamics (by symmetry), thus

which concludes the proof. To finish the proof, it suffices to establish the uniform continuity of $\frac{d}{dt} \mathcal{E}$, which is guaranteed if uniformly in time bounds on the second time derivative of $\mathcal{E}$ can be obtained. Indeed, we calculate

where $\mathrm{II}$ is given by

In the sequel, we shall denote by $C$ a time-independent constant whose value may vary from line to line (which may depend on $N$). Combining the boundedness of $\phi$ and $\phi'$ with the fact that $\frac{1}{2N}\sum_{i = 1}^N |{\bf v}_i(t)|^2 \leq C$ holds uniformly in time, one can easily achieve $|\mathrm{II}| \leq C$, where this bound on $|\mathrm{II}|$ is independent of both $N$ and $t$. For the trickier term $\mathrm{I}$, we have

Thus, the proof will be completed once we show that $\frac{1}{N} \sum\limits_{i = 1}^N |{\bf v}_i(t)|^3 \leq C$. To this end, we calculate

We have

and

Therefore, we deduce that

from which we obtain the uniform bound $\frac{1}{N} \sum\limits_{i = 1}^N |{\bf v}_i(t)|^3 \leq C$ as desired. This ends the proof.

Remark 2. The reason that we can not achieve a bound like $|\frac{d^2}{dt^2}\mathcal{E}| \leq C$ with the constant $C$ being independent of both $N$ and $t$ is due to the $N$-dependence of the constant $C$ appearing in the Lemmas 2.3 and 2.4.

2.3.   Numerical investigation

To illustrate the Theorem 2.5, we perform numerical experiments for various choices of attraction-repulsion potentials. The Theorem 2.5 guarantees that the velocities of the agents will converge to a single value, but there is no information about their position and in particular their relative distance. It is an open question to predict what shape the flock will have. All we know is that the distance between agents is bounded uniformly in time, which leaves the door open for many possible scenarios. Several studies have examined the stability of particular equilibrium solutions ^{[15,16,25,26,27]}. Models featuring self-propelled particles with an attraction-repulsion influence function have also been extensively studied ^[28,29], and several patterns observed (e.g., flock, mill formation). In our settings, however, mill formation cannot occur as the agents' velocities will converge to same value. Of particular interest is the shape of the swarm as the number of individuals $N$ increases.

To first illustrate the Theorem 2.5, we choose the following functions for the three-zone model (see Figure 2-left):

The potential $V(r)$ diverges at $+\infty$ (i.e., satisfies Eq (2.6)) and the alignment function is strictly positive (i.e., $\phi(r) > 0$), thus we can apply the Theorem 2.5 and deduces that the agents will always converge to a flock. Notice that the alignment function $\phi(r)$ is integrable, thus without the attraction/repulsion term $V(r)$ there is no guarantee that a flock will occur. In others words, since the three-zone models (2.1) and (2.2) reduces to the Cucker-Smale model when $V' = 0$, having $\phi$ integrable is not a sufficient condition to guarantee flocking.

We use as initial condition a uniform distribution of agents on a square of size $\sqrt{N}$. Their velocity is taken from a normal distribution. In the Figure 3, we plot the distribution of agents after $t = 200$ time units for four different group size: $N = 20, \, 50, \, 100$ and $1000$. For each group size, the agents regroup on a disc of radius close to $2$ space units and the distribution is uniform inside the disc. As the number of agents $N$ increases, the radius remains constant and therefore the average distance between particles decreases. This type of pattern has been called catastrophic ^[29,30] since the density will eventually become singular as $N \longrightarrow +\infty$ and thus there is no thermodynamic limit. In other words, the repulsion is not strong enough to push back nearby agents.

In our second illustration, we reduce even further the repulsion force among agents using the following potential $V(r)$ (Figure 2-right):

There are now two possible equilibrium points for attraction/repulsion at the distances $r = 1$ and $r = 0$. In the Figure 4, we plot the distribution of agents after $t = 200$ time units for two group sizes ($N = 50$ and $N = 200$). We observe that the agents are now agammaegating on a circle. This indicates that the equilibrium distribution might be a domain of dimension one ^[31].

The evolution of the total energy $\mathcal{E}$ from Eq (2.3) for all cases is given in Figure 5. As predicted by Lemma 2.2, the energy is always strictly decaying. Moreover, we observe oscillatory behavior between fast and slow decay. The reason for this behavior is the repeated contraction-expansion of the spatial configuration as the agents approach equilibrium. The energy is decaying slower when agents are far away due to the decay of $\phi$ at distances greater than one space unit. These types of oscillation are also observed for the convergence of Boltzmann equation toward global equilibrium ^[32,33].

3.   Kinetic equation

3.1.   Formal derivation

We would like to investigate the flocking behavior of dynamics in the limit of infinitely many agents, i.e., $N\longrightarrow\infty$. With this aim, we introduce the so-called kinetic equation associated to the particle dynamics (2.1) and (2.2). To derive the kinetic equation, one can introduce the empirical distribution ^{[34,35,36,37,38,39]}:

where $\{{\bf x}_i(t), {\bf v}_i(t)\}$ is the solution of the systems (2.1) and (2.2). By integrating the empirical distribution $f_N$ against a test function, we can show that $f_N$ satisfies in a weak-sense the following kinetic equation:

with

and

the spatial distribution of particles.

The rigorous convergence of the particle dynamics (2.1) and (2.2) toward the kinetic equation (3.2) is out of the scope of the present paper. But following the methods developed in ^[34,35,40], one would expect to have an error estimation between the empirical distribution $f_N$ given by Eq (3.1) and a 'classic' solution $f$ to the kinetic equation (3.2) and (3.3). More precisely, for any time $T$, there exists a constant $c$ such that the Wasserstein distance between the two distributions satisfies:

Notice that this result cannot be used to study the long time behavior of the solution of the kinetic equation $f(t)$ since the error-bound is not uniform in time.

3.2.   Flocking behavior

To analyze the long-time behavior of the solution to the kinetic equation (3.2), we introduce the following energy function:

Symmetry argument shows that the energy $\mathcal{E}$ is decaying (i.e., the system is dissipative).

Lemma 3.1. The functional $\mathcal{E}$ satisfies:

The proof is similar to the proof of Lemma 2.2 replacing the sums by integrals.

The decay of the energy $\mathcal{E}$ is the cornerstone to prove the flocking of the dynamics. However, in the context of the kinetic equation (3.2), we deal with a continuum of agents and therefore it is more delicate to prove that the velocity of all agents converge to a common value. We prove a $L^1$ type estimate for the decay of the velocity toward its average value. The method relies mainly on stochastic process theory.

We denote by $({\bf X}_t, {\bf V}_t)$ and $({\bf Y}_t, {\bf W}_t)$ two independent stochastic processes with probability density function $f(\cdot, t)$ solution to Eq (3.2). The energy $\mathcal{E}$ from Eq (3.5) can be written as:

and its decay as:

We first recall an elementary lemma in stochastic process theory that will be useful later. For the sake of completeness of the manuscript, we also give the proof.

Lemma 3.2. Suppose ${\bf X}_t$ is bounded uniformly in $L^2$ and that ${\bf X}_t$ converges in probability to $0$ (i.e., ${\bf X}_t \stackrel{P}{\longrightarrow} 0$). Then: ${\bf X}_t \stackrel{t \to +\infty}{\longrightarrow} 0$ in $L^1$.

Proof. First, we show that ${\bf X}_t$ bounded in $L^2$ implies that ${\bf X}_t$ is uniformly integrable. Denote $C$ the constant such that $\mathbb{E}[|{\bf X}_t|^2]\leq C$ for all $t$. We have:

using (resp.) Cauchy-Schwarz and Markov inequalities.

We now use that ${\bf X}_t \stackrel{P }{\longrightarrow} 0$ to conclude. Fix $\varepsilon > 0$:

By uniform integrability, there exists $\delta > 0$ such that:

Since ${\bf X}_t \stackrel{P}{\longrightarrow} 0$, there exists $t_*$ such that $\mathbb{P}(|{\bf X}_t| > \varepsilon/2)\leq\delta$ for $t\geq t_*$. Combined with Eq (3.9), we deduce $\mathbb{E}[|{\bf X}_t|\mathbb{1}_{\{|{\bf X}_t| > \varepsilon/2\}}]\leq\varepsilon/2$. Therefore, $\mathbb{E}[|{\bf X}_t|]\leq\varepsilon$ for $t\geq t_*$.

We now can prove our main theorem.

Theorem 3.3. Under the same assumptions of Theorem 2.5, with the additional assumption that $\inf_{s\geq 0} \phi(s) \geq c > 0$ for some $c$, the solution $f$ of Eq (3.2) satisfies:

Proof. Denote $({\bf X}_t, {\bf V}_t)$ and $({\bf Y}_t, {\bf W}_t)$ two independent stochastic processes with density distribution $f$ solution of Eq (3.2). We first show that ${\bf V}_t\!-\!{\bf W}_t \stackrel{P}{\longrightarrow} 0$. Fix $\delta > 0$ and $\varepsilon > 0$. We have to show that: $\mathbb{P}(|{\bf V}_t\!-\!{\bf W}_t| > \delta) < \varepsilon$ for a sufficiently large value of $t$.

Since the energy $\mathcal{E}$ is uniformly bounded, there exists $C$ such that $\mathbb{E}[V(|{\bf X}_t-{\bf Y}_t|)]\leq C$ for all time $t$. Since the potential $V$ satisfies Eq (2.6), there exists $L$ such that $V(r)\geq2C/\varepsilon$ for $r > L$. Now we split our estimation:

First, we find an upper-bound for $B$:

Then, we investigate $A$:

Consider $m = \inf_{r\leq L} \phi(r)\, > 0$. We have:

If $\frac{d\mathcal{E}}{dt}$ is uniformly continuous, then we have $\frac{d\mathcal{E}}{dt} \stackrel{t \to +\infty}{\longrightarrow} 0$, hence there exists $t_*$ such that $A\leq\varepsilon/2$ for $t\geq t_*$. Therefore, we conclude:

for $t\geq t_*$. Hence, ${\bf V}_t\!-\!{\bf W}_t \stackrel{P }{\longrightarrow} 0$.

Now, since the energy $\mathcal{E}$ remains uniformly bounded, we deduce that ${\bf V}_t\!-\!{\bf W}_t$ is uniformly bounded in $L^2$:

Using Lemma 3.2, we conclude that: ${\bf V}_t\!-\!{\bf W}_t \stackrel{t \to +\infty}{\longrightarrow} 0$ in $L^1$ leading to the result of Eq (3.10). To complete the proof, we have to demonstrate the uniform continuity of $\frac{d}{dt} \mathcal{E}$, which is ensured if uniformly in time bounds on the second time derivative of $\mathcal{E}$ can be obtained. Actually, this fact can be shown by mimicking the computations performed in the corresponding part of the proof of Theorem 2.5 and the computations are essentially the same. This ends the proof.

Remark 3. The reason that we need the somehow strong assumption that $\inf\limits_{s\geq 0} \phi(s) \geq c > 0$ is as follows: Similar to the computations performed in Theorem 2.5, we will have $|\frac{d^2}{dt^2} \mathcal{E}| \leq C$ for a time-independent constant $C$ if we can establish a uniform-in-time bound on $\int_{{\bf x}, {\bf v}} |{\bf v}|^3f({\bf x}, {\bf v}, t) \mathrm{d}{\bf x} \mathrm{d}{\bf v}$. Differentiating in time gives us

in which $C > 0$ is independent of time. With $\inf_{s\geq 0} \phi(s) \geq c > 0$ and Gronwall's inequality we obtain the desired uniform bound on $\int_{{\bf x}, {\bf v}} |{\bf v}|^3f({\bf x}, {\bf v}, t) \mathrm{d}{\bf x} \mathrm{d}{\bf v}$.

4.   Conclusions

In this study, we have derived sufficient conditions for the emergence of flock in a system of particles which includes attraction-repulsion and alignment interactions. The result sides with previous work on the Cucker-Smale model, but there is additional difficulty in the dynamics considered in this study, since energy estimates are insufficient to prove convergence. In particular, we do not have exponential decay towards equilibrium. However, it might be possible to obtain a stronger result, for instance by using commutator techniques ^[18,19] to compensate the lack of Gronwall-type inequality.

It would also be interesting to adapt this model to other types of collective behavior, such as milling. Of course, this would require several adjustments to our starting assumptions: one could suppose that alignment only occurs at close distances (i.e., the function $\phi$ has a compact support). Another extension would be to consider non-metric interactions such as topological distance or non-symmetric interactions (e.g., presence of leaders).

Conflict of interest

The authors declare no conflict of interest.