Previous researches have shown that adding local memory can accelerate the consensus. It is natural to question what is the fastest rate achievable by the $M$ -tap memory acceleration, and what are the corresponding control parameters. This paper introduces a set of effective and previously unused techniques to analyze the convergence rate of accelerated consensus with $M$ -tap memory of local nodes and to design the control protocols. These effective techniques, including the Kharitonov stability theorem, the Routh stability criterion and the robust stability margin, have led to the following new results: 1) the direct link between the convergence rate and the control parameters; 2) explicit formulas of the optimal convergence rate and the corresponding optimal control parameters for $M \leq 2$ on a given graph; 3) analytic formulas of the optimal worst-case convergence rate and the corresponding optimal control parameters for the memory $M \geq 1$ on a set of uncertain graphs. We show that the acceleration with the memory $M=1$ provides the optimal convergence rate in the sense of worst-case performance. Several numerical examples are given to demonstrate the validity and performance of the theoretical results.
26 April 2022 in IEEE Transactions on Signal and Information Processing over Networks
Consensus overmulti-agent networks can be accelerated by utilizing agent’s memory to the control protocol. In this paper, a general protocol with memory information from the node and its neighbors is designed. We aim to provide an optimal memory scheme to accelerate consensus. The contributions of this paper include: (i) For the one-tap memory scheme, we prove that the memory information of neighbors is unnecessary for the optimal convergence. (ii) It is proved that in the worst-case scenario, one-tap node memory is sufficient to achieve the optimal convergence rate, that is, adding more taps of past information from neighbors can not improve the rate further. (iii) It is found that the convergence rate with two-tap memory can be further improved on star networks. Numerical examples are presented to illustrate the validity and correctness of the obtained results.
10 November 2022 in IEEE Transactions on Cybernetics
For the centralized optimization, it is well known that adding one momentum term (also called the heavy-ball method) can obtain a faster convergence rate than the gradient method. However, for the distributed counterpart, there is quite few results about the effect of added momentum terms on the convergence rate. This article is aimed at studying the issue in the distributed setup, where $N$ agents minimize the sum of their individual cost functions using local communication over a network. The cost functions are twice continuously differentiable. We first study the algorithm with one momentum term and develop a distributed heavy-ball (D-HB) method by adding one momentum term on to the distributed gradient algorithm. By borrowing tools from the control theory, we provide a simple convergence proof and an explicit expression of the optimal convergence rate. Furthermore, we consider adding two momentum terms case and propose a distributed double-heavy-ball (D-DHB) method. We show that adding one momentum term allows faster convergence while adding two momentum terms does not perform any superiorities. Finally, simulation examples are given to illustrate our findings.
In this paper, the cluster consensus problem of linearly coupled multi-agent systems in directed networks is studied by constructing a Laplacian of a directed graph. Different from the former work in which the clusters are divided artificially, in this paper, the relationship between the number of the clusters and the Laplacian is revealed. It is obtained that the number of clusters equals to the multiplicity of the zero eigenvalue of the Laplacian. Based on the Algebraic Graph Theory, the Matrix Theory and the Modern Control Theory, a sufficient and necessary condition about the global stability of the cluster consensus in multi-agent system is derived. A numerical example is proposed to illustrate the effectiveness of the method.
5 December 2022 in IEEE Transactions on Control of Network Systems
In this paper, the fast consensus problem of high-order multi-agent systems (MASs) under undirected topologies is considered. The direct link between the consensus convergence rate and the control gains is established. A gradient descent based algorithm is proposed to optimize the convergence rate. By applying the Routh-Hurwitz stability criterion, the lower bound on the convergence rate is derived, and explicit control gains are derived as conditions to achieve the optimal convergence rate. Moreover, a protocol with time-varying control gains is designed to achieve the finite-time consensus. Explicit formulas for the time-varying control gains and the final consensus state are given. Numerical examples and simulation results are presented to illustrate the obtained theoretical results.