A cascade flocking model with feedback

1.   Introduction

Flocking behavior comes from the study of species in nature, such as migrating birds and anadromous fish. In practice, The researchers will use flocking system in artificial intelligence control and make unmanned aerial vehicle(UAV) formation flight according to the researchers' expectations by entering some hierarchical flocking models. Also, driving driverless cars is a hot topic right now. We can make a fleet of unmanned vehicles complete the task reasonably by establishing an appropriate flocking model ^[1,2,3]. Many excellent scholars have laid a solid foundation for the subject. Vicsek used alignment and bounded distance to describe flocking. The alignment means that all agents have the same direction to move, and the bounded distance means that all agents keep a finite distance from each other ^[4]. Cucker and Smale proposed an important model, which is defined as follows:

There are $N$ agents in the system. The position and the velocity of the agent $i$ are defined as $x_i(t)$ and $v_i(t)$, respectively; $a_{ij} = \frac{1}{N}\phi(\|x_{j}(t)-x_{i}(t)\|) = \frac{1}{N(\sigma^{2}+\|x_{j}(t)-x_{i}(t)\|^{2})^{\beta}}$ and the constants $\alpha, \beta, \sigma > 0$. Additionally, $\alpha$ measures the interaction strength, $a_{ij}$ is the influence function ^[5,6,7]. Inspired by the Cucker-Smale flocking model, Jackie Shen established the rates of convergence toward coherent patterns, which help us understand the advantages brought by the flocking system and show the hierarchical leadership where each follower was influenced by its superior leader ^[8]. In 2014, Motsch and Tadmor solved some disadvantages of the Cucker-Smale model and established the Motsch-Tadmor model which is famous by its non-symmetric influence ^[9]. Li and Xue made Shen's model broader to show that the superior leader influenced all followers ^[10]. Some researchers have further improved the Cucker-Smale flocking model in terms of hierarchical leadership, random interactions, asymptotic flocking dynamics and the mean-field limit ^[11,12,13].

Based on the Cucker-Smale model, Li et al. added hierarchy ranks to the model, which is called an HR model. He regarded the HR model as a self-organized system with $N$ agents ^[14]. There are $K$ ranks and the $m$-th rank $R_m$ has $N_m$ agents where $K > 1$ and $m > 1$ are both integers. For an arbitrary agent $i$ in $R_m$ we have

where $\alpha$ and $a_{ij}$ we have defined earlier.

We realize that the feedback mechanism broadly exists in the real world. For example, in primates, when a leader gives orders to a subordinate, the subordinate also gives feedback to the leader. In the driving process of an unmanned vehicle fleet, when the control terminal sends commands to all of the autonomous vehicles, it will also receive informal feedback from the autonomous vehicles to the control terminal. Significantly more, when we regard the modification of laws by human beings as a complete operation of a flocking system, we can find that leaders will also refer to the suggestions and ideas of the people at the bottom when they modify laws. However, in the past, we rarely encountered flocking models that included feedback mechanisms; instead, these models only attempted to capture the impact of the higher ranks on the lower ranks. The flocking model of agents with feedback mechanisms between various ranks in a hierarchical system will be covered in this essay. As we add the feedback mechanisms, the unilateral influence will be improved to the two-way influence, which will improve the previous flocking model to make the model more practical in real life. Additionally, we can develop a better relationship between the superior leader and the subordinate follower in the biological community. In addition, in the hot field of artificial intelligence control, the newly added feedback mechanisms can facilitate more precise positioning and control of the unmanned machine in the popular field of artificial intelligence control.

We have five models, ranging from shallow to deep. The model type can be divided into the model discussed according to dimension (Section 3) and the model discussed according to the number of ranks (Sections 4 and 5). In Section 2, we show the preparatory work, including the definition of flocking and the theorems. In Section 3, we prove the hierarchical feedback flocking model with only one individual in three ranks. In Section 4, we prove a feedback flocking model with finite agents in three ranks. In Section 5, we prove a feedback flocking model with finite agents in finite ranks.

2.   Preparatory work

The definition of flocking: flocking is a multiple-agent self-organized system's dynamic outcome, and the agents form a certain consensus regarding a process of adjusting the agent's motion state of each agent in relation to the others agent's relative motion state.

We suppose that there exist integers $K > 1$ and $N > 1$ which denote the number of ranks and the number of agents in a self-organized system, respectively. We use $dX$ and $dV$ to denote the maximum distance difference and maximum velocity difference corresponding to time $t$, respectively. If an agent $i \in R_m$ and agent $j \in R_s$ ($R_m$ means the $m$-th rank, $R_s$ means the $s$-th rank and $1 < m, s \leq N$). $x_i(t)\in R^n$, $x_j(t)\in R^n$, $v_i(t)\in R^n$ and $v_j(t)\in R^n (1\leq n < \infty)$ denote the distance of Agent $i$, the distance of Agent $j$, the velocity of Agent $i$ and the velocity of Agent $j$, respectively. Then, we have

We say that the system converges to a flock if and only if

3.   Hierarchical feedback flocking model with only one individual in three ranks

Whether at work with humans or in fleets of autonomous vehicles, we find a hierarchy in which subordinates receive orders from their superiors and give feedback to their superiors. In the past, many hierarchical flocking models seldom described the interactive process of "feedback", so we will propose a hierarchical flocking model with feedback. For the individual $"i"$, $x_i$ represents the position of the individual, $v_i$ denotes the velocity of the individual, the influence function $a_{ij} = \frac{1}{N}\phi(\|x_j(t)-x_i(t)\|), \phi(r) = \frac{1}{(1+{\|r\|}^2)^\beta}$ and $\beta > 0$. We propose a model to describe hierarchical flocking systems with feedback in three dimensions (one-dimensional, two-dimensional and three-dimensional). In between practical problems, the system may occur in two dimensions, such as driverless cars driving on the ground. Systems can also take place in three dimensions, such as the flight of a drone.

3.1.   Three ranks three agents model

Let $i\in R_1^n, j\in R_2^n, k\in R_3^n$ and $n$ be a positive finite integer. $R_1$, $R_2$ and $R_3$ denote the first rank, the second rank and the third rank, respectively.

$(x_i(t), v_i(t))$, $(x_j(t), v_j(t))$ and $(x_k(t), v_k(t))$ are the position and velocity of the only agent in $R_1$, $R_2$ and $R_3$, respectively. The parameter $\alpha (\alpha > 0)$ represents the degree of interaction between individuals in the system, and it varies in different systems. For $a_{ij}, a_{ji}$ and $a_{jk}$, they respectively represent the influence function between $R_1$ and $R_2$, $R_2$ and $R_1$ and $R_2$ and $R_3$.

$d\bar v(t)$ denotes the average of the maximum velocity difference among those three agents in this flocking system.

$\frac{d\bar v(t)}{dt} = 0$ if $dV(t) = \| v_i(t)-v_j(t) \|$ or $\| v_j(t)-v_k(t)\|$ or $\|v_k(t)-v_j(t) \|.$

$dV(t)$ denotes the maximum velocity difference in this hierarchical flocking model with feedback.

3.2.   One-dimensional space

Theorem 1. Assume ${(x_i(t), v_i(t)): x_i(t)\in R^n, v_i(t)\in R^n }$ is a solution of the system models described by (3.1)–(3.3); if $n = 1$ and the influence function $a_{ij}$ satisfies $\int^{\infty}_{0}\phi(t) = \infty$, then $\lim\limits_{t\to\infty}dv(t) = 0$ and $dX(t) < \infty$, which means that the system converges to a flock.

Proof. We assume

Then, we have

Thus,

Now, we need to discuss three cases about the maximum velocity:

1) If $dV(t) = \|v_1(t)-v_2(t)\|,$

2) If $dV(t) = \|v_2(t)-v_3(t)\|,$

(remark: $v_1(t)-v_2(t) > 0, v_2(t)-v_3(t) > 0).$

3) If $dV(t) = \|v_3(t)-v_2(t)\|,$

Since

we have

so $a_{ij}$ monotonically decreases:

The energy function is given by

$E(t)$is non-increasing.

There is a constant

Then,

For all $t\ge 0$, there is

By using Gronwall's inequality, we can get $\lim\limits_{t\to\infty}dv(t) = 0$.

3.2.1.   Example 1

In this one-dimension place system, we set three agents whose position and velocity are $(x_i(t), v_i(t))$ for $i = 1, 2$ and $3$, respectively. Let us set $\alpha = 0.5$ and $\beta = \frac{1}{3}$ and then pick the initial position and velocity randomly. When $t = 10,000$, the system converges to a flock. The simulation results are as follows:

3.3.   Two-dimensional space

Theorem 2. Assume ${(x_i(t), v_i(t)): x_i(t)\in R^n, v_i(t)\in R^n }$ is a solution of the system models described by (3.1)–(3.3); if $n = 2$ and the influence function $a_{ij}$ satisfies $\int^{\infty}_{0}\phi(t) = \infty$, then $\lim\limits_{t\to\infty}dv(t) = 0$ and $dX(t) < \infty$.

Proof. In the x direction, we denote $dv(t) \max = dv_1(t)$.

In the y direction, we denote $dv(t) \max = dv_2(t)$.

By using the triangular inequality, we can easily obtain that $dV(t) < dv_1(t)+dv_2(t)$:

We establish an energy function:

There exists a constant

Then,

For all $t\ge 0$, we have

By using Gronwall's inequality, we can get

3.3.1.   Example 2

In this two-dimension place system, we set three agents whose position and velocity are $(x_i(t), v_i(t))$ for $i = 1, 2$ and $3$, respectively. However, we separate the system in the x and y dimensions at the same time. Let us set $\alpha = 0.5$ and pick the initial position and velocity randomly. When $t = 10,000$, we can see that the system is a flock in both the x and y dimensions. The simulation results are as follows:

3.4.   Three-dimensional space

Theorem 3. Assume ${(x_i(t), v_i(t)): x_i(t)\in R^n, v_i(t)\in R^n }$ is a solution of the system models described by (3.1)–(3.3); if $n = 3$ and the influence function $a_{ij}$ satisfies $\int^{\infty}_{0}\phi(t) = \infty$, then the system converges to a flock.

Proof. We discuss the system in three dimensions:

In the x direction, we denote $dv(t) \max = dv_1(t)$.

In the y direction, we denote $dv(t) \max = dv_2(t)$.

In the z direction, we denote $dv(t) \max = dv_3(t)$.

The energy function is given by

Then,

Then,

There exists a constant $d^\ast < \infty$, where

Then,

For all $t\ge 0$, we have

By using Gronwall's inequality, we can get

3.4.1.   Example 3

In the three-dimension place system, we set three agents whose position and velocity are $(x_i(t), v_i(t))$ for $i = 1, 2$ and $3$, respectively, and we analyze it in the x, y and z dimensions. Let us set $\alpha = 0.5$ and $\beta = \frac{1}{3}$ and pick the initial position and velocity randomly. When $t = 10,000$, we can say that the system is a flock. The simulation results are as follows:

However, here is a counterexample. If we set $\alpha = 0.5$ and $\beta = \frac{2}{3}$, the system is not a flock, and the simulation results are as follows:

If $\beta > \frac{1}{2}$, the system is not a flock.

4.   Feedback flocking model with finite agents in three ranks

Lemma 1. In Model (4.2), we always have $\frac{d}{dt}dx(t) \le dv(t)$ where $dx(t)$ is the distance between two agents by time and $dv(t)$ is the velocity difference between two agents by time.

Proof. 1) For any agents $l$ and $k$, let $dx(t) = \|x_l(t)-x_k(t)\|, dv(t) = \|dv_l(t)-dv_k(t)\|$ and

2) For $dv(t)$, the velocity of Agent $i$ is $v_i(t)$, and $dv = \|v_i(t)-v_l(t)\|$

Because $\sum\limits_{j\in N+\{l\}}a_{ij} = 1,$

$\int^{\infty}_{0}\phi(r)dr = \infty$, and we have the following energy function:

So, the energy function is non-increasing and there is a constant $C > dx(0)$ such that

Because $dv(t), \alpha\frac{1}{N}, \phi(s) > 0$. When $t\in(0, \infty), dx(t) < C$ and

So,

By using Gronwall's inequality, we can get

Then,

So,

Lemma 2. In the same rank, each agent satisfies $\lim\limits_{t\to\infty}dv(t) = 0$ and $dX(t) < \infty$.

Proof. 1) We assume that there are two ranks $R_1$ and $R_2$.

Let Agents $i, j\in R_1$ and $k, l \in R_2$; then,

Remark: $a_{ii} = 1-\sum\limits_{i\in R_1, k\in R_1+R_2, k\neq i}a_{ki}, a_{jj} = 1-\sum\limits_{j\in R_1, l\in R_1+R_2, l\neq j}a_{lj}.$

Let $dv_{11}(t) = \|v_k(t)-v_i(t)\|$ and $dv_{12}(t) = \|v_i(t)-v_j(t)\|$;

Remark: $a_{ki} = \frac{1}{N_i}\phi(\|x_i(t)-x_k(t)\|), \phi(r) = \frac{1}{(1+\|r\|^2)^\beta}, \beta > 0,$

When $k = l$ and $i = j$, we have

According to Gronwall's inequality, we have

So, we have proved that each agent forms a flocking system within the same rank.

Remark: Here, we only discuss a three-rank flocking system which was composed of three agents.

We have shown that a feedback flocking system can be formed at three ranks and each rank has only one agent. Next, we need to prove a new situation that three ranks where each rank has $n (1\le n < \infty)$ agents can also form a feedback flocking system.

4.1.   Three-rank finite agents model

We regard $R_1, R_2$ and $R_3$ as a whole, and we have Agents $i, j, k, l \in R_1+R_2+R_3$, with

Theorem 4. The agents ${(x_i(t), v_i(t)): x_i(t)\in R^n, v_i(t)\in R^n }$ satisfy the model (4.2); if $\alpha > 0$ and the influence function $a_{ij}$ satisfies $\int^{\infty}_{0}\phi(t) = \infty$, then we say the agents form a flock.

Proof. Let $dX = \|x_m-x_n\|, \ m, n\in R_1+R_2+R_3$ and $dX$ denote the maximum distance between two ranks.

1) If $dv_{12}(t) = dV^\ast(t)$,

2) If $dv_{13}(t) = dV^\ast(t)$,

3) If $dv_{23}(t) = dV^\ast(t)$,

In each case, we can conclude that:

There is an energy function:

So, the function $E$ is monotonically decreasing, then we have

Because $\int^{\infty}_{0} = \infty$, there is a constant $d\ge dx(0)$ which makes

For all $t\ge 0$, we have $dx(t)\le d$.

So,

Let $C = \alpha\frac{1}{N^2}\phi^2(d)$, and we have

According to Gronwall's inequality, we have

For all $t > 0$, we have $dx(t) < \infty$ and $\lim\limits_{t\rightarrow \infty}dv(t) = 0.$

4.1.1.   Example 4

In this example, we set three ranks where the color blue represents Rank 1 with two agents, green represents Rank 2 with three agents and red represents Rank 3 with two agents. There are seven agents whose position and velocity are $(x_i(t), v_i(t))$ for $i = 1, 2, ..., 7$, respectively, and we analyze the system in the x and y dimensions. Let us set $\alpha = 0.5$ and pick the initial position and velocity randomly. When $t = 8000$, we can say that the system is a flock. The simulation results are as follows:

If $\alpha = 0.5$, $\beta = \frac{3}{4}$ and $t = 10000$, it is not a flock. The simulation results are as follows:

5.   Feedback flocking model with finite agents in finite ranks

When only $R_1$ and $R_2$ formed flocking, we added $R_3$ and proved that $R_1, R_2$ and $R_3$ also formed flocking; We set $dv(t)\le dv(0)e^{-Ct}, C = d\frac {1}{N^2}\phi^2(d)$ and a constant $d\ge dx(t)$. We assume that there are $k$ ranks and flocking is formed, and $R_{k+1}$ has been added to prove that $R_{k+1}$ forms flocking with the first $k$ flocking systems ($dv_k(t)\le\beta e^{-C_kt}, \beta$ and $C_k$ are constants). According to Gronwall's inequality, we know it is $\frac{ddv(t)}{dt}\le-\alpha\frac{1}{N^m}\phi^m(dx(t))dv$.

5.1.   Finite rank, finite agents model

There exist $n (1\le n < \infty)$ ranks and Agents $i$, $j$, $k$, $l\in R_1+R_2+...+R_n$; then,

Theorem 5. For the system model described by (5.1) which is in finite ranks with finite agents, if the influence function $a_{ij}$ has $\int^{\infty}_{0}\phi(t) = \infty$ and $\alpha > 0$, then the system converges to a flock.

Proof. We show that 1) $R_k$ and $R_{k+1}$ form flocking and 2) $R_j$ and $R_{k+1}$ form flocking $(0 < j < k)$.

We assume Agents $i, m$ and $j$ and $n$, $i\in R_k, m\in R_{k-1}+R_k+R_{k+1}, j\in R_{k+1}$ and $n\in R_k+R_{k+1}$;

We assume that the maximum displacement $dX$ in the flocking system is between the individuals $o$ and $p$. Let the distance $dX = \|x_o(t)-x_p(t)\|, 1\le o, p\le k+1$. Now we need to discuss the maximum speed difference between the two ranks across the flocking system, and then there are six situations:

a) If $max\{dv_{k, k+1}(t), dv_{k-1, k}(t), dv_{k-1, k+1}(t),$$dv_{k, k}(t), dv_{k-1, k-1}(t), dv_{k+1, k+1}(t)\} = dv_{k, k+1}(t) = dV^\star,$ then $\frac{d}{dt}dv^2_{k, k+1}(t)$

b) If $max\{dv_{k, k+1}(t), dv_{k-1, k}(t), dv_{k-1, k+1}(t),$$dv_{k, k}(t), dv_{k-1, k-1}(t), dv_{k+1, k+1}(t)\} = dv_{k-1, k}(t) = dV^\star$; then $\frac{d}{dt}dv^2_{k, k+1}(t)$

c) If $max\{dv_{k, k+1}(t), dv_{k-1, k}(t), dv_{k-1, k+1}(t),$$dv_{k, k}(t), dv_{k-1, k-1}(t), dv_{k+1, k+1}(t)\} = dv_{k-1, k+1}(t) = dV^\star$; then $\frac{d}{dt}dv^2_{k, k+1}(t)$

According to the triangle inequality, we have

d) If $max\{dv_{k, k+1}(t), dv_{k-1, k}(t), dv_{k-1, k+1}(t),$$dv_{k, k}(t), dv_{k-1, k-1}(t), dv_{k+1, k+1}(t)\} = dv_{k, k}(t) = dV^\star$, then $\frac{d}{dt}dv^2_{k, k+1}(t)$

e) If $max\{dv_{k, k+1}(t), dv_{k-1, k}(t), dv_{k-1, k+1}(t),$$dv_{k, k}(t), dv_{k-1, k-1}(t), dv_{k+1, k+1}(t)\} = dv_{k-1, k-1}(t) = dV^\star$, then $\frac{d}{dt}dv^2_{k, k+1}(t)$

f) If $max\{dv_{k, k+1}(t), dv_{k-1, k}(t), dv_{k-1, k+1}(t),$$dv_{k, k}(t), dv_{k-1, k-1}(t), dv_{k+1, k+1}(t)\} = dv_{k+1, k+1}(t) = dV^\star$, then $\frac{d}{dt}dv^2_{k, k+1}(t)$

The following holds under the condition that $dV(t)$ exists in $R_{k+1}$:

When $i, j\in R_{k+1}$ and $m, n\in R_k+R_{k+1}, dV(t) = \|v_i(t)-v_j(t)\|$,

Besides, we can know that $\frac{d}{dt}dv_{k, k}(t)\le-\alpha\frac{1}{N^2}\phi^2(dx(t))dv_{k, k}(t)$.

According to Gronwall's inequality, we have

Now we know that

Let the constant $D = \alpha\frac{1}{N^2}$ and the function $f(t) = dv(0)e^{-D\int^t_0\phi^2(2dx_{k, k+1}(t)+d^\ast)ds}.$

When the maximum velocity difference is between $R_k$ and $R_{k+1}$,

When the maximum velocity difference is in $R_{k+1}$,

When the maximum velocity difference is in the first $k$ ranks,

Between $R_1$ and $R_{k+1}$,

The energy function is given by

So, the function $E$ is monotonically decreasing; then, we have

Because $\int^\infty_0x(s)ds = \infty$, there is a constant $d_{k, k+1}\ge 2dx_{k, k+1}(0)+d^\ast$ making

Then,

Let

Then,

Let

If $dx = \infty$, then

Because

When $t > t_0$, we always have

So,

When $t\rightarrow \infty$,

However, $dv_{k, k+1}(t) > 0$, which conflicts with the formula we have.

So, for all $t\ge 0$, we can deduce that

5.1.1.   Example 5

In this example, to show finite ranks, we set five ranks, where the color blue represents Rank 1 with two agents, green represents Rank 2 with three agents, red represents Rank 3 with two agents, yellow represents Rank 4 with three agents and black represents Rank 5 with two agents. There are 12 agents whose position and velocity are $(x_i(t), v_i(t))$ for $i = 1, 2, ..., 12$, respectively, and we analyze the system in the x and y dimensions. Let us set $\alpha = 0.5$ and pick the initial position and velocity randomly. We can say that the system is a flock when $t = 8000$. The simulation results are shown in Figures 9 and 10.

Remark: Motsch and Tadmor established the Motsch-Tadmor model, which is non-symmetric, by building a differentiable function^[9]. Li and Xue considered the rooted leadership in the flocking model, and they proved that unconditional convergence is true when the conditions are satisfied by building a differentiable function ^[10]. Compared with these two models, we added a feedback mechanism, which makes it impossible to finish the proof by using the classic method, i.e., building a differentiable function. Then, we considered discussing the model in two dimensions and three dimensions according to the dimensions, and we separated the model into three different cases, i.e., three ranks with three agents, three ranks with finite agents and finite ranks with finite agents, to finish the proof sufficiently. Thus, in our proof, we used a creative method, i.e., mathematical induction, by assuming that the first k ranks form a flock and proving that the system where the newly added $R_{k+1}$ forms flocking with the first $k$ flocking systems, thus proving that a system that has finite ranks with finite individuals forms a flock. Such a feedback mechanism increases the complexity of the system and ensure agents' movement is more stable. The cascade flocking model with feedback models that we proposed can be applied in UAV groups flying and auto-driving. In the future, we will consider adding a function $f$ as a controller in this model to implement the fixed-time convergence.

6.   Conclusions

Our model further enhances the interaction between leaders and followers, as leaders and followers give each other feedback at the same time. The feedback mechanism in the model allows for more stable movement of the flocking in a hierarchical system. In the next step, we will investigate external disturbances of the model, such as free will, which allows the model to describe more complex system motions. In the model studied in this paper, we did not consider the problem of finite-time and fixed-time convergence of the system. In future studies, we will implement the fixed-time and finite-time convergence of the system by constructing a new controller. Compared with the previous models, our model has multiple leaders and a stepwise feedback system. This model is more in line with the laws and social structure of biological nature. On the one hand, there is a leadership and obedience relationship among most animals; on the other hand, the hierarchical feedback system is similar to the departmental feedback mechanism in some companies, where employees pass their opinions to their supervisors one by one.

Acknowledgments

We want to thank the National Natural Science Foundation of China. The corresponding author was supported by the National Natural Science Foundation of China (11801562).

Conflict of interest

The authors declared that they have no conflict of interest regarding this work.