# Flocking Control of Multiple Mobile Agents with the Rules of Avoiding Collision

Authors: Hongtao Zhou; Wenfeng Zhou; Wei Zeng
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper investigates the flocking and the coordinative control problems of multiple mobile agents with the rules of avoiding collision. We propose a set of control laws using hysteresis in adding new links and applying new potential function to guarantee that the fragmentation of the network can be avoided, under which all agents approach a common velocity vector, and asymptotically converge to a fixed value of interagent distances and collisions between agents can be avoided throughout the motion. Furthermore, we extend the flocking algorithm to solve the flocking situation of the group with a virtual leader agent. The laws can make all agents asymptotically approach the virtual leader and collisions can be avoided between agents in the motion evolution. Finally, some numerical simulations are showed to illustrate the theoretical results.


---

## Body

## 1. Introduction

In recent years, the problem of coordinated motion of multiple mobile agents, especially the flocking control [1–3], has attracted a lot of attention among researchers. Researchers structure a distributed model that simulates these behaviors such as flocks, herds, and schools [3–21]. The wide attention and research on this issue get a good application in biology, social behavior, statistical physics, control engineering, and other fields [2–11]. Most previous works of flocking algorithm are based on the assumption that the network topologies are always connected [12, 13]. However, in fact, it is difficult to ensure that network maintains connection at all times even if the initial network is connected [14]. Therefore, there is great realistic significance to find out an algorithm that ensures that the connectivity requirement of the network is always satisfied. Fortunately, a connectivity preserving flocking algorithm for network topologies with distributed control was studied in [14–17]. Under the condition that the initial network is connected, the author applies appropriate weight for network edge to make the network maintain connection. In [2, 16], in order to maintain network connectivity, the method of measuring the local network was applied. In [17], using the potential function method was considered. However, these methods were designed for single-integrator dynamics. In [13], the author first proposed a distributed connected algorithm for the second-order network system. With the algorithm, collisions between agents can be avoided in the motion evolution.In this work, we consider how to maintain network connectivity by constructing artificial potential function and investigating the flocking algorithm with avoiding collision rules. This algorithm is using hysteresis in adding new links [14] and applying new potential function method to maintain network connectivity. The major difference from the algorithm which was considered in [13, 15] is that we choose the new potential function. Furthermore, the situation of multiagent systems with a virtual leader is further investigated. We conclude that, in the case that the initial network is connected, the laws can make all agents approach a common velocity vector and asymptotically converge to a fixed value of interagent distances and collisions between agents can be avoided throughout the motion.The rest of this paper is organized as follows. We define the multiagent flocking problem in Section2, and some background on Graphs, Laplacian, and Reynolds model is presented in this section. In Section 3 we propose a new flocking algorithm and its results analyses are presented. Then, some numerical simulation examples are presented in Section 4. Finally, some conclusions are made in Section 5.


## 2. Problem Formulation

### 2.1. Background

In order to improve the understanding of the flocking control problem and facilitate the narrative for the next part, some basic knowledge including the undirected graphG(t), Laplacian matrix, and Reynolds model is introduced as follows.


#### 2.1.1. Algebraic Graph Theory

Assume that each agent has the same sensing radiusr, for given constants ε∈(0,r] and ε0∈(0,r), satisfying ε0≤ε. Consider the agent i as a node and use undirected edge link node i and other nodes which can be sensing. Thus, the graph consisting of a set of nodes V={1,…,N} and a time-varying set of edges E(t)={(i,j)∈V×V:i~j} can be expressed as an undirected graph G(t) at time t, and the detailed meaning is as follows [15, 22]:(i)
the initial edges are satisfied withE(0)={i,j∣si(0)-sj(0)<r,i,j∈V};(ii)
if the inequalityr≤si(0)-sj(0) is reasonable, we have (i,j)∉E(t);(iii)
ifr-ε>si(0)-sj(0) and (i,j)∉E(t-), a new edge is generated between agent i and agent j.Here,si(t) denotes the position vector of agent i and • expresses the Euclidean norm. The description of whether there exist edges between agent i and agent j at time t can use a symmetric indicator function σ(i,j)∈{0,1}, and we can describe it as follows:(1)σi,jt=k,k=0,1.Here, if ((σ(i,j)[t-]=0)∩(r-ε≤sit-sjt<r))∪(sit-sjt≥r), means that there is no edge between agent i and agent j at time t, then k=0. If ((σ(i,j)[t-]=0)∩(r-ε≤sit-sjt<r))∪(sit-sjt<r-ε), scilicet that exist edge between agent i and agent j at time t, then k=1.The above imply that a new edge will be added when the distance between the two agents is less than induction radiusr.


#### 2.1.2. Laplacian

Define the Laplacian of agenti as L=D-A, where A is the adjacency matrix of graph G(t) such that [13](2)A=aij∈Rn×n,aij=1,ifu,v∈GE0,otherwise,where D=diag{di,i∈V}, di=∑j∈Niaij, i=l,2,…,N, is the sum of ith row element of matrix A. Obviously, the sum is zero of all row elements for Laplacian. Furthermore, Laplacian is a positive semidefinite matrix that satisfies the following sum-of-squares property [14]:(3)ZTLZ=12∑i,j∈εaijzj-zi2,z∈Rn.For a given undirected graphG(t), the Laplace matrix is symmetrical, and the nonnegative adjacency matrix A satisfies AT=A.


#### 2.1.3. Reynolds Model

In 1986, Reynolds introduced three heuristic rules that led to creating the first computer animation of flocking [3]. Then, researchers used the name Reynolds model that describes the rules. The flocking algorithm that will be proposed is based on these rules. Here, we list three flocking rules of Reynolds [4].(i)
Flock centering: attempt to stay close to nearby agents.(ii)
Velocity matching: attempt to match velocity with nearby agents.(iii)
Collision avoidance: avoid collisions with nearby agents.


### 2.2. Problem Description

In our background, the Reynolds model was proposed based on the position and velocity of agents; consider a group of mobile agents moving in an-dimensional Euclidean space. Let s•i∈Rn and vi∈Rn denote the position vector and velocity vector of agent i, i=1,2,…,N, respectively. The motion equations of each agent are described by the following double integrator:(4)s•i=vi,v•i=ui,where ui∈Rn denotes the energy control input of agent i, i=1,2,…,N. The value of the position vector and the velocity vector of each agent is stored in the form of matrix; define(5)s=s1s2⋮sN,v=v1v2⋮vN.Then, the problems of flocking control can consider how to design the control input ui value, which can make all agent motion satisfy the three rules of Reynolds.The control purpose of this work is to make all agents approach a uniform velocity and asymptotically converge to a fixed value of interagent distances, and collisions can be avoided among agents in the motion evolution. Namely, for alli,j∈V, we require vi(t)-vj(t)→0 and si(t)-sj(t)→kij, and here kij∈Rn is offset constants. In general, we want the final desired formation that satisfies equation s1t=s2t=s3t=⋯=sn(t). In order to achieve this goal, the control input ui is designed as follows:(6)ui=fi+hi.And consider the situation of the group with a virtual leader agent; the control inputui in this case can be described as follows:(7)ui=fi+hi+γiwhere fi∈Rn is the gradient-base term and its action is enforced on each agent that asymptotically converges to the fixed value of interagent distances, ensures the network connectivity, and avoids collision between agents. The middle item of (7) hi∈Rn acts as a damping force, which makes every agent attempt to consistent velocity with nearby agent. And γi∈Rn is the navigational feedback term, which enforces that all agents are aware of the virtual leader.


## 2.1. Background

In order to improve the understanding of the flocking control problem and facilitate the narrative for the next part, some basic knowledge including the undirected graphG(t), Laplacian matrix, and Reynolds model is introduced as follows.


### 2.1.1. Algebraic Graph Theory

Assume that each agent has the same sensing radiusr, for given constants ε∈(0,r] and ε0∈(0,r), satisfying ε0≤ε. Consider the agent i as a node and use undirected edge link node i and other nodes which can be sensing. Thus, the graph consisting of a set of nodes V={1,…,N} and a time-varying set of edges E(t)={(i,j)∈V×V:i~j} can be expressed as an undirected graph G(t) at time t, and the detailed meaning is as follows [15, 22]:(i)
the initial edges are satisfied withE(0)={i,j∣si(0)-sj(0)<r,i,j∈V};(ii)
if the inequalityr≤si(0)-sj(0) is reasonable, we have (i,j)∉E(t);(iii)
ifr-ε>si(0)-sj(0) and (i,j)∉E(t-), a new edge is generated between agent i and agent j.Here,si(t) denotes the position vector of agent i and • expresses the Euclidean norm. The description of whether there exist edges between agent i and agent j at time t can use a symmetric indicator function σ(i,j)∈{0,1}, and we can describe it as follows:(1)σi,jt=k,k=0,1.Here, if ((σ(i,j)[t-]=0)∩(r-ε≤sit-sjt<r))∪(sit-sjt≥r), means that there is no edge between agent i and agent j at time t, then k=0. If ((σ(i,j)[t-]=0)∩(r-ε≤sit-sjt<r))∪(sit-sjt<r-ε), scilicet that exist edge between agent i and agent j at time t, then k=1.The above imply that a new edge will be added when the distance between the two agents is less than induction radiusr.


### 2.1.2. Laplacian

Define the Laplacian of agenti as L=D-A, where A is the adjacency matrix of graph G(t) such that [13](2)A=aij∈Rn×n,aij=1,ifu,v∈GE0,otherwise,where D=diag{di,i∈V}, di=∑j∈Niaij, i=l,2,…,N, is the sum of ith row element of matrix A. Obviously, the sum is zero of all row elements for Laplacian. Furthermore, Laplacian is a positive semidefinite matrix that satisfies the following sum-of-squares property [14]:(3)ZTLZ=12∑i,j∈εaijzj-zi2,z∈Rn.For a given undirected graphG(t), the Laplace matrix is symmetrical, and the nonnegative adjacency matrix A satisfies AT=A.


### 2.1.3. Reynolds Model

In 1986, Reynolds introduced three heuristic rules that led to creating the first computer animation of flocking [3]. Then, researchers used the name Reynolds model that describes the rules. The flocking algorithm that will be proposed is based on these rules. Here, we list three flocking rules of Reynolds [4].(i)
Flock centering: attempt to stay close to nearby agents.(ii)
Velocity matching: attempt to match velocity with nearby agents.(iii)
Collision avoidance: avoid collisions with nearby agents.


## 2.1.1. Algebraic Graph Theory

Assume that each agent has the same sensing radiusr, for given constants ε∈(0,r] and ε0∈(0,r), satisfying ε0≤ε. Consider the agent i as a node and use undirected edge link node i and other nodes which can be sensing. Thus, the graph consisting of a set of nodes V={1,…,N} and a time-varying set of edges E(t)={(i,j)∈V×V:i~j} can be expressed as an undirected graph G(t) at time t, and the detailed meaning is as follows [15, 22]:(i)
the initial edges are satisfied withE(0)={i,j∣si(0)-sj(0)<r,i,j∈V};(ii)
if the inequalityr≤si(0)-sj(0) is reasonable, we have (i,j)∉E(t);(iii)
ifr-ε>si(0)-sj(0) and (i,j)∉E(t-), a new edge is generated between agent i and agent j.Here,si(t) denotes the position vector of agent i and • expresses the Euclidean norm. The description of whether there exist edges between agent i and agent j at time t can use a symmetric indicator function σ(i,j)∈{0,1}, and we can describe it as follows:(1)σi,jt=k,k=0,1.Here, if ((σ(i,j)[t-]=0)∩(r-ε≤sit-sjt<r))∪(sit-sjt≥r), means that there is no edge between agent i and agent j at time t, then k=0. If ((σ(i,j)[t-]=0)∩(r-ε≤sit-sjt<r))∪(sit-sjt<r-ε), scilicet that exist edge between agent i and agent j at time t, then k=1.The above imply that a new edge will be added when the distance between the two agents is less than induction radiusr.


## 2.1.2. Laplacian

Define the Laplacian of agenti as L=D-A, where A is the adjacency matrix of graph G(t) such that [13](2)A=aij∈Rn×n,aij=1,ifu,v∈GE0,otherwise,where D=diag{di,i∈V}, di=∑j∈Niaij, i=l,2,…,N, is the sum of ith row element of matrix A. Obviously, the sum is zero of all row elements for Laplacian. Furthermore, Laplacian is a positive semidefinite matrix that satisfies the following sum-of-squares property [14]:(3)ZTLZ=12∑i,j∈εaijzj-zi2,z∈Rn.For a given undirected graphG(t), the Laplace matrix is symmetrical, and the nonnegative adjacency matrix A satisfies AT=A.


## 2.1.3. Reynolds Model

In 1986, Reynolds introduced three heuristic rules that led to creating the first computer animation of flocking [3]. Then, researchers used the name Reynolds model that describes the rules. The flocking algorithm that will be proposed is based on these rules. Here, we list three flocking rules of Reynolds [4].(i)
Flock centering: attempt to stay close to nearby agents.(ii)
Velocity matching: attempt to match velocity with nearby agents.(iii)
Collision avoidance: avoid collisions with nearby agents.


## 2.2. Problem Description

In our background, the Reynolds model was proposed based on the position and velocity of agents; consider a group of mobile agents moving in an-dimensional Euclidean space. Let s•i∈Rn and vi∈Rn denote the position vector and velocity vector of agent i, i=1,2,…,N, respectively. The motion equations of each agent are described by the following double integrator:(4)s•i=vi,v•i=ui,where ui∈Rn denotes the energy control input of agent i, i=1,2,…,N. The value of the position vector and the velocity vector of each agent is stored in the form of matrix; define(5)s=s1s2⋮sN,v=v1v2⋮vN.Then, the problems of flocking control can consider how to design the control input ui value, which can make all agent motion satisfy the three rules of Reynolds.The control purpose of this work is to make all agents approach a uniform velocity and asymptotically converge to a fixed value of interagent distances, and collisions can be avoided among agents in the motion evolution. Namely, for alli,j∈V, we require vi(t)-vj(t)→0 and si(t)-sj(t)→kij, and here kij∈Rn is offset constants. In general, we want the final desired formation that satisfies equation s1t=s2t=s3t=⋯=sn(t). In order to achieve this goal, the control input ui is designed as follows:(6)ui=fi+hi.And consider the situation of the group with a virtual leader agent; the control inputui in this case can be described as follows:(7)ui=fi+hi+γiwhere fi∈Rn is the gradient-base term and its action is enforced on each agent that asymptotically converges to the fixed value of interagent distances, ensures the network connectivity, and avoids collision between agents. The middle item of (7) hi∈Rn acts as a damping force, which makes every agent attempt to consistent velocity with nearby agent. And γi∈Rn is the navigational feedback term, which enforces that all agents are aware of the virtual leader.


## 3. Flocking Algorithms

### 3.1. Without a Virtual Leader

We have assumed that multiple mobile agents are moving inn-dimensional Euclidean space; consider the fact that the agent can only sense other agents in its epsilon neighborhood because of the limited awareness of each agent. So we define Ni(t)={j∣σi,jt=1,j≠i,j=1,…N} stand for the epsilon neighborhood of agent i at time t. The control input (6) for agent i is governed by (8)ui=∑j∈Niωijvj-∑j∈Ni∇siψsij+ωijvi,where sij=(si-sj) and weight number wij=wji>0. The ψsij where in (8) is nonnegative artificial potential function, which independent variables is the distance sij between agent i and agent j; here sij∈[0,r]. It has the following properties:(i)
the potential functionψsij achieves its unique minimum value when sij reaches a desired distance;(ii)
ifsij→0 and sij→r, the potential function ψsij→∞.We can know that no distance between agents will tend to 0 orr at all times, which implies that any two agents can attract each other and collisions can be avoided by constructing ψsij. One example to meet the above features of artificial potential function is as follows:(9)ψsij=1sij+1r-sij,sij∈0,r+∞,sij=rorsij=0.For the physical properties of the dynamic agent, we define the total energy of agent system as follows:(10)Q=-12∑i=1N∑j∈Niψsij+viTvi.It shows that Q is the sum of the total potential energy and the total relative kinetic energy among agents. Define the initial energy Q0=Q(s0,v(0)); it is easy to see that Q is a positive semidefinite function.For the convenience of description, denote the velocity and position of the center of mass (COM) of all agents as follows [22]:(11)v-=∑i=1NviN,s-=∑i=1NsiN.Considering a group ofN agents with dynamic motion (4) steered by protocol (8) in combination with the artificial potential function which we have put forward, the following conclusion can be got based on the above description.Theorem 1.
Assume that the initial energyQ0=Q(s(0),v(0)) and the initial network G(0) are finite and connected, respectively. Then, one has the main result: (i) for all t≥0, the G(t) will maintain connection; (ii) the velocity v- of the COM remains the same for all t≥0; (iii) all agents approach a uniform velocity v- and asymptotically converge to the fixed value of interagent distances; (iv) collisions among agents can be avoided.Proof.
Part one of Theorem1 is proved first. We can speculate that the topology of G(t) is fixed at the time period [tk-1,tk) under the assumption that G(t) switches at time tk(k=1,2,…,N). In view of initial energy Q0 is finite, and we obtain the time derivative of energy equation Q(t) in [t0,t1) as follows:(12)Q•t=12∑i=1N∑j∈Niψ•sij+∑i=1NviTvi•=∑i=1NviT∑j∈Ni∇siψsij-∑j∈Ni∇siψsijmiimm-∑j∈Niωijvi-vj=∑i=1NviT∑j∈Niωijvj-vi=-vTLt⊗Inv.
One hasQ•(t)≤0 in the time [t0,t1) because of the fact that L(t) is positive semidefinite [14], and it means that the following inequality is established at the time period(13)Qmax≥Q0≥Qt.
According to the definition of the artificial potential function, it is easy to knowψ(r)>Qmax≥Q0. Therefore, all existing edge-distances will not tend to r in [t0,t1) from the definition of artificial potential function, which implies that fragmentation of existing edges will be avoided at time t1. Hence, the edge number of the interaction network must be increased. The potential energy, which comes from the new edges, is a limited value because of the effect of hysteresis.
Using a similar analysis method, we can obtain the time derivative ofQ(t), and the following equation exists in time period [tk-1,tk):(14)Q•t=-vTLt⊗Inv≤0.
Based on this fact, the inequation is reasonable in[tk-1,tk)(k=1,2,…,N) as follows:(15)Qmax>Qtk-1≥Qt.It is obvious that all existing edge-distances will not tend to r in [tk-1,tk), which implies that fragmentation of existing edges will be avoided at time tk. Therefore, Qmax≥Q(tk).
According to the above analysis, we know thatG(0) is connected and no edge in E(0) will be fragmented, and it proves that G(t) maintains connection for all t≥0.
In what follows, we will give the proof procedure of parts (ii) and (iii).
Let us consider that there arenk edges being added to the dynamic network at tk; it is easy to know that(16)0<nk≤NN-12-N-1=ΔM.
From (9) and (15), we have(17)Qtk≤Q0+n1+n2+n3+⋯+nkψr-ε.Combined with (16), clearly, Qmax≥Q(t) for all time t≥0. Hence, we can define the positive invariant set Ω that goes with above analysis. Consider the following:(18)Ω=s^∈Dg,v∈RNn∣Qs^,v≤Qmax.Here, Dg={s^∈RN2n∣sij∈[0,r),∀(i,j)∈E(t)}, s^=[s11T,…,s1NT,…,sN1T,…,sNNT], and v=[v1T,v2T,…,vNT]T.
The inequalitysij≤(N-1)r is reasonable for all agents i and j under the fact that G(t) always maintains connection. From Q(t)≤Qmax, we have viTvi≤2Qmax or vi≤2Qmax, and it means that the positive invariant set Ω is compact. Note that network G(t) is a fixed topology; combining with LaSalle’s invariance principle [23], we know that the value of each solution lies in set Ω that tends to the range of the invariant set(19)S=s^∈Dg,v∈RNn∣Q•=0.
From (14), we can get(20)Q•t=-vTLt⊗Inv=12∑i,j∈Ewijvj-vi2.It is easy to see that Q• = 0 if and only if v1=v2=⋯=vN, which shows that all agents approach a uniform velocity v-.
For given conditionswij=wji and ψ(sij)=ψ(sji) and the control input (8), we have(21)u-=v-•=∑i=1NuiN=-1N∑i=1N‍∑j∈Nit∇siψsijmmmmm+∑j∈Nitωijvi-vj=0.This formula implies that part (ii) of Theorem 1 is established.
From the control input (8), we have(22)ui=v•i=-∑j∈Nit∇siψsij=-∑j∈Nit∂ψsij∂sij·1sijsi-sj,i=1,…,N.
In a stable state, clearlyv1=v2=⋯=vN=v-, which implies that vi•=v-•=0 for all i∈V. We can rewrite (22) in a matrix form such that(23)-Lt^⊗Ins=0.Here s=[s1T,s2T,…,sNT], the element of matrix L(t)^=[lij^] is lij^=∂ψsij/∂sij·1/sij, and lii^=-∑j=1,j≠NN∂ψsij/∂sij·1/sij. For a given initial network and combining the definition of Laplacian matrix L(t)^⊗In, one has s1=s2=⋯=sN, and it means that part (iii) is reasonable.
At the end of Section3, we prove part (iv). According to the set Ω={s^∈Dg,v∈RNn∣Q(s^,v)≤Qmax}, it is easy to know that Q≤Qmax for all t≥0. Hence, we can deduce that limsij→0ψ(sij)=∞ combines with the definition of artificial potential function. Thus, collisions between any two agents can be avoided.


### 3.2. With a Virtual Leader

The situation of multiagent systems (4) with a virtual leader is considered in this subsection. The control input is governed by(24)ui=-∑j∈Ni∇siψsij-∑j∈Niωijvi-vj-c1vi-vγ,where vγ denotes the velocity of the virtual leader agent and it is a constant vector. If c1=1, it means that agent i has the information of the virtual leader, and otherwise c1=0. The last item in the equation has the same role of the γi in (7).We define the total energy of agent system as follows:(25)U=12∑i=1N∑j∈Nitψsij+∑i=1Nvi-vγTvi-vγ.It shows thatU is the sum of the total interrelated kinetic energy and the total potential energy between the virtual leader and the agents of dynamic network, and it satisfies the feature of positive semidefinite function. In this work, we will choose the artificial potential function ψ(sij) which satisfies the property defined in Section 2.Similar to the analysis of flocking behavior without the virtual leader, considering a group ofN agents with dynamic motion (4) steered by protocol (24) in combination with the artificial potential function which we have put forward, we can get the following conclusion.Theorem 2.
Assume that the initial energyQ0=Q(s(0),v(0)) and the initial network G(0) are finite and connected, respectively. Then, the following hold: (i) the G(t) will maintain connection for all t≥0; (ii) all agents approach a uniform velocity vγ and asymptotically converge to the fixed value of interagent distances; (iii) collisions can be avoided between any agents; (iv) the velocity of the COM will exponentially converge to the desired velocity vγ, and the group keeps on moving with the velocity vγ all the following time.Proof.
Part one of Theorem2 is proved first.
Assume thatsi=si-vγt represents the position difference and v~i=vi-vγ represents the velocity difference between agent i of the network and virtual leader. The kinetic equation of agent i is given by(26)s~•i=v~iv~•i=ui,i=1,…,N.
According to the definition ofψ(sij), we have ψ(sij)=ψ(s~ij); therefore, the control input (24) can be rewritten as follows:(27)ui=-∑j∈Ni∇s~iψs~ij-∑j∈Niωijv~i-v~j-c1v~i.The energy equation (25) can be rewritten as follows:(28)U=12∑i=1N(∑j∈Niψ(sij))+v~iTv~i.
Referencing the proof of part (i) of Theorem1, we obtain the time derivative of energy equation U(t) at the time [tk-1,tk):(29)U•t=12∑i=1N∑j∈Niψ•sij+∑i=1Nv~iTv~•i=-v~TLt+c1IN⊗Inv~≤0.It is clear that U(t)≤0, which implied that the following inequality is existing in [tk-1,tk), (k=1,2,…,N). Consider the following:(30)Ut≤Utk-1<Umax.Hence, all existing edge-distances will not tend to radius r in [tk-1,tk), (k=1,2,…,N), which implies that fragmentation of existing edges will be avoided at time t1; thus U(tk)≤Umax. We further understand that G(0) is connected and no edge in E(0) will be fragmentated, and it ensures that G(t) maintains connection for all t≥0.
Then, we give the proof procedure of part (ii). We can get that the positive invariant set is(31)Ω=s^∈Dg,v∈RNn∣Us^,v≤Umax,where Dg={s^∈RN2n∣sij∈[0,r),∀(i,j)∈E(t)}, s~^=[s~11Ts~11T,…,s~1NT,…,s~N1T,…,s~NNT], Umax=ΔU0+(1/2N2-3/2N+1)ψ(r-ε), and v~=[v~1T,v~2T,…,v~NT]T.
The following equation is given combined with LaSalle’s invariance principle [23]:(32)U•t=-v~TLt+c1IN⊗Inv~=-v~TLt⊗Inv~-c1v~Tv~=0.Hence v~1=v~2=⋯=v~N=0, and it means that v1=v2=⋯=vN=vγ, which implies that all agents approach a uniform velocity vγ.
We now prove part (iii) of Theorem2. According to the set Ω={s^∈Dg,v∈RNn∣U(s^,v)≤Umax}, it is easy to know that U≤Umax for all t≥0. However, we can deduce limsij→0ψ(sij)=∞ from the definition of artificial potential function. Thus collisions will be avoided among agents.
At the end of this section, we will prove part (iv). We can get the following equation from the control protocol (24):(33)v-•=∑i=1NuiN=-1N∑i=1N∑j∈Ni∇siψsij+∑j∈Niωijvi-vjhhhhhhhhhhhhhhhh+c1vi-vγ∑j∈Niωijvi-vj=-c1v-+c1vγ.We can get the solution of the equation(34)v-=vγ+v-0-vγe-c1t,which implies that the initial velocity of the COM will exponentially converge to the desired velocityvγ.


## 3.1. Without a Virtual Leader

We have assumed that multiple mobile agents are moving inn-dimensional Euclidean space; consider the fact that the agent can only sense other agents in its epsilon neighborhood because of the limited awareness of each agent. So we define Ni(t)={j∣σi,jt=1,j≠i,j=1,…N} stand for the epsilon neighborhood of agent i at time t. The control input (6) for agent i is governed by (8)ui=∑j∈Niωijvj-∑j∈Ni∇siψsij+ωijvi,where sij=(si-sj) and weight number wij=wji>0. The ψsij where in (8) is nonnegative artificial potential function, which independent variables is the distance sij between agent i and agent j; here sij∈[0,r]. It has the following properties:(i)
the potential functionψsij achieves its unique minimum value when sij reaches a desired distance;(ii)
ifsij→0 and sij→r, the potential function ψsij→∞.We can know that no distance between agents will tend to 0 orr at all times, which implies that any two agents can attract each other and collisions can be avoided by constructing ψsij. One example to meet the above features of artificial potential function is as follows:(9)ψsij=1sij+1r-sij,sij∈0,r+∞,sij=rorsij=0.For the physical properties of the dynamic agent, we define the total energy of agent system as follows:(10)Q=-12∑i=1N∑j∈Niψsij+viTvi.It shows that Q is the sum of the total potential energy and the total relative kinetic energy among agents. Define the initial energy Q0=Q(s0,v(0)); it is easy to see that Q is a positive semidefinite function.For the convenience of description, denote the velocity and position of the center of mass (COM) of all agents as follows [22]:(11)v-=∑i=1NviN,s-=∑i=1NsiN.Considering a group ofN agents with dynamic motion (4) steered by protocol (8) in combination with the artificial potential function which we have put forward, the following conclusion can be got based on the above description.Theorem 1.
Assume that the initial energyQ0=Q(s(0),v(0)) and the initial network G(0) are finite and connected, respectively. Then, one has the main result: (i) for all t≥0, the G(t) will maintain connection; (ii) the velocity v- of the COM remains the same for all t≥0; (iii) all agents approach a uniform velocity v- and asymptotically converge to the fixed value of interagent distances; (iv) collisions among agents can be avoided.Proof.
Part one of Theorem1 is proved first. We can speculate that the topology of G(t) is fixed at the time period [tk-1,tk) under the assumption that G(t) switches at time tk(k=1,2,…,N). In view of initial energy Q0 is finite, and we obtain the time derivative of energy equation Q(t) in [t0,t1) as follows:(12)Q•t=12∑i=1N∑j∈Niψ•sij+∑i=1NviTvi•=∑i=1NviT∑j∈Ni∇siψsij-∑j∈Ni∇siψsijmiimm-∑j∈Niωijvi-vj=∑i=1NviT∑j∈Niωijvj-vi=-vTLt⊗Inv.
One hasQ•(t)≤0 in the time [t0,t1) because of the fact that L(t) is positive semidefinite [14], and it means that the following inequality is established at the time period(13)Qmax≥Q0≥Qt.
According to the definition of the artificial potential function, it is easy to knowψ(r)>Qmax≥Q0. Therefore, all existing edge-distances will not tend to r in [t0,t1) from the definition of artificial potential function, which implies that fragmentation of existing edges will be avoided at time t1. Hence, the edge number of the interaction network must be increased. The potential energy, which comes from the new edges, is a limited value because of the effect of hysteresis.
Using a similar analysis method, we can obtain the time derivative ofQ(t), and the following equation exists in time period [tk-1,tk):(14)Q•t=-vTLt⊗Inv≤0.
Based on this fact, the inequation is reasonable in[tk-1,tk)(k=1,2,…,N) as follows:(15)Qmax>Qtk-1≥Qt.It is obvious that all existing edge-distances will not tend to r in [tk-1,tk), which implies that fragmentation of existing edges will be avoided at time tk. Therefore, Qmax≥Q(tk).
According to the above analysis, we know thatG(0) is connected and no edge in E(0) will be fragmented, and it proves that G(t) maintains connection for all t≥0.
In what follows, we will give the proof procedure of parts (ii) and (iii).
Let us consider that there arenk edges being added to the dynamic network at tk; it is easy to know that(16)0<nk≤NN-12-N-1=ΔM.
From (9) and (15), we have(17)Qtk≤Q0+n1+n2+n3+⋯+nkψr-ε.Combined with (16), clearly, Qmax≥Q(t) for all time t≥0. Hence, we can define the positive invariant set Ω that goes with above analysis. Consider the following:(18)Ω=s^∈Dg,v∈RNn∣Qs^,v≤Qmax.Here, Dg={s^∈RN2n∣sij∈[0,r),∀(i,j)∈E(t)}, s^=[s11T,…,s1NT,…,sN1T,…,sNNT], and v=[v1T,v2T,…,vNT]T.
The inequalitysij≤(N-1)r is reasonable for all agents i and j under the fact that G(t) always maintains connection. From Q(t)≤Qmax, we have viTvi≤2Qmax or vi≤2Qmax, and it means that the positive invariant set Ω is compact. Note that network G(t) is a fixed topology; combining with LaSalle’s invariance principle [23], we know that the value of each solution lies in set Ω that tends to the range of the invariant set(19)S=s^∈Dg,v∈RNn∣Q•=0.
From (14), we can get(20)Q•t=-vTLt⊗Inv=12∑i,j∈Ewijvj-vi2.It is easy to see that Q• = 0 if and only if v1=v2=⋯=vN, which shows that all agents approach a uniform velocity v-.
For given conditionswij=wji and ψ(sij)=ψ(sji) and the control input (8), we have(21)u-=v-•=∑i=1NuiN=-1N∑i=1N‍∑j∈Nit∇siψsijmmmmm+∑j∈Nitωijvi-vj=0.This formula implies that part (ii) of Theorem 1 is established.
From the control input (8), we have(22)ui=v•i=-∑j∈Nit∇siψsij=-∑j∈Nit∂ψsij∂sij·1sijsi-sj,i=1,…,N.
In a stable state, clearlyv1=v2=⋯=vN=v-, which implies that vi•=v-•=0 for all i∈V. We can rewrite (22) in a matrix form such that(23)-Lt^⊗Ins=0.Here s=[s1T,s2T,…,sNT], the element of matrix L(t)^=[lij^] is lij^=∂ψsij/∂sij·1/sij, and lii^=-∑j=1,j≠NN∂ψsij/∂sij·1/sij. For a given initial network and combining the definition of Laplacian matrix L(t)^⊗In, one has s1=s2=⋯=sN, and it means that part (iii) is reasonable.
At the end of Section3, we prove part (iv). According to the set Ω={s^∈Dg,v∈RNn∣Q(s^,v)≤Qmax}, it is easy to know that Q≤Qmax for all t≥0. Hence, we can deduce that limsij→0ψ(sij)=∞ combines with the definition of artificial potential function. Thus, collisions between any two agents can be avoided.


## 3.2. With a Virtual Leader

The situation of multiagent systems (4) with a virtual leader is considered in this subsection. The control input is governed by(24)ui=-∑j∈Ni∇siψsij-∑j∈Niωijvi-vj-c1vi-vγ,where vγ denotes the velocity of the virtual leader agent and it is a constant vector. If c1=1, it means that agent i has the information of the virtual leader, and otherwise c1=0. The last item in the equation has the same role of the γi in (7).We define the total energy of agent system as follows:(25)U=12∑i=1N∑j∈Nitψsij+∑i=1Nvi-vγTvi-vγ.It shows thatU is the sum of the total interrelated kinetic energy and the total potential energy between the virtual leader and the agents of dynamic network, and it satisfies the feature of positive semidefinite function. In this work, we will choose the artificial potential function ψ(sij) which satisfies the property defined in Section 2.Similar to the analysis of flocking behavior without the virtual leader, considering a group ofN agents with dynamic motion (4) steered by protocol (24) in combination with the artificial potential function which we have put forward, we can get the following conclusion.Theorem 2.
Assume that the initial energyQ0=Q(s(0),v(0)) and the initial network G(0) are finite and connected, respectively. Then, the following hold: (i) the G(t) will maintain connection for all t≥0; (ii) all agents approach a uniform velocity vγ and asymptotically converge to the fixed value of interagent distances; (iii) collisions can be avoided between any agents; (iv) the velocity of the COM will exponentially converge to the desired velocity vγ, and the group keeps on moving with the velocity vγ all the following time.Proof.
Part one of Theorem2 is proved first.
Assume thatsi=si-vγt represents the position difference and v~i=vi-vγ represents the velocity difference between agent i of the network and virtual leader. The kinetic equation of agent i is given by(26)s~•i=v~iv~•i=ui,i=1,…,N.
According to the definition ofψ(sij), we have ψ(sij)=ψ(s~ij); therefore, the control input (24) can be rewritten as follows:(27)ui=-∑j∈Ni∇s~iψs~ij-∑j∈Niωijv~i-v~j-c1v~i.The energy equation (25) can be rewritten as follows:(28)U=12∑i=1N(∑j∈Niψ(sij))+v~iTv~i.
Referencing the proof of part (i) of Theorem1, we obtain the time derivative of energy equation U(t) at the time [tk-1,tk):(29)U•t=12∑i=1N∑j∈Niψ•sij+∑i=1Nv~iTv~•i=-v~TLt+c1IN⊗Inv~≤0.It is clear that U(t)≤0, which implied that the following inequality is existing in [tk-1,tk), (k=1,2,…,N). Consider the following:(30)Ut≤Utk-1<Umax.Hence, all existing edge-distances will not tend to radius r in [tk-1,tk), (k=1,2,…,N), which implies that fragmentation of existing edges will be avoided at time t1; thus U(tk)≤Umax. We further understand that G(0) is connected and no edge in E(0) will be fragmentated, and it ensures that G(t) maintains connection for all t≥0.
Then, we give the proof procedure of part (ii). We can get that the positive invariant set is(31)Ω=s^∈Dg,v∈RNn∣Us^,v≤Umax,where Dg={s^∈RN2n∣sij∈[0,r),∀(i,j)∈E(t)}, s~^=[s~11Ts~11T,…,s~1NT,…,s~N1T,…,s~NNT], Umax=ΔU0+(1/2N2-3/2N+1)ψ(r-ε), and v~=[v~1T,v~2T,…,v~NT]T.
The following equation is given combined with LaSalle’s invariance principle [23]:(32)U•t=-v~TLt+c1IN⊗Inv~=-v~TLt⊗Inv~-c1v~Tv~=0.Hence v~1=v~2=⋯=v~N=0, and it means that v1=v2=⋯=vN=vγ, which implies that all agents approach a uniform velocity vγ.
We now prove part (iii) of Theorem2. According to the set Ω={s^∈Dg,v∈RNn∣U(s^,v)≤Umax}, it is easy to know that U≤Umax for all t≥0. However, we can deduce limsij→0ψ(sij)=∞ from the definition of artificial potential function. Thus collisions will be avoided among agents.
At the end of this section, we will prove part (iv). We can get the following equation from the control protocol (24):(33)v-•=∑i=1NuiN=-1N∑i=1N∑j∈Ni∇siψsij+∑j∈Niωijvi-vjhhhhhhhhhhhhhhhh+c1vi-vγ∑j∈Niωijvi-vj=-c1v-+c1vγ.We can get the solution of the equation(34)v-=vγ+v-0-vγe-c1t,which implies that the initial velocity of the COM will exponentially converge to the desired velocityvγ.


## 4. Numerical Simulation

In this section, several numerical examples of the proposed control laws are presented to illustrate the rationality of the theoretical analysis.


### 4.1. Flocking without a Virtual Leader

The simulation is performed with 10 agents moving in a two-dimensional Euclidean space under the control protocol (8). All initial positions are chosen randomly from the plane [0,8]×[0,8], and initial velocities of the 10 agents are set with arbitrary directions and magnitudes within the plane [0,4]×[0,4]. The potential function which is selected for the control protocol (8) with the sensing radius r=4 and the switching threshold dictating is ε=0.1, the difference between r and ε is the threshold of add edges. The simulation results are shown as follows in the figures. The initial states of each agent are shown in Figure 1; the black lines represent existing neighboring relations between agent i and agent j at time t, and the blue point and the solid lines with arrows represent the multiagent and the direction of velocity, respectively. Figure 2 shows the final states of the 10 agents with the control protocol (8), which showed that all agents eventually move in the same direction. The paths and final states of the agents’ motion that evolve according to the control protocol (8) are captured in Figure 3, where the dotted line represents the path of each agent. Figures 4 and 5 describe the convergence process of the agents velocity over the x-axis and the y-axis. It is clearly known that all agents approach a uniform velocity v-. The convergence process of position over the x-axis and the y-axis is demonstrated in Figures 6 and 7. We can know clearly that all agents asymptotically converge to the stabilization of interagent distances.Figure 1
Initial states.Figure 2
Final states.Figure 3
Paths and final states.Figure 4
Velocity convergence without virtual leader (x-axis).Figure 5
Velocity convergence without virtual leader (y-axis).Figure 6
The process of position convergence forε=0.1 (x-axis).Figure 7
The process of position convergence forε=0.1 (y-axis).


### 4.2. Flocking with a Virtual Leader

This simulation is performed with a virtual leader and 10 agents moving in a two-dimensional Euclidean space under the control protocol (24). The choice of initial positions and initial velocities of the 10 agents is the same with the simulation of the flocking without a virtual leader. The initial position and velocity of the virtual leader are chosen randomly. Here we set sγ=[10,10]T and vγ=[3,3]T, respectively. The radius for interagent sensing and communication is r=4 and we will perform the simulation with ε=0.1. The initial states of each agent are shown in Figure 8; the pink hexagons represent the virtual leader and its velocity vector is described as the solid lines with arrows. Figure 9 shows the final states of the 10 agents with the control protocol (24), which showed that all agents eventually move in the same direction of the virtual leader. The paths and final states of the agents’ motion that evolve according to the control protocol (24) are captured in Figure 10. Figures 11 and 12 describe the convergence process of the agents velocity over the x-axis and the y-axis, where the dotted line represents the path of the ten agents and the red solid line represents the virtual leader, which makes it clearly known that all agents approach the velocity vγ of virtual leader and the group with the virtual leader keeps on moving at this velocity vγ all the time. The convergence process of position over the x-axis and the y-axis is demonstrated in Figures 13 and 14. These figures are in close agreement with our theoretical predictions in Theorem 2.Figure 8
Initial states with a virtual leader.Figure 9
Final states with a virtual leader.Figure 10
Paths and final states.Figure 11
Velocity convergence with a virtual leader (x-axis).Figure 12
Velocity convergence with a virtual leader (y-axis).Figure 13
The process of position convergence (x-axis).Figure 14
The process of position convergence (y-axis).


## 4.1. Flocking without a Virtual Leader

The simulation is performed with 10 agents moving in a two-dimensional Euclidean space under the control protocol (8). All initial positions are chosen randomly from the plane [0,8]×[0,8], and initial velocities of the 10 agents are set with arbitrary directions and magnitudes within the plane [0,4]×[0,4]. The potential function which is selected for the control protocol (8) with the sensing radius r=4 and the switching threshold dictating is ε=0.1, the difference between r and ε is the threshold of add edges. The simulation results are shown as follows in the figures. The initial states of each agent are shown in Figure 1; the black lines represent existing neighboring relations between agent i and agent j at time t, and the blue point and the solid lines with arrows represent the multiagent and the direction of velocity, respectively. Figure 2 shows the final states of the 10 agents with the control protocol (8), which showed that all agents eventually move in the same direction. The paths and final states of the agents’ motion that evolve according to the control protocol (8) are captured in Figure 3, where the dotted line represents the path of each agent. Figures 4 and 5 describe the convergence process of the agents velocity over the x-axis and the y-axis. It is clearly known that all agents approach a uniform velocity v-. The convergence process of position over the x-axis and the y-axis is demonstrated in Figures 6 and 7. We can know clearly that all agents asymptotically converge to the stabilization of interagent distances.Figure 1
Initial states.Figure 2
Final states.Figure 3
Paths and final states.Figure 4
Velocity convergence without virtual leader (x-axis).Figure 5
Velocity convergence without virtual leader (y-axis).Figure 6
The process of position convergence forε=0.1 (x-axis).Figure 7
The process of position convergence forε=0.1 (y-axis).


## 4.2. Flocking with a Virtual Leader

This simulation is performed with a virtual leader and 10 agents moving in a two-dimensional Euclidean space under the control protocol (24). The choice of initial positions and initial velocities of the 10 agents is the same with the simulation of the flocking without a virtual leader. The initial position and velocity of the virtual leader are chosen randomly. Here we set sγ=[10,10]T and vγ=[3,3]T, respectively. The radius for interagent sensing and communication is r=4 and we will perform the simulation with ε=0.1. The initial states of each agent are shown in Figure 8; the pink hexagons represent the virtual leader and its velocity vector is described as the solid lines with arrows. Figure 9 shows the final states of the 10 agents with the control protocol (24), which showed that all agents eventually move in the same direction of the virtual leader. The paths and final states of the agents’ motion that evolve according to the control protocol (24) are captured in Figure 10. Figures 11 and 12 describe the convergence process of the agents velocity over the x-axis and the y-axis, where the dotted line represents the path of the ten agents and the red solid line represents the virtual leader, which makes it clearly known that all agents approach the velocity vγ of virtual leader and the group with the virtual leader keeps on moving at this velocity vγ all the time. The convergence process of position over the x-axis and the y-axis is demonstrated in Figures 13 and 14. These figures are in close agreement with our theoretical predictions in Theorem 2.Figure 8
Initial states with a virtual leader.Figure 9
Final states with a virtual leader.Figure 10
Paths and final states.Figure 11
Velocity convergence with a virtual leader (x-axis).Figure 12
Velocity convergence with a virtual leader (y-axis).Figure 13
The process of position convergence (x-axis).Figure 14
The process of position convergence (y-axis).


## 5. Conclusion

In this paper, we have investigated the flocking and the coordinative control problems of mobile autonomous agents with preserved network connectivity and proposed the flocking algorithm with avoiding collision rules. This algorithm has proposed using hysteresis in adding new links and applying new potential function method to ensure that the network always stays connected and collisions between agents can be avoided. The extended application of the flocking algorithm with a virtual leader has been investigated. The simulation has proved that the laws can make all agents approach a common velocity vector and asymptotically converge to the fixed value of interagent distances and collisions between any agents can be avoided throughout the motion. The laws also satisfy the situation that there exists a virtual leader in the group of all agents, and it is proved that the value of desired velocity of the group is the same as that of the virtual leader. Future work will pay attention to the situation of how to make the network topology be connected as the initial network is not satisfied.



---

*Source: 529538-2015-09-03.xml*