A new finite-time average consensus protocol with boundedness of convergence time for multi-robot systems

Abstract

Multi-robot consensus has been extensively applied in robotics. In this study, a new protocol is proposed to solve the finite-time average consensus problem. The protocol can improve the convergence rate. The upper bound of the convergence time is obtained. Analysis shows that there exists a limit value of the convergence time when the disagreement of initial states tends to be infinitely large, and the value is irrelevant to the initial states. The relationship between convergence time and initial states, communication topology, parameter is analysed. Lastly, the effectiveness of the results is verified by simulations.

Introduction

In recent years, many applications require a massive number of robots or vehicles to work cooperatively and accomplish a complicated task. Thus, many researchers investigated coordination control of multi-robot systems or multi-agent systems, such as the flocking, ¹ formation control ^{2 –4} and cooperative control of the unmanned aerial vehicles ^5,6 and the attitude alignment of clusters of the artificial satellites. ² The multi-robot consensus means all the robots of a system can reach an agreement with regard to certain quantities of interest through designing a proper consensus protocol. The protocol is based on the local information of each robot. ⁷ Additional details can be found in the studies by Cao et al. ⁸ and Kantamneni et al. ⁹ and the references therein.

In the study of the consensus problem, convergence time is a significant performance indicator for a consensus protocol. The typical linear model of the consensus for multi-robot systems was proposed by Olfati-Saber. ¹ The authors used a graph to model the communication topology among agents and demonstrated that the second smallest eigenvalue of the graph Laplacian matrix quantifies the convergence rate; this finding prompted many researchers to develop ways to increase algebraic connectivity and lots of valuable achievements have been obtained. ^10,11

Unfortunately, the protocols in the aforementioned works can only achieve state consensus in infinite time interval, that is, the consensus is achieved only asymptotically. However, the stability or performance of a multi-robot system in a finite-time interval needs to be considered in several cases. The finite-time stability focuses on the behaviour of a system response over a finite-time interval. ¹² Therefore, studying the finite-time stability of a multi-robot system is valuable to some extent. The multi-agent finite-time stability analysis has attracted the attention of many researchers recently. Wang and Xiao ¹³ discussed two continuous finite-time consensus protocols and determined the conditions under which the protocols are guaranteed to achieve the finite-time consensus. Shang ¹⁴ proposed a sufficient criterion to ensure that the system reaches a consensus in finite time. Zhang et al. ¹⁵ investigated the distributed finite-time consensus-tracking problem for coupled harmonic oscillators using both state feedback control and output feedback control. In the study by Zuo and Lin, ¹⁶ a new consensus protocol was constructed, and the convergence time of the proposed consensus protocol has an upper bound for the arbitrary initial state. Zhu et al. ¹⁷ investigated the finite-time consensus problem with single and double integrator dynamics and constructed new non-linear protocols for the first-order and second-order leader–follower multi-agent systems. In the study by Wang et al., ¹⁸ a linear term was added to the protocol to solve the finite-time average consensus problem, thereby improving the convergence performance. Yu and Long ¹⁹ investigated the distributed finite-time consensus problem of the second-order multi-agent systems in the presence of bounded disturbances. In the study by Zhu et al., ²⁰ the finite-time consensus problems of heterogeneous multi-agent systems composed of both linear and non-linear dynamics agents were investigated. Some sufficient conditions for the finite-time consensus were established in the leaderless and leader-following cases.

However, the convergence time of most existing protocols is closely related to the initial states of the robots. If the states of different robots significantly differ, then the convergence time is very large, and this condition limits the practical engineering applications. Although the convergence time of the protocol in the study by Zuo and Lin ¹⁶ has an upper bound for the arbitrary initial state, the protocol is complex and the parameters are restricted. Furthermore, the relationship between convergence time and the factors is unclear. In the current study, a new protocol is proposed to solve the finite-time average consensus problem and overcome the defect of existing protocols.

The main contributions of this study are threefold: (1) a new protocol is proposed to solve the finite-time average consensus problem, and it can improve the convergence rate. (2) The stability is verified, and the upper bound of convergence time is obtained. The analysis result shows that there exists a limit value of the convergence time when the disagreement of initial states is infinitely large, and the value is irrelevant to the initial states. (3) The relationship between convergence time and protocol parameter, communication topology, initial state is analysed.

The rest of the article is organized as follows. ‘Preliminaries and problem formulation’ section presents several basic definitions and results on algebraic graph theory, the formulation of the problem and a list of basic properties. The main results and the proof are provided in ‘Main results’ section. The simulation results are presented in ‘Simulations’ section, and the conclusions are elaborated in the last section.

Notations

${\mathcal{I}}_n=\{1,2,\mathrm{...},n\}$ , 1 = [1, 1,…, 1]^T with compatible dimensions and $\text{span}\left\{\mathbf{1}\right\}=\{\epsilon \in R^n:\epsilon =r\mathbf{1},r\in R\}$ . ‖ is the absolute value of the real numbers. For any 1 < p < ∞, ‖ ‖ _p denotes the l_p -norm in Rⁿ .

Preliminaries and problem formulation

Preliminaries

Several basic definitions and results on the algebraic graph theory are introduced in this subsection. Comprehensive discussions are found by Godsil and Royle. ²¹

We let $\mathcal{G}=\left(\mathcal{V},\mathcal{E},\mathcal{A}\right)$ be a weighted graph of order n with vertex set $\mathcal{V}=\{v_1,v_2,\mathrm{...},v_n\}$ , edge set $\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$ and weighted adjacency matrix $\mathcal{A}=[a_{ij}]$ , which contains non-negative adjacency elements a_ij . An edge of the graph is denoted by e_ij = (v_i , v_j ). An available information channel that connects agents i and j exists if the adjacency elements a_ij with associated edges are positive. In this study, we assume that no self-loops exist, that is, a_ii = 0 for all $i\in {\mathcal{I}}_n$ . The neighbours of vertex v_i are denoted by ${\mathcal{N}}_i\left(\mathcal{G},i\right)=\{v_j\in \mathcal{V}:(v_i,v_j)\in \mathcal{E}\}$ . A directed path between two distinct vertices v_i and v_j is a finite-ordered sequence of distinct edges with the form $(v_i,v_{k_1}),(v_{k_1},v_{k_2}),\mathrm{...},(v_{k_l},v_j)$ . If ${\mathcal{A}}^T=\mathcal{A}$ , then the graph is an undirected graph. An undirected graph is regarded as connected if a path exists between any two different vertices (v_i , v_j ).

Lemma 1

Let $L=[l_{ij}]\in R^{n\times n}$ denote a graph Laplacian matrix, which is defined as ⁹

$l_{ij}=\{\begin{array}{c}{\sum }_{k=1,k\ne i}^n{a}_{ik},j=i\\ -a_{ij},j\ne i\end{array}$

1

then L has the following properties

 L always has a 0 eigenvalue and 1 is the associated eigenvector.

For any $\epsilon ={[{\epsilon }_1,{\epsilon }_2\cdots ,{\epsilon }_n]}^T\in R^n$ , ${\epsilon }^{T}L\epsilon =\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{a}_{ij}{({\epsilon }_j-{\epsilon }_i)}^2$ , which implies that all eigenvalues of L are nonnegative real numbers.

If the graph is undirected and connected, then the second smallest eigenvalue of L, which is denoted by λ ₂(L), called the algebraic connectivity of graph, is larger than zero and ${\lambda }_2(L)={\text{min}}_{\epsilon \ne 0,1^T\epsilon =0}\frac{{\epsilon }^{T}L\epsilon }{{\epsilon }^T\epsilon }$ . Therefore, if ${\mathbf{1}}^T\epsilon =0$ , ${\epsilon }^{T}L\epsilon \ge {\lambda }_2(L){\epsilon }^T\epsilon$ .

Lemma 2

Suppose that function V(t): [0, ∞) → [0, ∞) is differentiable and satisfies the condition ²²

$\frac{\text{d}V\left(t\right)}{\text{d}t}\le -KV{\left(t\right)}^{\alpha }$

2

where K > 0 and 0 < α < 1, then V reaches zero at t*, and V(t) = 0 for all t ≥ t*

$t^{*}=\frac{V{\left(0\right)}^{1-\alpha }}{K\left(1-\alpha \right)}$

3

Lemma 3

If ${\xi }_1,{\xi }_2,\cdots ,{\xi }_n\ge 0$ and 0< p ≤1, then ²³

${\left({\sum }_{i=1}^n{\xi }_i\right)}^p\le {\sum }_{i=1}^n{\xi }_i^p$

4

If ${\xi }_1,{\xi }_2,\cdots ,{\xi }_n\ge 0$ and p ≥ 1, then

${\sum }_{i=1}^n{\xi }_i^p\ge n^{1-p}{\left({\sum }_{i=1}^n{\xi }_i\right)}^p$

5

Problem formulation

Under the assumption that n nodes exist in the studied multi-robot system, each robot can get up to the required rate for the proposed protocol of this study. The state of robot v_i is denoted by x_i , $i\in {\mathcal{I}}_n$ and x = [x ₁, x ₂,…, x_n ]^T. The dimension of x_i can be arbitrary, as long as all the robots have the same dimension. For simplicity, we only analyse the 1D case. The results are still valid for multi-dimensional cases through the introduction of the Kronecker product. We suppose that each robot satisfies the kinematics as follows

${\dot{x}}_i\left(t\right)=u_i\left(t\right)$

6

where u_i is called the consensus protocol.

With the given protocol u_i , for any initial states, if there exists stable equilibrium x* satisfying x_i = x* for all $i\in {\mathcal{I}}_n$ with t → ∞, then the asymptotical consensus problem is solved. ²⁴ If there exist stable equilibrium x* and time t* satisfying x_i = x* for all $i\in {\mathcal{I}}_n$ with t ≥ t*, then the finite-time consensus problem is solved. ¹³ Moreover, the χ-consensus problem is solved if the final consensus state is a function of the initial states, namely, $x_i(t)=\chi (\mathbf{x}(0))$ for all $i\in {\mathcal{I}}_n$ with t → ∞, where χ is a function of Rⁿ → R. ²⁴ In particular, if $\chi (\mathbf{x}(0))={\sum }_{i=1}^n{x}_i(0)/n$ , the system achieves the average consensus.

The protocol which is utilized to solve the finite-time average consensus problem is

$u_i=\mu \sum _{j\in I_n}{a}_{ij}\text{sign}\left(x_j-x_i\right){\left|x_j-x_i\right|}^{2-1/m}+\eta \sum _{j\in I_n}{a}_{ij}\text{sign}\left(x_j-x_i\right){\left|x_j-x_i\right|}^{1/m}$

7

where μ > 0, η > 0 and m > 1, and the sign(·) is a sign function defined as

$\text{sign}\left(x\right)=\{\begin{array}{c}1,\\ 0,\\ -1,\end{array}\begin{array}{c}x>0\\ x=0\\ x<0\end{array}$

8

Basic properties

Property 1

Protocol (7) is continuous with respect to the variables x ₁, x ₂,…, x_n . Under this protocol, at least one solution of the differential equation (6) exists in [0, ∞) for any initial states x . Furthermore, $\underset{i\in {\mathcal{I}}_n}{\text{min}}(x_i(t))$ is non-decreasing, and $\underset{i\in {\mathcal{I}}_n}{\text{max}}(x_i(t))$ is non-increasing.

Proof

Consider the function f(r) = μsign|r|^2−1/m + ηsign|r|^1/m , where m > 1. If r > 0, then f(r) = μr ^2−1/m + ηr ^1/m is continuous and $\underset{r\to 0^{+}}{\text{lim}}f(r)=0$ . If r < 0, then f(r) = −μ(−r)^2−1/m − η(−r)^1/m is continuous and $\underset{r\to 0^{-}}{\text{lim}}f(r)=0$ . Given that f(0) = 0, f(r) is continuous in R. Therefore, protocol (7) is continuous with respect to the variables x ₁, x ₂,…, x_n .

According to Peano’s existence theorem, ²⁵ at least one solution of differential equation (6) exists in [0, t] for any initial states x (0). At any moment t > 0, according to protocol (7), if $x_k(t)=\underset{i\in {\mathcal{I}}_n}{\text{max}}(x_i(t))$ , then ${\dot{x}}_k(t)\le 0$ ; if $x_k(t)=\underset{i\in {\mathcal{I}}_n}{\text{min}}(x_i(t))$ , then ${\dot{x}}_k(t)\ge 0$ . Therefore, $\underset{i\in {\mathcal{I}}_n}{\text{min}}(x_i(t))$ is non-decreasing and $\underset{i\in {\mathcal{I}}_n}{\text{max}}(x_i(t))$ is non-increasing, that is, ${\Vert x(t)\Vert }_{\infty }$ is non-increasing and ${\Vert x(t)\Vert }_{\infty }\le {\Vert x(0)\Vert }_{\infty }$ for all t ≥ 0.

Property 2

With protocol (7), the equilibrium point set of the differential equation (6) belongs to span{1} provided that the graph is strongly connected.

Proof

We prove this property by contradiction. We let $\xi ={[{\xi }_1,{\xi }_2,\mathrm{...},{\xi }_n]}^T$ satisfy the equation ${\dot{x}}_i(t)=u_i(t)=0$ . We assume that $\underset{i\in {\mathcal{I}}_n}{\text{min}}({\xi }_i)\ne \underset{i\in {\mathcal{I}}_n}{\text{max}}({\xi }_j)$ . Thus, i ≠ j. Given that the graph is strongly connected, between any two different vertices (v_i , v_j ), a path that begins with v_i and ends with v_j exists. Supposing m is one of the numbers of the minimum values. With protocol (7), u_m > 0, which is a contradiction. Thus, $\underset{i\in {\mathcal{I}}_n}{\text{min}}({\xi }_i)=\underset{i\in {\mathcal{I}}_n}{\text{max}}({\xi }_j)$ , namely, $\xi \in \text{span}\left\{\mathbf{1}\right\}$ .

To prove the opposite, we suppose that $\xi \in \text{span}\left\{\mathbf{1}\right\}$ . Then, all $u_i{|}_{x=\xi }=0,i\in {\mathcal{I}}_n$ . Therefore, ξ belongs to the equilibrium point set.

Main results

Stability analysis

Protocol (7) is studied in this subsection. The protocol is verified to solve the finite-time average consensus problem. The stability of the system is guaranteed. Furthermore, the upper bound of convergence time is obtained. Moreover, there exists a limit value of the convergence time when the disagreement of initial states is infinitely large, and the value is irrelevant to the initial states.

Theorem 1

Suppose that communication topology $\mathcal{G}(A)$ of a multi-robot system is undirected and connected, then protocol (7) can solve the finite-time average consensus problem.

Proof

Given that the topology is undirected and connected, a_ij = a_ji for all $i,j\in {\mathcal{I}}_n$ . We obtain

${{\sum }_{i=1}^n\dot{x}}_i\left(t\right)=0$

9

We let

$\kappa =\frac{1}{n}{{\sum }_{i=1}^{n}x}_i\left(t\right)$

10

According to equation (9), κ is time invariant. We let $\delta (t)={[{\delta }_1(t),{\delta }_2(t),\dots ,{\delta }_n(t)]}^T$ and ${\delta }_i(t)=x_i(t)-\kappa$ . Thus

${\dot{\delta }}_i\left(t\right)={\dot{x}}_i\left(t\right)$

11

Consequently

${\mathbf{1}}^T\delta \left(t\right)={\sum }_{i=1}^n{x}_i\left(t\right)-n\kappa ={\sum }_{i=1}^n{x}_i\left(t\right)-{\sum }_{i=1}^n{x}_i\left(t\right)=0$

12

Here, the first Lyapunov function is taken

$V_1\left(t\right)=\frac{1}{2}{\sum }_{i=1}^n{\delta }_i^2\left(t\right)$

13

Obviously, V ₁(t) ≥ 0 for all δ, and V ₁(t) = 0 if and only if δ(t) = 0.

By differentiating V ₁(t) versus time, we obtain

$\begin{array}{c}\frac{\text{d}{V}_1\left(t\right)}{\text{d}t}={\displaystyle {\sum }_{i=1}^n{\delta }_i}{\dot{\delta }}_i\\ ={\displaystyle {\sum }_{i=1}^n{\delta }_i}\left(\mu {\displaystyle \sum _{j\in I_n}{a}_{ij}}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{2-1/m}+\eta {\displaystyle \sum _{j\in I_n}{a}_{ij}}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{1/m}\right)\\ ={\displaystyle {\sum }_{i,j=1}^n{\delta }_i\left(\mu a_{ij}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{2-1/m}+\eta a_{ij}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{1/m}\right)}\\ =\frac{1}{2}{\displaystyle {\sum }_{i,j=1}^n({\delta }_i\mu a_{ij}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{s-1/m}+{\delta }_j\mu a_{ji}\text{sign}\left({\delta }_i-{\delta }_j\right){\left|{\delta }_i-{\delta }_j\right|}^{s-1/m}}\\ +{\delta }_i\eta a_{ij}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{1/m}+{\delta }_j\eta a_{ji}\text{sign}\left({\delta }_i-{\delta }_j\right){\left|{\delta }_i-{\delta }_j\right|}^{1/m})\\ =\frac{1}{2}{\displaystyle {\sum }_{i,j=1}^n({\delta }_i\mu a_{ij}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{2-1/m}-{\delta }_j\mu a_{ji}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{2-1/m}}\\ +{\delta }_i\eta a_{ij}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{1/m}-{\delta }_j\eta a_{ji}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{1/m})\\ =\frac{1}{2}{\displaystyle {\sum }_{i,j=1}^n\left(\left({\delta }_i-{\delta }_j\right)\mu a_{ij}\text{sign}({\delta }_j-{\delta }_i){\left|{\delta }_j-{\delta }_i\right|}^{2-1/m}+\left({\delta }_i-{\delta }_j\right)\eta a_{ij}\text{sign}\left({\delta }_j-{\delta }_i\right){\left|{\delta }_j-{\delta }_i\right|}^{1/m}\right)}\\ =-\frac{1}{2}{\displaystyle {\sum }_{i,j=1}^n{a}_{ij}\left(\mu {\left|{\delta }_j-{\delta }_i\right|}^{3-1/m}+\eta {\left|{\delta }_j-{\delta }_i\right|}^{1+1/m}\right)}\end{array}$

14

Equation (14) results from ${\delta }_j-{\delta }_i=x_j-x_i$ . Then

$\begin{array}{c}\frac{\text{d}{V}_1(t)}{\text{d}t}=-\frac{1}{2}{\displaystyle {\sum }_{i,j=1}^n\left(a_{ij}\mu {\left|{\delta }_j-{\delta }_i\right|}^{3-1/m}\right)}-\frac{1}{2}{\displaystyle {\sum }_{i,j=1}^n\left(a_{ij}\eta {\left|{\delta }_j-{\delta }_i\right|}^{1+1/m}\right)}\\ =-\frac{1}{2}\mu {\displaystyle {\sum }_{i,j=1}^n{\left({\left(a_{ij}\right)}^{\frac{2}{3-1/m}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}^{\frac{3-1/m}{2}}}-\frac{1}{2}\eta {{\displaystyle {\sum }_{i,j=1}^n\left({\left(a_{ij}\right)}^{\frac{2}{1+1/m}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}}^{\frac{1+1/m}{2}}\\ =-\frac{1}{2}\mu {\displaystyle {\sum }_{i,j=1}^n{\left({\left(a_{ij}\right)}^{\frac{2m}{3m-1}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}^{\frac{3m-1}{2m}}}-\frac{1}{2}\eta {{\displaystyle {\sum }_{i,j=1}^n\left({\left(a_{ij}\right)}^{\frac{2m}{m+1}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}}^{\frac{m+1}{2m}}\end{array}$

15

Denote

$\begin{array}{l}{Z}_1=-\frac{\mu }{2}{\sum }_{i,j=1}^n{\left({\left(a_{ij}\right)}^{\frac{2m}{3m-1}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}^{\frac{3m-1}{2m}}\\ Z_2=-\frac{\eta }{2}{{\sum }_{i,j=1}^n\left({\left(a_{ij}\right)}^{\frac{2m}{m+1}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}^{\frac{m+1}{2m}}\end{array}$

16

Suppose that V ₁ ≠ 0, then δ ≠ 0. For m > 1, we have (3m−1)/2 m > 1 and 0 < (m+1)/2 m < 1. With lemma 3, we have

$\begin{array}{c}{Z}_1\le -\frac{\mu }{2}{n}^{\frac{1-m}{2m}}{\left({\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{3m-1}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}^{\frac{3m-1}{2m}}\\ =-\frac{\mu }{2}{n}^{\frac{1-m}{2m}}{\left(\frac{{\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{3m-1}}{\left({\delta }_j-{\delta }_i\right)}^2}{V_1\left(t\right)}{V}_1\left(t\right)\right)}^{\frac{3m-1}{2m}}\\ =-\frac{\mu }{2}{n}^{\frac{1-m}{2m}}{\left(\frac{{\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{3m-1}}{\left({\delta }_j-{\delta }_i\right)}^2}{\frac{1}{2}{\sum }_{i=1}^n{\delta }_i^2}{V}_1\left(t\right)\right)}^{\frac{3m-1}{2m}}\end{array}$

17

We assume that $C=[c_{ij}]\in R^{n\times n}$ , where $c_{ij}={\left(a_{ij}\right)}^{\frac{2m}{3m-1}}$ . With equation (17) and lemma 1

${\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{3m-1}}{\left({\delta }_j-{\delta }_i\right)}^2={\sum }_{i,j=1}^n{c}_{ij}{\left({\delta }_j-{\delta }_i\right)}^2=2{\delta }^{T}L(C)\delta$

18

$\frac{{\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{3m-1}}{\left({\delta }_j-{\delta }_i\right)}^2}{\frac{1}{2}{\sum }_{i=1}^n{\delta }_i^2}=\frac{2{\delta }^{T}L(C)\delta }{\frac{1}{2}{\delta }^T\delta }\ge 4{\lambda }_2(L(C))>0$

19

$Z_1\le -\frac{\mu }{2}{n}^{\frac{1-m}{2m}}{(4{\lambda }_2(L\left(C\right)V_1\left(t\right)))}^{\frac{3m-1}{2m}}$

20

$\begin{array}{c}{Z}_2\le -\frac{\eta }{2}{\left({\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{m+1}}{\left({\delta }_j-{\delta }_i\right)}^2\right)}^{\frac{m+1}{2m}}\\ =-\frac{\eta }{2}{\left(\frac{{\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{m+1}}{\left({\delta }_j-{\delta }_i\right)}^2}{V_1\left(t\right)}{V}_1\left(t\right)\right)}^{\frac{m+1}{2m}}\\ =-\frac{\eta }{2}{\left(\frac{{\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{m+1}}{\left({\delta }_j-{\delta }_i\right)}^2}{\frac{1}{2}{\sum }_{i=1}^n{\delta }_i^2}{V}_1\left(t\right)\right)}^{\frac{m+1}{2m}}\end{array}$

21

We assume that $D=[d_{ij}]\in R^{n\times n}$ , where $d_{ij}={\left(a_{ij}\right)}^{\frac{2m}{m+1}}$ . With equation (21) and lemma 1

${\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{m+1}}{\left({\delta }_j-{\delta }_i\right)}^2={\sum }_{i,j=1}^n{d}_{ij}{\left({\delta }_j-{\delta }_i\right)}^2=2{\delta }^{T}L(D)\delta$

22

$\frac{{\sum }_{i,j=1}^n{\left(a_{ij}\right)}^{\frac{2m}{m+1}}{\left({\delta }_j-{\delta }_i\right)}^2}{\frac{1}{2}{\sum }_{i=1}^n{\delta }_i^2}=\frac{2{\delta }^{T}L(D)\delta }{\frac{1}{2}{\delta }^T\delta }\ge 4{\lambda }_2(L(D))>0$

23

$Z_2\le -\frac{\eta }{2}{\left(4{\lambda }_2(L(D))V_1(t)\right)}^{\frac{m+1}{2m}}$

24

Combining the above formulas results in

$\frac{\text{d}{V}_1(t)}{\text{d}t}\le -\frac{1}{2}\mu n^{\frac{1-m}{2m}}{\left(4{\lambda }_2(L(C))V_1(t)\right)}^{\frac{3m-1}{2m}}-\frac{1}{2}\eta {\left(4{\lambda }_2(L(D))V_1(t)\right)}^{\frac{m+1}{2m}}$

25

We let ${\lambda }_{\text{min}}=\text{min}({\lambda }_2(L(C),{\lambda }_2(L(D))$ , then

$\frac{\text{d}{V}_1(t)}{\text{d}t}\le -\frac{1}{2}\left(\mu n^{\frac{1-m}{2m}}{(4{\lambda }_{\text{min}}{V}_1(t))}^{\frac{3m-1}{2m}}+\eta {(4{\lambda }_{\text{min}}{V}_1(t))}^{\frac{m+1}{2m}}\right)$

26

We let $s=\sqrt{4{\lambda }_{\text{min}}{V}_1}$ , then

$\frac{\text{d}{V}_1(t)}{\text{d}t}=\frac{2s}{4{\lambda }_{\text{min}}}\frac{\text{d}s}{\text{d}t}$

27

Then

$\frac{\text{d}s}{\text{d}t}=-\mu n^{\frac{1-m}{2m}}{\lambda }_{\text{min}}{s}^{\frac{2m-1}{m}}-\eta {\lambda }_{\text{min}}{s}^{\frac{1}{m}}$

28

Here, the second Lyapunov function is taken, we let V ₂ = s ². Evidently, V ₂ ≥ 0 for all s, and V ₂ = 0 if and only if s = 0. By differentiating V ₂ versus time, we obtain

$\begin{array}{c}\frac{\text{d}{V}_2}{\text{d}t}=2s\left(-\mu n^{\frac{1-m}{2m}}{\lambda }_{\text{min}}{s}^{\frac{2m-1}{m}}-\eta {\lambda }_{\text{min}}{s}^{\frac{1}{m}}\right)\\ =-2\mu n^{\frac{1-m}{2m}}{\lambda }_{\text{min}}{(s^2)}^{\frac{3m-1}{2m}}-2\eta {\lambda }_{\text{min}}{(s^2)}^{\frac{m+1}{2m}}\\ =-2{\lambda }_{\text{min}}\left(\mu n^{\frac{1-m}{2m}}{V}_2^{\frac{m-1}{m}}+\eta \right)V_2^{\frac{m+1}{2m}}\end{array}$

29

$\frac{1}{V_2^{\frac{m+1}{2m}}}\frac{\text{d}{V}_2}{\text{d}t}=-2{\lambda }_{\text{min}}\left(\mu n^{\frac{1-m}{2m}}{V}_2^{\frac{m-1}{m}}+\eta \right)$

30

$\frac{m}{m-1}\frac{\text{d}{V}_2^{\frac{m-1}{2m}}}{\text{d}t}=-{\lambda }_{\text{min}}\left(\mu n^{\frac{1-m}{2m}}{V}_2^{\frac{m-1}{m}}+\eta \right)$

31

We let $y=V_2^{(m-1)/2m}$ , then

$\frac{m}{m-1}\frac{\text{d}y}{\text{d}t}=-{\lambda }_{\text{min}}\left(\mu n^{\frac{1-m}{2m}}{y}^2+\eta \right)$

32

$\frac{1}{\left(\mu n^{\frac{1-m}{2m}}{y}^2+\eta \right)}\text{d}y=-{\lambda }_{\text{min}}\frac{m-1}{m}\text{d}t$

33

${\int }_0^t\frac{1}{\left(\mu n^{\frac{1-m}{2m}}{y}^2+\eta \right)}\text{d}y={\int }_0^t-{\lambda }_{\text{min}}\frac{m-1}{m}\text{d}t$

34

$\frac{1}{\sqrt{\mu \eta n^{\frac{1-m}{2m}}}}\text{arctan}\left(\sqrt{\frac{\mu n^{\frac{1-m}{2m}}}{\eta }}y(t)\right)-\frac{1}{\sqrt{\mu \eta n^{\frac{1-m}{2m}}}}\text{arctan}\left(\sqrt{\frac{\mu n^{\frac{1-m}{2m}}}{\eta }}y(0)\right)=-{\lambda }_{\text{min}}\frac{m-1}{m}t$

35

The function f(x) = arctan(x) is monotonically increasing. If x > 0, we get f(x) > 0, and if and only if x = 0, we get f(x) = 0. Supposing when the convergence time is T, V ₁(t) converges to zero. That is

$\underset{t\to T}{\text{lim}}{V}_1(t)=0$

36

Finally, we can get

$\begin{array}{c}T=\frac{m}{{\lambda }_{\text{min}}\left(m-1\right)}\frac{1}{\sqrt{\mu \eta n^{\frac{1-m}{2m}}}}\text{arctan}\left(\sqrt{\frac{\mu n^{\frac{1-m}{2m}}}{\eta }}y(0)\right)\\ =\frac{m}{{\lambda }_{\text{min}}\left(m-1\right)}\frac{n^{\frac{m-1}{4m}}}{\sqrt{\mu \eta }}\text{arctan}\left(\sqrt{\frac{\mu }{\eta }}\frac{{\left(4{\lambda }_{\text{min}}{V}_1(0)\right)}^{\frac{m-1}{2m}}}{n^{\frac{m-1}{4m}}}\right)\end{array}$

37

Obviously, T is the upper bound of the convergence time. Moreover, if the disagreement of the robots’ initial states is infinitely large, we can obtain a limit value T_u

$T_u=\underset{V_1(0)\to \infty }{\text{lim}}T=\frac{\pi m{n}^{\frac{m-1}{4m}}}{2\sqrt{\mu \eta }{\lambda }_{\text{min}}\left(m-1\right)}$

38

Now we have proved that V ₁(t) satisfies the condition of lemma 2 and thus makes V ₁(t) reach zero in finite time. Finally, the states of all robots reach final state κ, the average of their initial states.

If V ₁(t) = 0, then δ = 0, which implies that u_i = 0, $i\in {\mathcal{I}}_n$ . Thus, $\mathbf{x}(t)\in \text{span}\{1\}$ based on property 2. Therefore, the proposed protocol can guarantee the system stability and solve the finite-time average consensus problem.

Remark 1

Theorem 1 offers a new protocol to solve the finite-time average consensus problem. The system stability is guaranteed. The upper bound of convergence time is obtained. Analysis shows there is a limit value of the convergence time when the disagreement of initial states is infinitely large and the value is irrelevant to the initial states, and it also shows that the limit value is the upper bound of upper bound of convergence time.

Remark 2

The kinematics equation of the proposed protocol shows that the changing rate of system state is larger compared with that of the typical finite-time consensus protocol in the studies by Wang and Xiao ¹³ and Wang et al. ¹⁸ owing to the existence of the first non-linear term, especially during the early stage. Thus, the convergence rate of the system can be improved effectively. Moreover, the second non-linear term guarantees that the system can achieve the consensus in finite time.

Performance analysis

In this subsection, we study the relationship between convergence time and other factors, including initial states, underlying communication topology and parameter.

Convergence time is defined as the amount of time the system consumes to reach a consensus. Obtaining the precise convergence time of the studied non-linear system is difficult. However, convergence time can be analysed through its upper bound obtained using equations (37) and (38).

Firstly, we study the relationship between convergence time and initial states. In the consensus problem, rather than the size of the initial states, the disagreement between states is more concerned. By definition, V ₁(t) measures the disagreement of the robots’ current states with their common final state. In particular, V ₁(0) measures the disagreement of the initial states with the final state. Equation (37) shows that the convergence time increases when V ₁(0) increases. The convergence time tends to the limit value T_u if V ₁(0) is infinitely large.

Given the unique advantage of the protocol, next we only study the relationship between convergence time and communication topology, parameters m and n when V ₁(0) is infinitely large.

As shown in equation (38), the convergence time decreases when λ _min is large. Therefore, the convergence time can be decreased by increasing the algebraic connectivity.

Lastly, we study the relationship between convergence time and parameters m and n. Using equation (38), and taking the derivative with respect to m, we obtain

$\begin{array}{c}\frac{d{T}_u}{dm}=\frac{\pi }{2\sqrt{\mu \eta }{\lambda }_{\text{min}}}\frac{\left(n^{\frac{m-1}{4m}}+m\left(n^{\frac{m-1}{4m}}\frac{1}{4m^2}\text{ln}n\right)\right)\left(m-1\right)-m{n}^{\frac{m-1}{4m}}}{{\left(m-1\right)}^2}\\ =\frac{\pi }{2\sqrt{\mu \eta }{\lambda }_{\text{min}}}\frac{n^{\frac{m-1}{4m}}}{{\left(m-1\right)}^2}\left(\left(1+\frac{\text{ln}n}{4m}\right)\left(m-1\right)-m\right)\\ =\frac{\pi }{8\sqrt{\mu \eta }{\lambda }_{\text{min}}}\frac{n^{\frac{m-1}{4m}}}{{\left(m-1\right)}^2}\left(\text{ln}n\left(1-\frac{1}{m}\right)-4\right)\end{array}$

39

For m > 1, we obtain 0 < 1−1/m < 1. If a small number of nodes are present in the multi-robot system (approximately n<53), we obtain dT_u /dm < 0. Therefore, the convergence time decreases when m is large. If a large number of nodes are present in the multi-robot system (approximately n > 53), we obtain dT_u /dm < 0 if m is small and dT_u /dm > 0 if m is large (the size of m is decided by the number of nodes). In other words, the convergence time decreases initially and then increases as m becomes large. Therefore, an optimal parameter m which can enable the convergence time to obtain the minimum value exists.

Remark 3

The relationship between convergence time and initial states, communication topology, parameters m and n is analysed. Accordingly, the convergence time can be effectively adjusted.

Simulations

For simplicity, we suppose the control gain of protocol (7) μ = η = 1 in this study. Consider an undirected network with n = 6 nodes as shown in Figure 1. The graph has 0−1 weights. Through calculation, we obtain λ ₂(L) = 0.2679. When m = 2, the initial states are [−3; −2; −1; 1; 2; 3]^T, and the state trajectories of robots are shown in Figure 2 when protocol (7) is applied. The red asterisk (*) denotes the limit value T_u . The final consensus state is ${\sum }_{i=1}^n{x}_i(0)/6=0$ , such that protocol (7) can solve the finite-time average consensus problem.

Figure 1.

The communication topology of six robots.

Figure 2.

The state trajectories when m = 2 and the initial states are [−3; −2; −1; 1; 2; 3]^T.

Under the initial states of [−30; −20; −10; 10; 20; 30]^T, the state trajectories when m = 2 and m = 4 are shown in Figures 3 and 4, respectively. Comparing Figures 2 and 3 shows that the convergence time is large when V ₁(0) is large. Therefore, when the difference in the initial state is large, the convergence time is long. Moreover, comparing Figures 3 and 4 shows that the convergence time decreases when m is large and if n is small (n = 6).

Figure 3.

The state trajectories when m = 2 and the initial states are [−30; −20; −10; 10; 20; 30]^T.

Figure 4.

The state trajectories when m = 4 and the initial states are [−30; −20; −10; 10; 20; 30]^T.

The state trajectories under the consensus protocol in the study by Wang et al. ¹⁸ are shown in Figure 5. The communication topology when the initial state is [−30; −20; −10; 10; 20; 30]^T and the other parameters are the same is provided in Figure 1. Comparison with Figure 3 shows that the convergence time of protocol (7) is shorter than that of the consensus protocol in the study by Wang et al. ¹⁸ Therefore, the existence of the first non-linear term can effectively reduce the convergence time.

Figure 5.

The state trajectories of robots under the consensus protocol in the study by Wang. ¹⁸

We verify the relationship between convergence time and communication topology. Another undirected network with n = 6 nodes is shown in Figure 6. The graph also has 0−1 weights. Through calculation, we obtain λ ₂(L) = 1. The state trajectories when m = 2 and the initial states are [−3; −2; −1; 1; 2; 3]^T are shown in Figure 7.

Figure 6.

Another communication topology of six robots.

Figure 7.

The state trajectories of robots when topology is Figure 6.

Comparison with Figure 2 indicates that the convergence time decreases if the algebraic connectivity is large and when the other conditions are similar.

We demonstrate that the convergence time has a limit value when V ₁(0) is infinitely large through the topology given in Figure 1. The relationship between convergence time and parameters m and V ₁(0) is simulated, and the result is shown in Figure 8(a). In particular, the relationship between convergence time and V ₁(0) when m = 4 is shown in Figure 8(b). The red solid line represents the relationship between T and V ₁(0). The red broken line represents the limit value T_u . Comparing the two figures shows that the convergence time moves to a limit value which is irrelevant to the initial states, when V ₁(0) is infinitely large.

Figure 8.

The relationship between convergence time and parameters V ₁(0) and m.

Lastly, we demonstrate the relationship between convergence time and parameters m and n when V ₁(0) is infinitely large. For a series of different undirected and connected graphs with 4 nodes to 30 nodes, we suppose that the algebraic connectivity of all the graphs is 1. The relationship between convergence time and parameters m and n is shown in Figure 9(a). In particular, the relationship between T and m when n = 10 is shown in Figure 9(b). The two figures show that the convergence time decreases when m is large and if a small number of nodes are present in the multi-robot system.

Figure 9.

The relationship between convergence time and parameters m and n (if n is small).

For a series of different undirected and connected graphs with 180 nodes to 210 nodes, we suppose the algebraic connectivity of all the graphs is also 1. The relationship between T and parameters m and n is shown in Figure 10(a). In particular, the relationship between T and m when n = 200 is shown in Figure 10(b). The two figures show that if a large number of nodes are present in the multi-robot system, then the convergence time decreases initially and then increases as m becomes large. Therefore, an optimal parameter m which can enable the convergence time to obtain the minimum value exists.

Figure 10.

The relationship between convergence time and parameters m and n (if n is large).

Conclusions

In this study, a new protocol was developed to solve the finite-time average consensus problem in multi-robot systems. The relationship between convergence time and initial states, communication topology, parameters m and n was analysed. Through simulation, the following conclusions were obtained.

The proposed protocol can solve the finite-time average consensus problem. The system stability can be guaranteed and the upper bound of the convergence time was obtained. Analysis shows that the new protocol can effectively improve the convergence rate; moreover, there exists a limit value of the convergence time when the disagreement of initial states is infinitely large, and the value is irrelevant to the initial states.

The convergence time decreases when the parameter m increases if a small number of nodes are present in the multi-robot system (approximately n < 53). If a large number of nodes are present in the multi-robot system (approximately n > 53), then the convergence time decreases initially and then increases as m becomes large.

The authors in this study only considered leaderless first-order multi-agent systems. Future works will focus on extending the proposed protocol to second-order or high-order multi-robot systems with directed and time-varying networks.