Consensus in Networks of Agents with Cooperative and Antagonistic Interactions

Abstract

This paper studies the consensus of first-order discrete-time multi-agent systems with fixed and switching topology, and there exists cooperative and antagonistic interactions among agents. A signed graph is used to model the interactions among agents, and some sufficient conditions for consensus are obtained by analyzing the eigenvalues of a Laplacian matrix in the case of fixed topology. The results indicate that having a spanning tree is only a necessary condition for the consensus of multi-agent systems with signed graphs, which is also affected by edge weights. Consensus is further discussed in the case of switching topology, and the results reveal that consensus can be reached if the controller gain and the union graphs among some consecutive time intervals satisfy some conditions. Finally, several simulation examples further confirm the theoretical results.

1. Introduction

Consensus has a long history in the distributed coordination of multi-agent systems [1]. It has important applications in the formation control of mobile robots [2,3], sensor networks [4,5], group decision, opinion forming [6,7], etc, and has been studied widely from many viewpoints, such as interaction topology [8,9], updated method of control input [10,11], convergence rate [12], dynamics of agents [13,14], and so on.

In the study of consensus, graphs are often applied to model the interactions among agents, where each node denotes one agent, and the weight associated with each edge represents the interaction intensity between two agents. In most existing works, such as [8,9,10,11,12,13,14], it is assumed that each weight is non-negative, which means agents are cooperative. For consensus with non-negative graphs, a lot of results have been obtained. For example, consensus can be reached for single integrators if and only if the interaction topology has a spanning tree, or if the eigenvalues of the Lapalacian matrix have some special features [15]. In addition to cooperative relationships, there are also antagonistic relationships in many contexts, such as economic systems, social networks, robot competitions, biology systems, and so on [16,17]. A negative weight can be applied to model these antagonistic relationships. A graph with a negative weight is called a signed graph [18]. It is quite meaningful to study the consensus of multi-agent systems with a signed graph.

In [19], consensus is discussed for first-order continuous-time multi-agent systems with signed graphs and bipartite consensus is first introduced. Some sufficient and necessary conditions are obtained in the case of fixed topology. If all agents eventually reach a state with the same magnitude but the opposite sign, then bipartite consensus is reached. Bipartite consensus is usually discussed for structurally balanced graphs, which can be converted into graphs with non-negative weights by applying a gauge transformation. Hence, the analysis for the consensus in the case of a signed graph is equivalent to that in the case of a non-negative graph. There has been some research into the bipartite consensus of multi-agent systems [20,21,22,23,24,25,26]. It should be noted that gauge transformations cannot be applied to structurally unbalanced graphs. In [20], bipartite consensus and trivial consensus were discussed for first-order discrete-time multi-agent systems in the case of structurally balanced signed graphs and structurally unbalanced signed graphs, respectively, where the control input was similar to that in [19] and the topology graph is fixed. In [21], some sufficient conditions for bipartite consensus were established for linear continuous-time multi-agent systems based on the event-triggered output feedback, where the topology graph was assumed to be fixed and structurally balanced. In [22], some adaptive neural network distributed control algorithms were proposed by using conventional Nussbaum-type functions, and some sufficient conditions for bipartite consensus were provided for high-order nonlinear multi-agent systems with signed time-varying graphs. In [23], the convergence behavior was analyzed for the discrete Altafini model, and some sufficient and necessary conditions were established for modulus consensus in the case of structurally balanced graphs and structurally unbalanced graphs, respectively, where module consensus includes consensus and bipartite consensus. In [24], the stabilizability of continuous-time multi-agent systems was considered and some relations between network topology and stabilizability were revealed. In [25], the bipartite consensus was discussed for continuous-time multi-agent systems with fixed topology, where an edge state is introduced. In [26], the behavior of continuous-time multi-agent systems was analyzed in the case of fixed topology and switching topology. Note that the topology graph was structurally balanced at all times and the two groups with antagonistic relations were time-invariant in [22,26].

Theonvergence was analyzed for first-order continuous-time and discrete-time multi-agent systems with signed graphs by virtue of an eventually positive matrix in [27], where the interaction graph was not assumed to be structurally balanced. The eventually positive matrix had a certain relation with a strongly connected graph. In [28], two kinds of protocols were discussed for first-order discrete-time multi-agent systems in the case of asynchronous interactions, where the first protocol was similar to that in [19] and the topology graph was fixed. The convergence behavior under two such protocols was analyzed by applying matrix theory and by reconstructing signed graphs.

In most work on consensus with signed graphs, such as that of [19,21,22], it is often assumed the the signed graph is a structurally balanced graph or the Laplacian matrix of the graph is similar to that in [19], then the convergence behavior of multi-agent systems, such as bipartite consensus, is further analyzed. This paper studies the consensus of first-order discrete-time multi-agent systems with signed graphs, which is different from the discrete-time model in [20,23]. The topology graph is not required to be a structurally balanced graph, and some sufficient conditions will be established for consensus in the case of fixed topology and switching topology, respectively, by applying matrix theory. In the case of switching topology, the topology does not need to have a spanning tree at each time to reach consensus.

This paper is organized as follows. Some concepts and models are introduced in Section 2. The main results are presented in Section 3. Simulations are provided to illustrate the effectiveness of the theoretical results in Section 4, and the concluding remarks are made in Section 5.

2. Preliminaries

2.1. Graph Theory

Some basic definitions in graph theory are introduced [29].

For a directed graph $\mathcal{G}$, let $\mathcal{V}\left(\mathcal{G}\right)$ and $\mathcal{E}\left(\mathcal{G}\right)$ denote its vertex set and edge set, respectively, where $\mathcal{V}\left(\mathcal{G}\right)=\{v_1,\cdots ,v_n\}$ and $\mathcal{E}\left(\mathcal{G}\right)\subseteq \mathcal{V}\left(\mathcal{G}\right)\times \mathcal{V}\left(\mathcal{G}\right)$. For edge $(v_j,v_i)$, $v_j$ is the parent vertex of $v_i$ and $v_i$ is the child vertex of $v_j$. An edge is called a self-loop if its two ends are the same vertex. For $v_i$, the set of its neighbors is denoted by $N(\mathcal{G},v_i)=\{v_j:(v_j,v_i)\in \mathcal{E}\left(\mathcal{G}\right)\}$ or $N(\mathcal{G},i)=\{j:v_j\in N(\mathcal{G},v_i)\}$. A (directed) path from $v_{i_1}$ to $v_{i_k}$ is a sequence, $v_{i_1},\cdots ,v_{i_k}$, of distinct vertices such that $(v_{i_j},v_{i_{j+1}})\in \mathcal{E}\left(\mathcal{G}\right),j=1,\cdots ,k-1$. A directed graph $\mathcal{G}$ is strongly connected if there exists a path from each vertex to each other vertex. A directed tree is a directed graph, where every vertex, except one special vertex, has exactly one parent vertex, and the special vertex, called a rooted vertex, has no parent vertices and can be connected to any other vertices by paths. A subgraph, ${\mathcal{G}}_s$, of $\mathcal{G}$ is a graph such that $\mathcal{V}\left({\mathcal{G}}_s\right)$$\subseteq \mathcal{V}\left(\mathcal{G}\right)$ and $\mathcal{E}\left({\mathcal{G}}_s\right)$$\subseteq \mathcal{E}\left(\mathcal{G}\right)$. ${\mathcal{G}}_s$ is said to be a spanning subgraph if $\mathcal{V}\left({\mathcal{G}}_s\right)=\mathcal{V}\left(\mathcal{G}\right)$. For any $v_i,v_j\in \mathcal{V}\left({\mathcal{G}}_s\right)$ if $(v_i,v_j)\in \mathcal{E}\left({\mathcal{G}}_s\right)$ if and only if $(v_i,v_j)\in \mathcal{E}\left(\mathcal{G}\right)$. Then ${\mathcal{G}}_s$ is said to be an induced subgraph of $\mathcal{G}$, and ${\mathcal{G}}_s$ is also said to be induced by $\mathcal{V}\left({\mathcal{G}}_s\right)$. A spanning tree of $\mathcal{G}$ is a directed tree which is a spanning subgraph of $\mathcal{G}$. $\mathcal{G}$ is said to have a spanning tree if some edges form a spanning tree of $\mathcal{G}$. A subgraph ${\mathcal{G}}_s$ is called a strongly connected component if it is the maximal strongly connected subgraph of $\mathcal{G}$. Furthermore, if there is no edge from any nodes except in ${\mathcal{G}}_s$ to nodes in ${\mathcal{G}}_s$, then ${\mathcal{G}}_s$ is called a rooted strongly connected component of $\mathcal{G}$.

A directed graph $\mathcal{G}$ with a matrix $A=\left[a_{ij}\right]\in {\mathbb{R}}^{n\times n}$ is called a weighted directed graph $\mathcal{G}\left(A\right)$, where $a_{ij}\ne 0$ if and only if $(v_j,v_i)\in \mathcal{E}\left(\mathcal{G}\right)$ and $a_{ii}=0,i=1,\cdots ,n$. $a_{ij}$ is called the weight of $(v_j,v_i)$. $\mathcal{G}\left(A\right)$ is also called an undirected graph if A is a symmetric matrix. Each element of the Laplacian matrix $L=\left(l_{ij}\right)\in {\mathbb{R}}^{n\times n}$ is defined as

$$l_{ij}=\left\{\begin{array}{cc}-a_{ij},\hfill & i\ne j\hfill \\ {\displaystyle \sum _{s=1,s\ne i}^n}{a}_{is},\hfill & i=j\hfill \end{array}\right..$$

(1)

If each element of A is non-negative, then A (resp. $\mathcal{G}\left(A\right)$) is called a non-negative matrix (resp. non-negative graph); otherwise, A (resp. $\mathcal{G}\left(A\right)$) is called a signed matrix (signed graph).

Let $\mathcal{G}\left(A\right(t\left)\right)$ denote the topology graph at time t, and let ${\mathcal{G}}_{t_1,\cdots ,t_s}$ denote the union graph of $\mathcal{G}\left(A\right(t\left)\right)$ at time $t_1,\cdots ,t_s$, where the vertex set of ${\mathcal{G}}_{t_1,\cdots ,t_s}$ is the same as that of $\mathcal{G}\left(A\right(t\left)\right)$. If there exists $t_k$ such that $(v_j,v_i)\in \mathcal{E}\left(\mathcal{G}\left(A\left(t_k\right)\right)\right),k\in \{1,\cdots ,s\}$, then $(v_j,v_i)\in \mathcal{E}\left({\mathcal{G}}_{t_1,\cdots ,t_s}\right)$.

The following properties of the Laplacian matrix have been proven in [15].

Lemma 1 

([15]). Assume A is a non-negative matrix; then,

(i) 

L has an eigenvalue of zero and ${\mathbf{1}}_n$ is the associated right eigenvector;

(ii) 

$\mathcal{G}\left(A\right)$ has a spanning tree if and only if L has an eigenvalue of zero and its other eigenvalues have positive real parts.

In Lemma 1, (i) still holds for a signed matrix, but (ii) does not always hold.

Example 1. 

Consider four agents with the topology shown in Figure 1.

Although $\mathcal{G}\left(A\right)$ has a spanning tree, the eigenvalues of its Laplacian matrix are 0, 1.6727, −1.8424, and 5.1755.

2.2. Model

Consider a group of agents with first-order discrete-time dynamics,

$$x_i(k+1)=x_i\left(k\right)+u_i\left(k\right),i=1,\cdots ,n,k=0,1,\cdots ,$$

(2)

where $x_i\left(k\right)$ and $u_i\left(k\right)$ are the state and conrol input (or protocol) of agent i at time k, respectively. Without loss of generality, assume $x_i\in \mathbb{R},i=1,\cdots ,n$. The following control input is introduced,

$$u_i\left(k\right)=h\sum _{j\in N_i}{a}_{ij}(x_j\left(k\right)-x_i\left(k\right)),i=1,\cdots ,n,k=0,1,\cdots ,$$

(3)

where h is the controller gain.

Let $X\left(t\right)={(x_1\left(t\right),x_2\left(t\right),\cdots ,x_n\left(t\right))}^T$, then the multi-agent system (2) with protocol (3) can be written as

$$X(k+1)=(I-hL)X\left(k\right),$$

(4)

where $L=\left(l_{ij}\right)\in {\mathbb{R}}^{n\times n}$ is demonstrated by (1).

For a signed graph, two kinds of consensus are mainly discussed: the traditional consensus and the bipartite consensus. The traditional consensus is considered in the following analysis.

Definition 1. 

For given protocol (3), multi-agent system (2) solves a consensus problem asymptotically if ${lim}_{k\to +\infty }(x_i\left(k\right)-x_j\left(k\right))=0,i,j=1,\cdots ,n,$ for any initial states $x_1\left(0\right),\cdots ,x_n\left(0\right)$.

Based on the results in [15], the following lemma is obtained.

Lemma 2. 

A consensus problem is solved asymptotically for the multi-agent system (2) with protocol (3) if and only if $I-hL$ has an algebraically simple eigenvalue 1, and its other eigenvalues are located in a unit circle.

Remark 1. 

Lemma 2 holds whether the topology graph is a non-negative graph or a signed graph. Note that the Laplacian matrix $L=\left(l_{ij}\right)\in {\mathbb{R}}^{n\times n}$ of a signed graph in some works, such as [19,20,21,23], is

$$l_{ij}=\left\{\begin{array}{cc}-a_{ij},\hfill & i\ne j\hfill \\ {\displaystyle \sum _{s=1,s\ne i}^n}\mid a_{is}\mid ,\hfill & i=j\hfill \end{array}\right.,$$

(5)

which is different from (1). For Lapalcian matrix (5), if the signed graph is structurally balanced, then it can be transformed into a non-negative graph by applying a gauge transformation, and the tools for analyzing a non-negative graph can consequently be used. However, a gauge transformation is not feasible for a Laplacian matrix (1).

3. Main Results

In this section, some sufficient conditions are provided for consensus in the case of fixed topology and switching topology, respectively.

3.1. Fixed Topology

For a directed graph $\mathcal{G}\left(A\right)$, let $\mathcal{G}\left(A_1\right)$ denote its rooted strongly connected component, and let $\mathcal{G}\left(A_2\right)$ denote the subgraph induced by the rest nodes. Thus,

$$A=\left(\begin{array}{cc}{A}_1& 0\\ A_{21}& A_2\end{array}\right),L=\left(\begin{array}{cc}{L}_1& 0\\ -A_{21}& L_2+diag\left\{A_{21}{\mathbf{1}}_{\mathbf{m}}\right\}\end{array}\right),$$

where $L_1\in {\mathbb{R}}^{m\times m}$ and $L_2\in {\mathbb{R}}^{(n-m)\times (n-m)}$ are the Laplacian matrices of $\mathcal{G}\left(A_1\right)$ and $\mathcal{G}\left(A_2\right)$, respectively. Let ${(b_{m+1},\cdots ,b_n)}^T=A_{21}{\mathbf{1}}_{\mathbf{m}}$.

First, some assumptions are made for $\mathcal{G}\left(A\right)$:

(A1)

$\mathcal{G}\left(A\right)$ has a spanning tree.

(A2)

Zero is an algebraically simple eigenvalue of $L_1$ and all the other eigenvalues of $L_1$ have positive real parts.

It is known that (A2) is satisfied when $A_1$ is non-negative. When $A_1$ is not non-negative, some methods are provided to verify whether (A2) is satisfied. For example, zero is an algebraically simple eigenvalue of $L_1$ and its other eigenvalues are with positive real parts if there exists a scalar $e\ge 0$ such that $e{\mathbf{I}}_m-L_1$ is an eventually positive matrix [27]. In addition, the verification of the eventually positive of matrix B can lead to the result in [30].

The following lemma is needed to establish the main result.

Lemma 3 

([31]). $C=\left(c_{ij}\right)\in R^{n\times n}$ is nonsingular if the following three conditions all hold:

(1) 

$c_{ii}\ge {\sum }_{j\ne i}\mid c_{ij}\mid ,i=1,\cdots ,n$;

(2) 

There exists $i\in \{1,\cdots ,n\}$ such that $c_{ii}>{\sum }_{j\ne i}\mid c_{ij}\mid$;

(3) 

For any $s\in S$, there exists $t\in T$ such that there exists a directed path from agent t to agent s, where $S=\{s:s\in \{1,\cdots ,n\}s\notin T\},T=\{t:t\in \{1,\cdots ,n\},and{c}_{tt}>{\sum }_{j\ne t}\mid c_{tj}\mid \}.$

By Lemma 3, a sufficient condition is established for the fixed topology case.

Theorem 1. 

Assume (A1) and (A2) hold. The multi-agent system (2) with protocol (3) solves a consensus problem asymptotically if the following conditions are all satisfied:

(1) 

$b_i+{\sum }_{j=m+1,j\ne i}^n{a}_{ij}\ge {\sum }_{j=m+1,j\ne i}^n\mid a_{ij}\mid ,i=m+1,\cdots ,n$;

(2) 

There exists $i\in \{m+1,\cdots ,n\}$ such that

$$b_i+\sum _{j=m+1,j\ne i}^n{a}_{ij}>\sum _{j=m+1,j\ne i}^n\mid a_{ij}\mid ;$$

(3) 

For any $s\in S$, there exists $t\in T$ such that a directed path from agent t to agent s exists, where $T=\{t:t\in \{m+1,\cdots ,n\},b_t+{\sum }_{j=m+1,j\ne t}^n{a}_{tj}>{\sum }_{j=m+1,j\ne t}^n\mid a_{tj}\mid \}$, and $S=\{s:s\in \{m+1,\cdots ,n\}ands\notin T\}$;

(4) 

$0<h<\widehat{h}={min}_{\lambda \in \mathsf{\Lambda }\left(L\right)}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2}$, where $\mathsf{\Lambda }(·)$ denotes the set of all nonzero eigenvalues of a matrix.

Proof. 

By Lemma 2, a consensus problem can be solved asymptotically for the multi-agent system (2) with protocol (3) if and only if $I-hL$ has an algebraically simple eigenvalue 1 and its other eigenvalues are located in a unit circle, where

$$\begin{array}{cc}\hfill I-hL=& \left(\begin{array}{cc}I-h{L}_1& 0\\ h{A}_{21}& I-h(L_2+diag\left\{A_{21}{\mathbf{1}}_{\mathbf{m}}\right\})\end{array}\right)\hfill \\ \hfill =& \left(\begin{array}{cc}I-h{L}_1& 0\\ h{A}_{21}& I-h(L_2+diag\{b_{m+1},\cdots ,b_n\})\end{array}\right).\hfill \end{array}$$

Next, the eigenvalues of $I-h{L}_1$ and $I-h(L_2+diag\{b_{m+1},\cdots ,b_n\})$ are analyzed, respectively.

By the first condition in Theorem 1, $L_2+diag\{b_{m+1},\cdots ,b_n\}$ is a diagonally dominant matrix. By Geršgorin’s Disk Theorem [32], the eigenvalues of $L_2+diag\{b_{m+1},\cdots ,b_n\}$ are zero or have positive real parts. By Lemma 3, $L_2+diag\{b_{m+1},\cdots ,b_n\}$ is nonsingular under conditions (1–3); namely, zero is not its eigenvalue. Hence, all eigenvalues of $L_2+diag\{b_{m+1},\cdots ,b_n\}$ have positive real parts. Obviously, $0<h<{min}_{\lambda \in \mathsf{\Lambda }\left(L\right)}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2}$ means

$$0<h<\underset{\lambda \in \mathsf{\Lambda }(L_2+diag\{b_{m+1},\cdots ,b_n\})}{min}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2},0<h<\underset{\lambda \in \mathsf{\Lambda }\left(L_1\right)}{min}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2},$$

and then all eigenvalues of $I-h(L_2+diag\{b_{m+1},\cdots ,b_n\})$ are located in a unit circle.

Based on (A2), $L_1$ has an algebraically simple eigenvalue 0 and its other eigenvalues are located in the right plane. By $0<h<{min}_{\lambda \in \mathsf{\Lambda }\left(L_1\right)}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2}$, 1 is an algebraically simple eigenvalue of $I-h{L}_1$, and its other eigenvalues are located in a unit circle.

Hence, 1 is an algebraically simple eigenvalue of $I-hL$, and its other eigenvalues are located in a unit circle. By Lemma 2, consensus can be reached asymptotically. □

In the multi-agent system with a leader, $m=1$. In this case, $\mathcal{G}\left(A_1\right)$ has only one agent, denoted by agent 1. Then, the following result is obtained.

Corollary 1. 

Assume (A1) holds and agent 1 is a rooted vertex. The multi-agent system (2) with protocol (3) solves a consensus problem asymptotically if the following conditions are all satisfied:

(1) 

$a_{i1}+{\sum }_{j=2,j\ne i}^n{a}_{ij}\ge {\sum }_{j=2,j\ne i}^n\mid a_{ij}\mid ,i=2,\cdots ,n$;

(2) 

There exists $i\in \{2,\cdots ,n\}$ such that

$$a_{i1}+\sum _{j=2,j\ne i}^n{a}_{ij}>\sum _{j=2,j\ne i}^n\mid a_{ij}\mid ;$$

(3) 

For any $s\in S$, there exists $t\in T$ such that a directed path from agent t to agent s exists, where $T=\{t:t\in \{2,\cdots ,n\},a_{t1}+{\sum }_{j=2,j\ne t}^n{a}_{tj}>{\sum }_{j=2,j\ne t}^n\mid a_{tj}\mid \}$, and $S=\{s:s\in \{2,\cdots ,n\}ands\notin T\}$;

(4) 

$h<{min}_{\lambda \in \mathsf{\Lambda }\left(L\right)}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2}={min}_{\lambda \in \mathsf{\Lambda }(L_2+diag\left\{A_{21}{\mathbf{1}}_{\mathbf{m}}\right\})}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2}$.

Especially, if $\mathcal{G}\left(A_2\right)$ is strongly connected, then condition (3) in Corollary 1 is obviously satisfied. Hence, the following corollary can be established.

Corollary 2. 

Assume agent 1 is a rooted vertex and $\mathcal{G}\left(A_2\right)$ is strongly connected. The multi-agent system (2) with protocol (3) solves a consensus problem asymptotically if the following conditions are all satisfied:

(1) 

$a_{i1}+{\sum }_{j=2,j\ne i}^n{a}_{ij}\ge {\sum }_{j=2,j\ne i}^n\mid a_{ij}\mid ,i=2,\cdots ,n$;

(2) 

There exists $i\in \{2,\cdots ,n\}$ such that

$$a_{i1}+\sum _{j=2,j\ne i}^n{a}_{ij}>\sum _{j=2,j\ne i}^n\mid a_{ij}\mid ;$$

(3) 

$h<{min}_{\lambda \in \mathsf{\Lambda }(L_2+diag\left\{A_{21}{\mathbf{1}}_{\mathbf{m}}\right\})}\frac{2\mathrm{Re}\lambda }{{\left|\lambda \right|}^2}$.

In this section, some sufficient conditions are provided for consensus in the case of fixed topology. For multiple agents with cooperative and antagonistic interactions, the topology structure, the cooperative and antagonistic intensity (or edge weight), and the controller gain jointly determine whether consensus can be reached.

3.2. Switching Topology

For the case of switching topology, a leader is introduced and is labeled as agent 0 for the multi-agent system (2). Assume the state of the leader is time-invariant; namely, $x_0(k+1)=x_0\left(k\right),k=0,1,\cdots$.

Consider the following protocol for the multi-agent system (2),

$$\begin{array}{cc}\hfill & u_i\left(k\right)=h[\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)(x_j\left(k\right)-x_i\left(k\right))+{\gamma }_i\left(k\right)(x_0\left(k\right)-x_i\left(k\right))],\hfill \\ \hfill & i=1,\cdots ,n,k=0,1,\cdots ,\hfill \end{array}$$

(6)

where $h>0,{\gamma }_i\left(k\right)\ge 0$, and ${\gamma }_i\left(k\right)>0$ denote agent i can receive the information from the leader.

Let ${\theta }_i\left(k\right)=x_i\left(k\right)-x_0\left(k\right)$, then multi-agent system (2) with protocol (6) can be written as:

$${\theta }_i(k+1)={\theta }_i\left(k\right)+h\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)({\theta }_j\left(k\right)-{\theta }_i\left(k\right))-h{\gamma }_i\left(k\right){\theta }_i\left(k\right).$$

(7)

Obviously, consensus can be reached for multi-agent system (2) with protocol (6) if and only if system (7) is asymptotically stable. Let $\Theta \left(k\right)={({\theta }_1\left(k\right),\cdots ,{\theta }_n\left(k\right))}^T$, then

$$\Theta (k+1)=(I-h(L\left(k\right)+R\left(k\right)\left)\right)\Theta \left(k\right),$$

(8)

where $R\left(k\right)=diag\{{\gamma }_1\left(k\right),\cdots ,{\gamma }_n\left(k\right)\}$.

Remark 2. 

In the works of consensus for discrete-time multi-agent systems, the Laplacian matrix is characterized by (1) or (5). Ref. [28] proposes two kinds of protocols for first-order discrete-time multi-agent systems with asynchronous interactions, where the Laplacian matrix in the second protocol is (1). Although the Laplacian matrix in protocol (6) is also (1), there is a difference between the second protocol in [28] and (6). In [28], it is assumed that the underlying interaction relationship is fixed, described by a fixed graph $\mathcal{G}$. That is, the topology graph at each time k, denoted by $\mathcal{G}\left(k\right)$, is the subgraph of $\mathcal{G}$. Such an assumption is not made for (6).

By analyzing the stability of system (8), a sufficient condition is obtained for consensus of multi-agent system (2) with protocol (6) in the case of time-varying topology. Let $\mathcal{G}\left(\widehat{A}\left(k\right)\right)$ denote the topology formed by the leader and n agents. It is assumed that $\{\mathcal{G}\left(\widehat{A}\left(0\right)\right),\mathcal{G}\left(\widehat{A}\left(1\right)\right),\cdots \}$ is a finite set.

Theorem 2. 

Assume there exists discrete time instants $n_0=0,n_1,\cdots$, where $n_0<n_1<\cdots$ and $n_{l+1}-n_l\le \overline{n},l=0,1,\cdots$, such that

$$\begin{array}{cc}\hfill & \sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))>\sum _{j\in N_i\left(k\right)}|\sum _{k\in [n_l,n_{l+1})}{a}_{ij}\left(k\right)|;\hfill \\ \hfill & i=1,2,\cdots ,n,l=0,1,\cdots \hfill \end{array}$$

(9)

then, there exists h such that multi-agent system (2) with protocol (6) solves a consensus problem asymptotically in the case of switching topology.

Proof. 

Let $\Gamma \left(k\right)=I-h\left(L\right(k)+R(k\left)\right)$; then,

$$\Theta \left(k\right)=\Gamma (k-1)\Gamma (k-2)\cdots \Gamma \left(0\right)\Theta \left(0\right).$$

The asymptotical stability of system (8) is equivalent to

$$\underset{k\to +\infty }{lim}\Gamma (k-1)\Gamma (k-2)\cdots \Gamma \left(0\right)=0.$$

Let $\Psi \left(l\right)=\Gamma (n_{l+1}-1)\Gamma (n_{l+1}-2)\cdots \Gamma \left(n_l\right)$; then,

$$\underset{k\to +\infty }{lim}\Gamma (k-1)\Gamma (k-2)\cdots \Gamma \left(0\right)=\underset{l\to +\infty }{lim}\Psi \left(l\right)\Psi (l-1)\cdots \Psi \left(0\right).$$

By calculation,

$$\begin{array}{cc}\hfill \Psi \left(l\right)=& \Gamma (n_{l+1}-1)\Gamma (n_{l+1}-2)\cdots \Gamma \left(n_l\right)\hfill \\ \hfill =& [I-h(L(n_{l+1}-1)+R(n_{l+1}-1))][I-h(L(n_{l+1}-2)+R(n_{l+1}-2))]\hfill \\ \hfill & \cdots [I-h(L\left(n_l\right)+R\left(n_l\right))]\hfill \\ \hfill =& I-h\sum _{k=n_l}^{n_{l+1}-1}(L\left(k\right)+R\left(k\right))+O\left(h^2\right)\hfill \end{array}$$

(10)

where $O\left(h^p\right)$ represents a matrix or a scalar, which is an infinitesimal of the same order of $h^p$, and p is a positive integer.

By (9), ${\sum }_{k\in [n_l,n_{l+1})}({\sum }_{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))>0$. Hence, h can be chosen small enough such that $1-h{\sum }_{k\in [n_l,n_{l+1})}({\sum }_{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))+O\left(h^2\right)>0$. Let h be small enough, then

$$\begin{array}{cc}\hfill \parallel \Psi \left(l\right)\parallel =& \underset{i=1,\cdots ,n}{max}\{1-h\sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))+O\left(h^2\right)\hfill \\ \hfill & +\sum _{j\in N_i\left(k\right)}|h\sum _{k\in [n_l,n_{l+1})}{a}_{ij}\left(k\right)+O\left(h^2\right)\left|\right\}\hfill \\ \hfill =& \underset{i=1,\cdots ,n}{max}\{1-h\sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))\hfill \\ \hfill & +h\sum _{j\in N_i\left(k\right)}|\sum _{k\in [n_l,n_{l+1})}{a}_{ij}\left(k\right)|+O\left(h^2\right)\}\hfill \\ \hfill =& \underset{i=1,\cdots ,n}{max}\{1-h{\varphi }_i\left(l\right)+O\left(h^2\right)\}\hfill \end{array}$$

where $\parallel \Psi \left(l\right)\parallel$ denotes the infinite norm of $\Psi \left(l\right)$, and

$${\varphi }_i\left(l\right)=\sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))-\sum _{j\in N_i\left(k\right)}|\sum _{k\in [n_l,n_{l+1})}{a}_{ij}\left(k\right)|.$$

By (9), ${\varphi }_i\left(l\right)>0,i=1,\cdots ,n,l=0,1,\cdots$. Hence, $0<1-h{\varphi }_i\left(l\right)+O\left(h^2\right)<1$ if h is small enough. There are finite different topologies among the leader and n agents, and $n_{l+1}-n_l\le \overline{n},l=0,1,\cdots$. Hence, $\{\Psi (0),\Psi (l),\cdots \}$ is a finite set. Let $d={max}_{l=0,1,2,\cdots }\parallel \Psi \left(l\right)\parallel$, then, $0<d<1$ and

$$\begin{array}{cc}\hfill & \underset{l\to +\infty }{lim}\parallel \Psi \left(l\right)\Psi (l-1)\cdots \Psi \left(0\right)\parallel \hfill \\ \le \hfill & \underset{l\to +\infty }{lim}\parallel \Psi \left(l\right)\parallel \parallel \Psi (l-1)\parallel \cdots \parallel \Psi \left(0\right)\parallel \hfill \\ \le \hfill & \underset{l\to +\infty }{lim}{d}^{l+1}\hfill \\ =\hfill & 0\hfill \end{array}$$

Thus, ${lim}_{l\to +\infty }\parallel \Psi \left(l\right)\Psi (l-1)\cdots \Psi \left(0\right)\parallel =0$; namely,

$$\underset{l\to +\infty }{lim}\Psi \left(l\right)\Psi (l-1)\cdots \Psi \left(0\right)=0.$$

Hence, ${lim}_{k\to +\infty }\Gamma (k-1)\Gamma (k-2)\cdots \Gamma \left(0\right)=0$ and ${lim}_{k\to +\infty }\Theta \left(k\right)=0$, which means system (8) is asymptotically stable. Consensus can be reached asymptotically. □

Remark 3. 

Some points should be noted. (9) implies that the union graph among the leader and n agents during each time interval $[n_l,n_{l+1})$ has a spanning tree. Based on the assumption that $\{\mathcal{G}\left(\widehat{A}\left(0\right)\right),\mathcal{G}\left(\widehat{A}\left(1\right)\right),\cdots \}$ is a finite set, there are finite inequalities in (9). In addition, the parameter d characterizes the convergence rate of multi-agent system (2) with protocol (6); namely, the smaller the parameter d, the faster the consensus is reached.

The following theorem further provides a range of h which ensures consensus.

Theorem 3. 

Assume there exists discrete time instants $n_0=0,n_1,\cdots$, where $n_0<n_1<\cdots$ and $n_{l+1}-n_l\le \overline{n},l=0,1,\cdots$, such that

$$\begin{array}{cc}\hfill & \sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))>\sum _{j\in N_i\left(k\right)}|\sum _{k\in [n_l,n_{l+1})}{a}_{ij}\left(k\right)|,\hfill \\ \hfill & i=1,2,\cdots ,n,l=0,1,\cdots \hfill \end{array}$$

(11)

If $0<h<\overline{h}$, then multi-agent system (2) with protocol (6) solves a consensus problems asymptotically in the case of switching topology, where

$$\overline{h}=\left\{\begin{array}{cc}min\{\frac{1}{{\epsilon }_2},\frac{1}{\varsigma },\frac{\varsigma }{\sigma }\},\hfill & if{\varsigma }^2-4\sigma \le 0\hfill \\ min\{\frac{1}{{\epsilon }_2},\frac{1}{\varsigma },\frac{\varsigma -\sqrt{{\varsigma }^2-4\sigma }}{2\sigma }\},\hfill & if{\varsigma }^2-4\sigma >0\hfill \end{array}\right.$$

and

$$\begin{array}{cc}\hfill & {\epsilon }_1=\underset{i=1,\cdots ,n,k=0,1,\cdots }{max}\left\{\right|\sum _{j\in N_i\left(k\right)}(a_{ij}\left(k\right)+{\gamma }_i\left(k\right))|+\sum _{j\in N_i\left(k\right)}|a_{ij}\left(k\right)\left|\right\},\hfill \\ \hfill & {\epsilon }_2=\underset{i=1,\cdots ,n,l=0,1,\cdots }{max}\{\sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}(a_{ij}\left(k\right)+{\gamma }_i\left(k\right)))\},\hfill \\ \hfill & \varsigma =\underset{i=1,\cdots ,n,l=0,1,\cdots }{min}\{\sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))-\sum _{j\in N_i\left(k\right)}|\sum _{k\in [n_l,n_{l+1})}{a}_{ij}\left(k\right)\left|\right\},\hfill \\ \hfill & \sigma =\underset{l=0,1,\cdots }{max}\{{\epsilon }_1^2{C}_{n_{l+1}-n_l}^2+\cdots +{\epsilon }_1^{n_{l+1}-n_l}{C}_{n_{l+1}-n_l}^{n_{l+1}-n_l}\}.\hfill \end{array}$$

Proof. 

By calculation,

$$\begin{array}{cc}\hfill \Psi \left(l\right)=& \Gamma (n_{l+1}-1)\Gamma (n_{l+1}-2)\cdots \Gamma \left(n_l\right)\hfill \\ \hfill =& [I-h(L(n_{l+1}-1)+R(n_{l+1}-1))][I-h(L(n_{l+1}-2)+R(n_{l+1}-2))]\hfill \\ \hfill & \cdots [I-h(L\left(n_l\right)+R\left(n_l\right))]\hfill \\ \hfill =& I-h{\Psi }_1\left(l\right)+{(-1)}^2{h}^2{\Psi }_2\left(l\right)+{(-1)}^3{h}^3{\Psi }_3\left(l\right)+\cdots \hfill \\ \hfill & +{(-1)}^{n_{l+1}-n_l}{h}^{n_{l+1}-n_l}{\Psi }_{n_{l+1}-n_l}\left(l\right),\hfill \end{array}$$

where

$$\begin{array}{c}{\Psi }_1\left(l\right)=\sum _{k=n_l}^{n_{l+1}-1}(L\left(k\right)+R\left(k\right))\hfill \\ {\Psi }_2\left(l\right)=\sum _{n_{l+1}>i>j\ge n_l}(L\left(i\right)+R\left(i\right))(L\left(j\right)+R\left(j\right))\hfill \\ {\Psi }_3\left(l\right)=\sum _{n_{l+1}>i>j>k\ge n_l}(L\left(i\right)+R\left(i\right))(L\left(j\right)+R\left(j\right))(L\left(k\right)+R\left(k\right))\hfill \\ \cdots \hfill \\ {\Psi }_{n_{l+1}-n_l}\left(l\right)=(L(n_{l+1}-1)+R(n_{l+1}-1))(L(n_{l+1}-2)+R(n_{l+1}-2))\hfill \\ \cdots (L\left(n_l\right)+R\left(n_l\right)).\hfill \end{array}$$

Obviously, $\parallel L\left(i\right)+R\left(i\right)\parallel \le {\epsilon }_1,i=0,1,\cdots$. Then,

$$\begin{array}{cc}\hfill & \parallel \Psi \left(l\right)\parallel \hfill \\ \le \hfill & \Vert I-h{\Psi }_1\left(l\right)\Vert +{\epsilon }_1^2{h}^2{C}_{n_{l+1}-n_l}^2+{\epsilon }_1^3{h}^3{C}_{n_{l+1}-n_l}^3+\cdots +{\epsilon }_1^{n_{l+1}-n_l}{h}^{n_{l+1}-n_l}{C}_{n_{l+1}-n_l}^{n_{l+1}-n_l}.\hfill \end{array}$$

By (11), ${\sum }_{k\in [n_l,n_{l+1})}({\sum }_{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))>0$ and ${\epsilon }_2>0$. If $0<h<\frac{1}{{\epsilon }_2}$, then $1-h{\sum }_{k\in [n_l,n_{l+1})}({\sum }_{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))>0$ and

$$\Vert I-h{\Psi }_1\left(l\right)\Vert =\underset{i=1,\cdots ,n}{max}\{1-h\sum _{k\in [n_l,n_{l+1})}(\sum _{j\in N_i\left(k\right)}{a}_{ij}\left(k\right)+{\gamma }_i\left(k\right))+h\sum _{j\in N_i\left(k\right)}|\sum _{k\in [n_l,n_{l+1})}{a}_{ij}\left(k\right)\left|\right\}.$$

By (11), $\varsigma >0$. Then, $\Vert I-h{\Psi }_1\left(l\right)\Vert \le 1-h\varsigma <1$ and

$$\parallel \Psi \left(l\right)\parallel \le 1-h\varsigma +h^2({\epsilon }_1^2{C}_{n_{l+1}-n_l}^2+\cdots +{\epsilon }_1^{n_{l+1}-n_l}{C}_{n_{l+1}-n_l}^{n_{l+1}-n_l})=1-h\varsigma +h^2\sigma .$$

If h satisfies

$$h\in \left\{\begin{array}{cc}(0,\frac{\varsigma }{\sigma }),\hfill & if{\varsigma }^2-4\sigma \le 0\hfill \\ (0,\frac{\varsigma -\sqrt{{\varsigma }^2-4\sigma }}{2\sigma }),\hfill & if{\varsigma }^2-4\sigma >0\hfill \end{array}\right.$$

then $0<1-h\varsigma +h^2\sigma <1$. Hence,

$$\begin{array}{cc}\hfill & \underset{l\to +\infty }{lim}\parallel \Psi \left(l\right)\Psi (l-1)\cdots \Psi \left(0\right)\parallel \hfill \\ \le \hfill & \underset{l\to +\infty }{lim}\parallel \Psi \left(l\right)\parallel \parallel \Psi (l-1)\parallel \cdots \parallel \Psi \left(0\right)\parallel \hfill \\ \le \hfill & \underset{l\to +\infty }{lim}{(1-h\varsigma +h^2\sigma )}^{l+1}\hfill \\ =\hfill & 0,\hfill \end{array}$$

which means ${lim}_{k\to +\infty }\Gamma (k-1)\Gamma (k-2)\cdots \Gamma \left(0\right)=0$ and system (8) is asymptotically stable. Therefore, consensus can be reached asymptotically. □

Remark 4. 

It is assumed that $\{\mathcal{G}\left(\widehat{A}\left(0\right)\right),\mathcal{G}\left(\widehat{A}\left(1\right)\right),\cdots \}$ is a finite set, and thus ${\epsilon }_1,{\epsilon }_2,\varsigma$ and σ can be obtained by finding the maximum or minimum from finite numbers. Although Theorem 3 is obtained based on the assumption ${\gamma }_i\left(k\right)\ge 0,i=1,\cdots ,n$, it still holds if there exists some ${\gamma }_i\left(k\right)<0$ by the proof of Theorem 3.

4. Simulations

In this section, some simulation examples are provided to illustrate the effectiveness of the theoretical results.

Example 2. 

Consider six agents, where the interaction topology among such six agents is shown in Figure 2. Obviously, the interaction topology has a spanning tree, and the subgraph induced by vertices 1, 5, and 6 is a rooted strongly connected component. The conditions in Theorem 1 hold for this multi-agent system. By calculation, $\widehat{h}=0.2$, and the eigenvalues of $L_1$ are 0, 1, and 5. Let $h=0.15,x_1\left(0\right)=-40,x_2\left(0\right)=75,x_3\left(0\right)=30,x_4\left(0\right)=45,x_5\left(0\right)=-20$, and $x_6\left(0\right)=-100$, then the state trajectories of such six agents are shown in Figure 3, which validates the effectiveness of Theorem 1.

Example 3. 

Consider four agents, labeled as agent 1, 2, 3, and 4, respectively. There is a leader for the four agents, labeled as agent 0. Assume the interaction topology among such five agents is chosen randomly from three topologies, shown in Figure 4, and each topology appears at each time interval $[3n,3n+2),n=0,1,\cdots$. The conditions in Theorem 2 are satisfied for this switching topology. Let $x_0=1,x_1\left(0\right)=-50,x_2\left(0\right)=20,x_3\left(0\right)=-10$, and $x_4\left(0\right)=65$, and the state trajectories of such four agents for $h=0.01,0.002,$ and $0.29$ are shown in Figure 5, Figure 6 and Figure 7, respectively, which validates the effectiveness of Theorem 2 and Theorem 3.

5. Conclusions

This paper has studied the consensus of first-order discrete-time multi-agent systems with cooperative and antagonistic interactions. By analyzing the eigenvalues of the Laplacian matrix, it is revealed that consensus is affected jointly by the interaction topology structure, the edge weights, and the controller gain in the case of fixed topology. For the case of switching topology, the results show that there exists controller gain such that consensus can be reached if the union graphs among some consecutive time intervals satisfy some quantity requirement, and the range for such a controller gain is further provided. It is shown that the topology graph at some time instants can be without a spanning tree, which is a relaxed requirement for the case of switching topology. However, the main results are obtained at the cost of restricting the range of the controller gain. The range may be relaxed by seeking other methods, which is our future focus point.

There are some other interesting problems for the consensus of agents with cooperative and antagonistic interactions. Several topics, such as the convergence rate, the robustness against uncertainties, and the consensus with predictive mechanism, require future research.