On the minimum number of neighbors needed for consensus of flocks

Chen CHEN,Ge CHEN,Lei GUO?

1.Noah’s Ark Laboratory,2012 Lab,Huawei Technologies Co.Ltd,Beijing 100085,China;

2.LSC&NCMIS,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China

On the minimum number of neighbors needed for consensus of flocks

Chen CHEN1,Ge CHEN2,Lei GUO2?

1.Noah’s Ark Laboratory,2012 Lab,Huawei Technologies Co.Ltd,Beijing 100085,China;

2.LSC&NCMIS,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China

This paper investigates consensus of flocks consisting of n autonomous agents in the plane,where each agent has the same constant moving speed vnand updates its heading by the average value of the knnearest agents from it,with vnand knbeing two prescribed parameters depending on n.Such a topological interaction rule is referred to as kn-nearest-neighbors rule,which has been validated for a class of birds by biologists and verified to be robust with respect to disturbances.A theoretical analysis will be presented for this flocking model under a random framework with large population,but without imposing any a priori connectivity assumptions.We will show that the minimum number of knneeded for consensus is of the order O(logn)in a certain sense.To be precise,there exist two constants C1＞C2＞0 such that,if kn＞C1logn,then the flocking model will achieve consensus for any initial headings with high probability,provided that the speed vnis suitably small.On the other hand,if kn＜C2logn,then for large n,with probability 1,there exist some initial headings such that consensus cannot be achieved,regardless of the value of vn.

k-nearest-neighbor,consensus,topological interaction,random geometric graph

1 Introduction

Collective behavior,which is widely observed in physical,chemical,social,and biological systems,does not seem to have global information transfer among the components of the system,but the overall can display some highly ordered behavior.From a scientific point of view,how locally interacting rules lead to ordered phenomena is a basic and challenging issue to be understood.In recent years,much attempt has been made to observe,describe and model the collective behavior ranging from molecules to groups of animals,trying to find the mechanism behind these phenomena[1–24]etc.To mimic the flock of birds,Reynolds proposed a Boid model which employs three simple local interaction rules:flocking cohesive,collision avoidance and velocity alignment[1].These rules have been realized by(discrete or continuous)dynamical systems[2,3].To carry out a theoretical study on Boid model,the authors of[3,4]constructed some collective potential functions to characterize the attraction and repulsion among agents,adopted consensus algorithm to achieve velocity consensus,and provided the corresponding stability analysis.Note that in many practical systems,the velocities of the neighboring individuals tend to become parallel to each other,and such motion seems to be safe,stable and collision-free[5].Consequently,the velocity alignment or consensus problem has drown wide attention from researchers in recent years.In particular,Vicsek et al.proposed a simplified Boid model[6],which consist of n autonomous agents moving in the plane with the same constant speed and with the heading of each being updated by the average of its geometric neighbors’.This model has also been generalized to other forms together with numerical simulations,see,e.g.,[7]and[8].To analyze the so-called Vicsek’s model introduced in[6],Jadbabaie et al.[9]further simplified the Vicsek model,and initiated a theoretical study by resorting to some connectivity assumptions on the system dynamics,followed by many researchers,see,e.g.,[10]and[11].Another typical flocking model is the so-called Cucker-Smale model[12],in which the interaction between two agents is a monotonously decreasing function with respect to their distance.Some variants of this model can be found in e.g.,[13],and the convergence time of flocks has been studied in-depth in[14].

We would like to point out that,in most of the local interaction-based flocking models studied in the existing literature,the “neighbor”is often defined via the geometrical distance,that is,each agent’s neighbors are defined as the ones within a prescribed geometric distance from it,as can be seen from the models mentioned above.However,the geometric distance cannot cover all the interesting situations either practically or theoretically.

Take a group of animals for instance,as pointed out by[25],under the geometric interaction rule,once the inter-individual distance became larger than the prescribed geometric distance,there would be no interaction and stragglers would “evaporate”from the aggregation,and so,the cohesion in the case of strong perturbations or predators invasion cannot be kept.Hence,whether the practical interaction is indeed determined by a geometric distance remains to be a question.

In fact,a group of scientists has carried out an experimental observation for starlings within flocks,with a significant finding that the starlings in huge flocks interact with a fixed number(6 or 7)of nearest individuals(i.e.,“topological distance”)[25],instead of those within a given geometric distance.Moreover,they have also made comparisons with the geometric distance based rules via numerical simulations,and revealed that the topological interaction significantly outperforms the geometrical interaction towards maintaining the connectivity of the flocks.Based on this,they claimed that“topological interaction is the only mechanism granting the robust cohesion with higher biological fitness”[25].Such interaction have also been valided in[26]through establishing a maximum entropy model to empirical data.Furthermore,Ballerini et al.[25]also discussed why the neighbor’s number is 6 or 7,which may be explained as follows:on one hand,birds cannot distinguish and track too many individuals due to the limited visual capacity and this has been validated in trained pigeons[27]and shoaling fish[28].On the other hand,the number of 6–7 is the result of some optimization.In[29],the authors showed that the flock interaction networks with 6–7 neighbors optimizes the trade-off between group cohesion and individual effort.

It is worth mentioning that the topological interaction has also been studied in wireless networks,where nodes are located randomly on the plane according to a Poisson point process and each node is connected to a fixed number of nearest ones.In order to conserve energy and reduce disturbance from communication noise,it is meaningful to find the minimum number of neighbors that each node should link to,so that the overall network becomes connected.To address this issue,[30]pioneered the investigation of the connectivity of a random topological graph denoted by G(n,mn)with n nodes and mnneighbors,and successfully proved that there exist two constants 0＜c1＜c2such that G(n,c1logn)is disconnected and G(n,c2logn)is connected with high probability.This result has later been refined in[31].

Hereinafter,the topological interaction rule or the“knearest-neighbor rule”will be used exclusively in the paper.We will investigate the consensus property of flocks in the following scenario:n autonomous agents move in the plane with the same constant speed vnand with heading of each agent updated according to the av-eraged direction of its knnearest neighbors.This model is obviously related to but different from those with geometric distance based rules,including the abovementioned Vicsek’s model and its variations.

We remark that,to the best of our knowledge,there are few theoretical results on the flocking model with k-nearest-neighbor rule,although there is a vast literature on the related geometric distance based flocking models,see,e.g.,[3,4],[9–11]and[18–21].The theoretical difficulties in the current paper lie at least in the following two aspects:one is that some kind of connectivity is required in the theoretical investigation of consensus which is also adopted as a basic assumption in[3,4]and[9–11].This is a well-known “bottleneck”problem,because the topology of the flocks is timevarying and state-dependent,and thus,how to sidestep or verify the connectivity conditions turns out to be a difficult and challenging mathematical problem.Another difficulty is that the underlying topological graphs are directed due to the k-nearest-neighbor rule,and therefore a lot of nice properties with beauty of symmetry for undirected graphs are lost,which brings a big difference from the undirected case as in Vicsek’s model.Therefore,the results and methods used in[19–21]for flocks with undirected graphs cannot be directly applied here,and new methods in analyzing nonlinearly coupled dynamical flocks with directed position graphs should be developed.This constitutes one new contribution of the paper,with parts of the results presented in[22].

Next,since the neighbors number kncan be treated as a parameter of the system,then how knaffects the ordering phenomenon on earth?It is obvious that if kn=0,the system cannot achieve consensus in general whatever the speed is,but if kn=n,then consensus would be achieved immediately.Thus,it is nontrivial to ask“dose a critical neighbor number kn,or at least a critical order exist for the emergence of consensus?”From an engineering viewpoint,the critical number of neighbors also plays an important role in designing distributed cooperative control or communication networks.Recall that for a static random k-nearest-neighbor graph with n nodes to be asymptotically connected,the order Θ(logn)neighbors are kind of necessary and sufficient[30].We would then naturally expect and will actually prove that for the current nonlinear dynamical system,similar consensus results can also be established,under some conditions on the speed and initial settings.This will constitutes another original contribution of the work,with parts of the results presented in[23]without full proof.

The rest of this paper is organized as follows:some notations used in the paper are defined in Section 2.In Section3,we will present the formulation of the problem and the main results,with their detailed proofs given in Section 4 and the Appendix.A simulation example will be showed in Section 5,followed by the concluding remarks in Section 6.

2 Some basic definitions

Graph theory plays an important role in the research of dynamical network and some basic notations and concepts deserve to point out first.A directed graph(digraph)G={V,E}is composed of a vertex(or node)set V={1,2,...,n}and an edge set E={(i,j)?V×V},where(i,j)∈E is a directed edge from i to j,and also means that j is a neighbor of i.If vice versa,then G is undirected.For any vertex i∈V,if(i,i)∈E,then it is called a loop of G.A path of length l in G that joins vertexes i and j means that there is a sequence of vertexes i1,i2,...,ilsuch that(im,im+1)∈E,0≤m≤l with i0=i,il+1=j.A digraph is called strongly connected if for any two different vertexes i and j,there always exists a path from i to j.If a strongly connected graph is undirected,then it is called connected.A digraph is said to have a spanning tree if and only if there exists a vertex i∈V,called root,such that there is a path from i to any other vertex.The adjacency matrix M=(mij)n×nof graph G is a 0?1 matrix,where mij=1 if and only if(i,j)∈E.

In this article,we use the following standard notations.The symbol:=denotes definition.The set of real numbers is denoted by R and the set of non-negative integers is denoted by Z+.For a set U,|U|denotes the cardinality of U.Given t∈ R,we write t」for the value of t rounded down to the nearest integer,and 「tfor the value of t rounded up to the nearest integer.For integers n≥m≥1,Hereinafter,all logarithms are base e.

For all x∈Rdwith x:=(x1,...,xd),the so-called lpnorms of x,?·?p,are defined for 1≤p＜∞by

The l2norm is also denoted by the Euclidean norm.Let B(x,r):={y∈R2:?x?y?2≤r}denotes the ball centered at x with radius r.The following notation is quite important in our paper,we highlight it.

De fi nition 1We say that a sequence of events En,n≥1 occur with high probability(w.h.p.)if=1.Moreover,we say Enoccur with probability 1 for large n if almost surely Ecn,n≥1 only happen finite times in terms of n.

3 Model and main results

3.1 Model

Let us assume that n autonomous agents move in the plane with the same speed vn(vn＞0)but with different headings.At any time t∈Z+,the position and heading of agent i are denoted by Xi(t)(∈R2)and θi(t)(∈ (?π,π])respectively.The distance between agents i and j is denoted by dij(t):=?Xi(t)?Xj(t)?2.For any agent i(1≤i≤n),the neighbors of i are defined as the nearest knindividuals from it,where knis a prescribed value depending on n,and the neighbor set of i at t is denoted by Ni(t).If at time t,there is more than one agents who are eligible to be the kn-th nearest one from agent i,then i chooses one randomly among them.In particular,we define that each agent is a neighbor of itself.For arbitrary t∈ Z+and 1 ≤ i≤ n,the position’s updating rule for i is as follows:

This paper will mainly investigate the consensus property of the model(2)–(4).Following Tang and Guo[19],we give the definition of“consensus”.

Definition 2If there exists a constantθ ∈(?π,π]such that?1≤i≤n,then we say the model(2)–(4)achieve consensus.

3.2 Main results

For t∈Z+,let

be the set including the positions of n agents at t.To analyze the consensus behavior,we will use the following graph sequence{G(t),t=0,1,...}to describe the relationship among neighbors.For t∈Z+,define

to be the position graph of the model at t,where(i,j)∈E(t)if and only if j∈Ni(t).Note that(i,i)∈E(t)for all 1≤i≤n,since self-loop is contained.It worth mentioning that the graphs formed in this way are directed.Denote P(t)=Pn,kn(t)as the average matrix of the graph G(t),i.e.,

It can be seen immediately that P(t)is a stochastic matrix.Set θ(t):=(θ1(t),θ2(t),...,θn(t))τ,then the iteration rule of the model based on(2)and(4)can be rewritten as the following compact matrix form:

We will proceed our analysis under the assumption that the initial positions{Xi(0)∈R2,1≤i≤n}are independently and uniformly distributed in the unit square[0,1]2with the initial headings{θi(0)∈ R2,1 ≤ i≤ n}arbitrarily distributed in(?π,π].Then the position graph at the initial time instant G(0)is the random kn-nearest neighbor graph,which has been investigated in[30]and[31],etc.

Theorem 1For the flocking model(2)–(4),suppose that the initial positions of n agents are uniformly and independently distributed in the unit square[0,1]2.Then there exist some constants 0＜C2＜C1and C∈(0,1),such that the following two assertions are true:

i)If kn＞C1logn andthen the system will achieve consensus w.h.p.for arbitrary initial headings.

ii)If kn≤C2logn,then for large n with probability 1,there exist some initial headings’configurations such that the flocking model cannot achieve consensus for any speed vn≥0.

Remark 1The precise value of the constants C1,C2,C can be found from the proof of Theorem 1 in the next section.Here,we just mention that some calculations can give rough estimates for C1and C2as 50 and 0.1360,respectively.

4 Proof of Theorem 1

Theorem 1 consists of two parts whose proof will be proceeded in Section 4.1 and 4.2,respectively.

4.1 Analysis of Theorem 1 i)

Throughout the proof,all analysis will be carried out under the assumption that the positions of all the agents are independently and uniformly distributed in[0,1]2,then the initial random kn-nearest-neighbor graph will have some nice properties.

Let[0,1]2be divided equally intosmall squares whose side length is defined aspicted in Fig.1,where K＞0 is a tunable parameter.We label the small squares asleft to right,and from bottom to top.Denote bythe number among the n agents,that fall into the squareThen the following estimation for

Fig.1 The unit square[0,1]2is equally divided tosmallsquareswhicharelabeledasSin,K,i=1,2,...,Mn,K,from left to right,and from bottom to top.

Lemma 1Assume thatand let μ0∈(0,1)be the sole root of the equation

with respect with μ.Then for any μ ＞ μ0:

ProofThis result can be obtained by the method of the proof of Lemma 3.1 in[30]with slight adjustment.

Before proceeding further,define the large deviations rate function H:[0,∞)→ R by H(0)=1 and

Note that H(1)=0 and the unique turning point of H is the minimum at 1.Also H(a)is increasing on(1,∞).

For any fixed agent i,the following lemma estimates the number of agents falling into a ball centered at i,see Fig.2.

Fig.2 The ball with red boundary represents B(Xi(0),(1+

Lemma 2Suppose rn(n≥1)is a positive real number sequence satisfying πnr2n≥ 2logn.Then with probability 1,

for large n,where anis the solution to the following equation:

ProofThis result can be deduced directly from Theorem 6.14 of[32].

Lemma 3Pick arbitrary 0＜η＜1 and defineIf kn＞ C1logn with C1=(5π × 1.23)/log(4/e),then we can find some K and η such tha tand the following assertion is true:

ProofThe relationship among an,K,rK,ηand(1+η)rK,ηcan be seen in Fig.2.

Let kn≥ C1logn and set K=1/(5π×1.23),then by the value of C1,we havewhich is followed by

By computing,we have

then the condition of Lemma 2 is satisfied.Applying Lemma 2 directly,we can obtain that w.h.p.

where anis a root of H(an)Again by the value of K and C1,we have H(an)＜and we can also verify that H(1.23)＞Since H(a)is monotonously increasing on a∈(1,∞),we can get 1＜ an＜ 1.23,then there always exists some 0＜ η ＜ 1 such thatCombing this with(11),we have

From now on,when we refer to rK,η,it means the same as that in Lemma 3.Next,we define a new graph based on the agents’initial positions.

Def i nition 3

where

Remark 2Evidently,GKis undirected.By the construction of rK,η,it can be seen that(1 ? η)rK,η=which is equal to the diagonal line length of two adjacent small squares as depicted in Fig.2.We also provide an example of GKwith n=21,kn=5 in Fig.3.

Fig.3 Here is an example of G(0)and GKwith n=21 and kn=5.We use arrows(both red and blue dotted arrows)to represent edges in E(0),which are defined according to the 5-nearest-neighbor rule,where double arrows represent the mutual neighbor relationship and one-way arrows represent the unidirectional neighbor relationship.When two agents’distance is smaller thanthen there is a red double arrow between them which belong to EK.

Throughout the sequel,let kn＞ C1logn.Fix K?=1/(5π ·1.23)and η?such that Lemma 3 holds.For this K?,we can also find some μ?∈ (0,1)such that Lemma 1 holds.And the variables Ln,K?,rK?,η?are as defined in the above.The following Lemmas 4-8 are all based on this premise.

Lemma 4Suppose that kn＞C1logn,then w.h.p.GK?? G(0)and GK?is connected.

ProofAccording to Lemma 3,we obtain that w.h.p.

Then by kn-nearest-neighbor rule,we have w.h.p.

Pick arbitrary(i,j) ∈ EK?,by the construction of EK?,it can be seen that

Combining(13)with(12),we can obtain that w.h.p.for arbitrary i,j,

which means

Then we have EK?? E(0)w.h.p.,which is followed by GK?? G(0)w.h.p.

Now we prove the connectivity of GK?.Notice that GK?is actually a standard random geometric graph with radiusAnd it has been proved in[33]that the random geometric graph with radiuswill be connected w.h.p.,if and only if cn→ ∞.Hence,GK?is connected w.h.p.,by the fact that K?kn＞ 1/log(4/e).

Lemma 5Assume that there exists a virtual vertexin the center of ea chsqu areand a virtual edgeThen for arbitrary i,j,the number of virtual undirected paths with length 2(Ln,K??1)joining

The proof of Lemma 5 is given in the appendix.

Let MK?be the adjacency matrix of the graph GK?,we have:

Lemma 6Suppose that kn≥C1logn,then

where 1 is all 1’s vector.

ProofFor any i,j,represents the total number of paths from agent i to agent j in GK?with length 2(Ln,K?? 1).Assume that i and j locate inrespectively.From Lemma 5,the total number of virtual undirected path fromwith length 2(Ln,K?? 1)is at leastAnd by Lemma 1,each virtual directed path can be substituted by((1?μ?)K?kn)2(Ln,K??1)?1realpathsinGK?w.h.p.,which derives Lemma 6 immediately.

Lemma 7Suppose that kn＞ C1logn.If GK?? G(s)on s∈ Z+∩[t+1,t+2(Ln,K??1)],then w.h.p.,

ProofBy the assumption that GK?? G(s),we have M(t)≥ MK?on s∈ Z+∩[t+1,t+2(Ln,K??1)].Then Lemma 7 can be derived immediately noting that

Corollary 1Under the same condition of Lemma 7,the following inequality holds w.h.p.:

where C∈(0,1)is a computable constant only depending on K?,η?,μ?.

ProofAs n→ ∞,Ln,K?=there-Plus the fact that Ln,K?=theinequalitycanbeobtainedimmediately.

Lemma 8Suppose that kn＞C1logn.If for any i≠ j and t∈[0,T]∩Z+,the following inequality holds:

then w.h.p.GK?? G(t)for all t∈ [0,T]∩Z+.

The proof of Lemma 8 is similar to that of Lemma 3.3 in[22],so we omit it due to space limitation.

Now we are ready to prove Theorem 1 i).

Proof of Theorem 1 i)SetBy the heading iteration(4),it can be seen immediately that Δtis monotonously decreasing with respect to t.Now we prove that w.h.p.Δtis exponentially decreasing,that is,

where C∈(0,1)is defined in Corollary 1.

The main idea to prove(15)is that once vnis moderately small,GK?,as a subgraph of G(0),can be maintained as the associated dynamical position graphs G(t)evolve,therefore a generic “convergence factor”of the corresponding stochastic matrices can be estimated only with respect to GK?,then the convergence speed of Δtcan be computed.To this end,we need not only to verify the connectivity of position graphs but also to prove the headings’consensus at the same time on a bounded period of time and then repeat the process again and again.Similar proof line has been presented in[22],and we omit the details for saving space.

4.2 Analysis of Theorem 1 ii)

In this part we will give the proof of Theorem 1 ii).To achieve this,we still focus on investigating the initial position graph G(0)and try to find moderately small knsuch that G(0)is disconnected.

Some new notations are introduced first.In subsequent paper,let L(A)denote the area for the set A?R2.For a point x∈R2and a set S?R2,the distance and the biggest distance between x and S are denoted by d(x,S)respectively.Pick λ ＞ 0 arbitrarily,we write Po(λ)for any Poisson random variable with parameter λ.Define a Poisson point process Pλby Pλ:={Y1,Y2,...,YPo(λ)},where{Y1,Y2,...}is the set of points independently and uniformly distributed in[0,1]2and Pλis independently of{Y1,Y2,...}.ForasetA?[0,1]2,|Pλ∩A|,thenumber of points lying in A is a Poisson random variable with parameter λL(A).For any two sets A1,A2? [0,1]2,if L(A1∩A2)=0,then the random variables|Pλ∩A1|and|Pλ∩A2|are mutually independent.This property is called spatial independence of a Poisson point process.

The following lemma will be useful.

Lemma 9[31]Let A1,...,Arbe disjoint regions of R2and ρ1,...,ρr≥ 0 be real numbers such that ρiL(Ai)λ ∈ Z+,where λ ＞ 0.Then the probability that a Poisson process with intensity λ has precisely ρiL(Ai)λ points in each region Aiis

with the convention that 0log0=0,and log+x=max(logx,1).

We redivide[0,1]2as followes:let[0,1]2be divided equally intosmall squares with side length

where K＞0 is a tunable parameter.The small squares are labeled as Sin,K,i=1,2,...,Mn,K,from left to right,and from bottom to top.Now we construct some special position configurations,whose uses will be showed later.

Def i nition 4(Trapε

r0) We call the configuration in Fig.4 a Trapεr0.It is a semi-disk D with center on x-axis and radius 5r0,which is located in one of the bottom squares,i.e.,someSin,K,wherei=1,...,Ln,K,r0ispending.Inside D,A1is a concentric semi-disk with radius r0,and A2is a concentric semi-annulus with radii r0and 3r0.The remaining region of D is denoted by A,which is divided into N?2 small regions,i.e.,with each Aiof diameter at most εr0.

Fig.4 A Trapεr0is a semi-disk D with center on x-axis and radius 5r0.Inside D,A1is a concentric semi-disk with radius r0,and A2is a concentric semi-annulus with radii r0and 3r0.The remaining region of D is denoted∪ by A,which is divided into N?2 small regions,i.e.,with each Aiof diameter at most εr0.

Def i nition 5(the smallest cover in) For any region D′?A,define

as D′’s smallest cover in Trapεr0,see Fig.5.

Remark 3? It can be deduced immediately that L(AD′)=See Fig.5.

Fig.5 ADx∩Ais the region with the red boundary,which is composed of all the Aiintersecting with Dx∩A.

Def i nition 6(k-filling event) We say a k-filling event occurs in Trapεr0if i)|A1∩Xn(0)|≥ k,ii)|A2∩Xn(0)|=0 and iii)for arbitrary point x ∈ A,|ADx∩A∩ Xn(0)|≥ k,where Dx:=B(x,r? (1+ ε)r0)and r is the distance between x and the center of D.See Fig.6.

Fig.6 A k-filling event occurs in Trapεr0if(i)|A1∩Xn(0)|≥ k,(ii)|A2∩Xn(0)|=0 and(iii)for arbitrary point x∈A,|ADx∩A ∩ Xn(0)|≥ k,where Dx:=B(x,r? (1+ ε)r0)and r is the distance between x and the center of D.

Remark 4Intuitively,(iii)guarantees that the points in A are relatively uniform with the “average density”in each ball Dxbeing larger than k.

Lemma 10For some ε and r0,if a kn-filling event occurs in a Trapεr0,then under kn-nearest-neighbor rule,G(0)is disconnected.

Now for the bottom row squares of1,2,...,Ln,K},wheredefine the event

and another event

Intuitively,2ρ and ρ represent a kind of“densities”in A1and A,respectively,and the value of ρ can be chosen arbitrarily.Then we have

Lemma 11For small enough ε,the following assertion holds:

Set λn1:=and λn2:=.Letanddenote Poisson point processes in[0,1]2with parameters λn1,λn2,respectively.Define the event

Then we can get the following two lemmas:

Lemma 12

Lemma 13If kn＜C2logn withthen for n large enough,with probability 1.

The proofs of Lemma 10-Lemma 13 are given in the appendix.

Proof of Theorem 1 ii)In Lemma 13,we have proved that under the condition kn＜C2logn and n large enough,at least one of the bottom row squares contains a Trapεr0,in which a kn-filling event occurs.Hence,we set the initial headings of the agents in A1toand the others to beFor such case,the system cannot achieve consensus regardless of the value of vn,which completes the proof.

Remark 5The idea stems from[21]but has a key difference rooted in the different interaction rules,and a much more complicated way is needed in our case to construct the disconnected component.The design of the kn-filling event is partially inspired by[31],however we demand the configuration occur along the border of the[0,1]2due to the headings’specific configuration,while[31]does not,which makes construction design,connectivity analysis and probability computation quite different.

5 Simulations

In this section,we provide a simulation example.Here,we take the population as n=5000,and set the neighbors number kn=80logn.The initial positions and headings of the n agents are mutually independent,with positions and headings uniformly and independently distributed in[0,1]2and(?π,π],respectively.Fig.7 shows how the probability of consensus changes with moving speed.From this simulation,we see that if the speed is small,the system can achieve consensus with high probability,and the probability of consensus will tend to small as the speed increases.

Fig.7 Simulation example.

6 Conclusions

Most of the existing literature on flocks is concerned with interaction rules that are based on geometric distance in nature.In this paper,we have investigated a rather different class of flocks with k-nearest-neighbor rule.Such a topological distance-based interaction rule has been validated by biologists and verified to be robust with respect to disturbances.By overcoming the mathematical difficulties concerning with connectivity of the underlying nonlinear flocking dynamical systems,and with non-symmetry of the underlying dynamical topology resulted from the used directed k-nearest-neighbor rule,we are able to establish that the minimum number of neighbors knneeded for consensus is of the order O(logn)for large population with size n.It goes without saying that this nice result may have meaningful implications in many related fields including biology,communication and social networks.For further investigation,it is desirable to shrink the “gap”between the two constants in our main theorem,and to extend the results to more complicated anisotropic updating rules.

[1]C.W.Reynolds.Flocks,herds and schools:A distributed behavioral model.ACM SIGGRAPH Computer Graphics,1987,21(4):25–34.

[2]I.D.Couzin,J.Krause,R.James,et al.Collective memory and spatial sorting in animal groups.Journal of Theoretical Biology,2002,218(1):1–11.

[3]R.Olfati-Saber.Flocking for multi-agent dynamic systems:Algorithms and theory.IEEE Transactions on Automatic Control,2006,51(3):401–420.

[4]H.G.Tanner,A.Jadbabaie,G.J.Pappas.Flocking in fixed and switching networks.IEEE Transactions on Automatic Control,2007,52(5):863–868.

[5]C.Viragh,G.Vasarhelyi,N.Tarcai,et al.Flocking algorithm for autonomous flying robots.Bioinspiration and Biomimetics,2014,9(2):DOI 10.1088/1748-3182/9/2/025012.

[6]T.Vicsek,A.Czir′ok,E.Ben-Jacob,et al.Novel type of phase transition in a system of self-driven particles.Physical Review Letters,1995,75(6):1226–1229.

[7]P.Szab′o,M.Nagy,T.Vicsek.Transitions in a self-propelledparticles model with coupling of accelerations.Physical Review E,2009,79(2):DOI 10.1103/PhysRevE.79.021908.

[8]I.D.Couzin,J.Krause,N.R.Franks,et al.Effective leadership and decision-making in animal groups on the move.Nature,2005,433(7025):513–516.

[9]A.Jadbabaie,J.Lin,A.S.Morse.Coordination of groups of mobile autonomous agents using nearest neighbor rules.IEEE Transactions on Automatic Control,2003,48(6):988–1001.

[10]L.Moreau.Stability of multi-agent systems with time-dependent communication links.IEEE Transactions on Automatic Control,2005,50(2):169–182.

[11]W.Ren,R.W.Beard,E.M.Atkins.A survey of consensus problems in multi-agent coordination.Proceedings of the American Control Conference,Portland:IEEE,2005:1859–1864.

[12]F.Cucker,S Smale.Emergent behavior in flocks.IEEE Transactions on Automatic Control,2007,52(5):852–862.

[13]J.A.Carrillo,M.Fornasier,J.Rosado,et al.Asymptotic flocking dynamics for the kinetic Cucker-Smale model.SIAM Journal on Mathematical Analysis,2010,42(1):218–236.

[14]B.Chazelle.The geometry of flocking.Proceedings Of the 26th Annual Symposium on Computational Geometry,New York:ACM,2010:19–28.

[15]A.Okubo.Dynamical aspects of animal grouping:swarms,schools,flocks,and herds.Advances in Biophysics,1986,22:1–94.

[16]D.Gr¨unbaum,A.Okubo.Modeling social animal aggregations.Frontiers in Mathematical Biology.Berlin:Springer,1994:296–325.

[17]A.Mogilner,L.Edelstein-Keshet,L.Bent,etal.Mutual interactions,potentials,and individual distance in a social aggregation.Journal of Mathematical Biology,2003,47(4):353–389.

[18]Z.Liu,J.Han,X.M.Hu.The proportion of leaders needed for the expected consensus.Automatica,2009,47(12):2697–2703.

[19]G.Tang,L.Guo.Convergence of a class of multi-agent systems in probabilistic framework.Journal of Systems Science and Complexity,2007,20(2):173–197.

[20]Z.Liu,L.Guo.Synchronization of multi-agent systems without connectivity assumptions.Automatica,2009,45(12):2744–2753.

[21]G.Chen,Z.Liu,L.Guo.The smallest possible interaction radius for synchronization of self-propelled paricles.SIAM Review,2014,56(3):499–521.

[22]C.Chen,G.Chen,L.Guo.Synchronization ofmobile autonomous agents with M-nearest-neighbor rule.Journal of Systems Science and Complexity,2015,28(1):1–15.

[23]C.Chen,G.Chen,L.Guo.The number of neighbors needed for consensus of flocks.Proceedings of the 32nd Chinese Control Conference,Xi’an:IEEE,2013:7060 – 7065.

[24]L.Wang,X.Wang,X.Hu.Synchronization of multi-agent systems with topological interaction.Proceedings of the 18th IFAC World Congress,Milano,Italy,2011.

[25]M.Ballerini,N.Calbibbo,R.Candeleir,et al.Interaction ruling animal collective behavior depends on topological rather than metric distance:Evidence from a field study.Proceedings of the National Academy of Sciences,2008,105(4):1232–1237.

[26]W.Bialek,A.Cavagna,I.Giardina,et al.Statistical mechanics for natural flocks of birds.Proceedings of the National Academy of Sciences,2012,109(13):4786–4791.

[27]J.Emmerton,J.D.Delius.Beyond sensation:Visual cognition in pigeons.Vision,Brain,and Behavior in Birds.Cambridge:MIT Press,1993:377–390.

[28]R.W.Tegeder,J.Krause.Density dependence and numerosity in fright stimulated aggregation behaviour of shoaling fish.Philosophical Transactions of the Royal Society of London,1995,350(1334):381–390.

[29]G.F.Young,L.Scardovi,A.Cavagna,et al.Starling flock networks manage uncertainty in consensus at low cost.PLOS Computational Biology,2013,9(1):DOI 10.1371/journal.pcbi.1002894.

[30]F.Xue,P.R.Kumar.The number of neighbors needed for connectivity of wireless networks.Wireless Networks,2004,10(2):169–181.

[31]P.Balister,B.Bollob′as,A.Sarkar,et al.Connectivity of random knearest-neighbour graphs.Advances in Applied Probability,2005,37(1):1–24.

[32]M.Penrose.Random Geometric Graphs.Oxford:Oxford University Press,2003.

[33]P.Gupta,P.R.Kumar.Critical power for asymptotic connectivity in wireless networks.Stochastic Analysis,Control,Optimization and Applications.Boston:Birkh¨auser,1999:547–566.

10 September 2017;revised 9 October 2017;accepted 9 October 2017

DOIhttps://doi.org/10.1007/s11768-017-7097-7

?Corresponding author.

E-mail:lguo@amss.ac.cn.Tel.:86-10-62620724;fax:86-10-62626870.

This paper is dedicated to Professor T.J.Tarn on the occasion of his 80th birthday.

This work was supported by the National Natural Science Foundation of China(No.91427304,61673373,11688101),the National Key Basic Research Program of China(973 program)(No.2014CB845301/2/3),and the Leading Research Projects of Chinese Academy of Sciences(No.QYZDJ-SSW-JSC003).

?2017 South China University of Technology,Academy of Mathematics and Systems Science,CAS,and Springer-Verlag GmbH Germany

Appendix

Proof of Lemma 5In the following proofs,we will get rid of the subscripts from all the variablesfor the sake of convenience.

For arbitrary two virtual vertices vjand vk,we can construct an undirected path with length 2(L?1)joining vjand vk.Without loss of generality,assume that vjlies on the left of vkas illustrated in Fig.a1.We begin from vjand select virtual edges on the straight line from left to right until we arrive at right above or below vk,then we select virtual edges on the straight line from top to bottom or bottom to top.By such method,the length of the virtual path from vjto vkis not larger than 2(L?1).If the length is strictly smaller than 2(L?1),then we add a number of loops(vk,vk)to lengthen it.It worth mentioning that the loops play an important role in the proof to be seen later.Now we prove the number of such undirected paths is not smaller thanin two situations:

Fig.a1 The construction of virtual vertexes and edges.

i)vjand vklie in the opposite corners of[0,1]2respectively,for example,vjlies in the bottom-left square and vklies in the top-right square.We use a walk sequence from vjto vkto represent a path.In order to arrive at vkexactly at the 2(L?1)-th walk,each walk has to be either from left to right or from bottom to top,denoted as “→”and “↑”,respectively,and a path is determined only by the order of→and↑(For example,“→→ ···↑↑”and “→↑ ···→↑”represent different paths).For the walk sequence in demand,the number of→should be(L?1),and so is the number of↑.As a result,we can choose(L?1)walks as→among the total walks and the others as↑,with the combinatorial number

ii)vjand vkdo not lie in the opposite corners of[0,1]2.Assume that their coordinates arerespectively,where a is the side length of the square Si.Then from the construction of virtual vertices,we can deduce that|k1?j1|,|k2?j2|are both integers and min{|k1?j1|,|k2?j2|}＜L?1.In such case,in order to arrive at vkat exactly the 2(L?1)-th walk,each walk may have more choices to move,not only to right and top but also to left,bottom and itself,denoted as“←”,“↓”and “?”respectively.For convenience,we denot→,← as?,and ↑,↓ as?.Now assume that L?1 is even without loss of generality:

.If j1?k1and j2?k2are both even,then let the walk sequence from vjto vkcontain exactly(L?1)?and(L?1)?,therefore the combinatorial number is.Now the problem is converted into a new one that whether vjcan arrive at vkthrough exactly L?1?and L?1?.Since L?1 is also even,such a walk sequence can be constructed easily:it first takes k1?j1→from vjto vp,and then L?1?(k1?j1)walks from vpto vpwith→and←alternating,next takes k2?j2↑from vpto vk,and finally L?1?(k2?j2)walks from vkto vkwith↑and↓alternating,See Fig.a1.

.If j1?k1is even and j2?k2is odd,let the walk sequence contain exactly(L?1)?and(L?1)?and?,then the combinatorial number isas expected.Such path can be constructed similarly to the design above:it takes L?1?from vjto vpjust the same as above,and then take L?2?from vpto vkbecause L?1 is odd,finally we can add a?from vkto vk.

.If j1?k1is odd while j2?k2is even,then the combinatorial number of the walk sequences isusing the same analysis as above.

.If j1?k1and j2?k2are both odd,let the walk sequence contain exactly L?and(L?2)?,then the combinatorial number is

Proof of Lemma 10For any x∈A with distance r from D’s center,d(x,A1)= r? r0.Now we claim that dia(x,ADx∩A)＜ r? r0.Pick arbitrary Ai? ADx∩A,if Ai? Dx,then from the construction of Dx,we have dia(x,Ai)≤r?(1+ε)r0＜ r?r0immediately;If Ai? Dx,then a portion of Aiis outside Dx,since the diameter of Ai(3≤i≤N)is at most εr0,then dia(x,Ai)＜ r? (1+ ε)r0+ εr0＜ r? r0.Hence,the points in ADx∩Aare closer to x than the points in A1.Since|ADx∩A∩Xn(0)|≥ knby(iii),then the neighbors of x all lie in ADx∩A? A.Notice that|A1∩Xn(0)|≥ kn,then for any point in A1,its neighbors all lie in A1itself,which makes no edge between A1and A,therefore G(0)is disconnected.

Proof of Lemma 11By the definition ofit is obvious that the conditions i)and ii)of Definition 6 are satisfied,and it remains to check condition iii)of Definition 6.

Pick any x with r=3r0and ε small enough,then L(Dx∩A)≥(1/2+ δ)L(Dx)for some δ ＞ 0,independent of ε.Hence for sufficiently small ε,

If we move the point x radially outwards from the center of D,the regions Dxform a nested family.Thus L(Dx∩A)≥ 2L(A1)for all x.

From ADx∩A? Dx∩A and|Ai∩X(0)|≥ ρL(Ai),3 ≤ i≤ N,we have

which satisfies condition iii)of Definition 6.

Proof of Lemma 12Using Lemma 1.4 in[32],for large n we can get

Then by these two inequalities,

Proof of Lemma 13Now we fix the value of ρ asthen the number of points in D of ais as expected,i.e.,

Suppose that for 3 ≤ i≤ N,ρnλn1L(Ai)∈ Z(for large enough n and suitable ε,r0,this can be realized)and exactly ρnλn1L(Ai)points lie in each Aifor i≠2,then from Lemma 9 and the spatial independence of the Poisson point process,

where cnmonotonously decreases and satisfies

Note that under the conditionthere always exists some M＞0 such that for n＞M,logn and cn＜cM.Again using the spatial independence of the Poisson point process,we have for n＞M,

where we have used the inequality log(1?x)≤ ?xforx∈(0,1)and(a2).Combing this with Lemmas 11 and 12,

which is followed by

From Borel-Cantelli theorem,(a3)means that

which completes the proof of Lemma 13.

Chen CHENwas born in Shannxi,China,in 1987.She received the B.Sc.degree in Mathematics from Beihang University in 2009,and the Ph.D.degree in Control Theory from the Academy of Mathematics and Systems Science,Chinese Academy of Sciences,in 2014.She is currently a researcher at Huawei Technologies Co.Ltd.Her research interests include complex systems,distributed filters,reinforcement learning and deep learning.E-mail:chenchen9@huawei.com.

GeCHENreceived the B.Sc.degree in Mathematics from the University of Science and Technology of China in 2004,and the Ph.D.degree in Mathematics from the University of Chinese Academy of Sciences,China,in 2009.He jointed the National Center for Mathematics and Inter disciplinary Sciences,Academy of Mathematics and Systems Science,Chinese Academy of Sciences in2011,and is currently an Associate Professor.His current research interest is the collective behavior of multi-agent systems.Dr.Chen received the First Prize of the Application Award from the Operations Research Society of China(2010).One of his papers was selected as a SIGEST paper by the SIAM Review(2014).He was also a finalist for the OR in Development prize from the International Federation of Operations Research Societies(2011),and for the best theoretical paper award at the 10th World Congress on Intelligent Control and Automation(2012).E-mail:chenge@amss.ac.cn.

Lei GUOwas born in China in 1961.He received the B.Sc.degree in Mathematics from Shandong University in 1982,and the Ph.D.degree in Control Theory from the Chinese Academy of Sciences(CAS)in 1987.He is currently a professor at the Academy of Mathematics and Systems Science,CAS,and Director of National Center for Mathematics and Interdisciplinary Sciences(NCMIS),CAS.He is a Fellow of both IEEE and IFAC,Member of CAS,Foreign Member of the Royal Swedish Academy of Engineering Sciences.His current research interests include feedback capability,nonlinear and adaptive control,multi-agent systems,distributed adaptive filtering,and game-based control systems,among others.E-mail:lguo@amss.ac.cn.