IEEE/CAA Journal of Automatica Sinica  2018, Vol. 5 Issue(6): 1044-1053 PDF
Necessary and Sufficient Conditions for Consensus in Third Order Multi-Agent Systems
Chi Huang1, Guisheng Zhai2, Gesheng Xu1
1. College of Mathematics, Taiyuan University of Technology, Taiyuan 030024, China;
2. Department of Mathematical Sciences, Shibaura Institute of Technology, Saitama 337-8570, Japan
Abstract: We deal with a consensus control problem for a group of third order agents which are networked by digraphs. Assuming that the control input of each agent is constructed based on weighted difference between its states and those of its neighbor agents, we aim to propose an algorithm on computing the weighting coefficients in the control input. The problem is reduced to designing Hurwitz polynomials with real or complex coefficients. We show that by using Hurwitz polynomials with complex coefficients, a necessary and sufficient condition can be obtained for designing the consensus algorithm. Since the condition is both necessary and sufficient, we provide a kind of parametrization for all the weighting coefficients achieving consensus. Moreover, the condition is a natural extension to second order consensus, and is reasonable and practical due to its comparatively decreased computation burden. The result is also extended to the case where communication delay exists in the control input.
Key words: Communication delay     consensus algorithms     graph Laplacians     Hurwitz polynomials     third order multi-agent systems
Ⅰ. INTRODUCTION

There has been great interest in cooperative control of multi-agent systems, where all agents are connected by a network (described by a graph), and they communicate to neighbor agents for necessary information such that the whole group can achieve a collective behavior. The specification for collective behavior includes flocks and swarms, sensor fusion, random networks, synchronization of coupled oscillators, formation control of multi robots, optimization-based cooperative control, etc. For more detailed information, see the cornerstone paper [1], the survey paper [2], the book [3], [4] and the references therein.

One important control problem in cooperative control is the consensus problem, which involves reaching an agreement regarding a certain quantity of interest that depends on the states of all agents. There are many important papers which have made great contributions in consensus problems for self-organizing networked systems [5]-[8]. For networked second-order integrators, [9] presented a necessary and sufficient condition for achieving consensus, where it is shown that both real and imaginary parts of the eigenvalues of the Laplacian matrix of the corresponding network play key roles. Recently, [10] presented a necessary and sufficient condition for consensus among second-order controllable canonical multi-agent systems. Both [9] and [10] dealt with communication delay in the discussion. The consensus problem of third-order nonlinear multi-agent systems with a fixed communication topology was discussed, and a consensus algorithm was proposed with several sufficient conditions in [11]. For consensus control of higher order linear systems, a sufficient and necessary condition was obtained in [12] where the local control input included two parts: a feedback controller and the interactions from the neighbors. The interconnection graph considered in [12] is undirected, and thus, the discussion can not be extended to directed interconnection cases. Moreover, an approach of achieving consensus for more general linear agents in the framework of matrix inequalities and stabilization was proposed in [13], and the extension to the consensus problem for networked nonholonomic systems was dealt with in [14]. For multi-agent systems with switching interconnection graphs, [15] adopted a combination of connected and disconnected graphs to achieve desired consensus, where the basic idea was inspired by switched systems analysis.

The main purpose of this paper is to extend the results in [9] and [10] to third order agents networked by directed interconnection graphs, that is, to provide a necessary and sufficient condition to design a consensus algorithm for a group of agents described by third order integrators. The motivation of dealing with third order agents is not only from theoretical interest but also from the fact that there are many real systems which are described by third order differential equations; for example, the location of bouncing robots, road vehicles with random terrain, and aircrafts in the wind [16], [17]. A typical example is a mass-spring-damper system with jerk term [16], [17] whose dynamics is described by $x^{(3)}=-a x^{(2)}+(x^{(1)})^2-x$. Third order integrators are the simplest third order linear systems, and they exist in real systems such as electronic circuits (shown later in Remark 1). Since single or double integrators are typically used in consensus control in the literature, we choose to focus on third order integrators in this paper.

As in the literature including [9] and [10], we assume here that the control input of each agent is constructed based on the weighted difference between its states and those of its neighbor agents, in a decentralized manner, and aim at proposing an algorithm for computing the weighting coefficients in the control input. The problem is reduced to design a third-order Hurwitz polynomial with real or complex coefficients. It is noted that the direct computation method in [9] and the frequency domain test approach in [10] can not be applied directly and effectively to design the third-order polynomial with complex coefficients. For that purpose, we propose to adopt the generalized Hurwitz condition [18] in our design, and obtain a necessary and sufficient condition for the consensus algorithm design. Since the obtained condition is both necessary and sufficient, we provide a kind of parametrization for all the weighting coefficients (feedback gains) achieving consensus. Moreover, the condition turns out to be a natural extension to second order consensus, and is reasonable and practical due to its comparatively decreased computation burden. The discussion is extended to the case where communication delay exists in the control input. With the same control gains as in the case without delay, we aim to establish a tight upper bound for the delay as a necessary and sufficient condition such that consensus is maintained when involving communication delay. It is noted that the method of discussing delay in the Hurwitz polynomial is encouraged and revised from that in [10]. Moreover, although the main idea and approach are different, we would like to mention that there have been many references discussing communication delays in consensus control of networked agents [19]-[23].

The remainder of this paper is organized as follows. In Section Ⅱ we give some preliminary information about graph theory and provide two lemmas for the benefit of discussion later. Section Ⅲ is devoted to describe the system of networked agents with the control input protocol including three design parameters, and to reduce the control problem to designing Hurwitz polynomials with complex coefficients. Then, Section Ⅳ gives a detailed discussion on the design of third-order Hurwitz polynomials together with some possible simplification and generalization. Furthermore, the extension to the case of control input with communication delay among agents is made in Section Ⅴ, where a tight upper bound is established for the delay such that the desired consensus is maintained when the real communication delay is smaller than the bound. Two numerical examples are given in Sections Ⅳ and Ⅴ to show effectiveness of the results. Finally, Section Ⅵ concludes the paper.

Ⅱ. PRELIMINARIES

Let us first review some basic definitions for graphs and consensus in network of multi-agents. The interconnection of a family of agents can be represented by using a directed graph (or digraph) $G=(\mathcal{V}, \mathcal{E})$ with the sets of nodes $\mathcal{V}=\{1, \ldots, N\}$ and edges $\mathcal{E}\subset \mathcal{V}\times \mathcal{V}$. The edge $(i, j) \in \mathcal{E}$ or $i \rightarrow j$ means that the information of the $i$th agent is available for the $j$th agent. The neighbor agents set of the $i$th agent is defined as $\mathcal{N}_i \stackrel{\mathit{\boldsymbol{\triangle}}}= \left\{j\in\mathcal{V} \Big| (j, i)\in \mathcal{E}\right\}$, which is the index set of the agents from which the $i$th agent can obtain necessary information.

A directed path is a sequence of ordered edges, and a digraph is called strongly connected if there is a directed path from every node to every other node. A directed tree is a digraph, where every node, except the root, has exactly one parent. A spanning tree of a digraph is a directed tree formed by graph edges that connect all the nodes of the graph. We say that a digraph has (or contains) a spanning tree if there exists a spanning tree that is a subset of the graph. It is known that the condition that a digraph has a spanning tree is equivalent to the case that there exists a node having a directed path to all other nodes.

The Laplacian of a graph is defined as $\mathcal{L}=[l_{ij}]_{N\times N}$, where

 $\begin{eqnarray*} l_{ij}= \begin{cases} -1, & j\in \mathcal{N}_i \\ |\mathcal{N}_i|, & j=i \\ 0, & \mbox{otherwise} \end{cases} \end{eqnarray*}$

and $|\mathcal{N}_i|$ denotes the number of neighbors of the $i$th agent. It is easy to see from the above definition that all row-sums of a graph Laplacian $\mathcal{L}$ are zero, and thus $\mathcal{L}$ always has a zero eigenvalue and a corresponding (right) eigenvector ${\bf 1} = [1\ 1\ \ldots\ 1]^T$, satisfying $\mathcal{L} {\bf 1}=0$. Furthermore, it is known that $rank(\mathcal{L})=N-1$ if and only if the graph has a spanning tree. For other spectral properties of graph Laplacians, see for example [24].

The next two lemmas will be used in the following sections.

Lemma 1 [25]: Suppose $A$ and $D$ are square matrices. Consider the determinant of the block matrix

 $\begin{eqnarray} W=\left[\begin{array}{cc} A & B \\ C & D \end{array}\right]. \end{eqnarray}$

1) If $|A| \ne 0$, then $|W|=|A|\times |D-CA^{-1}B|$

2) If $|D| \ne 0$, then $|W|=|D|\times|A-BD^{-1}C|$

3) If $AC=CA$, then $|W|=|AD-CB|$

4) If $BD=DB$, then $|W|=|DA-BC|$.

Lemma 2 [25]: Let $A_1\in\mathbb{R}^{n_1\times n_1}$, $A_2\in\mathbb{R}^{n_2\times n_2}$ and $A_3$ be arbitrary. Then, the following properties of the Kronecker product hold:

1) $A_1\otimes A_3+A_2\otimes A_3=(A_1+A_2)\otimes A_3$

2) $|A_1\otimes A_2|$=$|A_1|^{n_2}$$|A_2|^{n_1}$.

Ⅲ. PROBLEM FORMULATION

Consider a group of networked third order agents whose dynamics are described by

 $$$y_i^{(3)}(t) = u_i(t)\, , \quad i=1, 2, \ldots, N$$$ (1)

where $y_i(t)\in \mathbb{R}^m$ is generalized coordinate of the $i$th agent, and $u_i(t)\in \mathbb{R}^m$ is the control input. Let the Laplacian of the interconnection graph be denoted by $\mathcal{L}$. To consider consensus among the agents, we assume that there is a spanning tree in the graph, and thus $rank(\mathcal{L}) = N-1$. Throughout this paper, we assume that the eigenvalues of $\mathcal{L}$ are $\mu_1=0, \mu_2 \ne 0, \ldots, \mu_N \ne 0$.

Define

 $\begin{eqnarray} x_i &=& \left[\begin{array}{c} x_i^1 \\ x_i^2 \\ x_i^3 \end{array}\right] \equiv \left[\begin{array}{c} y_i \\ y_i^{(1)} \\ y_i^{(2)} \end{array}\right] \\ A_i &=& \left[\begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array}\right]\, , \quad b_i= \left[\begin{array}{c} 0 \\ 0 \\ 1 \end{array}\right] \end{eqnarray}$

and rewrite the system as

 $\begin{eqnarray} x_i^{(1)}(t) = A_i x_i(t) + b_i u_i(t)\, , \quad i=1, 2, \ldots, N\, . \end{eqnarray}$ (2)

As in the literature, we assume that the available information for the $i$th agent is the states of itself and the neighboring agents, i.e., $x_i$ and $\{x_j: j\in \mathcal{N}_i\}$. Then, the control problem is to design $u_i(t)$, using the available information, such that the consensus is achieved among all agents, that is,

 $\begin{eqnarray} x_i-x_j = \left[\begin{array}{c} x_i^1-x_j^1 \\ x_i^2-x_j^2 \\ x_i^3-x_j^3 \end{array}\right] \to 0\, , \quad \forall i \ne j. \end{eqnarray}$ (3)

Note that the consensus problem is different from the stabilization one in the sense that convergence to an equilibrium point such as the origin is not desired. In real systems, we usually do not want the system state to stop but rather, to track each other in a flexible manner. Therefore, even if the pair $(A_i, b_i)$ is controllable and we can use a local state feedback $u_i=K_ix_i$ to drive the state to zero, the consensus control of achieving ([3]) is significant.

Similarly to the literature such as [9] and [10], we adopt the control input (consensus protocol) given by

 $\begin{eqnarray} u_i &=& \displaystyle{\sum\limits_{j\in \mathcal{N}_i}} \left[\gamma_1(x_j^1-x_i^1)+\gamma_{2} (x_j^2-x_i^2) +\gamma_{3} (x_j^3-x_i^3)\right] \\ &=& \displaystyle{\sum\limits_{j\in \mathcal{N}_i} \sum\limits_{k=1}^3 \gamma_k (x_j^k-x_i^k)} \end{eqnarray}$ (4)

where $\gamma_1$, $\gamma_2$ and $\gamma_3$ are design parameters to be determined.

Remark 1: It is noted that the formulation of the third order integrator model in (1) is reasonable in two aspects. First, there are real examples that are described by third order integrators especially in electronic circuits. For example, consider a parallel circuit composed of an inductor ($L$) and a capacitor ($C$). If the variable $y$ is the electronic charge on the inductor, and the control input $u$ is the current in the capacitor, then we use Kirchhoff's law to obtain $u=CV^{(1)}=C(Ly^{(2)})^{(1)}$, or equivalently, $y^{(3)}=\frac{1}{LC}u$, which is exactly a third order integrator.

Secondly, in the case that the dynamical equation of each agent is given by the more general form

 $\begin{eqnarray} y_i^{(3)}(t) + \beta_1 y_i^{(2)}(t) + \beta_{2} y_i^{(1)}(t) + \beta_3 y_i (t)= u_i(t) \end{eqnarray}$

since it is reasonable to assume that each agent can obtain all states of itself, we define $u_i(t)=\bar{u}_i(t)+ \beta_1 y_i^{(2)}(t) + \beta_{2} y_i^{(1)}(t) + \beta_3 y_i (t)$ to obtain $y_i^{(3)}(t)=\bar{u}_i(t)$, which is exactly the third order integrator model (1). Then, as a result, we modify the control input (4) as

 $\begin{eqnarray} u_i &=& \displaystyle{\sum\limits_{j\in \mathcal{N}_i} \left[\gamma_1(x_j^1-x_i^1)+\gamma_{2} (x_j^2-x_i^2)+\gamma_{3} (x_j^3-x_i^3)\right]} \\ && + \beta_1 x_i^{3} + \beta_{2} x_i^2 + \beta_3 x_i^1 \end{eqnarray}$ (5)

with the same design parameters $\gamma_k$'s. The remaining discussion is completely the same.

Remark 2: Although in this paper we focus our attention on third order agents for notation simplicity, as can be seen later, it is easy to extend the discussion to higher order integrators described by

 $\begin{eqnarray*} y_i^{(n)}(t) = u_i(t)\, , \quad i=1, 2, \ldots, N\, . \end{eqnarray*}$

In this case, the matrices $A_i$ and $b_i$ are

 $\begin{eqnarray*} A_i = \left[\begin{array}{ccc} 0 & I_{n-1} \\ 0 & 0 \end{array}\right]\, , \quad b_i= \left[\begin{array}{c} 0_{(n-1)\times 1} \\ 1 \end{array}\right] \end{eqnarray*}s$

and the control input is $\begin{array} u_i = \displaystyle{\sum\limits_{j\in \mathcal{N}_i} \sum\limits_{k=1}^n \gamma_k (x_j^k-x_i^k)}\, . \end{array}$

The closed-loop system composed of the system (1) (or the system (2)) and the controller (4) is

 $\begin{eqnarray} \dot{\tilde{x}} = \left(\Theta\otimes I_m\right) \tilde{x} \end{eqnarray}$ (6)

where

 $\begin{eqnarray} \tilde{x}= \left[\begin{array}{c} x^1 \\ x^2\\ x^3 \end{array}\right]\, , \quad x^j = \left[\begin{array}{c} x_1^j \\ x_2^j \\ \vdots \\ x_N^j \end{array}\right]\, , \quad j=1, 2, 3 \end{eqnarray}$

and

 $\begin{eqnarray} \Theta = \left[\begin{array}{ccc} 0 & I_N & 0 \\ 0 & 0 & I_N \\ -\gamma_1 \mathcal{L} & -\gamma_2 \mathcal{L} & -\gamma_{3} \mathcal{L} \end{array}\right]. \end{eqnarray}$

According to Lemma 2, we obtain that the characteristic polynomial is

 $\left|\lambda I- \left(\Theta\otimes I_m\right) \right|= \left|(\lambda I- \Theta)\otimes I_m \right|= \left|(\lambda I- \Theta) \right|^m\, .$

Then, using the same technique as in [4], [9] and [10], the following fact can be proved easily.

Lemma 3: Consensus is achieved in (1) with (4) if and only if $\Theta$ has exactly three zero eigenvalues and all others have negative real parts.

According to Lemma 3, our design problem is to choose $\gamma_1$, $\gamma_2$ and $\gamma_3$ such that $\Theta$ has three zero eigenvalues and all others have negative real parts. To proceed, we need the following lemma to analyze the spectral property of $\Theta$.

Lemma 4: The characteristic equation of $\Theta$ is

 $$$\left|\lambda I- \Theta\right| = \left|\lambda^3 I_N+ (\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2 ) \mathcal{L}\right|\, .$$$ (7)

Furthermore, if the eigenvalues of $\mathcal{L}$ are $\mu_1, \ldots, \mu_N$, then

 $$$\left|\lambda I- \Theta\right| = \displaystyle{\prod\limits_{i=1}^N} \left( \lambda^3 + \left(\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2\right) \mu_i \right) \, .$$$ (8)

Proof: Using the definition of matrix eigenvalues, the characteristic equation of $\Theta$ is computed as

 $\begin{eqnarray} \left|\lambda I- \Theta\right| = \left|\begin{array}{ccc} \lambda I_{N} & -I_{N} & 0 \\ 0 & \lambda I_{N}&-I_{N} \\ \gamma_{1}\mathcal{L}& \gamma_{2}\mathcal{L}& \lambda I_{N} + \gamma_{3}\mathcal{L} \end{array}\right|\, . \end{eqnarray}$

In the case of $\lambda=0$, we have

 $\begin{eqnarray} \left|\lambda I- \Theta\right| &=& \left|\begin{array}{ccc} 0 & -I_{N} & 0 \\ 0 & 0 & -I_{N} \\ \gamma_{1}\mathcal{L} & \gamma_{2}\mathcal{L} & \gamma_{3}\mathcal{L} \end{array}\right| \\ &=& \left|\begin{array}{ccc} -I_{N} & 0 & 0\\ 0 & -I_{N} & 0\\ \gamma_{2}\mathcal{L} & \gamma_{3}\mathcal{L} &\gamma_{1}\mathcal{L} \end{array}\right| = |\gamma_1 \mathcal{L}| \end{eqnarray}$

which is consistent with (7) with $\lambda=0$.

In the case of $\lambda \ne 0$, we use 1) of Lemma 1 to obtain

 $\begin{eqnarray} \left|\lambda I- \Theta\right| &=& \left|\begin{array}{ccc} \lambda I_{N} & -I_{N} & 0 \\ 0 & \lambda I_{N}&-I_{N} \\ \gamma_{1}\mathcal{L} & \gamma_{2}\mathcal{L} & \lambda I_{N} + \gamma_{3}\mathcal{L} \end{array}\right| \\ &=& \left| \lambda I_{N} \right| \times \left| \left[\begin{array}{cc} \lambda I_{N} & -I_{N} \\ \gamma_{2}\mathcal{L} + \frac{\gamma_1}{\lambda} \mathcal{L}& \lambda I_{N} + \gamma_{3}\mathcal{L}\end{array}\right] \right| \end{eqnarray}$

and, by 3) or 4) of Lemma 1,

 $\begin{eqnarray} \left|\lambda I- \Theta\right| &=& \left| \lambda I_{N} \right| \times \left| \lambda^2 I_{N} + \gamma_3\lambda \mathcal{L} + \gamma_2 \mathcal{L} + \frac{\gamma_1}{\lambda} \mathcal{L} \right| \\ &=& \left|\lambda^3 I_N+ (\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2 )\mathcal{L}\right| \, . \end{eqnarray}$

This completes the proof of (7).

Next, when the eigenvalues of $\mathcal{L}$ are $\mu_1, \mu_2, \ldots, \mu_N$, the eigenvalues of $-\mathcal{L}$ are $-\mu_1, -\mu_2, \ldots, -\mu_N$, which leads to

 $\begin{eqnarray} \left|\zeta I_N+ \mathcal{L}\right| = \prod\limits_{i=1}^N (\zeta+\mu_i)\, , \end{eqnarray}$

and thus

 $\begin{eqnarray} {\left|\lambda I- \Theta\right|} \\ &=& \left( \gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2 \right)^N \left|\frac{\lambda^3}{\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2} I_N+ \mathcal{L}\right| \\ &=& \left( \gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2 \right)^N \displaystyle{\prod\limits_{i=1}^N} \left( \frac{\lambda^3}{\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2} +\mu_i \right) \\ &=& \displaystyle{\prod\limits_{i=1}^N} \left( \lambda^3 + \left(\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2\right) \mu_i \right)\, . \end{eqnarray}$

It is observed from the above that $\mu_1=0$ corresponds to three zero eigenvalues of $\Theta$. Therefore, according to Lemma 3, our design problem is reduced to choosing $\gamma_1$, $\gamma_2$ and $\gamma_3$ such that the zeros of

 $\begin{eqnarray} p_{\mu}(\lambda) = \lambda^3 + (\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2)\mu \end{eqnarray}$

have negative real parts for all $\mu=\mu_i$, $i=2, \ldots, N$.

Remark 3: Although the approaches in [9] and [10] are efficient in analyzing second order Hurwitz polynomials, they can not be used to design the third order polynomial $p_{\mu}(\lambda)$. More precisely, the method in [9] needs to solve the characteristic equation with parameters, which is difficult for third equations. The design procedure in [10] is based on a frequency domain test for Hurwitz polynomial where it is required to check whether a polynomial pair is interlaced or not, which is also difficult in the present case.

Ⅳ. DESIGN OF CONSENSUS PROTOCOL

In this section, we discuss how to design the parameters $\gamma_1$, $\gamma_2$ and $\gamma_3$ in the consensus protocol (4) such that the zeros of $p_{\mu}(\lambda)$ have negative real parts for all $\mu=\mu_i$, $i=2, \ldots, N$.

A. Approach Using Real Hurwitz Polynomials

Notice that when $\mu_i$ is a nonzero complex eigenvalue of $\mathcal{L}$, $\bar{\mu}_i$ is also an eigenvalue of $\mathcal{L}$. In addition,

 $\begin{eqnarray*} p_{\mu_i}(\lambda) p_{\bar{\mu}_i}(\lambda) &=& \left( \lambda^3 + \left(\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2\right) \mu_i \right) \\ && \times \left( \lambda^3 + \left(\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2\right) \bar{\mu}_i \right) \end{eqnarray*}$

is a polynomial with real coefficients. Then, based on the discussion in Section Ⅲ, we have the following result.

Lemma 5: Suppose $\mathcal{L}$ has one zero eigenvalue $\mu_1=0$, $s-1$ nonzero real eigenvalues $\mu_2, \ldots, \mu_s$, and $2p$ complex eigenvalues $\sigma_1$, $\bar{\sigma}_1$, $\ldots$, $\sigma_p$, $\bar{\sigma}_p$ $(s+2p=N)$. Then, consensus is achieved if and only if all $p_{\mu_i}(\lambda)\ (2\leq i \leq s)$ and $p_{\sigma_j}(\lambda)p_{\bar{\sigma}_j}(\lambda)$ $(1\le j \le p)$ are real Hurwitz polynomials with respect to $\lambda$.

For $\mu_i=a_i>0$ ($2 \le i \le s$),

 $\begin{eqnarray} p_{\mu_i}(\lambda) = \lambda^3 + (\gamma_3 a_i) \lambda^2 + (\gamma_2 a_i) \lambda + \gamma_1 a_i\, . \end{eqnarray}$

The Hurwitz matrix of $p_{\mu_i}(\lambda)$ is

 $$$H_1=\left[\begin{array}{ccc} \gamma_3 a_i & \gamma_1 a_i & 0 \\ 1 & \gamma_2 a_i & 0 \\ 0 & \gamma_3 a_i & \gamma_1 a_i \end{array}\right]$$$ (9)

and thus, the necessary and sufficient condition for the zeros of $p_{\mu_i}(\lambda)$ to have negative real parts is

 $\begin{eqnarray} \gamma_3 a_i > 0\, , \quad \left|\begin{array}{cc} \gamma_3 a_i & \gamma_1 a_i \\ 1 & \gamma_2 a_i \end{array}\right|>0 \\ \left|\begin{array}{ccc} \gamma_3 a_i & \gamma_1 a_i & 0 \\ 1 & \gamma_2 a_i & 0 \\ 0 & \gamma_3 a_i & \gamma_1 a_i \end{array}\right|>0\, . \end{eqnarray}$

Solving these inequalities, we reach

 $$$\gamma_1 >0, \quad \gamma_3>0, \quad \gamma_2> \frac{\gamma_1}{\gamma_3 a_i}$$$ (10)

which gives a simple and explicit condition for the parameters.

However, for $\sigma_{j}= b_j + \sqrt{-1}\, c_j$ ($b_j>0$, $1 \le j \le p$), which is not real, the degree of $p_{\sigma_j}(\lambda)p_{\bar{\sigma}_j}(\lambda)$ is $6$. Then, if we apply the Hurwitz matrix condition under which the zeros of $p_{\sigma_j}(\lambda)p_{\bar{\sigma}_j}(\lambda)$ have negative real parts, we will obtain very complicated inequalities which are not practical.

B. Approach Using Complex Hurwitz Polynomials

To overcome the computational difficulty mentioned in the above subsection, we choose to consider the zeros of each $p_{\sigma_j}(\lambda)$ and $p_{\bar{\sigma}_j}(\lambda)$ separately. Fortunately, since

 $\begin{eqnarray} \bar{p}_{\sigma_j}(\lambda) = p_{\bar{\sigma}_j}(\lambda)\, , \end{eqnarray}$

zeros of $p_{\sigma_j}(\lambda)$ are conjugate to those of $p_{\bar{\sigma}_j}(\lambda)$. Using this fact, we can rewrite Lemma 5 by using Hurwitz polynomials with complex coefficients.

Lemma 6: Suppose $\mathcal{L}$ has one zero eigenvalue $\mu_1=0$, $s-1$ nonzero real eigenvalues $\mu_2, \ldots, \mu_s$, and $2p$ complex eigenvalues $\sigma_1$, $\bar{\sigma}_1$, $\ldots$, $\sigma_p$, $\bar{\sigma}_p$ $(s+2p=N)$. Then, consensus is achieved in (1) with (4) if and only if all $p_{\mu_i}(\lambda)\ (2\leq i \leq s)$ and $p_{\sigma_j}(\lambda)$ $(1\le j \le p)$ are complex Hurwitz polynomials with respect to $\lambda$.

To use the above lemma for consensus parameters design, we need the condition under which a polynomial with complex coefficients is Hurwitz.

Lemma 7 [18]: The polynomial $p(z)$ with complex coefficients,

 $\begin{eqnarray} \begin{array}{c} p(z)=z^n+\alpha_1 z^{n-1}+\alpha_2 z^{n-2}+ \cdots+\alpha_n\, , \\ (\alpha_k=p_k+\sqrt{-1}q_k, \ k=1, \ldots, n) \end{array} \end{eqnarray}$

has all its zeros in the left half-plane if and only if the next determinants are all positive.

 $\begin{eqnarray} \begin{array}{l} \Delta_1=p_1\, , \quad \Delta_2=\left|\begin{array}{cc|c} p_1 & p_3 & -q_2 \\ 1 & p_2 & -q_1 \\ \hline 0 & q_2 & p_1 \end{array}\right| \\ \Delta_3=\left|\begin{array}{ccc|cc} p_1 & p_3 & p_5 & -q_2 & -q_4 \\ 1 & p_2 & p_4 & -q_1 & -q_3 \\ 0 & p_1 & p_3 & 0 & -q_2 \\ \hline 0 & q_2 & q_4 & p_1 & p_3 \\ 0 & q_1 & q_3 & 1 & p_2 \end{array}\right| \end{array} \end{eqnarray}$
 $\begin{array}{l} \Delta_k=\left|\begin{array}{ccccc|cccc} p_1 & p_3 & p_5 & \ldots & p_{2k-1} & -q_2 & -q_4 & \ldots & -q_{2k-2} \\[0mm] 1 & p_2 & p_4 & \ldots & p_{2k-2} & -q_1 & -q_3 & \ldots & -q_{2k-3} \\[0mm] & & & \ldots & & & & \ldots & \\[0mm] 0 & & & \ldots & p_k & 0 & & \ldots & -q_{k-1} \\[0mm] \hline 0 & q_2 & q_4 & \ldots & q_{2k-2} & p_1 & p_3 & \ldots & p_{2k-3} \\[0mm] 0 & q_1 & q_3 & \ldots & q_{2k-3} & 1 & p_2 & \ldots & p_{2k-4} \\[0mm] & & & \ldots & & & & \ldots & \\[0mm] 0 & & & \ldots & q_k & 0 & & \ldots & p_{k-1} \end{array}\right| \\ k=2,3, \ldots, n\,\, (p_r=q_r=0\ \mbox{for}\ r>n). \end{array}$

Using the above lemma for

 $\begin{array}{l} {p_{\sigma_j}(\lambda)} \\ &=& \lambda^3 +(\gamma_1+\gamma_2 \lambda + \gamma_3 \lambda^2)(b_j+\sqrt{-1}c_j) \\ &=& \lambda^3 +(\gamma_3b_j+\sqrt{-1}\, \gamma_3 c_j) \lambda^2 + (\gamma_2 b_j + \sqrt{-1}\, \gamma_2 c_j) \lambda \\ && + (\gamma_1 b_j + \sqrt{-1}\, \gamma_1 c_j) \, , \end{array}$

where $p_1=\gamma_3b_j, q_1=\gamma_3c_j, p_2=\gamma_2b_j, q_2=\gamma_2c_j, p_3=\gamma_1b_j, q_3=\gamma_1c_j$ in $p(z)$, we obtain that the polynomial $p_{\sigma_j}(\lambda)$ has all its zeros in the left half-plane if and only if

 $\Delta_{1j} = \gamma_3b_j>0$ (11)
 $\begin{eqnarray} \Delta_{2j} &=& \left|\begin{array}{rr|r} \gamma_3b_j & \gamma_1b_j & -\gamma_2c_j \\ 1 & \gamma_2b_j & -\gamma_3c_j \\ \hline 0 & \gamma_2c_j & \gamma_3b_j \end{array}\right| >0 \end{eqnarray}$ (12)
 $\begin{eqnarray} \Delta_{3j} &=& \left|\begin{array}{ccc|cc} \gamma_3b_j & \gamma_1b_j & 0 & -\gamma_2c_j & 0 \\ 1 & \gamma_2b_j & 0 & -\gamma_3c_j & -\gamma_1c_j \\ 0 & \gamma_3b_j & \gamma_1b_j & 0 & -\gamma_2c_j \\ \hline 0 & \gamma_2c_j & 0 & \gamma_3b_j & \gamma_1b_j \\ 0 & \gamma_3c_j & \gamma_1c_j & 1 & \gamma_2b_j \end{array}\right|>0\, . \\ \end{eqnarray}$ (13)

Since $b_j>0$, the condition (10) requires $\gamma_3>0$. Concerning (12), we obtain after simple calculation that

 $$$\Delta_{2j} = \gamma_2\gamma_3^2 b_j(b_j^2+c_j^2)-\gamma_1 \gamma_3 b_j^2-\gamma_2^2 c_j^2 > 0 \, .$$$ (14)

Next, we try to simplify the computation of $\Delta_{3j}$. Using the property of determinants (exchange the 3rd and the 4th row, and then exchange the 3rd and the 4th column), we obtain

 $\begin{eqnarray*} \Delta_{3j} = \left|\begin{array}{ccc|cc} \gamma_3b_j & \gamma_1b_j & -\gamma_2c_j & 0 & 0 \\ 1 & \gamma_2b_j & -\gamma_3c_j & 0 & -\gamma_1c_j \\ 0 & \gamma_2c_j & \gamma_3b_j & 0 & \gamma_1b_j \\ \hline 0 & \gamma_3b_j & 0 & \gamma_1b_j & -\gamma_2c_j \\ 0 & \gamma_3c_j & 1 & \gamma_1c_j & \gamma_2b_j \end{array}\right|. \end{eqnarray*}$

Notice that the leading principal minor of order $3$ in $\Delta_{3j}$ is exactly $\Delta_{2j}$, and thus $\Delta_{2j}>0$ results in

 $\begin{array}{l} &&{ \left[\begin{array}{ccc} \gamma_3b_j & \gamma_1b_j & -\gamma_2c_j \\ 1 & \gamma_2b_j & -\gamma_3c_j \\ 0 & \gamma_2c_j & \gamma_3b_j \end{array}\right]^{-1} = \frac{1}{\Delta_{2j}} } \\ && \times\left[\begin{array}{ccc} \gamma_2\gamma_3(b_j^2+c_j^2) & -\gamma_1\gamma_3b_j^2-\gamma_2^2c_j^2 & (\gamma_2^2-\gamma_1\gamma_3)b_jc_j \\ -\gamma_3b_j & \gamma_3^2b_j^2 & \gamma_3^2b_jc_j-\gamma_2c_j \\ \gamma_2c_j & -\gamma_2\gamma_3b_jc_j & \gamma_2\gamma_3b_j^2-\gamma_1b_j \end{array}\right]\, . \end{array}$

Then, using 1) of Lemma 1, we obtain after some manipulation that

 $\begin{array}{l} {\Delta _{3j}} = {\mkern 1mu} {\Delta _{2j}}\\ \;\;\;\;\;\;\;\;\;\; \times \left| {\left[ {\begin{array}{*{20}{c}} {{\gamma _1}{b_j}}&{ - {\gamma _2}{c_j}}\\ {{\gamma _1}{c_j}}&{{\gamma _2}{b_j}} \end{array}} \right] - \left[ {\begin{array}{*{20}{c}} 0&{{\gamma _3}{b_j}}&0\\ 0&{{\gamma _3}{c_j}}&1 \end{array}} \right]} \right.\\ \;\;\;\;\;\;\;\;\;\; \times \left. {{{\left[ {\begin{array}{*{20}{c}} {{\gamma _3}{b_j}}&{{\gamma _1}{b_j}}&{ - {\gamma _2}{c_j}}\\ 1&{{\gamma _2}{b_j}}&{ - {\gamma _3}{c_j}}\\ 0&{{\gamma _2}{c_j}}&{{\gamma _3}{b_j}} \end{array}} \right]}^{ - 1}}\left[ {\begin{array}{*{20}{c}} 0&0\\ 0&{ - {\gamma _1}c}\\ 0&{{\gamma _1}b} \end{array}} \right]} \right|\\ \;\;\;\;\; = {\Delta _{2j}} \times \left| {\left[ {\begin{array}{*{20}{c}} {{\gamma _1}{b_j}}&{ - {\gamma _2}{c_j}}\\ {{\gamma _1}{c_j}}&{{\gamma _2}{b_j}} \end{array}} \right] - \left[ {\begin{array}{*{20}{c}} 0&{\frac{{ - {\gamma _1}{\gamma _2}{\gamma _3}b_j^2{c_j}}}{{{\Delta _{2j}}}}}\\ 0&{\frac{{{\gamma _1}{\gamma _2}{\gamma _3}b_j^3 - \gamma _1^2b_j^2}}{{{\Delta _{2j}}}}} \end{array}} \right]} \right|\\ \;\;\;\;\; = {\Delta _{2j}} \times \left| {\begin{array}{*{20}{c}} {{\gamma _1}{b_j}}&{ - {\gamma _2}{c_j} + \frac{{{\gamma _1}{\gamma _2}{\gamma _3}b_j^2{c_j}}}{{{\Delta _{2j}}}}}\\ {{\gamma _1}{c_j}}&{{\gamma _2}{b_j} - \frac{{{\gamma _1}{\gamma _2}{\gamma _3}b_j^3 - \gamma _1^2b_j^2}}{{{\Delta _{2j}}}}} \end{array}} \right|\\ \;\;\;\; = \left| {\begin{array}{*{20}{c}} {{\gamma _1}{b_j}}&{ - {\gamma _2}{c_j}{\Delta _{2j}} + {\gamma _1}{\gamma _2}{\gamma _3}b_j^2{c_j}}\\ {{\gamma _1}{c_j}}&{{\gamma _2}{b_j}{\Delta _{2j}} - {\gamma _1}{\gamma _2}{\gamma _3}b_j^3 + \gamma _1^2b_j^2} \end{array}} \right|\\ \;\;\;\; = {\gamma _1}{\gamma _2}(b_j^2 + c_j^2){\Delta _{2j}} + \gamma _1^2b_j^2[{\gamma _1}{b_j} - {\gamma _2}{\gamma _3}(b_j^2 + c_j^2)]{\mkern 1mu} . \end{array}$

It is noted here that $c_j$ appears in $\Delta_{2j}$ and $\Delta_{3j}$ in the form of $c_j^2$, and thus $p_{\sigma_j}(\lambda)$ and $p_{\bar{\sigma}_j}(\lambda)$ have the same $\Delta_{2j}$ and $\Delta_{3j}$, which is reasonable since their zeros have the same real parts.

Moreover, the above discussion is also valid for real eigenvalues, i.e., $c_j=0$. In this case, $\sigma_j=b_j$, $\Delta_{1j}=\gamma_3b_j>0$ requires $\gamma_3>0$, and

 $\Delta_{2j}= \gamma_2\gamma_3^2 b_j^3- \gamma_1\gamma_3 b_j^2 =\gamma_3(\gamma_2\gamma_3b_j-\gamma_1)b_j^2>0$

requires that $\gamma_2> \frac{\gamma_1}{\gamma_3 b_j}$, which is the same as the final inequality in (10). And,

 $\begin{eqnarray*} \Delta_{3j} &=& \gamma_1\gamma_2b_j^2 \Delta_{2j}+\gamma_1^2b_j^2(\gamma_1b_j-\gamma_2\gamma_3b_j^2) \\ &=& \gamma_1\gamma_2b_j^2 \gamma_3(\gamma_2\gamma_3b_j-\gamma_1) b_j^2 +\gamma_1^2b_j^2(\gamma_1b_j-\gamma_2\gamma_3b_j^2) \\ &=& \gamma_1 b_j^3 (\gamma_2\gamma_3b_j-\gamma_1)^2 > 0 \end{eqnarray*}$

leads to $\gamma_1>0$, which appears in the first inequality of (10).

We summarize the above discussion in the following theorem, where we treat all the nonzero eigenvalues of $\mathcal{L}$ in a unified manner.

Theorem 1: Suppose that the Laplacian matrix $\mathcal{L}$ has the eigenvalues $\mu_1=0, \mu_2\neq 0, \ldots, \mu_N \neq 0$, and the real parts and imaginary parts of nonzero $\mu_j$ are $b_j$ and $c_j$, respectively. Then, consensus is achieved in (1) with (4) if and only if the parameters $\gamma_1$, $\gamma_2$, and $\gamma_3$ are chosen to satisfy

 $\gamma_3 > 0$ (15)
 $\Delta_{2j} = \gamma_2\gamma_3^2 b_j(b_j^2+c_j^2)- \gamma_1\gamma_3 b_j^2- \gamma_2^2 c_j^2 > 0$ (16)
 $\begin{eqnarray} \Delta_{3j} &=& \gamma_1\gamma_2(b_j^2+c_j^2) \Delta_{2j} \\ && +\gamma_1^2b_j^2[\gamma_1b_j-\gamma_2\gamma_3(b_j^2+c_j^2)] > 0 \end{eqnarray}$ (17)

for all $j=2, \ldots, N$.

As mentioned in the above, when the Laplacian matrix only has real eigenvalues (including the case of undirected interconnection among agents), the inequalities (15)-(17) shrink into (10). Since the condition (10) is much simpler to implement, we state the following corollary.

Corollary 1: Suppose that the Laplacian matrix $\mathcal{L}$ has only real nonzero eigenvalues $\mu_j>0$, $j=2, \ldots, N$. Then, consensus is achieved in (1) with (4) if and only if $\gamma_1$, $\gamma_2$, and $\gamma_3$ are chosen to satisfy

 $\begin{array}{l} \gamma_1 >0, \quad \gamma_3>0, \quad \gamma_2> \frac{\gamma_1}{\gamma_3\min\limits_{2\le j \le N}\{ \mu_j \}} \, . \end{array}$ (18)
C. Discussion on Computation of Parameters

When the Laplacian matrix $\mathcal{L}$ has only real eigenvalues, the condition (18) is straightforward and thus the design of parameters $\gamma_i$'s is easy. However, when there are complex eigenvalues, it is not an easy task to choose parameters satisfying (16) and (17). Although $\gamma_3>0$ has been obtained in (15), we can not determine whether $\gamma_1$ and $\gamma_2$ are positive or not, if $\mathcal{L}$ has no nonzero real eigenvalues. Fortunately, the answer to this question is solved in the following theorem.

Theorem 2: Suppose that the Laplacian matrix $\mathcal{L}$ has the eigenvalues $\mu_1=0, \mu_2\neq 0, \ldots, \mu_N \neq 0$. Then, with the control input (4), the necessary condition for achieving consensus in (1) is $\gamma_1>0$, $\gamma_2>0$ and $\gamma_3>0$.

Proof: Consensus in (1) with (4) is achieved if and only if the conditions (15)-(17) are satisfied. $\gamma_3>0$ has been obtained in (15), and the remaining task is to show $\gamma_1>0$, $\gamma_2>0$.

First, we obtain from the definition of $\Delta_{2j}$ that

 $$$\gamma_2\gamma_3b_j(b_j^2+c_j^2)-\gamma_1b_j^2=\frac{\Delta_{2j}+\gamma_2^2c_j^2}{\gamma_3}.$$$ (19)

Substituting (19) into $\Delta_{3j}$ in (17), we have

 $\begin{eqnarray} \Delta_{3j} &=& \gamma_1\gamma_2(b_j^2+c_j^2) \Delta_{2j}+\gamma_1^2b_j^2[\gamma_1b_j-\gamma_2\gamma_3(b_j^2+c_j^2)] \\ &=& \gamma_1\gamma_2(b_j^2+c_j^2) \Delta_{2j}- \frac{\gamma_1^2b_j}{\gamma_3} (\Delta_{2j}+\gamma_2^2c_j^2) \\ &=& \frac{\gamma_1 \Delta_{2j}}{\gamma_3 b_j} \left( \gamma_2\gamma_3 b_j (b_j^2+c_j^2)-\gamma_1 b_j^2 \right) - \frac{\gamma_1^2 \gamma_2^2}{\gamma_3} b_j c_j^2 \\ &=& \frac{\gamma_1 \Delta_{2j}}{\gamma_3^2 b_j} \left(\Delta_{2j}+\gamma_2^2 c_j^2\right)- \frac{\gamma_1^2 \gamma_2^2}{\gamma_3} b_j c_j^2 \\ &=& \frac{\gamma_1 \Delta_{2j}(\Delta_{2j}+\gamma_2^2 c_j^2)}{\gamma_3^2 b_j} - \frac{\gamma_1^2 \gamma_2^2}{\gamma_3} b_j c_j^2 \end{eqnarray}$ (20)

which is equivalent to

 $\Delta_{3j} + \frac{\gamma_1^2 \gamma_2^2}{\gamma_3} b_j c_j^2 = \gamma_1 \frac{\Delta_{2j}(\Delta_{2j}+\gamma_2^2 c_j^2)}{\gamma_3^2 b_j}.$

Since $\gamma_3>0$, $b_j>0$, $\Delta_{2j}>0$ and $\Delta_{3j}>0$, one easily obtains $\gamma_1>0$ from the above equation.

Next, rewriting (19) into

 $\gamma_2\gamma_3b_j(b_j^2+c_j^2)=\gamma_1b_j^2+\frac{\Delta_{2j}+\gamma_2^2c_j^2}{\gamma_3}>0,$

we get $\gamma_2>0$ easily.

The above theorem shows that the parameters have to be positive. In addition, we shall show that the conditions (16) and (17) may be combined to compute the solution. Since (20) is equivalent to

 $\begin{eqnarray*} \frac{\gamma_3^2 b_j}{\gamma_1}\Delta_{3j} = \Delta_{2j}(\Delta_{2j}+\gamma_2^2 c_j^2) - \gamma_1 \gamma_2^2 \gamma_3 b_j^2 c_j^2\, , \end{eqnarray*}$

our problem is reduced to solving

 $$$\Delta_{2j}(\Delta_{2j}+\gamma_2^2 c_j^2) - \gamma_1 \gamma_2^2 \gamma_3 b_j^2 c_j^2 > 0$$$ (21)

together with $\Delta_{2j}>0$, with respect to positive parameters $\gamma_1, \gamma_2, \gamma_3$. Furthermore, we obtain from (21) that

 $\left( \Delta_{2j}+\frac{\gamma_2^2 c_j^2}{2} \right)^2 > \gamma_1 \gamma_2^2 \gamma_3 b_j^2 c_j^2 + \frac{\gamma_2^4 c_j^4}{4}$

and thus

 $$$\Delta_{2j}+\frac{\gamma_2^2 c_j^2}{2} > \sqrt{\gamma_1 \gamma_2^2 \gamma_3 b_j^2 c_j^2 + \frac{\gamma_2^4 c_j^4}{4}}\, ,$$$ (22)

which guarantees $\Delta_{2j}>0$.

Substituting $\Delta_{2j}$ in (16) into (22) and summarizing the above discussion, we obtain the following result.

Theorem 3: Suppose that the Laplacian matrix $\mathcal{L}$ has the eigenvalues $\mu_1=0, \mu_2\neq 0, \ldots, \mu_N \neq 0$, and the real parts and imaginary parts of nonzero $\mu_j$ are $b_j$ and $c_j$, respectively. Then, consensus is achieved in (1) with (4) if and only if the parameters $\gamma_1$, $\gamma_2$, and $\gamma_3$ are chosen to be positive and satisfy

 $\begin{array}{l} \gamma_2\gamma_3^2 b_j(b_j^2+&c_j^2)-\gamma_1\gamma_3 b_j^2-\frac{\gamma_2^2 c_j^2}{2} \\ & > \sqrt{\gamma_1 \gamma_2^2 \gamma_3 b_j^2 c_j^2 + \frac{\gamma_2^4 c_j^4}{4}} \end{array}$ (23)

for all $j=2, \ldots, N$.

Remark 4: Although (23) is a nonlinear and complicated inequality, we can analyze it efficiently to design the parameters. Firstly, when all $c_j$'s are zero (the case where $\mathcal{L}$ has only real eigenvalues), (23) shrinks into $\gamma_2\gamma_3 b_j>\gamma_1$, which again is the same as in (10). Secondly, when there are nonzero $c_j$'s, given positive $\gamma_1, \gamma_3$, we see easily from (23) that $\gamma_2$ can not be very large due to the term $\gamma_2^2 c_j^2$ on both sides of (23), and we can evaluate an upper bound for $\gamma_2$ such that (23) is satisfied. Moreover, (23) does not hold when $\gamma_2\to 0$, and thus, there is a lower bound for $\gamma_2$. Therefore, we can first fix positive parameters $\gamma_1, \gamma_3$, to evaluate the upper bound and lower bound for $\gamma_2$, i.e.,

 $\begin{array}{l} \gamma_{2U} = \sup\left\{\gamma_2>0: (23)\ \mbox{holds for all }c_j\neq 0\right\} \\ \gamma_{2L} = \inf\left\{\gamma_2>0: (23)\ \mbox{holds for all }c_j\neq 0\right\}\, , \end{array}$

and then choose $\gamma_2$ satisfying $\gamma_{2L} < \gamma_2 < \gamma_{2U}$.

There are many practical tools for evaluating $\gamma_{2L}$ and $\gamma_{2U}$. For example, one can numerically solve the nonlinear equations

 $\begin{eqnarray*} f_j(\gamma_2) &=& \gamma_2\gamma_3^2 b_j(b_j^2+c_j^2)-\gamma_1\gamma_3 b_j^2 -\frac{1}{2}\gamma_2^2 c_j^2 \\ && - \sqrt{\gamma_1 \gamma_2^2 \gamma_3 b_j^2 c_j^2 + \frac{\gamma_2^4 c_j^4}{4}}=0\, , \\ && j=2, \ldots, N \end{eqnarray*}$

by using bisection, the Newton method or other numerical algorithms.

D. Numerical Example

In the end of this section, we give an example for the consensus algorithm proposed above.

Example 1: Consider 5 agents connected as in Fig. 1, which is a directed graph. Then, $N=5$ and the Laplacian of the network is

 $\begin{eqnarray*} \mathcal{L} = \left[\begin{array}{ccccc} 1 & 0 & 0 & -1 & 0 \\ -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 2 & -1 \\ -1 & 0 & 0 & 0 & 1 \end{array}\right]. \end{eqnarray*}$
 Download: larger image Fig. 1 Five agents networked by directed graph (Example 1, 2).

The eigenvalues of $\mathcal{L}$ are $\mu_1=0$, $\mu_2=1$, $\mu_3=2$, $\sigma_{1, 2}=\frac{3}{2}\pm \sqrt{-1} \frac{\sqrt{3}}{2}$. In correspondence with the notations we used, let $a=\min\{\mu_2, \mu_3\}=1$, $b_1=\frac{3}{2}$, and $c_1=\frac{\sqrt{3}}{2}$. Then, for the real eigenvalues, we obtain from (18) that

 $\begin{eqnarray} \gamma_1 >0, \ \gamma_3>0, \ \gamma_2> \frac{\gamma_1}{\gamma_3}\, \end{eqnarray}$ (24)

and for the complex eigenvalues we have

 $\begin{eqnarray} \Delta_{21} &=& \frac{9}{2}\gamma_2\gamma_3^2-\frac{9}{4}\gamma_1\gamma_3-\frac{3}{4}\gamma_2^2 \\ &=& \frac{3}{4}\left(6\gamma_2\gamma_3^2-\gamma_2^2-3\gamma_1\gamma_3 \right)>0 \end{eqnarray}$ (25)

and

 $\begin{eqnarray} \Delta_{31} &=& 3\gamma_1\gamma_2 \Delta_{21} + \frac{9}{4} \gamma_1^2 \left(\frac{3}{2}\gamma_1- 3\gamma_2\gamma_3\right) \\ &=& \frac{9}{4} \gamma_1\gamma_2 \left(6\gamma_2\gamma_3^2-\gamma_2^2-3\gamma_1\gamma_3 \right) \\ && + \frac{9}{4} \gamma_1^2 \left(\frac{3}{2}\gamma_1- 3\gamma_2\gamma_3\right) \\ &=& \frac{9}{8} \gamma_1 \left[12\gamma_2\gamma_3(\gamma_2\gamma_3-\gamma_1)+3 \gamma_1^2-2\gamma_2^3\right]>0 \end{eqnarray}$ (26)

On the other hand, the inequality (23) turns out to be

 $\begin{eqnarray*} \frac{9}{2}\gamma_2\gamma_3^2 - \frac{9}{4} \gamma_1\gamma_3-\frac{3}{8}\gamma_2^2 > \sqrt{\frac{27}{16}\gamma_1\gamma_2^2\gamma_3 + \frac{9}{64}\gamma_2^4} \end{eqnarray*}$

or equivalently,

 $\begin{eqnarray} 12\gamma_2\gamma_3^2 - 6 \gamma_1\gamma_3-\gamma_2^2 > \gamma_2 \sqrt{12\gamma_1\gamma_3 + \gamma_2^2}\, . \end{eqnarray}$ (27)

It is easy to observe that there are infinite solutions to the simultaneous inequalities (24)-(26) or (27). For example,

 $\begin{eqnarray*} \gamma_1=1, \ \ \gamma_2=1, \ \ \gamma_3=2 \end{eqnarray*}$

is one solution.

Using the consensus algorithm (4) with these parameters, the plots of the systems' trajectories are depicted in Fig. 2, where the initial conditions are

 \begin{align*} &x_1(0)= \begin{bmatrix}-8 & 10 & 1 \end{bmatrix}^T \\ &x_2(0)= \begin{bmatrix}-2 & 5 & -5 \end{bmatrix}^T \\ &x_3(0)= \begin{bmatrix} 4 & -5 & 7 \end{bmatrix}^T \\ &x_4(0)= \begin{bmatrix} 10 & -10 & 14 \end{bmatrix}^T \\ &x_5(0)= \begin{bmatrix} 16 & -15 & 20 \end{bmatrix}^T. \end{align*}
 Download: larger image Fig. 2 States of five agents achieving consensus (Example 1, $\gamma_1=1, \gamma_2=1, \gamma_3=2$).

It can be observed that consensus has been achieved.

On the contrary, if we choose the parameters

 $\begin{eqnarray*} \gamma_1=1, \ \ \gamma_2=30, \ \ \gamma_3=2 \end{eqnarray*}$

then (26) and (27) are not satisfied. With the same initial conditions, the plots of the systems' trajectories are depicted in Fig. 3, and consensus has not been achieved.

 Download: larger image Fig. 3 States of five agents not achieving consensus (Example 1, $\gamma_1=1, \gamma_2=30, \gamma_3=2$).
Ⅴ. CONSENSUS WITH COMMUNICATION DELAY

In this section, we assume that the design parameters $\gamma_1$, $\gamma_2$ and $\gamma_3$ have been designed so that the conditions in Theorem 1 are satisfied, and analyze the period of time delay that the proposed algorithm can tolerate. In the case of constant communication delay, the control input takes the form of

 $\begin{eqnarray} u_{i}(t) &=&\displaystyle{\sum\limits_{j\in \mathcal{N}_i}}\left(\gamma_{1}(x_{j}^{1}(t-\tau)-x_{i}^{1}(t-\tau))+ \cdots \right. \\ && \left. +\, \gamma_{3}(x_{j}^{3}(t-\tau)-x_{i}^{3}(t-\tau))\right) \\ &=& \displaystyle{\sum\limits_{j\in \mathcal{N}_i} \sum\limits_{k=1}^3} \gamma_k \left(x_{j}^{k}(t-\tau)-x_{i}^{k}(t- \tau)\right)\, \end{eqnarray}$ (28)

where $\tau\geq 0$ is the constant time-delay. Then, the system (1) with the above control input can be rewritten in the compact form

 $\begin{eqnarray*} \dot{\tilde{x}}=(\Theta_{1}\otimes I_{m})\tilde{x}+(\Theta_{2}\otimes I_{m})\tilde{x}(t-\tau) \end{eqnarray*}$

where

 $\begin{eqnarray*} \Theta_{1}=\left[\begin{array}{cccc}0&I_{N}&0 \\ 0 & 0 &I_{N} \\ 0 & 0 & 0 \end{array}\right]\, , \Theta_{2}=\left[\begin{array}{ccc}0 & 0 & 0 \\ 0 & 0 & 0 \\ -\gamma_{1} \mathcal{L} & -\gamma_{2}\mathcal{L} & -\gamma_{3}\mathcal{L} \end{array}\right]\, . \end{eqnarray*}$

Similarly to the discussion in Lemma 4, the characteristic polynomial of the above system is

 $\begin{array}{l} {\left|\lambda I- \Theta_{1}\otimes I_{m} - e^{-\lambda\tau}(\Theta_{2}\otimes I_{m} )\right|} \\ ~~~~~ = \left|(\lambda I- \Theta_{1}-e^{-\lambda\tau}\Theta_{2})\otimes I_m \right| \\ ~~~~~= \left|\lambda I- \Theta_{1}-e^{-\lambda\tau}\Theta_{2}\right|^m \end{array}$

and thus the characteristic equation is dominated by

 $\begin{array}{l} { \left|\lambda I-\Theta_{1}-e^{-\lambda\tau}\Theta_{2}\right|} \\ = \left|\begin{array}{ccc} \lambda I_{N} & -I_{N} & 0 \\ 0 & \lambda I_{N}&-I_{N} \\ \gamma_{1}e^{-\lambda\tau}\mathcal{L} & \gamma_{2}e^{-\lambda\tau}\mathcal{L} & \lambda I_{N} + \gamma_{3}e^{-\lambda\tau}\mathcal{L} \end{array}\right| \\ = \left|\lambda^{3}I_N+(\gamma_{1}+\gamma_{2}\lambda+\gamma_{3}\lambda^{2})e^{-\lambda\tau}\mathcal{L}\right| \\ =\displaystyle{\prod\limits_{i=1}^{N}}\left(\lambda^{3}+(\gamma_{1}+\gamma_{2}\lambda+\gamma_{3}\lambda^{2})e^{-\lambda\tau}\mu_{i}\right) = 0\, . \end{array}$

Then, consensus is achieved if and only if the above equation has exactly three zero eigenvalues and all other eigenvalues have negative real parts.

Let $p_{\mu_i}(\lambda, \tau)=\lambda^{3}+(\gamma_{1}+\gamma_{2}\lambda+\gamma_{3}\lambda^{2})e^{-\lambda\tau}\mu_{i}$, then

 $\begin{eqnarray*} \left|\lambda I-\Theta_{1}-e^{-\lambda\tau}\Theta_{2}\right| =\prod\limits_{i=1}^{N}p_{\mu_i}(\lambda, \tau) \, . \end{eqnarray*}$

We see from the above that $\mu_1=0$ corresponds to zeros of $p_{\mu_1}(\lambda, \tau)=0$, which are three zero eigenvalues as before.

Next, we seek the condition about the communication delay $\tau$, under which each $p_{\mu_i}(\lambda, \tau)$, $2\le i \le N$, has zeros with negative real parts. The main idea is motivated and revised from the discussion in [10]. First, observe that the quasi-polynomial $p_{\mu_i}(\lambda, \tau)$ is Hurwitz stable when $\tau=0$ and unstable for some large positive $\tau$. Thus, there exists a positive upper bound $\tau_i$ for $\tau$ such that $p_{\mu_i}(\lambda, \tau_i)$ has a zero on the imaginary axis and it remains Hurwitz stable for any delay smaller than $\tau_i$. Therefore, the problem is reduced to finding the smallest $\tau_i$ for $i=2, \ldots, N$ such that one of $p_{\mu_i}(\lambda, \tau_i)$'s has imaginary roots.

For this purpose, we substitute $\lambda=\omega_{i}\sqrt{-1}$ ($\omega_{i}\in \mathbb{R}, \omega_{i}\neq 0$) into $p_{\mu_i}(\lambda, \tau_i)=0$ to obtain

 $\begin{eqnarray*} -\omega_{i}^{3} \sqrt{-1}+(\gamma_{1}+\gamma_{2}\omega_{i}\sqrt{-1}-\gamma_{3}\omega_{i}^{2})e^{-\omega_{i}\tau_{i} \sqrt{-1}}\mu_{i}=0\, . \end{eqnarray*}$

Separating the real and imaginary parts of the above yields

 $$$\left\{ \begin{array}{l} A_{i}\sin(\omega_{i}\tau_{i})-B_{i}\cos(\omega_{i}\tau_{i})=0 \\ B_{i}\sin(\omega_{i}\tau_{i})+A_{i}\cos(\omega_{i}\tau_{i})=\omega_{i}^{3} \end{array}\right.$$$ (29)

where

 $\begin{eqnarray*} \begin{array}{l} A_{i}=\gamma_{2}\omega_{i}\Re(\mu_{i})-(\gamma_{3}\omega_{i}^{2}-\gamma_{1})\Im(\mu_{i}) \\ B_{i}=\gamma_{2}\omega_{i}\Im(\mu_{i})+(\gamma_{3}\omega_{i}^{2}-\gamma_{1})\Re(\mu_{i}). \end{array} \end{eqnarray*}$

Then, it is easy to reach

 $\begin{eqnarray*} \sin(\omega_{i}\tau_{i})=\frac{B_{i}\omega_{i}^{3}}{A_{i}^{2}+B_{i}^{2}} \, , \quad \cos(\omega_{i}\tau_{i})=\frac{A_{i}\omega_{i}^{3}}{A_{i}^{2}+B_{i}^{2}} \end{eqnarray*}$

where

 $$$\tau_{i}=\frac{\arctan\psi_{i}+k_i\pi}{\omega_{i}}\, , \quad \psi_{i} = \frac{B_i}{A_i}$$$ (30)

and $k_i$ is the minimum integer such that $\tau_{i}>0$, $i=2, \ldots, N$.

Using $\sin^{2}(\omega_{i}\tau_{i})+\cos^{2}(\omega_{i}\tau_{i})=1$ in (29), we obtain

 $\begin{eqnarray*} A_i^2 + B_i^2 = \omega_i^6 \end{eqnarray*}$

and after simple calculation,

 $$$\omega_{i}^{6}-\gamma_{3}^{2}|\mu_{i}|^{2}\omega_{i}^{4}-(\gamma_{2}^{2}-2\gamma_{1}\gamma_{3})|\mu_{i}|^{2}\omega_{i}^{2}-\gamma_{1}^{2}|\mu_{i}|^{2}=0\, .$$$ (31)

The procedure of calculating the upper bound $\tau^*$ is summarized as follows:

1) For $\mu_i \ne 0$ ($2\le i \le N$), solve (31) to obtain the positive solution $\omega_i$.

2) Calculate $A_i$, $B_i$ and then $\tau_i$ as in (30).

3) Let $\tau^*=\min_{2\leq i\leq N}\{\tau_i\}$.

Theorem 4: Suppose that the parameters $\gamma_1, \gamma_2$ and $\gamma_3$ have been designed such that the third order multi-agent system (1) has achieved consensus with the algorithm (4). The system (1) with communication delay $\tau$, i.e., with the control input (28), achieves consensus if and only if $\tau < \tau^{*}=\min_{2\le i \le N}\tau_{i}$.

Example 2: Consider the multi-agent system used in Example 1. The nonzero eigenvalues of $\mathcal{L}$ are $\mu_2=1$, $\mu_3=2$, $\mu_4=\frac{3}{2} + \sqrt{-1} \frac{\sqrt{3}}{2}$, and $\mu_5=\frac{3}{2} - \sqrt{-1} \frac{\sqrt{3}}{2}$. Moreover, assume $\gamma_1=1, \ \gamma_2=1, \ \gamma_3=2$ have been chosen such that the consensus is achieved when no communication delay is involved.

Next, we compute $\tau_i$ for nonzero eigenvalues $\mu_i$.

1) For $\mu_2=1$, (31) is

 $\begin{eqnarray*} \omega_{2}^{6}-4\omega_{2}^{4}+3\omega_{2}^{2}-1=0 \end{eqnarray*}$

and its positive solution is $\omega_2=1.7742$. Correspondingly, $A_2=1.7742$, $B_2=5.2958$, and $\tau_2=(\tan^{-1}\frac{B_2}{A_2})/\omega_2=0.7031$.

2) For $\mu_3=2$, (31) is

 $\begin{eqnarray*} \omega_{3}^{6}-16\omega_{3}^{4}+12\omega_{3}^{2}-4=0 \end{eqnarray*}$

and its positive solution is $\omega_3=3.9025$. Correspondingly, $A_3 = 7.8049$, $B_3=58.9172$, and $\tau_3=(\tan^{-1}\frac{B_3}{A_3})/\omega_3=0.3688$.

3) For $\mu_4=\frac{3}{2} + \sqrt{-1} \frac{\sqrt{3}}{2}$, (31) is

 $$$\omega_{4}^{6}-12\omega_{4}^{4}+9\omega_{4}^{2}-3=0$$$ (32)

and its positive solution is $\omega_4=3.3499$. Correspondingly, $A_4 =-13.5459$, $B_4=35.0665$, and $\tau_4=(\tan^{-1}\frac{B_4}{A_4}+\pi)/\omega_4=0.5790$.

4) For $\mu_5=\frac{3}{2} - \sqrt{-1} \frac{\sqrt{3}}{2}$, the equation (31) is the same as (32), and thus $\omega_5=3.3499$. Then, we obtain $A_5 = 23.5956$, $B_5= 29.2643$, and $\tau_5=(\tan^{-1}\frac{B_5}{A_5})/\omega_5=0.2663$.

Therefore, $\tau^{*}=\min \{\tau_2, \tau_3, \tau_4, \tau_5\}=0.2663$.

Using the same initial condition as in Example 1, Fig. 4 shows that consensus has been achieved when $\tau=0.25$, while Fig. 5 shows that consensus can not be achieved when $\tau=0.27$.

 Download: larger image Fig. 4 States of five agents achieving consensus (Example 2, $\gamma_1=1, \gamma_2=1, \gamma_3=2$, $\tau=0.25$).
 Download: larger image Fig. 5 States of five agents not achieving consensus (Example 2, $\gamma_1=1, \gamma_2=1, \gamma_3=2$, $\tau=0.27$).
Ⅵ. CONCLUDING REMARKS

In this paper, we have considered the consensus algorithm for networked third order agents, and have established a necessary and sufficient condition (protocol) for designing the parameters in the control input. The key idea is to reduce the consensus problem into designing a Hurwitz polynomial with complex coefficients. The main result turns out to be a natural extension from second order consensus, and it does not require large computational efforts. Moreover, the discussion has also been extended to the case where a constant communication delay exists in the control inputs. A tight upper bound for the delay has been established as a necessary and sufficient condition under which consensus is maintained when communication delay is involved.

REFERENCES
 [1] T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and O. Shochet, "Novel type of phase transition in a system of self-driven particles, " Phys. Rev. Lett., vol. 75, no. 6, pp. 1226-1229, Aug. 1995. http://europepmc.org/abstract/MED/10060237 [2] R. Olfati-Saber, J. A. Fax, and R. M. Murray, "Consensus and cooperation in networked multi-agent systems, " Proc. IEEE, vol. 95, no. 1, pp. 215-233, Jan. 2007. http://ieeexplore.ieee.org/document/4118472/ [3] J. Shamma, Cooperative Control of Distributed Multi-Agent Systems. New York: Wiley, 2008. [4] W. Ren and R. Beard, Distributed Consensus in Multi-Vehicle Cooperative Control: Theory and Applications. London: Springer, 2008. [5] J. A. Fax and R. M. Murray, "Information flow and cooperative control of vehicle formations, " IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1465-1476, Sep. 2004. http://www.sciencedirect.com/science/article/pii/S1474667015385219 [6] A. Jadbabaie, J. Lin, and A. S. Morse, "Coordination of groups of mobile autonomous agents using nearest neighbor rules, " IEEE Trans. Autom. Control, vol. 48, no. 6, pp. 988-1001, Jun. 2003. http://www.ams.org/mathscinet-getitem?mr=1986266 [7] L. Moreau, "Stability of multiagent systems with time-dependent communication links, " IEEE Trans. Autom. Control, vol. 50, no. 2, pp. 169-182, Feb. 2005. https://www.researchgate.net/publication/3032048_Stability_of_multiagent_systems_with_time-dependent_communication_links [8] W. Ren and R. W. Beard, "Consensus seeking in multiagent systems under dynamically changing interaction topologies, " IEEE Trans. Autom. Control, vol. 50, no. 5, pp. 655-661, May 2005. http://ieeexplore.ieee.org/document/1431045 [9] W. W. Yu, G. R. Chen, and M. Cao, "Some necessary and sufficient conditions for second-order consensus in multi-agent dynamical systems, " Automatica, vol. 46, no. 6, pp. 1089-1095, Jun. 2010. https://www.sciencedirect.com/science/article/pii/S0005109810001251 [10] W. Y. Hou, M. Y. Fu, H. S. Zhang, and Z. Z. Wu, "Consensus conditions for general second-order multi-agent systems with communication delay, " Automatica, vol. 75, pp. 293-298, Jan. 2017. http://www.sciencedirect.com/science/article/pii/S0005109816303879 [11] Y. M. Xin, Y. X. Li, X. Huang, and Z. S. Cheng, "Consensus of third-order nonlinear multi-agent systems, " Neurocomputing, vol. 159, pp. 84-89, Jul. 2015. http://dl.acm.org/citation.cfm?id=2782194 [12] W. He and J. Cao, "Consensus control for high-order multi-agent systems, " IET Control Theory Appl., vol. 5, no. 1, pp. 231-238, Jan. 2011. https://www.mendeley.com/research-papers/consensus-control-highorder-multiagent-systems/ [13] G. S. Zhai, S. H. Okuno, J. Imae, and T. Kobayashi, "A matrix inequality based design method for consensus problems in multi-agent systems, " Int. J. Appl. Math. Comput. Sci., vol. 19, no. 4, pp. 639-646, Dec. 2009. http://dl.acm.org/citation.cfm?id=1721644 [14] G. Zhai, J. Takeda, J. Imae, and T. Kobayashi, "Towards consensus in networked non-holonomic systems, " IET Control Theory Appl., vol. 4, no. 10, pp. 2212-2218, Oct. 2010. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5611741 [15] G. S. Zhai and C. Huang, "A note on basic consensus problems in multi-agent systems with switching interconnection graphs". Int. J. Control , vol.88, no.3, pp.631–639, 2015. DOI:10.1080/00207179.2014.971431 [16] A. T. Azar and S. Vaidyanathan, Advances in Chaos Theory and Intelligent Control. Switzerland: Springer, 2016. [17] R. K. Upadhyay and S. R. K. Lyengar, Introduction to Mathematical Modeling and Chaotic Dynamics.. London: CRC Press, 2014. [18] E. Frank, "On the zeros of polynomials with complex coefficients". Bull. Am. Math. Soc. , vol.52, no.2, pp.144–157, 1946. DOI:10.1090/S0002-9904-1946-08526-2 [19] Z. H. Wang, J. J. Xu, and H. S. Zhang, "Consensus seeking for discrete-time multi-agent systems with communication delay, " IEEE/CAA J. of Autom. Sinica, vol. 2, no. 2, pp. 151-157, Apr. 2015. http://www.ieee-jas.org/EN/abstract/abstract54.shtml [20] H. Xia, T. Z. Huang, J. L. Shao, and J. Y. Yu, "Group consensus of multi-agent systems with communication delays, " Neurocomputing, vol. 171, pp. 1666-1673, Jan. 2016. http://www.sciencedirect.com/science/article/pii/S0925231215011571 [21] X. G. Yang, J. X. Xi, J. Y. Wu, and B. L. Yang, "Consensus transformation for multi-agent systems with topology variances and time-varying delays, " Neurocomputing, vol. 168, pp. 1059-1064, Nov. 2015. http://dl.acm.org/citation.cfm?id=2824619 [22] M. Yu, C. Yan, D. M. Xie, and G. M. Xie, "Event-triggered tracking consensus with packet losses and time-varying delays, " IEEE/CAA J. of Autom. Sinica, vol. 3, no. 2, pp. 165-173, Apr. 2016. http://ieeexplore.ieee.org/document/7451104/ [23] B. Zhou and Z. L. Lin, "Consensus of high-order multi-agent systems with large input and communication delays, " Automatica, vol. 50, no. 2, pp. 452-464, Feb. 2014. http://www.sciencedirect.com/science/article/pii/S0005109813005657 [24] B. Mohar, "The Laplacian spectrum of graphs, " Graph Theory, Combinatorics, and Applications, Y. Alavi, G. Chartrand, O. Ollermann, and A. Schwenk, eds. New York: Wiley, 1991, pp. 871-898. http://www.researchgate.net/publication/233407318_The_Laplacian_spectrum_of_graphs [25] A. J. Laub, Matrix Analysis for Scientists and Engineers. Philadelphia: SIAM, 2004.