Minimal-time Deadbeat Consensus and Individual Disagreement Degree Prediction for High-order Linear Multi-agent Systems

Due to their high efficiency, wide coverage and low cost, a large volume of efforts have been devoted to the distributed control of multi-agent systems (MASs). Therein, consensus situation is a requisite that refers to a certain state (i.e., acceleration, position, voltage) of all the agents reaching an agreement merely by using local interaction (Ren & Beard, 2008; Olfati-Saber, 2006). To this end, quite a few consensus algorithms have been proposed over the past few decades (Ren & Beard, 2005; Fax & Murray, 2004; Dimarogonas & Kyriakopoulos, 2007; Huang et al., 2014), which have been found universal applications to smart grids (Yang et al., 2013), social networks (Proskurnikov et al., 2015), multi-sensor networks (Sun et al., 2017), unmanned systems (Liu et al., 2019), etc. So far, most of the existing relevant approaches focus on asymptotically attaining consensus by utilizing local interactions (Olfati-Saber & Murray, 2004; Jadbabaie et al., 2003; Moreau, 2005; Xiao & Boyd, 2004), which update each agent’s state by some kinds of weighted linear combinations of itself and its neighbors. Therein, exact convergence to the consensus state could not be achieved within finite steps, which could not fulfill more and more strict cooperation efficiency requirements of modern industrial MASs.

In the past decades, as a remedy, a promising kind of scheme has been proposed, which calculates the exact final consensus value according to sequential individual states (Charalambous & Hadjicostis, 2018; Zhang et al., 2008, 2019; Manitara & Hadjicostis, 2017; Sundaram & Hadjicostis, 2010). As a pioneer work, a consensus prediction scheme for first-order linear MASs with time-invariant topology was proposed in (Sundaram & Hadjicostis, 2007), where each individual computes the consensus value using finite historical sampling series stored in its memory. Enlightened by such representative works, (Charalambous & Hadjicostis, 2018; Zhang et al., 2008, 2019; Manitara & Hadjicostis, 2017; Sundaram & Hadjicostis, 2010, 2007), some efforts (Yuan, 2012; Yuan et al., 2013) have further reduced the individual consensus prediction cost by substantially decreasing the total historical state series length required to be stored in individual memory. Following this research line, (Charalambous et al., 2015) proposed a distributed algorithm that calculate exact average consensus values in a finite period for first-order MASs with time-delays.

Till date, most of the aforementioned consensus value prediction algorithms focus on first-order MASs and adopt the final value theorem of $\mathcal{Z}$-transform to calculate the eventual consensus values, which can not be directly extended to high-order MASs since the limits of their eventual values do not always exist. Due to the challenges for high-order evolution calculation merely by local information exchanging, so far, minimal-time deadbeat consensus prediction for high-order linear MASs has not been touched. However, for both natural biological swarms/flocks/schools and engineering collective motion systems, it is often required for collective motional systems to take prompt reactions to environmental emergencies, urgent tasks or even suddenly-appeared group targets. In such universal situations, development of a deadbeat consensus prediction protocol becomes indispensable for high-order MASs, which needs to reach exact agreement upon not only positions and velocities, but also accelerations and jerks (Attanasi et al., 2014; Cavagna et al., 2015), with sufficiently short individual memory lengths. Therefore, consensus protocol design of high-order MASs has attracted more and more attention from relevant researchers (Rezaee & Abdollahi, 2015; Seo et al., 2009; Su & Lin, 2016; Zuo et al., 2018; Hu et al., 2019). This motivates us to consider an urgent yet challenging problem, i.e., designing a decentralized protocol to predict the exact eventual consensus values of high-order linear MASs with directed topological backbones merely according to individual memory as short as possible.

In brief, the main contribution of this paper is as below. A minimal-time deadbeat consensus prediction (MDCP) protocol is developed for discrete-time high-order linear MASs. Sufficient conditions are theoretically derived to guarantee the convergence of MDCP. Moreover, rather than just prediction of steady-state consensus values of MASs, the present MDCP could predict the instant states of each individual of the MASs as well, which in turn describes the future evolution of the individual disagreement degree among the MASs more delicately that is desirable for more complicated real application cases like rendezvous, coverage, flocking and formation control.

The remainder of this paper is organized as follows. In Section II, the main problem addressed by the present study is presented together with the preliminaries. Then, MDCP is designed in Section III and the sufficient conditions are derived to guarantee the convergence of MDCP. Afterwards, numerical simulations are conducted in Section IV to verify the effectiveness of the present protocol. Finally, conclusion is drawn in Section V.

Throughout this paper, the following symbols will be used. $\mathbb{R}$, $\mathbb{R}^{n}$, $\mathbb{R}^{n\times m}$, $\mathbb{R}^{+}$ refer to the sets of real number, $n$-dimensional real vector, $n\times m$ real matrix and positive real number, respectively. $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{Z}^{+}$ indicate the natural number, integer number and positive integer number sets, respectively. The transpose of a matrix $\ast$ is denoted by $\ast^{\mbox{\tiny\sf T}}$. Size$(\ast)$ indicates the rows of a square matrix $\ast$, and $\ast^{\bot}$ denotes the null space of $\ast$. $(e_{n}^{i})^{\mbox{\tiny\sf T}}=\left[0,\ldots,0,1_{i\text{-th }},0,\ldots,0\right]\in\mathbb{R}^{1\times n}$ is an $n$-dimension row vector with $i$-th element being 1 and the others 0. The symbol det$(\ast)$ denotes the determinant of a matrix $\ast$. $\otimes$ refers to the Kronecker product. $\textbf{1}_{n}\in\mathbb{R}^{n}$ and $\textbf{0}_{n}\in\mathbb{R}^{n}$ are the column vectors with all elements being 1 and 0, respectively. 0 is a matrix with compatible dimensions and all elements being 0. $I_{n}\in\mathbb{R}^{n\times n}$ denotes an $n\times n$ identity matrix. The $\mathcal{Z}$-transform of a function $f$ is denoted by $\mathcal{Z}(f)$. The symbol $\lfloor\ast\rfloor:=\max\{n\in\mathbb{Z}\mid n<\ast\}$ indicates the lower integral function. Euclidean norm of a vector $*$ is denoted by $\left\|*\right\|$. The symbol ${}_{i}^{j}*:=\left[*(i),*(i+1),\dots,*(j)\right]\in\mathbb{R}^{j-i+1},j>i,i,j\in\mathbb{N}$ denotes a row vector, where $*(i)$ refers to the $i$-th element of $*$. $\sup(*)$ denotes the supremum of set $*$.

Consider a fixed directed graph consisted of $n$ agents given by $\mathcal{G}=\left(\mathcal{V},\mathcal{E},\mathcal{A}\right)$, where $\mathcal{V}=\left\{1,2,\dots,n\right\}$ is a finite nonempty node set denoting the agents, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the edge set. $\mathcal{A}=\left[a_{ij}\right]\in\mathbb{R}^{n\times n}$ represents the weighted adjacency matrix. Here, $a_{ij}>0$ if $(j,i)\in\mathcal{E}$, and $a_{ij}=0$ otherwise, furthermore, only simple graph is considered. i.e., there is no self-loop. Let $\mathcal{L}:=[\mathcal{L}_{ij}]\in\mathbb{R}^{n\times n}$ denotes the Laplacian matrix, where $\mathcal{L}_{ii}=\sum_{i\neq j}a_{ij}$, $\mathcal{L}_{ij}=-a_{ij}$ for $i\neq j$. If directed graph $\mathcal{G}$ has a directed spanning tree, 0 is a simple eigenvalue of $\mathcal{L}$ corresponding to eigenvector $\textbf{1}_{n}$, i.e., $\mathcal{L}\textbf{1}_{n}=0$.

Consider a discrete-time $s$-order linear MAS consisted of $n$ agents with dynamics described by

where $x_{i}^{(s)}(k)\in\mathbb{R}^{m}$ denotes the $s$-order state of $i$-th agent at the $k$-th time instant, $i=1,2,\cdots,n$, $s,k\in\mathbb{Z}^{+}$, and $\epsilon\in\mathbb{R}^{+}$ represents the sampling time. Without loss of generality, $m=1$ is considered throughout this paper. The scenarios for $m>1$ can be easily extended with the assistance of the Kronecker product ‘$\otimes$’.

Conventional control protocol for high-order linear MASs is given as follows (Ren et al., 2007)

where $p_{s}(x):=c_{0}x+c_{1}x^{(1)}+\cdots+c_{s-1}x^{(s-1)}$ is an operator of variable $x$, external coupling weight $\omega<0$, and internal coupling weight coefficient $c_{l}>0$ with $l=0,1,2,\cdots,s-1$. Consensus is called to be reached for high-order MAS if $x_{i}^{(\ell)}\rightarrow x_{j}^{(\ell)}$, $\ell=1,2,\dots,s$, $\forall i\neq j$, $i,j=1,2,\cdots,n$. The $\ell$-order states of all agents are denoted by a vector $X^{(\ell)}:=\left[x_{1}^{(\ell)},x_{2}^{(\ell)},\dots,x_{n}^{(\ell)}\right]^{\mbox{\tiny\sf T}},\ell=1,2,\cdots,s$. The full-state of the $i$-th agent is denoted by a vector

Substituting (2) into (1), the dynamics of the whole MAS $\mathcal{G}$ can be rewritten in a compact form as

with $X:=\left[(X^{(1)})^{\mbox{\tiny\sf T}},(X^{(2)})^{\mbox{\tiny\sf T}},\dots,(X^{(s)})^{\mbox{\tiny\sf T}}\right]^{\mbox{\tiny\sf T}}$ and

being the Perron matrix (Olfati-Saber & Murray, 2004).

To facilitate further analysis, the following assumptions are necessary.

Assumptions 1 and 2 ensure the consensus accessibility of the discrete-time high-order linear MAS (4) (Wieland et al., 2008). Moreover, we give some definitions to facilitate further derivation.

Now, we are ready to introduce the two main problems addressed in this study as below.

In this section, Problems 1 and 2 will be addressed for the discrete-time high-order linear MAS (4). To this end, we provide the following Lemmas in advance.

Proof: Rewriting (1) in a compact form, one has that

with

Let $\Lambda:=\operatorname{diag}\left(\lambda_{1},\ldots,\lambda_{n}\right)$ be a matrix with diagonal elements being the eigenvalues associated with Laplacian $\mathcal{L}$, i.e., there exists a nonsingular matrix $P$ such that $P^{-1}\mathcal{L}P=\Lambda$. Then, multiply both sides of (12) by $I_{s}\otimes P^{-1}$, one has

with $B=\left(\epsilon C\otimes I_{n}+\omega R\otimes\Lambda\right)$. Let $\eta(k)=\left(I_{s}\otimes P^{-1}\right)X(k)$, one has

with $\eta_{i}(k)=\left[e_{sn}^{i},e_{sn}^{n+i},\cdots,e_{sn}^{(s-1)n+i}\right]^{\mbox{\tiny\sf T}}\eta(k)$, $B_{i}=\left(\epsilon C+\omega\lambda_{i}R\right)$ and $i=1,2,\dots,n$.

According to (Horn & Johnson, 2012), the characteristic polynomial of $B_{i}$ is derived as follows

Since $\mathcal{L}$ has a simple zero eigenvalue, i.e., there exists one and only one $\lambda_{i}=0$. Consequently, $p_{B_{i}}(\lambda)$ has $s$ zero eigenvalues, which implies that $B+I_{sn}$ only has $s$ eigenvalues at 1. Moreover,

which implies that $W$ has only $s$ eigenvalues at 1 as well.

Let $\mathcal{Q}:=[\mathcal{Q}_{1}^{\mbox{\tiny\sf T}},\mathcal{Q}_{2}^{\mbox{\tiny\sf T}},\dots\mathcal{Q}_{s}^{\mbox{\tiny\sf T}}]^{\mbox{\tiny\sf T}}\in\mathbb{R}^{sn}$ denotes the right eigenvector of $W$ associated to the eigenvalue 1, then one has

which implies $\mathcal{Q}_{i}=\mathbf{0}_{n},i=2,3\dots s$ whereas $\mathcal{L}\mathcal{Q}_{1}=\mathbf{0}_{n}$. Thereby, $\mathcal{Q}_{1}$ is an eigenvector of $\mathcal{L}$ associated to its eigenvalue at 0. Since $\mathcal{L}$ has only one linearly independent eigenvector $\mathcal{Q}_{1}$ associated to the eigenvalue at 0, which in turn implies that $W$ has only one linearly independent eigenvector $\mathcal{Q}=\left[\mathcal{Q}_{1}^{\mbox{\tiny\sf T}},\mathbf{0}_{n}^{\mbox{\tiny\sf T}},\dots,\mathbf{0}_{n}^{\mbox{\tiny\sf T}}\right]^{\mbox{\tiny\sf T}}$. Therefore, the eigenvalue of $W$ at 1 has algebraic multiplicity of $s$ but geometric multiplicity of 1. The proof is thus completed.  

Proof: Let $\lambda$ be an eigenvalue of $W$ that the algebraic multiplicity of $s$ and geometric multiplicity of 1. Define a Jordan block of order $s$ as follows

One has that

Case 1: if $\ell(i)=1$, one has that

Case 2: if $\ell(i)=m$ with $m\in\mathbb{Z}^{+},2\leq m\leq s$. By mathematical induction, one has that

with $v_{j,m}=\sum_{h=j}^{{D_{i}}-m+2}C_{m-2+h-j}^{m-2}\alpha_{i,h+m-1}\lambda^{h-j}$.

Bearing in mind Pascal’s Triangle $\sum_{j=0}^{x}C_{m-1+j}^{m-1}=C_{m+x}^{m},x\in\mathbb{Z}^{+}$, substituting $t=\lambda$ into (14) yields

and $q_{i,x}(\lambda)=0,x\in\mathbb{Z}^{+},x<m$.

Combining Cases 1 and 2, one has that $q_{i,x}(\lambda)=0,x\in\mathbb{Z}^{+},x\leq\ell(i)$. According to Lemma 2, let the Jordan decomposition of $W$ be indicated by

where $Z$ denotes the set of Jordan block whose eigenvalue does not equal 1, $\mathcal{T}$ is a nonsingular matrix with columns composed of the (generalized) eigenvectors of $W$.

From Definition 6, one has

Let $\mathbf{d}\in\mathbb{R}^{sn\times s}$ denotes the $1$-th to $s$-th columns of $\mathcal{T}$, direct calculation gives

where ${}_{1}^{s}d_{i}$ is $i$-th row of $\mathbf{d}$ and $[_{1}^{s}d_{i}\quad{}_{s+1}^{sn}\mathcal{T}_{i}]$ is the $i$-th row of $\mathcal{T}$. According to Lemma 2, $W$ has only one linearly independent eigenvector $\mathcal{Q}=\left[\mathcal{Q}_{1}^{\mbox{\tiny\sf T}},\mathbf{0}_{n}^{\mbox{\tiny\sf T}},\dots,\mathbf{0}_{n}^{\mbox{\tiny\sf T}}\right]^{\mbox{\tiny\sf T}}$ associated to eigenvalue 1. Without loss of generality, let $\mathcal{Q}=\left[\mathbf{1}_{n}^{\mbox{\tiny\sf T}},\mathbf{0}_{n}^{\mbox{\tiny\sf T}},\dots,\mathbf{0}_{n}^{\mbox{\tiny\sf T}}\right]^{\mbox{\tiny\sf T}}$ and $\mathcal{Q}_{1,r}=\left[\mathbf{0}_{n}^{\mbox{\tiny\sf T}},\mathbf{0}_{n}^{\mbox{\tiny\sf T}},\dots,\frac{1}{\epsilon^{r-1}}\mathbf{1}_{r\text{-}th}^{\mbox{\tiny\sf T}},\cdots\mathbf{0}_{n}^{\mbox{\tiny\sf T}}\right]^{\mbox{\tiny\sf T}},r=2,3\dots,s$, be a right eigenvector and generalized right eigenvectors of $W$ associated to the eigenvalue at 1, respectively. Then,

Bearing $\boldsymbol{J}^{k}(\lambda)$ and (13), (15) in mind, one has

From (17), one has ${}_{1}^{s}d_{i}q_{i}(J(1))=0$, all elements of $\left(\lfloor\frac{i}{n}\rfloor+1\right)$-row of $q_{i}(J(1))$ are zeros for $i=1,2,\dots,sn$, i.e., $q_{i,m}(1)=0,m=1,2,\cdots,\ell(i)$, and the minimal polynomial pair $q_{i}(t)$ of $W$ has at least $\ell(i)$ eigenvalues at $1$. Since the degree of the polynomial pair is minimized, $q_{i}(t)$ has and only has $\ell(i)$ eigenvalues at 1. The proof is thus completed.  

Proof: The proof can be divided into three steps.

Step 1: Derive the parameter of the minimal polynomial pair.

Consider the memory vector (9) and Lemma 3, one has

with $\alpha_{i}=\left[\alpha_{i,0},\alpha_{i,1},\dots,\alpha_{i,D_{i}+1}\right]\in\mathbb{R}^{D_{i}+2}$ being the coefficients of the minimal polynomial pairs of $W$ to be calculated. Note that

where $\zeta_{i,j}\in\mathbb{R}$ is another null space coefficient parameters. From Leibniz’s Derivation Rule (Olver, 1993) and Definition 6, one has

with $\zeta_{i}=\left[\zeta_{i,0},\zeta_{i,1},\dots,\zeta_{i,\overline{D}_{i}}\right],\overline{D}_{i}=D_{i}+1-s$ and

According to (20), build up a Hankel matrix (Partington, 1988) as the following form

Gradually increase $\widehat{\overline{D}}_{i}$ until getting the minimal $\widehat{\overline{D}}_{i}$ such that the Hankel matrix $\Gamma$ becomes non-fully ranked. Then, $\widehat{\overline{D}}_{i}$ and $\Gamma_{i}^{\bot}$ become estimates of $\overline{D}_{i}$ and $\zeta_{i}$, respectively. Together with (18), (19), $\alpha_{i,j}$ can be obtained.

Step 2: Calculate and decompose-fit the $\mathcal{Z}$-transform of $x_{i}^{(1)}(t)$.

According to (18) and Definition 6, one has

Note that the $\mathcal{Z}$-transform $x_{i}^{(1)}(z)=\mathcal{Z}\left(x_{i}^{(1)}(t)\right)$, from $\mathcal{Z}$-transform time-shift properties and (23), one has

Let

which could be divided into two parts as

Here, $\beta_{i}\in\mathbb{R},i=0,1,\cdots,D_{i}$, is a parameter.

From Leibniz’s Derivation Rule (Olver, 1993), the $n$-th derivative of (26) is given as follows

for $n=0,1,\cdots,s-1$. Direct calculation gives

with

Since $p_{i}^{0}(1)\neq 0$, $\mathcal{M}$ is fully ranked, and $\beta_{i}$ always exists such that (26) holds.

Step 3: Predict the eventual consensus value of the MAS.

Under Assumptions 1 and 2, $x_{i}^{(s)}$ converges to a constant value. Denote the consensus item as the following form

where $\kappa_{i},i=0,1,\dots,s-1,$ is the coefficient to be determined later. According to the property of $\mathcal{Z}(C_{k}^{r})=\frac{z}{(z-1)^{r+1}},r\in\mathbb{N}$, in Remark 3, rewriting (29) in a compact form as