# Consensus of Noisy Multiagent Systems with Markovian Switching Topologies and Time-Varying Delays

Authors: Yilun Shang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Stochastic multiagent systems have attracted much attention during the past few decades. This paper concerns the continuous-time consensus of a network of agents under directed switching communication topologies governed by a time-homogeneous Markovian process. The agent dynamics are described by linear time-invariant systems, with random noises as well as time-varying delays. Two types of network-induced delays are considered, namely, delays affecting only the output of the agents’ neighbors and delays affecting both the agents’ own output and the output of their neighbors. We present necessary and sufficient consensus conditions for these two classes of multiagent systems, respectively. The design method of consensus gains allows for decoupling the design problem from the graph properties. Numerical simulations are implemented to test the effectiveness of our obtained results as well as the tightness of necessary/sufficient conditions.


---

## Body

## 1. Introduction

In the past few years, distributed coordination of multiagent systems has been considered by many researchers due to its broad applications in such areas as swarming of animals/robots, cooperative unmanned aerial/underwater vehicles, distributed computation, air traffic control, and distributed sensor networks. One of the important issues in coordinated control is network based consensus protocol design. In this setting, consensus refers to every agent achieving agreement about some common or shared quantity by exchanging information according to a set of rules.For the purpose of reaching consensus, important interaction details of agents in a system are mostly encoded by the communication graph of the system, which gives a general setting to study consensus and allows for the application of graph-theoretical notations and tools. Distributed computation over networks has been studied in the pioneering work of Tsitsiklis [1] and Chatterjee and Seneta [2] in systems and ergodicity theory. More recently, analytical frameworks for solving consensus problems were introduced by Olfati-Saber and Murray [3] and Jadbabaie et al. [4] based on graph and matrix theory. Since then numerous consensus protocols have been proposed, mostly for simple single- and double-integrator dynamics (see, e.g., [5–9] and references therein). It is pointed out that [10] design of consensus protocols for agent dynamics delineated, more generally, by linear time-invariant systems is more challenging due to the possible existence of strictly unstable eigenvalues (poles) in the open-loop matrix. Necessary and sufficient consensus conditions for linear time-invariant systems were explored in [11–14] recently.In many cases, the communication between agents is subject to stochastic perturbation—the connections change with time due to packet drops, agent failure, and various external disturbances. Therefore, the communication graphs underpinning the physical systems are better characterized by random switching networks. Stochastic consensus with single- and double-integrator dynamics has been well researched [15–21]. For example, asymptotic agreement of continuous-time single-integrator agent dynamics over Poisson random graphs is considered in [15]. The results are further extended in [16] to solve mean square consensus under directed and weighted independently switching random graphs. When the communication topology is described by a strictly stationary ergodic graph process, a necessary and sufficient condition for almost sure consensus of single-integrator agents is shown to be the connectivity of the mean topology with respect to a stationary distribution of the process [17]. For both discrete-time and continuous-time multiagent systems with single-integrator dynamics and balanced communication graphs, it has been shown in [21] that the ergodic Markov jump linear system achieves average consensus almost surely if and only if the union of topologies corresponding to the states of the Markov process is strongly connected. Similarly, for second-order discrete systems with (not necessarily ergodic) Markovian switching topologies, the necessary and sufficient condition for mean square consensus becomes that each union of graphs corresponding to the closed sets of positive recurrent states has a spanning tree [20]. Recently, this result is extended to linear time-invariant agent dynamics in [10] for both discrete- and continuous-time consensus.It is well documented in the literature [22] that unmodeled delay effects in a feedback mechanism may destabilize an otherwise stable system. In multiagent systems, time-varying delays may arise naturally due to the asymmetry of interactions, the congestion of the communication channels, and the finite transmission speed. Moreover, noise/uncertainty frequently occurs to agents through, for example, communication errors and spurious measurements in communication systems. Therefore, it would be desirable to understand consensus problems in the setting of Markovian switching topologies with interactions affected by both time-varying delays and random noises.In this paper, we investigate consensus problems for continuous-time multiagent systems with linear time-invariant agent dynamics under Markovian switching topologies, time-varying delays, and stochastic noises. In particular, we consider two types of communication delays: delays affecting both the state of the agents and that of their neighbors and delays affecting only the state of the agents’ neighbors. A unified framework that considers these delays in continuous-time multiagent systems with fixed topology is first established in [23]. It is worth noting that although other interesting delay-dependent robustness results are reported in, for example, [24–26], the communication topologies considered are either static or switch deterministically.This work deals with a group of identical agent dynamics, each of which follows a linear time-invariant system with white noises input. The information flow between agents is modeled by a time-homogenous Markov process, whose state space corresponds to all the possible communication patterns (directed graphs). We establish necessary and sufficient conditions to guarantee all agents asymptotically achieve an agreement in the mean square sense and in the almost sure sense for both types of time delays, respectively. When each graph corresponding to a state of the Markov process contains a spanning tree or isd-regular for a fixed d≥1, we show that the agents can reach consensus for suitable time-varying delays in terms of M-matrices if the agent dynamics is stabilizable. Conversely, if the consensus is achieved, the agent dynamics must be stabilizable and each union of graphs corresponding to the closed sets of positive recurrent states of the Markov process contains a spanning tree. The main mathematical techniques used here are based on the stability analysis of Markovian jump linear systems, stochastic differential delay equations, and graph and matrix theory.The rest of the paper is organized as follows. Section2 contains the problem formulation. Section 3 presents the main results. A couple of numerical examples are given in Section 4. The conclusion is drawn in Section 5.Notation. Let 1n and 0n be the n-dimensional column vectors of all ones and all zeros, respectively. In represents an n×n identity matrix. If the dimension is clear from the context, we sometimes suppress the subscript n. The sets of real and complex numbers are denoted by R and C, respectively. The closed right half plane is signified by C+. We say A>B (A≥B) if A-B is positive definite (semidefinite), where A and B are symmetric matrices of the same dimensions. AT means the transpose of matrix A, while AH means its conjugate transpose. For a vector x, x refers to its Euclidean norm; for a matrix A, A=trace(ATA) represents its trace norm. Let ·max represent the max norm of a matrix, namely, the maximum of the absolute values of elements. For a matrix A∈Rn×n, its null space is designated by Null(A)=x∈Rn:Ax=0. By A⊗B we denote the Kronecker product of matrices A and B, which admits the following properties: (A⊗B)(C⊗D)=AC⊗BD, (A⊗B)-1=A-1⊗B-1, and (A⊗B)T=AT⊗BT. Denote by {λi(A)}i=1n the eigenvalues of a matrix A∈Cn×n. Throughout this paper, we will order them in a nondecreasing order according to their modules: λ1A≤λ2A≤⋯≤λnA.


## 2. Problem Formulation and Preliminary Results

### 2.1. Graph and Consensus Properties

LetG=(V,E,A) represent a directed graph of order N, where V=v1,v2,…,vN is the set of nodes (agents) and E⊆V×V is the set of directed edges. The ordered pair (vi,vj)∈E denotes a directed edge from node vi to node vj, indicating that the information can be sent from agent vi to agent vj. The weighted adjacency matrix A=(aij)∈RN×N is defined by aij>0 if (vj,vi)∈E and aij=0 otherwise. Define the in-degree matrix as a diagonal matrix D=diag⁡(d1in,…,dNin), with diin=∑j=1N‍aij being the in-degree of agent vi. Similarly, the out-degree of agent vi is defined by diout=∑j=1N‍aji. G is said to be balanced if diin=diout for all i=1,…,N [3]. Define the graph Laplacian matrix as L=(lij)=D-A, which has all row sums equal to zero.A sequence of edges(vi1,vi2),(vi2,vi3),…,(vik-1,vik), with (vij-1,vij)∈E for j=2,…,k, is called a directed path from agent vi1 to agent vik. We say that G contains a spanning tree if there is an agent (called root) such that every other agent can be connected by a directed path starting from the root. By Lemma 3.3 of [6], G contains a spanning tree if and only if 0=λ1(L)<λ2L. Let s be a positive integer. The union of s graphs G1=(V,E1,A1),…,Gs=(V,Es,As) is denoted by ⋃i=1sGi=V,⋃i=1sEi,∑i=1s‍Ai.Fort≥0, let τ(t)≥0 be a differentiable function which will stand for the time-varying communication delay. For i=1,…,N, the dynamics of each agent vi in continuous time takes the following two different forms:(i)
with self-delay:(1)x˙it=Axit-τt+Buiwt+A^xit-τtw˙it+B^u^iwt,(ii)
without self-delay:(2)x˙it=Axit+Buiot+A^xitw˙it+B^u^iot,where xi(t)∈Rn represents the state of agent vi at time t, uiw(t),u^iw(t),uio(t),u^io(t)∈Rm are control inputs of agent vi given by(3)uiwt=K∑j=1Naijtxjt-τt-xit-τt,(4)u^iwt=K^∑j=1Nσijtw˙ijtxjt-τt-xit-τt,(5)uiot=K∑j=1Naijtxjt-τt-xit,(6)u^iot=K^∑j=1Nσijtw˙ijtxjt-τt-xit,respectively, A,A^∈Rn×n, B,B^∈Rn×m are system matrices, and wit,wijt:i,j=1,2,…,N are independent standard white noises. Here, K,K^∈Rm×n are common consensus gains to be designed later, and σij are referred to as the intensity of noise. To highlight the presence of noise, it is natural to define a noise graph G^=(V,E,A^) with the adjacency matrix A^=(σij)∈RN×N satisfying σij>0 if (vj,vi)∈E and σij=0 otherwise. By definition, if viewing G and G^ as unweighted graphs, that is, the adjacency matrices are taken as binary ones, we have G=G^. Likewise, the corresponding degree and Laplacian matrices are denoted by D^=diag⁡(σ1,…,σN) with σi=∑j=1N‍σij and L^=(l^ij)=D^-A^, respectively.Remark 1.
The above dynamical models characterize system uncertainties with Gaussian white noise appearing as an exogenous input (similar treatment can be found in, e.g., [27–30]). To see this, take A^=ζ1A and B^=ζ2B (ζ1,ζ2>0). System (1), for example, can be recast as (7)x˙it=A1+ζ1w˙itxit-τt+B∑j=1NKaijt+K^ζ2σijtw˙ijt·xjt-τt-xit-τt.The perturbations are represented by a linear combination of gain matrices K and K^ to be determined. Moreover, if ζ1=1, we take K^=K. (Although other choices are theoretically allowed as per Theorem 8 below, we make them equal in practice since one usually is not able to separate out the noise from the rest of the state.) Thus, the uncertainty reduces to the conventional form aij(t)+ζ2σij(t)w˙ij(t). We mention that other commonly studied uncertainties pertaining to the consensus problems include the measurement noises which only affect the received neighbors’ states (e.g., [18]) and the additive plant noises (e.g., [31]).
Multiagent system (2) with consensus protocols (5) and (6) considers only propagation delays for information transmitted from agent vj to agent vi on the communication network. Propagation delay has been addressed previously, for example, in works [24, 32–35]. Multiagent system (1) with consensus protocols (3) and (4) models both self-delay and neighboring delay. This scheme is relevant for dynamic agents with computation or reaction delays; see, for example, [3, 25, 26, 36, 37]. Although it would be more realistic to explore heterogeneous delays, we consider the uniform delay τ(t) as a first step, and this simplifies the derivation.
In the current work, we deal with delay robustness in both multiagent systems (1) and (2) over a stochastically time-varying interaction topology G(t) as well as its associated noise topology G^(t), which is governed by a homogeneous continuous-time Markov process θ(t), taking value in the finite set S=1,2,…,s. More precisely, G(t)∈G1,…,Gs and G^(t)∈G^1,…,G^s; G(t)=Gi and G^(t)=G^i if and only if θ(t)=i. For each i, the adjacency, degree, and Laplacian matrices for Gi (G^i, resp.) will be denoted by Ai, Di, and Li (A^i, D^i, and L^i, resp.), respectively.Definition 2.
System (1) ((2), resp.) under control protocols (3) and (4) ((5) and (6), resp.) achieves consensus if there exist consensus gains K,K^ such that, for any xi(0)∈Rn and initial distribution of θ(0),(8)limt→∞⁡Exit-xjt2=0for any i,j∈1,2,…,N.We say matrixA in (1) and (2) is Hurwitz (or stable) if every eigenvalue of A has strictly negative real part; that is, it belongs to C∖C+. The pair (A,B) is called stabilizable if there exists C∈Rm×n such that A+BC is Hurwitz [38].Assumption 3.
The following assumptions are made throughout the paper:(a)
Communication graphsG1,G2,…,Gs are balanced.(b)
MatrixA is not Hurwitz.(c)
The white noiseswi(t)=dwij(t) for all i,j=1,…,N, where =d means equality in distribution.(d)
The Markov processθ(t) is independent of the Brownian motions wi(t)(i=1,…,N).Item (a) in Assumption3 is also used in [10, 21]. Item (b) is meant to eliminate the triviality, since consensus can be reached by setting zero consensus gains if A is Hurwitz. In this paper, we assume a special sort of noise—possibly due to the homogeneity of the communication channels between each agent and its neighbors—in which wij(t) is independent of j as item (c) indicated. The consensus in Definition 2 is defined in the sense of mean square convergence. This implies that the consensus can also be achieved in the almost sure sense in view of item (d) and the homogeneity of the Markov process (see Corollary 3.46 of [39, 40]).


### 2.2. Exponential Stability for Delay Markovian Jump Systems

Denote by(Ω,F,P) the underlying common probability space for the Markov process and Brownian motions discussed above. The homogeneous continuous-time Markov process θ(t) with generator Q=(qij)∈Rs×s is formally given by (9)Pθt+h=j∣θt=i=qijh+oh,ifi≠j,1+qiih+oh,ifi=j,where h>0 and h→0. Here qij is the transition rate from i to j if i≠j, while qii=-∑j≠i‍qij. As is known, the state space S=1,2,…,s of θ(t) can be decomposed uniquely into the form S=J∪S1∪⋯∪Sr, where each Sj(j=1,…,r) is a closed communication class (i.e., closed set in the Markov process) of positive recurrent states and J is a set of transient states [41].Letx(t)∈Rn for t≥0. Consider a stochastic differential delay equation with Markovian switching of the form(10)dxt=fxt,xt-τt,θtdt+gxt,xt-τt,θtdwt,where w(t) is an m-dimensional standard Brownian motion and f:Rn×Rn×S→Rn and g:Rn×Rn×S→Rn×m are locally Lipschitz continuous satisfying the following.Assumption 4.
For eachi∈S, there exist constants αi∈R and ρi,γi,βi≥0 such that, for all x,y∈Rn, (a)
2xTf(x,0,i)≤αix2;(b)
f(x,0,i)-f(x,y,i)≤ρiy;(c)
g(x,y,i)2≤γix2+βiy2.DefineF=diag⁡(-α1-ρ1-γ1,…,-αs-ρs-γs)-Q∈Rs×s. A square matrix F is called a nonsingular M-matrix if all the off-diagonal entries are nonpositive and F-1 is a nonnegative matrix. A list of equivalent conditions for M-matrix can be found in [41]. The following result establishes the exponential stability of system (10).Lemma 5 (see [42]).
Assume thatF is a nonsingular M-matrix and ((ρ1+β1)-1,…,(ρs+βs)-1)T-F-11s∈Rs is a positive vector. Then the trivial solution x(t)≡0 of (10) is exponentially stable in mean square if(11)τ˙t<1-κ,for all t≥0, where κ=max1≤i≤sbi(ρi+βi) and (b1,…,bs)T=F-11.It is obvious thatκ<1. Therefore, unbounded time delay is allowed. This is a desirable feature, for example, in delayed cellular neural networks, where delays are variable and in effect unbounded [43–46].Remark 6.
The existence of solutions to dynamical systems (1) and (2), in an even more general nonlinear setting, has been studied in [47]. Let Z(t)=(x1T(t),…,xNT(t))T∈RnN. For τ>0, let τ(t):[0,∞)→[0,τ] be a continuous function. Denote by C([-τ,0];RnN) the family of continuous functions from [-τ,0] to RnN. It is shown that [47] for any bounded and F-measurable initial condition Z0∈C([-τ,0];RnN) system (1) (as well as (2)) has a unique continuous solution Z(t;Z0) on t≥-τ. Our strategy in the sequel is to first transfer the systems to error dynamics (see (13) and (26) below) and then address the stability of zero solution utilizing Lemma 5.
The objective of this paper is to reveal how stability analysis of differential delay equations, together with techniques used in matrix, Markov chain, and graph theory, can be applied to investigate stochastic consensus problems (1) and (2).


## 2.1. Graph and Consensus Properties

LetG=(V,E,A) represent a directed graph of order N, where V=v1,v2,…,vN is the set of nodes (agents) and E⊆V×V is the set of directed edges. The ordered pair (vi,vj)∈E denotes a directed edge from node vi to node vj, indicating that the information can be sent from agent vi to agent vj. The weighted adjacency matrix A=(aij)∈RN×N is defined by aij>0 if (vj,vi)∈E and aij=0 otherwise. Define the in-degree matrix as a diagonal matrix D=diag⁡(d1in,…,dNin), with diin=∑j=1N‍aij being the in-degree of agent vi. Similarly, the out-degree of agent vi is defined by diout=∑j=1N‍aji. G is said to be balanced if diin=diout for all i=1,…,N [3]. Define the graph Laplacian matrix as L=(lij)=D-A, which has all row sums equal to zero.A sequence of edges(vi1,vi2),(vi2,vi3),…,(vik-1,vik), with (vij-1,vij)∈E for j=2,…,k, is called a directed path from agent vi1 to agent vik. We say that G contains a spanning tree if there is an agent (called root) such that every other agent can be connected by a directed path starting from the root. By Lemma 3.3 of [6], G contains a spanning tree if and only if 0=λ1(L)<λ2L. Let s be a positive integer. The union of s graphs G1=(V,E1,A1),…,Gs=(V,Es,As) is denoted by ⋃i=1sGi=V,⋃i=1sEi,∑i=1s‍Ai.Fort≥0, let τ(t)≥0 be a differentiable function which will stand for the time-varying communication delay. For i=1,…,N, the dynamics of each agent vi in continuous time takes the following two different forms:(i)
with self-delay:(1)x˙it=Axit-τt+Buiwt+A^xit-τtw˙it+B^u^iwt,(ii)
without self-delay:(2)x˙it=Axit+Buiot+A^xitw˙it+B^u^iot,where xi(t)∈Rn represents the state of agent vi at time t, uiw(t),u^iw(t),uio(t),u^io(t)∈Rm are control inputs of agent vi given by(3)uiwt=K∑j=1Naijtxjt-τt-xit-τt,(4)u^iwt=K^∑j=1Nσijtw˙ijtxjt-τt-xit-τt,(5)uiot=K∑j=1Naijtxjt-τt-xit,(6)u^iot=K^∑j=1Nσijtw˙ijtxjt-τt-xit,respectively, A,A^∈Rn×n, B,B^∈Rn×m are system matrices, and wit,wijt:i,j=1,2,…,N are independent standard white noises. Here, K,K^∈Rm×n are common consensus gains to be designed later, and σij are referred to as the intensity of noise. To highlight the presence of noise, it is natural to define a noise graph G^=(V,E,A^) with the adjacency matrix A^=(σij)∈RN×N satisfying σij>0 if (vj,vi)∈E and σij=0 otherwise. By definition, if viewing G and G^ as unweighted graphs, that is, the adjacency matrices are taken as binary ones, we have G=G^. Likewise, the corresponding degree and Laplacian matrices are denoted by D^=diag⁡(σ1,…,σN) with σi=∑j=1N‍σij and L^=(l^ij)=D^-A^, respectively.Remark 1.
The above dynamical models characterize system uncertainties with Gaussian white noise appearing as an exogenous input (similar treatment can be found in, e.g., [27–30]). To see this, take A^=ζ1A and B^=ζ2B (ζ1,ζ2>0). System (1), for example, can be recast as (7)x˙it=A1+ζ1w˙itxit-τt+B∑j=1NKaijt+K^ζ2σijtw˙ijt·xjt-τt-xit-τt.The perturbations are represented by a linear combination of gain matrices K and K^ to be determined. Moreover, if ζ1=1, we take K^=K. (Although other choices are theoretically allowed as per Theorem 8 below, we make them equal in practice since one usually is not able to separate out the noise from the rest of the state.) Thus, the uncertainty reduces to the conventional form aij(t)+ζ2σij(t)w˙ij(t). We mention that other commonly studied uncertainties pertaining to the consensus problems include the measurement noises which only affect the received neighbors’ states (e.g., [18]) and the additive plant noises (e.g., [31]).
Multiagent system (2) with consensus protocols (5) and (6) considers only propagation delays for information transmitted from agent vj to agent vi on the communication network. Propagation delay has been addressed previously, for example, in works [24, 32–35]. Multiagent system (1) with consensus protocols (3) and (4) models both self-delay and neighboring delay. This scheme is relevant for dynamic agents with computation or reaction delays; see, for example, [3, 25, 26, 36, 37]. Although it would be more realistic to explore heterogeneous delays, we consider the uniform delay τ(t) as a first step, and this simplifies the derivation.
In the current work, we deal with delay robustness in both multiagent systems (1) and (2) over a stochastically time-varying interaction topology G(t) as well as its associated noise topology G^(t), which is governed by a homogeneous continuous-time Markov process θ(t), taking value in the finite set S=1,2,…,s. More precisely, G(t)∈G1,…,Gs and G^(t)∈G^1,…,G^s; G(t)=Gi and G^(t)=G^i if and only if θ(t)=i. For each i, the adjacency, degree, and Laplacian matrices for Gi (G^i, resp.) will be denoted by Ai, Di, and Li (A^i, D^i, and L^i, resp.), respectively.Definition 2.
System (1) ((2), resp.) under control protocols (3) and (4) ((5) and (6), resp.) achieves consensus if there exist consensus gains K,K^ such that, for any xi(0)∈Rn and initial distribution of θ(0),(8)limt→∞⁡Exit-xjt2=0for any i,j∈1,2,…,N.We say matrixA in (1) and (2) is Hurwitz (or stable) if every eigenvalue of A has strictly negative real part; that is, it belongs to C∖C+. The pair (A,B) is called stabilizable if there exists C∈Rm×n such that A+BC is Hurwitz [38].Assumption 3.
The following assumptions are made throughout the paper:(a)
Communication graphsG1,G2,…,Gs are balanced.(b)
MatrixA is not Hurwitz.(c)
The white noiseswi(t)=dwij(t) for all i,j=1,…,N, where =d means equality in distribution.(d)
The Markov processθ(t) is independent of the Brownian motions wi(t)(i=1,…,N).Item (a) in Assumption3 is also used in [10, 21]. Item (b) is meant to eliminate the triviality, since consensus can be reached by setting zero consensus gains if A is Hurwitz. In this paper, we assume a special sort of noise—possibly due to the homogeneity of the communication channels between each agent and its neighbors—in which wij(t) is independent of j as item (c) indicated. The consensus in Definition 2 is defined in the sense of mean square convergence. This implies that the consensus can also be achieved in the almost sure sense in view of item (d) and the homogeneity of the Markov process (see Corollary 3.46 of [39, 40]).


## 2.2. Exponential Stability for Delay Markovian Jump Systems

Denote by(Ω,F,P) the underlying common probability space for the Markov process and Brownian motions discussed above. The homogeneous continuous-time Markov process θ(t) with generator Q=(qij)∈Rs×s is formally given by (9)Pθt+h=j∣θt=i=qijh+oh,ifi≠j,1+qiih+oh,ifi=j,where h>0 and h→0. Here qij is the transition rate from i to j if i≠j, while qii=-∑j≠i‍qij. As is known, the state space S=1,2,…,s of θ(t) can be decomposed uniquely into the form S=J∪S1∪⋯∪Sr, where each Sj(j=1,…,r) is a closed communication class (i.e., closed set in the Markov process) of positive recurrent states and J is a set of transient states [41].Letx(t)∈Rn for t≥0. Consider a stochastic differential delay equation with Markovian switching of the form(10)dxt=fxt,xt-τt,θtdt+gxt,xt-τt,θtdwt,where w(t) is an m-dimensional standard Brownian motion and f:Rn×Rn×S→Rn and g:Rn×Rn×S→Rn×m are locally Lipschitz continuous satisfying the following.Assumption 4.
For eachi∈S, there exist constants αi∈R and ρi,γi,βi≥0 such that, for all x,y∈Rn, (a)
2xTf(x,0,i)≤αix2;(b)
f(x,0,i)-f(x,y,i)≤ρiy;(c)
g(x,y,i)2≤γix2+βiy2.DefineF=diag⁡(-α1-ρ1-γ1,…,-αs-ρs-γs)-Q∈Rs×s. A square matrix F is called a nonsingular M-matrix if all the off-diagonal entries are nonpositive and F-1 is a nonnegative matrix. A list of equivalent conditions for M-matrix can be found in [41]. The following result establishes the exponential stability of system (10).Lemma 5 (see [42]).
Assume thatF is a nonsingular M-matrix and ((ρ1+β1)-1,…,(ρs+βs)-1)T-F-11s∈Rs is a positive vector. Then the trivial solution x(t)≡0 of (10) is exponentially stable in mean square if(11)τ˙t<1-κ,for all t≥0, where κ=max1≤i≤sbi(ρi+βi) and (b1,…,bs)T=F-11.It is obvious thatκ<1. Therefore, unbounded time delay is allowed. This is a desirable feature, for example, in delayed cellular neural networks, where delays are variable and in effect unbounded [43–46].Remark 6.
The existence of solutions to dynamical systems (1) and (2), in an even more general nonlinear setting, has been studied in [47]. Let Z(t)=(x1T(t),…,xNT(t))T∈RnN. For τ>0, let τ(t):[0,∞)→[0,τ] be a continuous function. Denote by C([-τ,0];RnN) the family of continuous functions from [-τ,0] to RnN. It is shown that [47] for any bounded and F-measurable initial condition Z0∈C([-τ,0];RnN) system (1) (as well as (2)) has a unique continuous solution Z(t;Z0) on t≥-τ. Our strategy in the sequel is to first transfer the systems to error dynamics (see (13) and (26) below) and then address the stability of zero solution utilizing Lemma 5.
The objective of this paper is to reveal how stability analysis of differential delay equations, together with techniques used in matrix, Markov chain, and graph theory, can be applied to investigate stochastic consensus problems (1) and (2).


## 3. Main Results

In this section, we derive necessary and sufficient conditions for reaching consensus of noisy linear systems (1) and (2) under Markovian switching topologies and time-varying delays.


### 3.1. Consensus Conditions for Systems with Self-Delay

We first consider multiagent system (1) with protocols (3) and (4), where both self-delay and neighboring delay are factored in.LetL(t)=(lij(t)) and L^(t)=(l^ij(t)) signify the Laplacian matrices for the switching topologies G(t) and G^(t) at time t. For i=1,…,N, define the disagreement error for agent vi as δi(t)=xi(t)-x¯(t), where x¯(t)=1/N∑i=1N‍xi(t) is the average state vector. Rearranging (1) with (3) and (4) gives(12)δ˙it=Aδit-τt+BK∑j=1Nlijtδjt-τt+A^δit-τt+B^K^∑j=1Nl^ijtδjt-τt·w˙it,where we have used Assumption 3(a). Set δ(t)=(δ1T(t),…,δNT(t))T∈RnN and w(t)=(w1(t),…,wN(t))T∈RN. Moreover, let δ′(t)=diag⁡(δ1(t),…,δN(t)) be an nN×N block diagonal matrix. Consequently, (12) can be recast as(13)dδt=IN⊗A-Lt⊗BKδt-τtdt+IN⊗A^-L^t⊗B^K^δ′t-τtdwt.Theorem 7 (necessary conditions).
Suppose that Assumption3 holds and system (1) with protocols (3) and (4) achieves consensus. Furthermore, assume that there exist ξi>0 for i=1,…,s, and ζ1,ζ2>0 such that A^i=ξiAi, A^=ζ1A, and B^=ζ2B. Then (a)
each union of the graphsGi(i=1,…,s) corresponding to all the states in the closed set Sj for j=1,…,r has a spanning tree;(b)
(A,B) is stabilizable.Proof.
To prove (a), letGS1=⋃i∈S1Gi be the union graph corresponding to the closed set S1. Without loss of generality, assume that GS1 does not contain a spanning tree. Denote by LS1 its Laplacian matrix. By Assumption 3(a), LS1T is also a Laplacian matrix. It follows from Corollary 4.2 of [48] that there is a unit vector c=(c1,…,cN)T∈RN such that cT1=0 and LS1Tc=0. Using Lemma 3.5 of [21], we obtain (14)Null-LS1T=⋂i∈S1Null-LiT.Hence, LiTc=0 for any i∈S1. There exists some Φ1 such that Φ=(1/N,c,Φ1)∈RN×N is an orthogonal matrix.
Defineδ~(t)=(Φ-1⊗In)δ(t). By partitioning δ~(t) in line with δ(t), that is, δ~(t)=(δ~1T(t),…,δ~NT(t))T with each δ~i(t)∈Rn, we get δ~1(t)≡0 and δ~2(t)=∑i=1N‍ciδi(t) by definition. Moreover, by using (13) we have for t≥0(15)δ~˙t=Φ-1⊗Aδt-τt-Φ-1Lt⊗BKδt-τt+Φ-1⊗A^δ′t-τtw˙t-Φ-1L^t⊗B^K^δ′t-τtw˙t.If the initial value θ(0)∈S1, then L(t)∈{Li}i∈S1 and L^(t)∈{L^i}i∈S1. Using the assumption A^i=ξiAi, we derive (16)δ~˙2t=Aδ~2t-τt+A^∑i=1Nciδit-τtw˙itfor t≥0.
IfA≠0, take δ~2(-τ(0))∉Null(A). Thus, limt→∞Eδ~2(t)≠0 under Assumption 3(b). This contradicts with the consensus definition.
IfA=0, we obtain Eδ~˙2(t)=0 and recall δ~2(t)=∑i=1N‍ciδi(t). Since cT1=0, there exist two components ci≠0 and cj≠0 satisfying ci≠cj. Take δi(0)=1, δj(0)=-1, and δk(0)=0 for all k∈1,…,N∖i,j. It yields that limt→∞Eδ~2(t)≠0. Again, it results in a contradiction.
To prove (b), assume that(A,B) is not stabilizable. Then A has an unstable and uncontrollable mode, denoted by λ∈C+. It follows from the Popov-Belevitch-Hautus controllability test [38] that there exists some complex vector c≠0 satisfying cHA=cHλ and cHB=0.
Lety(t)=(y1(t),…,yN(t))T=(IN⊗c)Hδ(t)∈RN. By means of (13) and the assumptions that A^=ζ1A and B^=ζ2B, we derive (17)y˙t=IN⊗cHAδt-τt-Lt⊗cHBKδt-τt+IN⊗cHA^δ′t-τtw˙t-L^t⊗cHB^K^δ′t-τtw˙t=λyt-τt+λζ1diag⁡y1t-τt,…,yNt-τtw˙t.Taking y(-τ(0))≠0, we see that liminft→∞Ey(t)>0 since λ is unstable. This contradicts with the consensus definition.Note that the assumptionA^i=ξiAi(i=1,…,s) is only used in the proof of statement (a), while the assumptions A^=ζ1A and B^=ζ2B are only used in the proof of statement (b).If(A,B) is stabilizable, there exists an n×n matrix P>0 such that(18)P>ATPA-ATPBBTPB-1BTPAby the Riccati inequality [49]. Similarly, if (A^,B^) is stabilizable, there exists an n×n matrix P^>0 such that(19)P^>A^TP^A^-A^TP^B^B^TP^B^-1B^TP^A^.Theorem 8 (sufficient conditions).
Suppose that Assumption3 holds, both (A,B) and (A^,B^) are stabilizable, and Gi contains a spanning tree for every i∈S. If F=-ρIs-Q is a nonsingular M-matrix and (ρ+β)-11s-F-11s is a positive vector, then system (1) with protocols (3) and (4) achieves consensus for τ(t) satisfying (20)τ˙t<1-ρ+β·F-11smax,where ρ=λn(P)/λ1(P), β=λn(P^)/λ1(P^), and P and P^ are given by (18) and (19), respectively.
Moreover, feasible consensus gainsK and K^ are given by K=η(BTPB)-1BTPA with η≥1/min2≤j≤N,1≤i≤sλjLi and K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min2≤j≤N,1≤i≤sλjL^i, respectively.Proof.
The idea is to apply Lemma5 to the error dynamics (13). It suffices to check Assumption 4 holds.
For item (a),αi=0 for all i∈S clearly. To check item (b), we take a unitary matrix for each i∈S: Φi=(1N/N,ϕi,2,…,ϕi,N), where ϕi,j∈CN satisfies Liϕi,j=λj(Li)ϕi,j for j=2,…,N. Given i∈S, by setting δ~=(ΦiH⊗In)δ (and partitioning it in conformity with that of δ as in Theorem 7), we derive that(21)δTIN⊗AT-LiT⊗KTBTIN⊗P·IN⊗A-Li⊗BKδ=δTIN⊗ATPA-LiTLi⊗KTBTPBKδ=δ~HIN⊗ATPA-ΦiHLiHLiΦi⊗KTBTPBKδ~=∑j=2Nδ~jH·ATPA-λjLi2η2ATPBBTPB-1BTPAδ~j≤∑j=1Nδ~jHPδ~j=δTIN⊗Pδ,where we have taken K=η(BTPB)-1BTPA with η≥1/min2≤j≤N,1≤i≤sλjLi and used inequality (18). Note that η is well defined, since Gi contains a spanning tree, and thus there is only one zero eigenvalue of Li [48].
SinceP>0, using (21) we obtain(22)IN⊗A-Li⊗BKδ2≤1λ1P·δTIN⊗AT-LiT⊗KTBTIN⊗P·IN⊗A-Li⊗BKδ≤1λ1PδTIN⊗Pδ≤λnPλ1Pδ2.Hence, we take ρ=ρi=λn(P)/λ1(P) independent of i.
To verify item (c), note that(23)
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
′
2
=
t
r
a
c
e
δ
′
T
I
N
⊗
A
^
T
-
L
^
i
T
⊗
K
^
T
B
^
T
·
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
′
=
δ
T
I
N
⊗
A
^
T
-
L
^
i
T
⊗
K
^
T
B
^
T
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
=
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
2
.Therefore, similarly as in the proof of (21) and (22) we obtain (24)IN⊗A^-L^i⊗B^K^δ′2≤λnP^λ1P^δ2,where we have taken K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min2≤j≤N,1≤i≤sλjL^i. Since the fact that Gi contains a spanning tree implies that G^i also contains a spanning tree, η^ is well defined with the same reason as above. Hence, we take γi=0 and β=βi=λn(P^)/λ1(P^) for all i∈S.Remark 9.
(a) The design of consensus gainsK and K^ splits the design problem from the underlying communication topology. For example, K is constructed based on the system matrices (18) and a multiplicative coefficient η depending only on the graphs. Such a design procedure decouples the effects of agent dynamics and the network topologies, which simplifies the consensus design for the cases where the number of agents is large (see also [10, 13]).
(b) Whenn=m, A=0, and B=In, we reproduce single-integrator agent dynamics, and (18) and (19) always hold true. This can be viewed as a generalization of results in [21] by introducing random noise and time delay.
(c) The assumption in Theorem8 about F being a nonsingular M-matrix and (ρ+β)-11s-F-11s having positive entries is easy to verify. Indeed, all the off-diagonal entries are nonpositive by the definition of generator Q. Thus, it suffices to show that F-1 is nonnegative (this always holds if n=1) and ensure that every row sum of it is less than (ρ+β)-1.
(d) There is a gap pertaining to graph connectivity between sufficient conditions (Theorem8) and necessary conditions (Theorem 7). Comparing with the previous work [10] for noise-free and delay-free systems, we understand that the stronger connectivity requirement—each graph Gi contains a spanning tree—is introduced to accommodate the added noises and time-varying delays. Notice that the results are based on Lemma 5, which is about nonlinear systems. This also suggests the conditions derived here could be conservative. Notwithstanding, the study of weaker sufficient condition (e.g., using some algebraic methods) comparable to that of the necessary condition is an interesting future research.


### 3.2. Consensus Conditions for Systems without Self-Delay

Next, we study multiagent system (2) with protocols (5) and (6), where only neighboring delay is considered.Similarly as above, fori=1,…,N, define the disagreement error for agent vi as δi(t)=xi(t)-x¯(t), and x¯(t)=1/N∑i=1N‍xi(t) is the average state vector. Under Assumption 3(a), (2) together with (5) and (6) yields(25)
δ
˙
i
t
=
A
δ
i
t
+
B
K
∑
j
=
1
N
a
i
j
t
δ
j
t
-
τ
t
-
δ
i
t
+
A
^
δ
i
t
-
τ
t
+
B
^
K
^
∑
j
=
1
N
σ
i
j
t
δ
j
t
-
τ
t
-
δ
i
t
w
˙
i
t
.Let δ(t)=(δ1T(t),…,δNT(t))T∈RnN, w(t)=(w1(t),…,wN(t))T∈RN, and δ′(t)=diag(δ1(t),…,δN(t)). We rewrite (25) in a compact form as(26)
d
δ
t
=
I
N
⊗
A
-
D
t
⊗
B
K
δ
t
+
A
t
⊗
B
K
δ
t
-
τ
t
d
t
+
I
N
⊗
A
^
-
D
^
t
⊗
B
^
K
^
δ
′
t
+
A
^
t
⊗
B
^
K
^
δ
′
t
-
τ
t
d
w
t
.Theorem 10 (necessary conditions).
Suppose that Assumption3 holds and system (2) with protocols (5) and (6) achieves consensus for some constant delay τ. Furthermore, assume that there exist ξi>0 for i=1,…,s, and ζ1,ζ2>0 such that A^i=ξiAi, A^=ζ1A, and B^=ζ2B. Then (a)
each union of the graphsGi(i=1,…,s) corresponding to all the states in the closed set Sj for j=1,…,r has a spanning tree;(b)
(A,B) is stabilizable.Proof.
Since consensus is achieved, we havelimt→∞δ(t)-δ(t-τ)=0 and limt→∞δ′(t)-δ′(t-τ)=0 for fixed τ. Therefore, system (26) can be recast as (27)
d
δ
t
=
I
N
⊗
A
-
L
t
⊗
B
K
δ
t
-
τ
+
O
δ
t
-
δ
t
-
τ
·
1
N
n
d
t
+
I
N
⊗
A
^
-
L
^
t
⊗
B
^
K
^
δ
′
t
-
τ
+
O
δ
′
t
-
δ
′
t
-
τ
·
1
N
n
d
w
t
.Hence, Theorem 10 can be proved by the same reasoning as in Theorem 7.As is noted below Theorem7, the assumption A^i=ξiAi(i=1,…,s) is only used in the proof of statement (a), while the assumptions A^=ζ1A and B^=ζ2B are only used in the proof of statement (b).Recall that if(A,B) is stabilizable, there exists a C∈Rm×n such that A+BC is Hurwitz. Therefore, by the Lyapunov stability theorem, there exists an n×n matrix P>0 such that(28)A+BCP+PA+BCT=-I.Define a symmetric matrix R∈Rn×n by(29)R=A+BCTP+PA+BC.Theorem 11 (sufficient conditions).
Suppose that Assumption3 holds, both (A,B) and (A^,B^) are stabilizable, and Gi is d-regular (d≥1) for any i∈S. If F=-(α+γ)Is-diag⁡(ρ1,…,ρs)-Q is a nonsingular M-matrix and ((ρ1+β1)-1,…,(ρs+βs)-1)T-F-11s is a positive vector, then system (2) with protocols (5) and (6) achieves consensus for τ(t) satisfying (30)τ˙t<1-max1≤i≤s⁡biρi+βi,where (b1,…,bs)T=F-11, α=(λn(R)-1)/(2λ1(P)), γ=2λn(P^)/λ1(P^), ρi=λNn(AiTAi⊗KTBTBK), and βi=2λNn(A^iTA^i⊗K^TB^TB^K^). Here, P, P^, and R are given by (28), (19), and (29), respectively.
Moreover, feasible consensus gainsK and K^ are given by K=-C/d and K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min1≤i≤s,1≤j≤Nσji, respectively. Here, D^i=diag(σ1i,…,σNi) for i=1,…,s.Proof.
As in the proof of Theorem8, we will apply Lemma 5 to the error dynamics (26).
To check item (a) in Assumption4, we note that(31)
2
δ
T
I
N
⊗
A
-
D
i
⊗
B
K
δ
=
δ
T
I
N
⊗
A
-
D
i
⊗
B
K
+
I
N
⊗
A
T
-
D
i
⊗
K
T
B
T
δ
≤
λ
N
n
I
N
⊗
A
-
D
i
⊗
B
K
+
I
N
⊗
A
T
-
D
i
⊗
K
T
B
T
δ
2
=
λ
n
A
-
d
B
K
+
A
-
d
B
K
T
δ
2
,where we have used the assumption that Gi is d-regular and the Rayleigh quotient inequality. Taking K=-C/d in (31) and utilizing (28) and (29), we get(32)
2
δ
T
I
N
⊗
A
-
D
i
⊗
B
K
δ
≤
λ
n
A
+
B
C
+
A
+
B
C
T
δ
2
=
1
2
λ
1
P
·
λ
n
A
+
B
C
+
A
+
B
C
T
λ
1
P
I
+
λ
1
P
I
A
+
B
C
+
A
+
B
C
T
δ
2
≤
1
2
λ
1
P
·
λ
n
A
+
B
C
+
A
+
B
C
T
P
+
P
A
+
B
C
+
A
+
B
C
T
δ
2
=
1
2
λ
1
P
λ
n
R
-
I
δ
2
.Therefore, we take α=αi=(λn(R)-1)/(2λ1(P)) for all i∈S.
For item (b), again by applying the Rayleigh quotient inequality we derive(33)Ai⊗BKδ2=δTAiT⊗KTBTAi⊗BKδ≤λNnAiTAi⊗KTBTBKδ2=1d2λNnAiTAi⊗CTBTBCδ2.Therefore, we take ρi=(1/d)λNn(AiTAi⊗CTBTBC) for i∈S.
To show (c), we recall the simple norm inequalitya+b2≤2(a2+b2). It suffices to find suitable γi and βi so that the following two inequalities hold for i∈S:(34)2IN⊗A^-D^i⊗B^K^δ′2≤γiδ′2,(35)2A^i⊗B^K^δ′2≤βiδ′2.
Since(A^,B^) is stabilizable, we get P^>0 such that (19) holds. Hence,(36)δTIN⊗A^T-D^iT⊗K^TB^TIN⊗P^·IN⊗A^-D^i⊗B^K^δ=δTIN⊗A^TP^A^-D^iTD^i⊗K^TB^TB^K^δ=∑j=1NδjT·A^TP^A^-σji2η^2A^TP^B^B^TP^B^-1B^TP^A^δj≤∑j=1NδjTP^δj=δTIN⊗P^δ,where we have taken K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min1≤i≤s,1≤j≤Nσji. Here σji are defined as in the statement of Theorem 11. Since d≥1, we have σji>0 for all i and j. Therefore, η^ is well defined.
Note that(37)
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
′
2
=
t
r
a
c
e
δ
′
T
I
N
⊗
A
^
T
-
D
^
i
T
⊗
K
^
T
B
^
T
·
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
′
=
δ
T
I
N
⊗
A
^
T
-
D
^
i
T
⊗
K
^
T
B
^
T
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
=
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
2
.Using (36) we obtain(38)IN⊗A^-D^i⊗B^K^δ′2≤1λ1P^·δTIN⊗A^T-D^iT⊗K^TB^TIN⊗P^·IN⊗A^-D^i⊗B^K^δ≤1λ1P^δTIN⊗P^δ≤λnP^λ1P^δTδ≤λnP^λ1P^δ′2.Therefore, (34) holds by taking γ=γi=2λn(P^)/λ1(P^) for any i∈S.
Similarly, (35) is true with βi=2λNn(A^iTA^i⊗K^TB^TB^K^) by using the Rayleigh quotient inequality.Remark 12.
(a) Similar comments in Remark9 can be applied here. In addition, we note that the requirement in Theorem 11—Gi are d-regular graphs for all i—is somewhat restrictive. If this condition is violated, we might use Weyl’s inequality (see, e.g., [50]) to bound the maximum eigenvalue in (31), which nonetheless will lead to a more cumbersome expression.
(b) Interestingly, sufficient conditions in Theorem11 do not explicitly mention connectivity assumptions, whereas necessary conditions in Theorem 10 clearly state certain connectivity assumption. To see how some connectivity is implicitly required in Theorem 11, we consider a special case with n=m=1, S=1,2, and Gi(i∈S) being not connected and having two connected components, out of which one is a complete graph with d+1 nodes. We can show that matrix F in Theorem 11 is not a nonsingular M-matrix, violating the assumption of Theorem 11. Indeed, it is straightforward to check that γ=2, ρ1=ρ2=dBK, and α=2(A+BC)<0 with A≥0. Setting Q=-aab-b with a,b>0, we obtain the 2×2 matrix F. F being a nonsingular M-matrix is equivalent to the fact that all its leading principal minors are positive [41], which in turn yields -2(A+BC)-2-dBK>0. However, this inequality does not hold for any K∈R when A+BC≥-1.


## 3.1. Consensus Conditions for Systems with Self-Delay

We first consider multiagent system (1) with protocols (3) and (4), where both self-delay and neighboring delay are factored in.LetL(t)=(lij(t)) and L^(t)=(l^ij(t)) signify the Laplacian matrices for the switching topologies G(t) and G^(t) at time t. For i=1,…,N, define the disagreement error for agent vi as δi(t)=xi(t)-x¯(t), where x¯(t)=1/N∑i=1N‍xi(t) is the average state vector. Rearranging (1) with (3) and (4) gives(12)δ˙it=Aδit-τt+BK∑j=1Nlijtδjt-τt+A^δit-τt+B^K^∑j=1Nl^ijtδjt-τt·w˙it,where we have used Assumption 3(a). Set δ(t)=(δ1T(t),…,δNT(t))T∈RnN and w(t)=(w1(t),…,wN(t))T∈RN. Moreover, let δ′(t)=diag⁡(δ1(t),…,δN(t)) be an nN×N block diagonal matrix. Consequently, (12) can be recast as(13)dδt=IN⊗A-Lt⊗BKδt-τtdt+IN⊗A^-L^t⊗B^K^δ′t-τtdwt.Theorem 7 (necessary conditions).
Suppose that Assumption3 holds and system (1) with protocols (3) and (4) achieves consensus. Furthermore, assume that there exist ξi>0 for i=1,…,s, and ζ1,ζ2>0 such that A^i=ξiAi, A^=ζ1A, and B^=ζ2B. Then (a)
each union of the graphsGi(i=1,…,s) corresponding to all the states in the closed set Sj for j=1,…,r has a spanning tree;(b)
(A,B) is stabilizable.Proof.
To prove (a), letGS1=⋃i∈S1Gi be the union graph corresponding to the closed set S1. Without loss of generality, assume that GS1 does not contain a spanning tree. Denote by LS1 its Laplacian matrix. By Assumption 3(a), LS1T is also a Laplacian matrix. It follows from Corollary 4.2 of [48] that there is a unit vector c=(c1,…,cN)T∈RN such that cT1=0 and LS1Tc=0. Using Lemma 3.5 of [21], we obtain (14)Null-LS1T=⋂i∈S1Null-LiT.Hence, LiTc=0 for any i∈S1. There exists some Φ1 such that Φ=(1/N,c,Φ1)∈RN×N is an orthogonal matrix.
Defineδ~(t)=(Φ-1⊗In)δ(t). By partitioning δ~(t) in line with δ(t), that is, δ~(t)=(δ~1T(t),…,δ~NT(t))T with each δ~i(t)∈Rn, we get δ~1(t)≡0 and δ~2(t)=∑i=1N‍ciδi(t) by definition. Moreover, by using (13) we have for t≥0(15)δ~˙t=Φ-1⊗Aδt-τt-Φ-1Lt⊗BKδt-τt+Φ-1⊗A^δ′t-τtw˙t-Φ-1L^t⊗B^K^δ′t-τtw˙t.If the initial value θ(0)∈S1, then L(t)∈{Li}i∈S1 and L^(t)∈{L^i}i∈S1. Using the assumption A^i=ξiAi, we derive (16)δ~˙2t=Aδ~2t-τt+A^∑i=1Nciδit-τtw˙itfor t≥0.
IfA≠0, take δ~2(-τ(0))∉Null(A). Thus, limt→∞Eδ~2(t)≠0 under Assumption 3(b). This contradicts with the consensus definition.
IfA=0, we obtain Eδ~˙2(t)=0 and recall δ~2(t)=∑i=1N‍ciδi(t). Since cT1=0, there exist two components ci≠0 and cj≠0 satisfying ci≠cj. Take δi(0)=1, δj(0)=-1, and δk(0)=0 for all k∈1,…,N∖i,j. It yields that limt→∞Eδ~2(t)≠0. Again, it results in a contradiction.
To prove (b), assume that(A,B) is not stabilizable. Then A has an unstable and uncontrollable mode, denoted by λ∈C+. It follows from the Popov-Belevitch-Hautus controllability test [38] that there exists some complex vector c≠0 satisfying cHA=cHλ and cHB=0.
Lety(t)=(y1(t),…,yN(t))T=(IN⊗c)Hδ(t)∈RN. By means of (13) and the assumptions that A^=ζ1A and B^=ζ2B, we derive (17)y˙t=IN⊗cHAδt-τt-Lt⊗cHBKδt-τt+IN⊗cHA^δ′t-τtw˙t-L^t⊗cHB^K^δ′t-τtw˙t=λyt-τt+λζ1diag⁡y1t-τt,…,yNt-τtw˙t.Taking y(-τ(0))≠0, we see that liminft→∞Ey(t)>0 since λ is unstable. This contradicts with the consensus definition.Note that the assumptionA^i=ξiAi(i=1,…,s) is only used in the proof of statement (a), while the assumptions A^=ζ1A and B^=ζ2B are only used in the proof of statement (b).If(A,B) is stabilizable, there exists an n×n matrix P>0 such that(18)P>ATPA-ATPBBTPB-1BTPAby the Riccati inequality [49]. Similarly, if (A^,B^) is stabilizable, there exists an n×n matrix P^>0 such that(19)P^>A^TP^A^-A^TP^B^B^TP^B^-1B^TP^A^.Theorem 8 (sufficient conditions).
Suppose that Assumption3 holds, both (A,B) and (A^,B^) are stabilizable, and Gi contains a spanning tree for every i∈S. If F=-ρIs-Q is a nonsingular M-matrix and (ρ+β)-11s-F-11s is a positive vector, then system (1) with protocols (3) and (4) achieves consensus for τ(t) satisfying (20)τ˙t<1-ρ+β·F-11smax,where ρ=λn(P)/λ1(P), β=λn(P^)/λ1(P^), and P and P^ are given by (18) and (19), respectively.
Moreover, feasible consensus gainsK and K^ are given by K=η(BTPB)-1BTPA with η≥1/min2≤j≤N,1≤i≤sλjLi and K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min2≤j≤N,1≤i≤sλjL^i, respectively.Proof.
The idea is to apply Lemma5 to the error dynamics (13). It suffices to check Assumption 4 holds.
For item (a),αi=0 for all i∈S clearly. To check item (b), we take a unitary matrix for each i∈S: Φi=(1N/N,ϕi,2,…,ϕi,N), where ϕi,j∈CN satisfies Liϕi,j=λj(Li)ϕi,j for j=2,…,N. Given i∈S, by setting δ~=(ΦiH⊗In)δ (and partitioning it in conformity with that of δ as in Theorem 7), we derive that(21)δTIN⊗AT-LiT⊗KTBTIN⊗P·IN⊗A-Li⊗BKδ=δTIN⊗ATPA-LiTLi⊗KTBTPBKδ=δ~HIN⊗ATPA-ΦiHLiHLiΦi⊗KTBTPBKδ~=∑j=2Nδ~jH·ATPA-λjLi2η2ATPBBTPB-1BTPAδ~j≤∑j=1Nδ~jHPδ~j=δTIN⊗Pδ,where we have taken K=η(BTPB)-1BTPA with η≥1/min2≤j≤N,1≤i≤sλjLi and used inequality (18). Note that η is well defined, since Gi contains a spanning tree, and thus there is only one zero eigenvalue of Li [48].
SinceP>0, using (21) we obtain(22)IN⊗A-Li⊗BKδ2≤1λ1P·δTIN⊗AT-LiT⊗KTBTIN⊗P·IN⊗A-Li⊗BKδ≤1λ1PδTIN⊗Pδ≤λnPλ1Pδ2.Hence, we take ρ=ρi=λn(P)/λ1(P) independent of i.
To verify item (c), note that(23)
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
′
2
=
t
r
a
c
e
δ
′
T
I
N
⊗
A
^
T
-
L
^
i
T
⊗
K
^
T
B
^
T
·
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
′
=
δ
T
I
N
⊗
A
^
T
-
L
^
i
T
⊗
K
^
T
B
^
T
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
=
I
N
⊗
A
^
-
L
^
i
⊗
B
^
K
^
δ
2
.Therefore, similarly as in the proof of (21) and (22) we obtain (24)IN⊗A^-L^i⊗B^K^δ′2≤λnP^λ1P^δ2,where we have taken K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min2≤j≤N,1≤i≤sλjL^i. Since the fact that Gi contains a spanning tree implies that G^i also contains a spanning tree, η^ is well defined with the same reason as above. Hence, we take γi=0 and β=βi=λn(P^)/λ1(P^) for all i∈S.Remark 9.
(a) The design of consensus gainsK and K^ splits the design problem from the underlying communication topology. For example, K is constructed based on the system matrices (18) and a multiplicative coefficient η depending only on the graphs. Such a design procedure decouples the effects of agent dynamics and the network topologies, which simplifies the consensus design for the cases where the number of agents is large (see also [10, 13]).
(b) Whenn=m, A=0, and B=In, we reproduce single-integrator agent dynamics, and (18) and (19) always hold true. This can be viewed as a generalization of results in [21] by introducing random noise and time delay.
(c) The assumption in Theorem8 about F being a nonsingular M-matrix and (ρ+β)-11s-F-11s having positive entries is easy to verify. Indeed, all the off-diagonal entries are nonpositive by the definition of generator Q. Thus, it suffices to show that F-1 is nonnegative (this always holds if n=1) and ensure that every row sum of it is less than (ρ+β)-1.
(d) There is a gap pertaining to graph connectivity between sufficient conditions (Theorem8) and necessary conditions (Theorem 7). Comparing with the previous work [10] for noise-free and delay-free systems, we understand that the stronger connectivity requirement—each graph Gi contains a spanning tree—is introduced to accommodate the added noises and time-varying delays. Notice that the results are based on Lemma 5, which is about nonlinear systems. This also suggests the conditions derived here could be conservative. Notwithstanding, the study of weaker sufficient condition (e.g., using some algebraic methods) comparable to that of the necessary condition is an interesting future research.


## 3.2. Consensus Conditions for Systems without Self-Delay

Next, we study multiagent system (2) with protocols (5) and (6), where only neighboring delay is considered.Similarly as above, fori=1,…,N, define the disagreement error for agent vi as δi(t)=xi(t)-x¯(t), and x¯(t)=1/N∑i=1N‍xi(t) is the average state vector. Under Assumption 3(a), (2) together with (5) and (6) yields(25)
δ
˙
i
t
=
A
δ
i
t
+
B
K
∑
j
=
1
N
a
i
j
t
δ
j
t
-
τ
t
-
δ
i
t
+
A
^
δ
i
t
-
τ
t
+
B
^
K
^
∑
j
=
1
N
σ
i
j
t
δ
j
t
-
τ
t
-
δ
i
t
w
˙
i
t
.Let δ(t)=(δ1T(t),…,δNT(t))T∈RnN, w(t)=(w1(t),…,wN(t))T∈RN, and δ′(t)=diag(δ1(t),…,δN(t)). We rewrite (25) in a compact form as(26)
d
δ
t
=
I
N
⊗
A
-
D
t
⊗
B
K
δ
t
+
A
t
⊗
B
K
δ
t
-
τ
t
d
t
+
I
N
⊗
A
^
-
D
^
t
⊗
B
^
K
^
δ
′
t
+
A
^
t
⊗
B
^
K
^
δ
′
t
-
τ
t
d
w
t
.Theorem 10 (necessary conditions).
Suppose that Assumption3 holds and system (2) with protocols (5) and (6) achieves consensus for some constant delay τ. Furthermore, assume that there exist ξi>0 for i=1,…,s, and ζ1,ζ2>0 such that A^i=ξiAi, A^=ζ1A, and B^=ζ2B. Then (a)
each union of the graphsGi(i=1,…,s) corresponding to all the states in the closed set Sj for j=1,…,r has a spanning tree;(b)
(A,B) is stabilizable.Proof.
Since consensus is achieved, we havelimt→∞δ(t)-δ(t-τ)=0 and limt→∞δ′(t)-δ′(t-τ)=0 for fixed τ. Therefore, system (26) can be recast as (27)
d
δ
t
=
I
N
⊗
A
-
L
t
⊗
B
K
δ
t
-
τ
+
O
δ
t
-
δ
t
-
τ
·
1
N
n
d
t
+
I
N
⊗
A
^
-
L
^
t
⊗
B
^
K
^
δ
′
t
-
τ
+
O
δ
′
t
-
δ
′
t
-
τ
·
1
N
n
d
w
t
.Hence, Theorem 10 can be proved by the same reasoning as in Theorem 7.As is noted below Theorem7, the assumption A^i=ξiAi(i=1,…,s) is only used in the proof of statement (a), while the assumptions A^=ζ1A and B^=ζ2B are only used in the proof of statement (b).Recall that if(A,B) is stabilizable, there exists a C∈Rm×n such that A+BC is Hurwitz. Therefore, by the Lyapunov stability theorem, there exists an n×n matrix P>0 such that(28)A+BCP+PA+BCT=-I.Define a symmetric matrix R∈Rn×n by(29)R=A+BCTP+PA+BC.Theorem 11 (sufficient conditions).
Suppose that Assumption3 holds, both (A,B) and (A^,B^) are stabilizable, and Gi is d-regular (d≥1) for any i∈S. If F=-(α+γ)Is-diag⁡(ρ1,…,ρs)-Q is a nonsingular M-matrix and ((ρ1+β1)-1,…,(ρs+βs)-1)T-F-11s is a positive vector, then system (2) with protocols (5) and (6) achieves consensus for τ(t) satisfying (30)τ˙t<1-max1≤i≤s⁡biρi+βi,where (b1,…,bs)T=F-11, α=(λn(R)-1)/(2λ1(P)), γ=2λn(P^)/λ1(P^), ρi=λNn(AiTAi⊗KTBTBK), and βi=2λNn(A^iTA^i⊗K^TB^TB^K^). Here, P, P^, and R are given by (28), (19), and (29), respectively.
Moreover, feasible consensus gainsK and K^ are given by K=-C/d and K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min1≤i≤s,1≤j≤Nσji, respectively. Here, D^i=diag(σ1i,…,σNi) for i=1,…,s.Proof.
As in the proof of Theorem8, we will apply Lemma 5 to the error dynamics (26).
To check item (a) in Assumption4, we note that(31)
2
δ
T
I
N
⊗
A
-
D
i
⊗
B
K
δ
=
δ
T
I
N
⊗
A
-
D
i
⊗
B
K
+
I
N
⊗
A
T
-
D
i
⊗
K
T
B
T
δ
≤
λ
N
n
I
N
⊗
A
-
D
i
⊗
B
K
+
I
N
⊗
A
T
-
D
i
⊗
K
T
B
T
δ
2
=
λ
n
A
-
d
B
K
+
A
-
d
B
K
T
δ
2
,where we have used the assumption that Gi is d-regular and the Rayleigh quotient inequality. Taking K=-C/d in (31) and utilizing (28) and (29), we get(32)
2
δ
T
I
N
⊗
A
-
D
i
⊗
B
K
δ
≤
λ
n
A
+
B
C
+
A
+
B
C
T
δ
2
=
1
2
λ
1
P
·
λ
n
A
+
B
C
+
A
+
B
C
T
λ
1
P
I
+
λ
1
P
I
A
+
B
C
+
A
+
B
C
T
δ
2
≤
1
2
λ
1
P
·
λ
n
A
+
B
C
+
A
+
B
C
T
P
+
P
A
+
B
C
+
A
+
B
C
T
δ
2
=
1
2
λ
1
P
λ
n
R
-
I
δ
2
.Therefore, we take α=αi=(λn(R)-1)/(2λ1(P)) for all i∈S.
For item (b), again by applying the Rayleigh quotient inequality we derive(33)Ai⊗BKδ2=δTAiT⊗KTBTAi⊗BKδ≤λNnAiTAi⊗KTBTBKδ2=1d2λNnAiTAi⊗CTBTBCδ2.Therefore, we take ρi=(1/d)λNn(AiTAi⊗CTBTBC) for i∈S.
To show (c), we recall the simple norm inequalitya+b2≤2(a2+b2). It suffices to find suitable γi and βi so that the following two inequalities hold for i∈S:(34)2IN⊗A^-D^i⊗B^K^δ′2≤γiδ′2,(35)2A^i⊗B^K^δ′2≤βiδ′2.
Since(A^,B^) is stabilizable, we get P^>0 such that (19) holds. Hence,(36)δTIN⊗A^T-D^iT⊗K^TB^TIN⊗P^·IN⊗A^-D^i⊗B^K^δ=δTIN⊗A^TP^A^-D^iTD^i⊗K^TB^TB^K^δ=∑j=1NδjT·A^TP^A^-σji2η^2A^TP^B^B^TP^B^-1B^TP^A^δj≤∑j=1NδjTP^δj=δTIN⊗P^δ,where we have taken K^=η^(B^TP^B^)-1B^TP^A^ with η^≥1/min1≤i≤s,1≤j≤Nσji. Here σji are defined as in the statement of Theorem 11. Since d≥1, we have σji>0 for all i and j. Therefore, η^ is well defined.
Note that(37)
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
′
2
=
t
r
a
c
e
δ
′
T
I
N
⊗
A
^
T
-
D
^
i
T
⊗
K
^
T
B
^
T
·
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
′
=
δ
T
I
N
⊗
A
^
T
-
D
^
i
T
⊗
K
^
T
B
^
T
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
=
I
N
⊗
A
^
-
D
^
i
⊗
B
^
K
^
δ
2
.Using (36) we obtain(38)IN⊗A^-D^i⊗B^K^δ′2≤1λ1P^·δTIN⊗A^T-D^iT⊗K^TB^TIN⊗P^·IN⊗A^-D^i⊗B^K^δ≤1λ1P^δTIN⊗P^δ≤λnP^λ1P^δTδ≤λnP^λ1P^δ′2.Therefore, (34) holds by taking γ=γi=2λn(P^)/λ1(P^) for any i∈S.
Similarly, (35) is true with βi=2λNn(A^iTA^i⊗K^TB^TB^K^) by using the Rayleigh quotient inequality.Remark 12.
(a) Similar comments in Remark9 can be applied here. In addition, we note that the requirement in Theorem 11—Gi are d-regular graphs for all i—is somewhat restrictive. If this condition is violated, we might use Weyl’s inequality (see, e.g., [50]) to bound the maximum eigenvalue in (31), which nonetheless will lead to a more cumbersome expression.
(b) Interestingly, sufficient conditions in Theorem11 do not explicitly mention connectivity assumptions, whereas necessary conditions in Theorem 10 clearly state certain connectivity assumption. To see how some connectivity is implicitly required in Theorem 11, we consider a special case with n=m=1, S=1,2, and Gi(i∈S) being not connected and having two connected components, out of which one is a complete graph with d+1 nodes. We can show that matrix F in Theorem 11 is not a nonsingular M-matrix, violating the assumption of Theorem 11. Indeed, it is straightforward to check that γ=2, ρ1=ρ2=dBK, and α=2(A+BC)<0 with A≥0. Setting Q=-aab-b with a,b>0, we obtain the 2×2 matrix F. F being a nonsingular M-matrix is equivalent to the fact that all its leading principal minors are positive [41], which in turn yields -2(A+BC)-2-dBK>0. However, this inequality does not hold for any K∈R when A+BC≥-1.


## 4. Simulation Examples

In this section, we present several examples to illustrate the availability of the proposed results. We consider all the adjacency matrices as binary 0-1 matrices in the following.Example 1 (system with self-delay).
Consider multiagent system (1) with N=4 agents. The communication topologies will randomly switch amongst the triad G1, G2, and G3 of Figure 1 following a homogeneous Markovian process with generator(39)Q=-2111-4311-2and state space S=1,2,3. Note that each of these three graphs is balanced and contains a spanning tree. For i=1,2,3, we choose A^i=0.01·Ai. Take n=3, m=1 and let the agent dynamics be specified as (40)A=-0.500010010,B=B^=010,and A^=0.01·A. Since A+BC and A^+B^C^ are Hurwitz by choosing C=(-1,-2,-1) and C^=0.01·C, both pairs (A,B) and (A^,B^) are stabilizable. Since Riccati inequalities (18) and (19) can be written as linear matrix inequalities (LMIs) (see, e.g., [51]), we obtain P=P^=diag(1,1.1,1) by using LMI Toolbox in MATLAB. We calculate(41)F-1=0.18070.12950.09040.31680.05650.01320.01680.28320.0681,which is a nonnegative matrix. In view of Theorem 8, we solve the consensus gains as K=K^=(2,2.5,2).
According to Theorem8, multiagent system (1) with protocols (3) and (4) achieves consensus for τ(t) satisfying (42)τ˙t<1-ρ+β·F-11smax=1-1.1+1.1×0.4006=0.1392.With the initial state of each agent being taken randomly from [-1,1], we show in Figures 2(a)–2(c) a sample path of the consensus errors δi(i=1,…,4) by choosing τ(t)=0.05sin2(t). Clearly, (42) is satisfied, and consensus is achieved. In Figure 2(d), we show only the third component of δi(i=1,…,4) with τ(t)=0.2sin2(t). This delay violates condition (42), and consensus is not achieved.Figure 1
Communication topologiesG1,G2, and G3 for system (1).Figure 2
Consensus errors of multiagent system (1) with respect to different time-delay τ(t).
(a)
τ
(
t
)
=
0.05
s
i
n
2
(
t
)
(b)
τ
(
t
)
=
0.05
s
i
n
2
(
t
)
(c)
τ
(
t
)
=
0.05
s
i
n
2
(
t
)
(d)
τ
(
t
)
=
0.2
s
i
n
2
(
t)Example 2 (system without self-delay).
Consider multiagent system (2) with N=4 agents. The communication topologies switch amongst G1, G2, and G3 of Figure 3 following the same Markovian process as defined in Example 1. Note that each of these three graphs is balanced and d-regular with d=1. G1 and G3 contain spanning trees but G2 does not. The adjacency matrices Ai,A^i(i=1,2,3) and the agent dynamics A,B,A^,B^ are taken as in Example 1. Solving Lyapunov equation (28) by using LYAP function in MATLAB, we obtain(43)P=1-0.2857-0.5714-0.28571.2857-0.5000-0.5714-0.50002.3571,and P^=diag(1,1.1,1) as in Example 1. It follows from (29) that (44)R=-10.285700.2857-2.57140000.We calculate α=-0.9690, γ=2.2, and a nonnegative matrix(45)F-1=0.23070.14530.07860.17220.12040.25480.04700.37930.0682.From Theorem 11, we solve the consensus gains as K=K^=(1,2,1).
In light of Theorem11, multiagent system (2) with protocols (5) and (6) achieves consensus for τ(t) satisfying(46)τ˙t<1-max1≤i≤3⁡biρi+βi=1-max⁡0.2510,0.7557,0.0586=0.2443.With the initial state of each agent being taken randomly from [-1,1], we show in Figures 4(a)–4(c) a sample path of the consensus errors δi(i=1,…,4) by choosing τ(t)=0.1cos2(t). Since (46) is satisfied, consensus is achieved. We plot in Figure 4(d) only the third component of δi(i=1,…,4) with τ(t)=0.3cos2(t). Condition (46) does not hold, and consensus is not achieved.Figure 3
Communication topologiesG1,G2, and G3 for system (2).Figure 4
Consensus errors of multiagent system (2) with respect to different time-delay τ(t).
(a)
τ
(
t
)
=
0.1
c
o
s
2
(
t
)
(b)
τ
(
t
)
=
0.1
c
o
s
2
(
t
)
(c)
τ
(
t
)
=
0.1
c
o
s
2
(
t
)
(d)
τ
(
t
)
=
0.3
c
o
s
2
(
t
)Example 3 (tightness of bounds).
In this example, we consider multiagent system (1) with N=1000 agents. The communication topologies will randomly switch amongst 10 random graphs G1,…,G10 in the classical Erdős-Rényi G(N,p) model with p being the connection probability between any two nodes [52]. The generator of the underlying Markovian process θ(t) with S=1,2,…,10 is taken as Q=-10I10+110110T. The adjacency matrices Ai,A^i(i=1,2,…,10) and the agent dynamics A,B,A^,B^ are taken as in Example 1. Moreover, we fix τ(t)≡0.05.
The program stops if all components ofδi(i=1,2,…,10) are less than 10-5; if the program does not stop before t=104, we regard that the consensus is not achieved. For each given p, we collect 500 samples (1 sample consists of 10 graphs) to check whether the system finally achieves consensus. The fraction of samples that reach consensus is shown in Figure 5 as a function of p. The curve displays a sigmoidal variation with respect to p, saturating at 1 when p is just over 3.1×10-3. It is well known that [52] the random graphs are not connected with high probability if p<(ln⁡N)/N (here, about 6.9×10-3) in the large N limit. Figure 5 reveals that consensus can still be achieved with a much smaller p than the connectivity threshold indicating that the sufficient condition regarding connectivity in Theorem 8 can be weakened.Figure 5
Probability of reaching consensus for multiagent system (1) as a function of p over Markovian switching random graphs G(N,p).


## 5. Conclusion

This paper has studied the continuous-time consensus problem of linear multiagent systems under Markovian switching interaction topologies, random noises, and time-varying delays. The agent dynamics are described by linear time-invariant systems, in which two types of network-induced delays are considered, namely, delays affecting only the output of the agents’ neighbors and delays affecting both the agents’ own output and the output of their neighbors. Necessary and sufficient consensus conditions have been derived, respectively, for these two classes of multiagent systems. The design of consensus gains has a computationally advantageous decoupling feature. Numerical examples are given to demonstrate the effectiveness of the proposed methods. Although there is a gap between necessary and sufficient conditions, the necessary one seems to be tighter in view of the simulations. Future research worth investigation could be the heterogeneous time delays, general uncertainties, and systems with different dynamics (see, e.g., [53]).



---

*Source: 453072-2015-10-18.xml*