{'fraction_non_alphanumeric': 0.05045544851370094, 'fraction_numerical': 0.015181617123364697, 'mean_word_length': 4.056482183472328, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Consensusability of linear interconnected multi-agent systems

Consensusability is an important property for many multi-agent systems (MASs) as it implies the existence of networked controllers driving the states of MAS subsystems to the same value. Consensusability is of interest even when the MAS subsystems are physically coupled, which is the case for real-world systems such as power networks. In this paper, we study necessary and sufficient conditions for the consensusability of linear interconnected MASs. These conditions are given in terms of the parameters of the subsystem matrices, as well as the eigenvalues of the physical and communication graph Laplacians. Our results show that weak coupling between subsystems and fast information diffusion rates in the physical and communication graphs favor consensusability. Technical results are verified through computer simulations.


Motivation and state of the art
In the past decades, results on multi-agent systems (MASs) found applications in several fields, ranging from biological networks to cooperative robotics and power systems. Consensus, i.e., the achievement of an agreement on a quantity of interest for all agents, is one of the most interesting collective behaviours for MASs.
Consensusability of MASs amounts to assessing whether there exists a distributed protocol such that the MAS can achieve consensus. The consensusability problem for linear MASs has been extensively studied in the past decades. For example, Ma and Zhang (2010) show that for continuous-time linear MASs, if the dynamics of each agent is controllable and the communication topology is connected, the MAS can reach consensus. You and Xie (2011) show that for discrete-time linear MASs, the unstable eigenvalues of the agent state matrix should satisfy certain conditions depending on the eigenvalues of the communication Laplacian to guarantee consensus. For consensus in MASs with switching communication topologies, Wang et al. (2019) develop an approach based on the Lyapunov exponent of agent dynamics and a suitably defined synchronizability exponent for the switching topology. More specifically, they show that if the Lyapunov exponent is less than the synchronizability exponent, the MAS can achieve consensus. These results reveal connections between consensus, the agent dynamics and the switching topology. Furthermore, Xu et al. (2018) study consensusability problems over random communication channels among agents. They provide a consensusability condition based on the statistics of the communication channel, the eigenvalues of the communication Laplacian and the instability degree of the agent dynamics. Li et al. (2018), Zheng et al. (2019) and Xu et al. (2019) consider time delay in communication channels among agents and derive upper bounds on communication delay to guarantee consensus. All the above research works provide analytic characterizations of linear MASs in order to achieve consensus with linear consensus protocols. However, the above research works assume that the agents have decoupled dynamics, which is not the case in some applications. For example, in power networks and microgrids, each node is physically interconnected with other nodes and consequently their dynamics are coupled (Guerrero et al. (2010)). Therefore, in this paper, we study the consensusability problem for linear interconnected MASs (LIMASs) and try to reveal how it is affected by physical couplings among agents. Consensus for LIMASs has been studied by Chen et al. (2015) and Cheng and Ugrinovskii (2015). Chen et al. (2015) investigate consensusability of LIMASs with linear protocols. They show that the consensusability is equivalent to the stability of a matrix constructed from the agent dynamics and the consensus protocol. Moreover, an LMI-based design procedure is provided for the consensus protocol. Cheng and Ugrinovskii (2015) consider leader-follower tracking problems for LIMASs. Interactions between agents are treated as dynamic uncertainties and are described in terms of integral quadratic constraints. A leader-follower tracking control protocol is proposed and sufficient conditions to guarantee that the followers track the leader's state are obtained in terms of the feasibility of LMIs. However, Chen et al. (2015) and Cheng and Ugrinovskii (2015) only give consensus conditions in terms of the feasibility of certain LMIs, which provide little insight into how physical couplings affect consensus.

Objectives and contributions
In this paper, we are interested in studying how the coupling among agents affect the consensus problem. For this purpose, we provide analytical characterizations of the consensusability of LIMASs. Specifically, for general systems, we show that linear consensus protocol design is equivalent to a control design problem with structural constraints, which is intractable. With the help of technical assumptions introduced to simplify the problem, we show that the consensusability of the LIMAS is equivalent to a simultaneous stabilizability problem. Then we derive first a sufficient condition and then a necessary condition for consensusability. For LIMAS with scalar agent dynamics, we remove the requirement of the technical assumptions by directly analyzing the eigenvalues of the state matrix of the consensus error dynamics. A sufficient consensus condition is further provided. All the derived results clearly illustrate how the existence of a linear distributed consensus protocol for LIMASs is influenced by the interplay between the coupling matrix, the coupling topology, the agent dynamics and the control topology. This paper is organized as follows. The problem formulation is given in Section 2. The consensus conditions are derived in Section 3. Simulations are provided in Section 4 and some concluding remarks are provided in Section 5.

Notation
In the paper, the operator |·| applied to a set determines its cardinality, while used with matrices or vectors it defines their component-by-component absolute value. The operator · is used to define the matrix norm. We use A > 0 (A ≥ 0) for denoting that the specific matrix A is positive (semi-) definite. The symbol ⊗ represents the Kronecker product. 1 n ∈ R n and 0 n ∈ R n represent column vectors with all elements equal to one and zero, respectively.

Preliminaries on algebraic graph theory
An undirected weighted graph of N nodes is defined as G = (V, W, E), where V = {1, 2, . . . , N } is the set of nodes, E ⊆ V × V is the set of edges with |E| = M , and W ∈ R M×M is a diagonal matrix with the weight of the corresponding edge in each diagonal entry. For each node i, the set of its neighbors is defined as N i = {j|(i, j) ∈ E}. A path p ij is defined as a sequence of consecutive edges such that every edge in the sequence is in E, the first edge starts from node i, and the last edge ends in node j. The adjacency matrix of G is defined as A = [a ij ] N ×N , where a ij = 0 if (i, j) / ∈ E or i = j and a ij > 0 is the positive weight of edge (i, j) ∈ E. The degree of a node i is defined as d i = j∈Ni a ij along with the degree matrix D = diag (d 1 , d 2 , . . . , d N ). The Laplacian matrix of G is given by L = D − A. An undirected graph is connected if there exists a path from every node i to every other node j for all i, j ∈ V.

PROBLEM FORMULATION
We consider the problem of consensusability for linear interconnected multi-agent systems (LIMASs). A LIMAS  (Tucci et al. (2018)).
In the scope of this work, we assume that the communication graph G c is connected, as this is necessary to reach consensus. For each subsystem S i , the set of its neighbors in the physical graph G p is denoted by N p i {j|(i, j) ∈ E p }, whereas, similarly, the set of its neighbors in the communication graph G c is denoted by N c i {j|(i, j) ∈ E c }. Figure 1 presents an example LIMAS with N = 4 subsystems, where physical graph edges are shown with blue arrows and communication graph edges are shown with red arrows. In particular, a LIMAS consists of N subsystems where each subsystem S i has the following dynamics: where x i ∈ R n are the states of the subsystem, u i ∈ R are the scalar control inputs to the subsystem, A ∈ R n×n is the state matrix identical to all subsystems, a ij = a ji ∈ R >0 are the symmetrical physical interconnection weights between subsystems i and its neighbors in the physical graph G p , A p ∈ R n×n is a matrix determining the type of physical coupling, and B ∈ R n×1 is the control matrix identical to all subsystems.
In this paper, we are interested in networked controllers producing scalar control inputs u i by utilizing the information from neighbors. More specifically, consensus-based controllers are considered: where K ∈ R 1×n is a control gain that is common to all subsystems and b ij = b ji ∈ R >0 denote the symmetrical weights of the communication graph G c . This particular class of controllers is used to make the states of every subsystem converge to each other, i.e., achieve that |x i − x j | → 0 for all i, j ∈ V. By combining (1) and (2), the overall dynamics of the whole LIMAS can be written as: and L p , L c are the Laplacian matrices associated with G p and G c , respectively. Note that, in the field of consensus for MASs, it is common to assume identical subsystem dynamics and feedback gains as in (1), (2), since application areas of interest, such as vehicle formation, inherently consider a swarm of identical agents achieving a collective task (Fax and Murray (2004); Ren et al. (2007)). Moreover, using a single static feedback gain for all agents would also alleviate the burden of designing different consensus gains for each agent, which is critical in deploying large scale multi-agent systems. We are interested in the following problem: Problem 1. (Consensusability). Given the dynamics of LI-MAS in (3), provide conditions for the existence of a static feedback gain K ∈ R 1×n such that the states of the subsystems converge to a global consensus state, i.e., the states x i (t) satisfy lim for somex ∈ R n . Remark 2. We note that the formulation in (3) matches models commonly used in the literature on consensusability of linear multi-agent systems (You and Xie (2011)), with the difference of the physical coupling term L p ⊗ A p . Because of this term, the method in You and Xie (2011) cannot be used to analyze the consensusability of (3).
Since the subsystem states need to converge to the same value, one can define the average of the cumulative state and analyze the evolution of the deviation from this consensus state: In particular, (4) is equivalent to lim t→∞ |δ(t)| = 0 for all initial conditions δ(0). For this purpose, we study the dynamics of δ, which is derived from (3) and (5) as: As the consensusability of (3) is equivalent to the stabilizability of (6), Problem 1 is equivalent to the following problem: Problem 2. (Stabilizability). Provide conditions for the existence of a static feedback gain K ∈ R 1×n such that is Schur stable, i.e., its eigenvalues are within the unit circle in the complex plane.

CONSENSUSABILITY
In the sequel, we analyze separately consensusability for subsystems of order n > 1 and n = 1. This is because the former case is more difficult to analyze without further assumptions. Instead, the latter case with scalar subsystem dynamics can be studied without restrictive assumptions and gives important insight into the solution of Problem 2.
3.1 Subsystems of order n > 1 Problem 2 can be seen as the problem of designing controllers with structure constraints. Indeed, the aim is to make the matrix Schur stable by designing the state feedbackK with a sparsity constraint, i.e., a decentralized controller. Prior work in literature show that this problem is difficult to tackle without focusing on special system structures (Blondel and Tsitsiklis (2000); Rotkowitz and Lall (2005)). Therefore, to facilitate the analysis, we introduce the following technical assumption. Assumption 1. The Laplacian matrices L p and L c commute.
Remark 3. Note that Assumption 1 is verified when the two Laplacians are equal to each other up to a scaling constant, i.e., L p = βL c , β ∈ R. Moreover, two Laplacians commute also when one of them is the Laplacian of a complete graph with uniform edge weights. Nevertheless, necessary and sufficient conditions for two generic Laplacians to commute are not yet available in the literature.
It is well known that, under Assumption 1, one can simultaneously diagonalize the two Laplacians L p and L c (Horn and Johnson (1985)). Therefore, it is possible to find a unitary matrix Φ = 1 N / √ N , φ 2 , . . . , φ N such that Φ ⊤ L p Φ = Λ p = diag (0, λ p,2 , . . . , λ p,N ) and Φ ⊤ L c Φ = Λ c = diag (0, λ c,2 , . . . , λ c,N ) are diagonal matrices that collect the eigenvalues of L p and L c in their diagonals, respectively. Note that the entries of Λ p and Λ c are not necessarily ordered by their magnitude, with the exception of the first diagonal entries of both matrices, which are 0. Next, we denote the largest and second smallest eigenvalues of L p as λ p,max max i∈{2,...,N } λ p,i and λ p,min min i∈{2,...,N } λ p,i , respectively. For L c , λ c,max and λ c,min are similarly defined.
In order to show the existence of such a feedback gain K, it is required that each systemδ i for i ∈ {2, . . . , N } is controllable. Therefore, we assume the following: Assumption 2. The pairs (A − λ p,i A p , B) are controllable for all i ∈ {2, . . . , N }. Remark 4. We note that this assumption is required, as the controllability of all the pairs (A − λ p,i A p , B) is not implied by that of the pair (A, B) for general LIMASs. For instance, when A p = A and λ p,i = 1 is an eigenvalue of L p , one has A − λ p,i A p = 0 and the pair (A − λ p,i A p , B) is uncontrollable unless B is full rank. We also stress that the controllability of (A − λ p,i A p , B) implies that of (A − λ p,i A p , λ c,i B), as λ c,i > 0, ∀i ∈ {2, . . . , N }.
Without further assumptions on the structures of A and A p , stabilizability of (7) is the same as the problem of simultaneous stabilizability of a set of linear systems with a common static state feedback, given as Despite a number of results on the simultaneous stabilzability of linear systems (Kabamba and Yang (1991); Vidyasagar and Viswanadham (1982); Saadatjoo et al. (2009);Blondel (1994)), it is difficult to give conditions on the simultaneous stabilizability of more than two systems (Blondel and Gevers (1993)). Therefore, we analyze the consensusability problem in the following scenario. Assumption 3. The physical interconnection matrix A p satisfies A p = αA, where α ∈ R.
The following proposition presents a sufficient condition for consensusability of LIMASs under Assumption 3. Proposition 1. Suppose that Assumptions 1, 2, and 3 hold. Then, the LIMAS in (3) where α i 1 − αλ p,i , α max max i |α i |, α min min i |α i |, and with λ u (.) denoting the unstable eigenvalues of its argument. If the condition (8) is satisfied, the control gain K is given by and P equal to the solution to the modified algebraic Riccati equation (MARE) given by (13).
Proof. Under Assumptions 1 and 3, consensusability of (3) is equivalent to the simultaneous stabilizability of which is equivalent to the existence of a P i > 0 and K such that for all i ∈ {2, . . . , N }. Letting P i = P for all i and selecting a static feedback gain as K = −k(B ⊤ P B) −1 B ⊤ P A, one gets the following condition: for all i ∈ {2, . . . , N }. Defining α max = max i |α i |, it can be seen that (11) is satisfied for all i ∈ {2, . . . , N } if is satisfied for all i. We note that, (12), for each i, can be written for the pair (Ā, B) withĀ α max A: where σ i 2αiλc,ik−λ 2 c,i k 2 α 2 max . We emphasize that, ifĀ is stable, the systems in (10) are already stable with K = 0, hence, simultaneously stabilizable, which corresponds to the solution of (13) with σ i = 0 for all i. Proceeding with the case of unstableĀ, we leverage the results in Sinopoli et al. (2004) and Schenato et al. (2007) to show that a critical value σ c ∈ [0, 1) can be found as in (9) such that there exists a P > 0 that solves (13) for all i ∈ {2, . . . , N } simultaneously if and only if min i σ i > σ c . Taking into consideration that σ i is a function of k, λ p,i , and λ c,i , along with the fact that λ p,i s and λ c,i s have no particular order, the condition on the solvability of (13) transforms into the existence of a k such that holds. Noticing that 2α i λ c,j k − λ 2 c,j k 2 = −λ 2 c,j (k − αi λc,j ) 2 + α 2 i , we get: we can derive the following condition guaranteeing that (14) is satisfied: Using that max i,j (k − αi λc,j ) 2 = (max i,j |k − αi λc,j |) 2 and defining the function f (k) max i,j |k − αi λc,j | ≥ 0, it can be shown that arg min k f (k) 2 = arg min k f (k). Moreover, thanks to the definition of f (k), Remark 5. We point out that condition (8) can be satisfied only if its right hand side is positive. Therefore, it is necessary that α 2 min > α 2 max σ c for (8) to hold. Taking into account that σ c increases with α max , this is possible when α max is small and close to α min . Note that α max takes small values for low values of α, i.e., when the effect of physical coupling is not strong. Moreover, α min and α max are close to each other when α is small or λ p,min and λ p,max are close to each other. Also note that the left-hand side of the inequality in (8) decreases as the ratio λc,min λc,max increases, i.e., the eigenvalues of the communication graph get closer to each other. Since a bigger ratio λc,min λc,max signifies better synchronizability of a graph (You and Xie (2011)), we conclude that condition (8) is easier to satisfy when the physical interconnection is weaker and both physical and communication graphs diffuse information more quickly, i.e., when they are closer to the complete graph.
We also provide the following result, which presents a necessary condition for the consensusability of the LIMAS in (3). Proposition 2. Suppose that Assumptions 1 and 2 hold and define γ c λc,max λc,min ≥ 1. Then, a necessary condition for the stabilizability of the LIMAS in (3) is: Proof. The proof is a modification of the proof of Lemma 3.1 in You and Xie (2011). We first show that, under Assumption 2, without loss of generality, each pair (A − λ p,i A p , B) can be written in controllable canonical form where |a i,1 | = | det(A − λ p,i A p )|. Given a simultaneously stabilizing feedback gain K = [k 1 , . . . , k N ], one can see This yields |a i,1 − λ c,i k 1 | < 1, which can be further manipulated to give This implies that Then, the two conditions above give (16). ⊳ Remark 6. We would like to emphasize that the condition in Proposition 2 is necessary, meaning that (16) holds if the LIMAS in (3) is consensusable. Thus, it can be utilized to verify that a LIMAS is not consensusable, in which case, there does not exist a static feedback gain K that makes (6) stable. In order to show the role of physical coupling, we look at the extreme case of A = 0, for which, (16) reads as |det(A p )| γ c λ n p,min − λ n p,max < γ c + 1. This condition is satisfied for small | det(A p )|, i.e., weak physical coupling between subsystems. We also note that the condition given in Proposition 2 recovers the necessary condition in You and Xie (2011) in the case of physically decoupled systems, i.e., when A p =0.

First-order subsystems
As a simplified scenario, here we investigate the consensusability of LIMAS with scalar subsystem dynamics, i.e., A, B, K ∈ R, and n = 1. In this case, the matrices A, B, and K in (3) are denoted as a, b, and k, respectively. The matrix A p is omitted in the scalar case, since it can be lumped into a ij s. Although this scenario is a subset of the higher-order dynamics in 3.1, we do not need the Assumptions 1 and 3 in the analysis of this section, which makes the results more general. The dynamics of the LIMAS with scalar subsystem dynamics is rewritten as We note that, for scalar systems, Assumption 2 corresponds to b = 0. Therefore, throughout this section, we assume b = 1 without loss of generality. Proposition 3. Suppose that Assumption 2 holds. Define ∆ p λ p,max − λ p,min ≥ 0. Then, the scalar system (20) is consensusable if one of the following conditions hold: Besides, the control gain k can be selected as k Moreover, a necessary condition for the consensusability of the scalar system (20) is: Proof. We first note that Assumption 2 is satisfied for b = 1 in the scalar case. We then go on to realize that, in the scalar case, the dynamics of δ can be written as We note thatÃ is symmetric with an eigenpair {a, 1 N / √ N }; therefore, for a unitary matrix Ψ = [1 N / √ N , ψ 2 , . . . , ψ N ] the dynamics ofδ Ψ ⊤ δ can be defined as whereÃ andΛ are congruent to each other, andL p andL c are positive definite matrices with eigenvalues λ p,i and λ c,i for i ∈ {2, . . . , N }, respectively. By definition, δ 1 = 1 ⊤ N δ/ √ N = 0; thus, the stabilizability of (23) is equivalent to the existence of a scalar k such that the matrix aI N −1 −L p + kL c is stable.
Noticing that both aI N −1 −L p and kL c are symmetric matrices, one can utilize the results on the eigenvalues of summation of Hermitian matrices (Fulton (2000)) to show that Therefore, (23) is stabilizable if it is possible to find a k ∈ R such that a − λ p,min + λ max kL c < 1 and a − λ p,max + λ min kL c > −1, which gives way to − 1 − a + λ p,max < λ min kL c and Realizing that the sign of k changes the expression of λ min (kL c ) and λ max (kL c ), we inspect the two cases k ≥ 0 and k < 0 separately. For the first case, we have λ min (kL c ) = kλ c,min and λ max (kL c ) = kλ c,max and the conditions above simplify to k ∈ K + ∩R ≥0 , where K + is as given in (21). This is possible if K + = ∅ and K + ∩R ≥0 = ∅, which translate into (γ c − 1) (1 − a + λ p,min ) < γ c (2 − ∆ p ) and 1 − a + λ p,min > 0, respectively. For the second case, where k < 0, we have λ min (kL c ) = kλ c,max and λ max (kL c ) = kλ c,min . Conditions in (25) are then written as k ∈ K − ∩ R <0 , where K − is as given in (21). This is , and −1 − a + λ p,max < 0, respectively. The necessary condition given in the proposition is the restatement of the condition given in Proposition 2 for scalar subsystem dynamics. ⊳ Remark 7. The results presented in Proposition 3 give valuable insight into the interplay between the agent dynamics a, physical interconnection G p , and cyber interconnection G c . In particular, these conditions depend on the scalar a as well as eigenvalues of physical and communication Laplacians and how much they are separated from each other. Firstly, condition C2 is satisfiable only if a > −1. ∆ p < 2, i.e., when the difference between the largest and second smallest eigenvalues of L p is not greater than 2. This is possible if λ p,max is small or close to λ p,min . We also note that, given ∆ p < 2 and the first inequality of C1 is satisfied, γ c values satisfying the second inequality can always be found in a neighborhood of γ c = 1. Moreover, this also holds for condition C2, showing that having a communication graph whose Laplacian has eigenvalues that are close to each other is a favorable scenario. As in Remark 5, these observations also show that having weaker physical interconnections or physical and communication graphs that allow for faster information diffusion are favorable for consensusability, which agrees with the results in You and Xie (2011).

SIMULATION RESULTS
We now validate our technical results via computer simulations. For this, we are interested in a system with dynamics in (1), equipped with a consensus-based controller as in (2). System matrices are chosen as: The topology of G p is as in Figure 1 with uniform edge weights of 0.1. Consequently, to satisfy Assumption 1, the communication graph is selected to be a complete graph with unit edge weights, i.e., L c = I N − 1 N 1 N 1 ⊤ N . Therefore, the LIMAS satisfies Assumptions 1, 2, and 3, hence enabling the application of Proposition 1 to see whether it is consensusable. Noting that λ p = {0, 0.2, 0.2, 0.4} and λ c = {0, 4, 4, 4}, one can see that the condition in (8) is satisfied. Thus, it is possible to solve (13) through an LMI formulation and obtain the feedback gain K = −k(B ⊤ P B) −1 B ⊤ P A = [0 −0.3412] . Since this LIMAS satisfies the sufficient condition in Proposition 1, it is consensusable and it will reach consensus with the static feedback gain K calculated above. To verify this, we run a computer simulation on MATLAB for the closed-loop system with random initial states between 0 and 10. In Figure 2, we show that the 2-norm of the deviation from consensus state converges to zero for all subsystems S i , i.e., consensus is asymptotically reached.
Having shown that this LIMAS is indeed consensusable and it reaches consensus from random initial states with a specific selection of matrix K, we verify that the necessary condition in Proposition 2 also holds. Observing that γ c = 1, it is straightforward to see that (16) holds, which confirms the result given in Proposition 2.

CONCLUSION AND FUTURE PERSPECTIVES
In this paper, we have presented conditions on the consensusability of linear interconnected multi-agent systems, that are either necessary or sufficient. We analyzed the two cases where subsystems have first-order or higher-order dynamics. The latter class of LIMASs is more general, yet more challenging to analyze without additional assumptions. Instead, the analysis of the former class, albeit less general, leads to valuable insight into the consequences of having different interconnection and communication graphs. Our results show that, to achieve consensusability, it is favorable to have weaker physical coupling, i.e., smaller α or smaller λ p,max . In addition, smaller separation between the eigenvalues of the physical graph Laplacian, as well as the communication graph Laplacian, are also beneficial for consensusability.
The presented results in the case of vector dynamics rely heavily on the assumptions on the commutativity of Laplacians of physical and communication graphs, as well as on properties of the physical coupling. Therefore, in the future, we will work on eliminating these assumptions. Another possible research direction is to relate consensusability conditions to other properties of the two graphs, instead of only using the eigenvalue information. Analysis of the stability of a multi-layer consensus scheme, where there are multiple graphs through which subsystems are coupled with each other, is also a future perspective.