含生成森林有向图的零特征值及在编队控制中的应用

李修贤 李 莉 谢立华

(1.同济大学 电子与信息工程学院 控制科学与工程系 上海自主智能无人系统科学中心上海智能科学与技术中心,上海 200240;2.同济大学高等研究院,上海 220240;3.南洋理工大学电气与电子工程学院,新加坡 999002)

Graph theory,as an important research topic,is of interest in its own right[1].In the meantime,it is also well known that graph theory is one powerful tool in distributed control (e.g.,formation control)[2-7],distributed (online) optimization[8-11],and multi-agent operators[12],and so forth,where a family of agents exists over a multi-agent network,who may be dispersed geographically and hold their own private information on a global mission,and the objective is for all agents to communicate with their neighbors through local information exchange in order to accomplish the global mission.In these problems,each agent is viewed as a node or vertex,the information flow is delineated by directed edges,and thereby the communication pattern among all agents can be captured by directed or undirected graphs.To ease the exposition,all those problems over multi-agent networks,where the interconnection of all agents is described as directed or undirected graphs,are collectively referred to as multi-agent problems.

For the aforementioned problems with underlying directed or undirected communication graphs,one important notion is the so-called Laplacian matrix(closely related to the adjacency matrix),which plays a pivotal role in the convergence of distributed controllers or algorithms in multi-agent problems.It is well known that all eigenvalues of the Laplacian matrix are nonnegative for undirected graphs,where all communication edges are bidirectional,and all real parts of eigenvalues of the Laplacian matrix are nonnegative for directed graphs,where each interaction edge may be unidirectional[2].Meanwhile,an important fact is that zero must be an eigenvalue of the Laplacian for both undirected and directed graphs[2].Furthermore,as an essential matrix,it has been shown that the multiplicity of the zero eigenvalue of the Laplacian matrix plays a significant role in determining the goal achievement for multi-agent problems.To be specific,the simplicity of its zero eigenvalue determines the achievement of consensus and so on,in which case it requires that undirected graphs (resp.directed graphs)are connected(resp.have a directed spanning tree)[2].Regarding connected undirected graphs,the smallest positive eigenvalue is usually called the algebraic connectivity,which often determines the convergence speed for consensus[13-14],and meanwhile,as for directed graphs with a directed spanning tree,the smallest real part of its nonzero eigenvalues,in some sense,also impacts the convergence speed for consensus[15-16].

As discussed above,the connectivity for undirected graphs and directed spanning tree for directed graphs are crucial in multi-agent problems,which are necessary and sufficient for the simple multiplicity of zero eigenvalue of the Laplacian matrix associated with undirected and directed graphs,respectively[2].However,what happens if graphs are not connected or do not have a spanning tree? For example,a connected comunication graph is attacked by insidious attackers or some communication edge is obstructed by some obstacles,and then the communication graph may be deformed to be unconnected even if it is connected at the beginning.As a result,it is important and practical to investigate the case where communication graphs are not connected or do not have a spanning tree.Along this line,for an undirected communication graph,it has been shown in[17]that the multiplicity of the zero eigenvalue of the Laplacian matrix is equal to the number of the connected components of the communication graph.However,it is yet to be studied for directed graphs,to our best knowledge,which is of also interest in its own right.

With the above motivation,this paper aims to investigate the multiplicity of the zero eigenvalue of the Laplacian matrix for directed graphs,which do not have a spanning tree in general.To address this issue,directed graphs that havem-spanning forest are taken into account for an integerm≥1,which include directed graphs with a directed spanning tree as a special case whenm1.In summary,the contributions of this paper lie in two facets as follows.

1) This paper shows for the first time that the multiplicity of the zero eigenvalue of the Laplacian matrix for a directed graph is equal to the number of spanning forests in the graph.Generally speaking,it extends the directed graph case with a directed spanning tree to a more general case.

2) The obtained result is applied to formation control for single-integrator multi-agent systems,for which it is shown that the achieved formation shape lies in the kernel space of the Laplacian matrix associated with the communication graph,thus called kernel formation.

The rest of this paper is organized as follows.Section 2 presents some useful notions and basic yet important results.Section 3 gives the main result of this paper.Section 4 provides an application to formation control.Section 5 provides an example for formation control,and the conclusion is finally given in Section 6.

2.1 Notations

Let us defineIk:{1,2,...,k}for an integerk＞0,and denote by Rn,Cnthen-dimensional real and complex Euclidean space,respectively.diag{a1,a2,...,an}(resp.diag{A1,A2,...,An})represents a diagonal matrix with diagonal scalar entriesak(resp.a blockdiagonal matrix with diagonal matrix entriesAk) for.For a complex numberz,denote by Re(z),Im(z),|z|the real part,imaginary part and modulus forC,respectively.ForRn×n,let rank(X),det(X)be the rank and determinant ofX,respectively.LetInbe then×nidentity matrix,and 0n(resp.1n)be then-dimensional column vector of all entries 0(resp.all entries 1)orn×nzero matrix.||.||and⊗stand for the standard Euclidean norm and the Kronecker product,respectively.

2.2 Graph theory

Denote by a directed graph(or digraph)G(V,E)withNnodes,consisting of the node setVand the edge setE,where an element(j,i)is called an edge,indicating the information flow from nodejto nodei(in this case,jis called a neighbor or parent of nodei).Self-loops are not allowed.Denote the neighbor set of nodeiasNi{j:(j,i)i}.In a directed graph,a directed path(resp.weak path)is comprised of a sequence of adjacent edges in the form(i1,i2),(i2,i3),...,(ik-1,ik),abbreviated asi1,i2,...,ik,such that(il,il+1)(resp.(il,il+1)or(il+1,il))for1.A directed graph is called a directed tree if except one node,called the root,every node has exactly one parent.Additionally,a directed graph is said to have a directed spanning tree if a subgraph of the directed graph,consisting of all its nodes and some edges,is exactly a directed tree.

The adjacency matrixA(aij)RN×Nis defined as:aij ＞0 if,andaij0 ()otherwise.Setaii0 for all.Moreover,the Laplacian matrixL(lij)RN×Nis defined asandlij-aijfor.

To proceed,the following concepts are necessary in this paper.

Definition 1A directed graph is called anmforest,if the graph consists ofmdisjoint components and each component is a directed tree.

Definition 2A directed graph is said to have a spanningm-forest if some subgraph of the graph is anm-forest,and meanwhile no subgraph of the graph is ak-forest for any integer 0＜k≤m-1.

Regarding a collection ofNnodes,a configuration in Rnis defined asp,piRnfor,(i.e.,a column vector).If equipping with a graphG,then a configuration in Rnis called a framework in Rn,denoted byF(G,p).Moreover,a configurationpin Rnis called generic if any algebraic equations do not hold for all entries ofpi,i INover the rational numbers[18-20],that is,there does not exist any nonzero polynomialP(z1,z2,...,znN) with rational coefficients such thatP(p11,...,p1n,...,pN1,...,pNn)0,wherepijis thejth entry ofpi.Intuitively speaking,a generic configuration is not degenerate (e.g.,no three points are positioned on a straight line).

2.3 An useful lemma

The following lemma is useful for the ensuing analysis.

Lemma 1[21] For a directed graph,zero is an eigenvalue of the Laplacian matrixLassociated with the eigenvector 1Nand all other eigenvalues are with positive real parts.Moreover,zero is a simple eigenvalue if and only if the graph has a spanning tree.

In view of Lemma 1,it is known that zero eigenvalue of the Laplacian matrix is simple if and only if the graph has a spanning tree.However,what about the situation where the graph does not have a spanning tree?Note that a graph may be degenerated due to malicious attacks or unexpected obstacles,etc.In this respect,a worse scenario than having a spanning tree,i.e.,having a spanning forest,is investigated in this paper.

To answer this question,the main result of this paper is given as follows.

Theorem 1For a directed graph with nonnegative weights,its LaplacianLhas preciselymzero eigenvalues if and only if the graph has a spanningmforest.Meanwhile,all nonzero eigenvalues ofLhave positive real parts.

ProofIn light of Lemma 1,it is known that all nonzero eigenvalues ofLhave positive real parts.Therefore,it remains to show the first part of this lemma.

(Sufficiency)To start,consider a special case when the graphGitself is anm-forest.In this case,one can renumber the nodes in the following order.Relabeling the nodes in the first component ask01 tok1in an arbitrary order if the first component hask1nodes.Similarly,one can relabel the nodes in thelth component as+1+klif thelth component hasklnodes,l2,...,m.Denoting byL1the new Laplacian matrix,it is known that there exists a permutation matrixPsuch thatL1PTLP[22].In the meantime,it is easy to see thatL1is block-diagonal in the formL1diag{L11,...,L1m},whereL1k,k Imis actually the Laplacian matrix corresponding to thekth component.In view of linear algebra,the eigenvalues ofL1exactly equal the set of eigenvalues ofL1kfor all.Note that thekth component for allis composed of a tree.By virtue of Lemma 1,eachL1khas exactly one zero eigenvalue and all other eigenvalues have positive real parts.Consequently,L1has exactlymzero eigenvalues and rank(L1)Nm,so doesLsince they are similar.

Up to now,it has been shown that the first part of this lemma holds for anm-forest.It should be noticed that every directed graph,which has a spanningmforest,can be obtained by consecutively adding edges to one of itsm-forest subgraph.Therefore,the sufficiency part can be proved if the result holds for every new graph by adding one edge each time to previous one with one initialm-forest subgraph,denoted byG0,of graphGuntil to the whole graphG.

Assume thatB(bij)RN×Nis obtained by adding a new edge (r,s) toG(gij)RN×Nassociated with graphG0.Then,one hasbsr-esr,bssgss+esrandgsr0,whereesr＞0 is the weight corresponding to the new edge (r,s).DefineG(λ)(gij(λ)) :λIN -GandB(λ)(bij(λ)) :λIN -B.Considering the characteristic polynomial ofB,one can obtain that

whereMij(Q) means the (i,j) minor for a matrixQ,that is,it is the determinant of the submatrix ofQby removing theith row andjth column,and we have used the fact thatbsr(λ)gsr(λ) +esr,bss(λ)gss(λ)-esr,andMsi(B(λ))Msi(G(λ)) for all.

Consider now the matrixT1given in (2) (without loss of generality,lets ＜r).DefineT1(λ)(t1ij(λ)):λIN -T1.In view of determinant’s property,it is easy to see that

which together with(1)follows

Observing carefully the structure ofT1,it can be seen that the graph associated with LaplacianT1is amforest.As a result,T1has exactlymzero eigenvalues.Consequently,applying Vieta’s formulas yields that

whereλi(Q) denotes theith eigenvalue of a matrixQin the ascending order of real parts,andgk(Q)is the coefficient ofλkin the characteristic polynomial of matrixQ.Thus,one has

Meanwhile,it is known thatGhas exactlymzero eigenvalues since its associated graph is anm-forest,which,invoking Vieta’s formulas,implies

At this point,for coefficientgk(B)1for matrixB,in view of(4)one can easily see that

As for the coefficientgm(B) ofλmfor matrixB,we consider two different cases for the parity ofN-m-1.

Case 1:N-m-1 is even.Inequality(6)results ingm(T1)≥0.Meanwhile,N-mis odd in this case and thereby it follows from inequality(7)thatgm(G)＜0.Hence,in view of(4)it is easy to see thatgm(B)＜0.

Case 2:N-m-1 is odd.Similarly,one can show thatgm(B)＞0.

In both cases,it can be concluded thatgm(B)0,which together with(6)and(7)leads to thatBhas exactlymzero eigenvalues.

To move forward,when adding another new directed edge to the previous graph associated withB,all are kept the same except that in this step the graph associated with LaplacianT2(defined similarly toT1) is with the structure: anm-forest with a new added edge,which has exactlymzero eigenvalues as shown in last step,(i.e.,at leastmzero eigenvalues).The above process can be continued by adding a new directed edge until to obtain the graphG.This ends the sufficiency part.

(Necessity) Let us prove it by contradiction.If it does not contain a spanningm-forest,then there exist two cases.The first one is that the graph contains a spanningm1-forest for somem1＜m.With regard to this case,following the same line in sufficiency part one can see that the Laplacian has exactlym1zero eigenvalues,which is a contradiction.The second case is that the graph contains a spanningm2-forest for somem2＞m.Similarly,it can be concluded that the Laplacian has exactlym2zero eigenvalues,which is also a contradiction.This completes the necessity part.

Remark 1It should be noted that,to our best knowledge,this paper is the first to establish the result in Theorem 1,which can be actually viewed as an extension of the case where the graph has a spanning tree(see Lemma 1),i.e.,whenm1 in Theorem 1.Moreover,it is worth mentioning that even though a communication graph indeed has a spanning tree at the beginning,it may not be the case at other times,which may occur due to insidious attacks or communication blocking by obstacles between two agents,for example,in distributed control,(online)optimization,multi-agent operators.Additionally,this problem is of independent interest as a theoretical research direction.

This section aims at applying the result in Theorem 1 to formation control.Towards this end,the following single-integrator multi-agent network,consisting ofNagents,is addressed

wherexi,uiRnare the state and input(or controller)of agenti,respectively.For this network,as done in[19,23-24] for affine formation,the controller is designed by only using the measurement of relative positions as follows:

which leads to that network(9)can be written in a compact form

wherexis the concatenated statex:()T.

To proceed,let us concentrate on dynamic formation control for network(11).Given a desired dynamic configurationp(t)(p1(t)...pN(t))T,pi(t)Rn,the configurationp(t) is said to be realizable (resp.achievable or stabilizable)under the directed graphGif a time-varying LaplacianL(t)corresponding toGexists such that(L(t)⊗In)p(t)0(resp.the state of network (11) can converge top(t)).It will be shown that a dynamic configuration can be achieved in some sense,if the communication graph has a spanningm-forest form≥2.

In the sequel,static configuration is first considered and dynamic one will be discussed later.It is easy to see that a configuration can be achievable only if it is in the kernel ofL ⊗In,which is determined by the kernel ofLsince zero eigenvalues only originate fromL.In fact,the essence of the Laplacian approach lies in confirming the number of zero eigenvalues of the LaplacianL.

It is now ready to analyze static formation control.It is well known that all agents will achieve consensus,i.e.,converging to the set{xiRn,i IN:x1x2...xN},if the directed graph has a spanning tree.Note that having a spanning tree is equivalent to having a spanning 1-forest.What if the directed graph has a spanning 2-forest? In light of Theorem 1,the Laplacian has exactly two zero eigenvalues,and thereby the weightsaijcan be selected to satisfy thatLhas two linearly independent eigenvectors associated with zero eigenvalue.Given a graphGhaving a spanningmforest,it is always feasible thatLcan be chosen for havingmlinearly independent eigenvectors in the eigenspace associated with zero eigenvalue (amounting to dim(ker(L))m,where dim(.)and ker(.)mean the dimension and kernel of a linear space,respectively),and the reason is as follows: 1)it is true for the Laplacian of anm-forest which can be seen from the proof of Theorem 1,i.e.,rank(L)N -m;2)after randomly selecting onem-forest subgraphG0ofG,all weights of those edges,which do not belong toG0,are viewed as variables in[0,+∞),and hence the determinant of a submatrix ofLbecomes a polynomial with aforementioned variables;3)it is well known that a nonzero polynomial does not equal zero almost everywhere.As a consequence,by selecting edge weights it can always be ensured that rank(L)N -mif the graph has a spanningm-forest,which results in dim(ker(L))m,and the set of weights that make this infeasible in fact has Lebesgue measure zero.

Now,coming back to the case when the graph has a spanning 2-forest,the LaplacianLcan be selected to have two linearly independent eigenvectors associated with zero eigenvalue.Since 1Nis an eigenvector corresponding with zero eigenvalue,there exists another eigenvectorv1(v11...v1N)TRN,linearly independent of 1N,such thatLv10.As a result,the kernel ofLhas the formc1v1+c21Nforc1,c2R.It should be noted thatc21Nwill not make an effect on the formation shape since it means physical translations of the formation shape.Consequently,the formation shape is utterly determined byc1v1,which together with network (11) follows that the final formation configuration is determined byc1v1⊗αforRn,which is actually a line-shape becausec1v1⊗α(c1v11αT...c1v1NαT)T.For example,letN4 andn3,ifv1(1 2 3 4)Tandc11,thenc1v1⊗α(αT2αT3αT4αT)Tfor a vectorR3,forming a straight line if03.Of course,in this case it is possible for some components ofv1to have the same value,leading to that some agents finally stay in the same position,which is simultaneously determined by the structure of the graph and the selection of edge weights.

Along the line,if one desires to achieve a formation configuration that is not a line-shape,it is necessary for the graph to have a spanningm-forest,wherem≥3.In the following,we assume that the interaction graphGhas a spanningm-forest,m≥3.Given a desired formation configurationpRn,one way to ensure that multi-agent network(11)can achieve the configurationpis to design the edge weightsaij’s as follows:

which can be done in a distributed means by resorting to distributed optimization as done in[19].However,one drawback is that this way is not always feasible,that is,there exist configurationsp’s that cannot be achieved by selecting any edge weights.But this problem can be solved by using real weights(i.e.,negative weights are allowed)in a generic sense(e.g.,see[19]).

Regarding a graph having a spanningm-forest,m≥3,the LaplacianLin general has several eigenvectors in its kernel space which are linearly independent of the eigenvector 1N.Let us denote these eigenvectors asv11N,v2,...,vm(here there aremlinearly independent eigenvectors that are viable by the foregoing argument).In this regard,as shown before,the main claim of this section is:

Note that any linear combination ofv2...vmis in the kernel ofL,thus called kernel formation for (11).However,the different linear combination ofv2...vmwill generally give rise to different formation shapes,thus leading to different formation shapes from the desired one.That is,a desired configurationpcan be achieved after properly selecting edge weights by(12),although a possibility exists for that the configurationpcannot be accurately achieved.For example,if a square shape in R2space can be achieved by appropriately computing weights via (12),by the same weights the ultimate formation shape that multi-agent network(11)will converge to may be a parallelogram,instead of a square.However,the advantage is that when an underlying communication graph that has a spanning tree is attacked such that the structure of spanning trees is destroyed,resulting in a spanning forest structure,the aforementioned result provides theoretical insight into the possible deformed formation shapes.

So far,static formation control has been discussed.With regard to dynamic formation control,given a dynamic configurationp(t)Rn,under suitable conditions it can also be handled by computing the equation(12)with time-varying weightsaij(t)’s.However,it will encounter the same problem as mentioned above.

This section provides an example to illustrate the application to formation control,as discussed in Section 4.

Example 1Consider the multi-agent network(11)consisting ofN4 agents with the state of each agent being in R2space.The communication graph is given by Fig.1,and it is easy to see that the communication graph has a spanning 3-forest.In addition,the desired formation shape is shown in Fig.2(a),which is bilaterally symmetrical.Specifically,one configuration of the desired shape is given in Fig.2(b),wherep()Twith

Fig.1 The interaction graph in Example 1

Fig.2 (a)Desired formation shape and(b)one corresponding configuration

Inserting the configurationpinto(12)yields that

In this case,randomly selecta412,a42a431.Note that all other weights are zero.Therefore,the LaplacianLis of the form

That is to say,by the Laplacian in(16)the desired configurationpis achievable for multi-agent network(11).

After some calculations,it is easy to obtain that a basis of the subspace ker(L)can be chosen as

As a result,any linear combination ofv1,v2,v3lies in the subspace ker(L),and furthermore any linear combination ofv1⊗b1,v2⊗b2,v3⊗b3is in the kernel ofL⊗I2,wherebiR23is arbitrary.For instance,letb1(1 0)T,b2(1/2 0)T,b3(1/2 1/2)T,and then one hasq:v1⊗b1+v2⊗b2+v3⊗b3(1 0-1/2 2 1/2 0 1/2 1/2)T,whereq()T,qiR24.It means that network(11)maybe converges to the configurationqwith

For example,if the configurationqis the initial state,then the agents will stay where they are in the configurationq,althoughqis different from the desired configurationp.The configurationqis shown in Fig.3,from which it is easy to see that the spatial shape with configurationqis different from that withp,which is consistent with the theoretical discussion in Section 4.

Fig.3 The configuration q in Example 1

The multiplicity of zero eigenvalue of the Laplacian matrix has been investigated for directed graphs that have a spanning forest,a more general case than having a spanning tree.For example,this case may arise when this network undergoes insidious attacks or encounters unexpected obstacles,even though the communication graph for all agents indeed has a spanning tree at the beginning.In fact,as a scientific problem,it is of also interest in its own right,as an extension of the case where a directed graph has a spanning tree.To address this problem,a necessary and sufficient condition has been established for confirming the multiplicity of the zero eigenvalue for the Laplacian matrix.In addition,the obtained result has also been applied to formation control,ensuring that a desired formation shape can be achieved in some sense.To be specific,the final formation shape is completely determined by the kernel space of the Laplacian matrix for the communication graph,which may be different from the desired formation shape.Finally,the theoretical result has been validated by a concrete example in the plane.