A Unified Optimization-Based Framework to Adjust Consensus Convergence Rate and Optimize the Network Topology in Uncertain Multi-Agent Systems

Mohammad Saeed Sarafraz and Mohammad Saleh Tavazoei,

Abstract—This paper deals with the consensus problem in an uncertain multi-agent system whose agents communicate with each other through a weighted undirected (primary) graph. The considered multi-agent system is described by an uncertain statespace model in which the involved matrices belong to some matrix boxes. As the main contribution of the paper, a unified optimization-based framework is proposed for simultaneously reducing the weights of the edges of the primary communication graph (optimizing the network topology) and synthesizing a controller such that the consensus in the considered uncertain multi-agent system is ensured with an adjustable convergence rate. Considering the NP-hardness nature of the optimization problem related to the aforementioned framework, this problem is relaxed such that it can be solved by regular LMI solvers.Numerical/practical-based examples are presented to verify the usefulness of the obtained results.

I. INTRODUCTION

THE distributed consensus is a fundamental issue in multiagent networks. Over the past few years, there has been considerable interest in developing algorithms to force a multi-agent system to reach a consensus. The survey paper [1]has summarized some new progress in this regard. It is well known that many practical problems in multi-agent networks such as flocking and swarming [2], [3], formation control [4],[5], sensor fusion [6], [7], and synchronization of coupled oscillators [8] can be formulated as a consensus problem.Generally speaking, in a consensus-seeking process, the agents in a given network try to agree on some quantity by communicating what they know only to their neighboring agents. As a particular type of consensus problem, some researchers have studied the multi-agent networks in which the aim is to converge to the average of the involved agents’initial values (e.g., [9]).

Up to now, various algorithms have been proposed and implemented to reach consensus in multi-agent systems. An important issue regarding the consensus algorithms is their performance. Considering this importance, the performance of consensus algorithms has been evaluated from different aspects. External attack resistance [10], robustness in the case of link failure [11] or the existence of delay [12], robustness to edge weight perturbations [13], and convergence rate are some indicators that determine the effectiveness of these algorithms. In this paper, we focus on the convergence speed in the consensus of multi-agent systems.

Regarding the convergence speed of the consensus, it is intuitively expected that the stronger connections in the communication graph yield a more enhanced convergence rate. Generally speaking, this expectation means that if the number of communication edges between the agents and the weight of these edges increases, the consensus’s convergence speed is improved. But, promoting the communication between the agents imposes additional costs, for example, in the viewpoint of energy consumption. In some real-world multi-agent systems, the batteries powering the agents have very low capacity and can not be conveniently recharged/replaced. As a result, reducing energy consumption to extend the agents’ battery lifetime has emerged as a critical issue in these networks. That is why various research studies have tried to reduce the energy consumption of communications [14]–[16]. Reviewing the facts mentioned above naturally raises a question about the best network topology for the neighborhood graph and corresponding distributed control law to optimize a cost function considering closed-loop performance (such as convergence speed) and communication costs.

On the other hand, in many practical cases, uncertainty is an inseparable part of modeling, and the controller should be designed to deal with the model’s uncertainties. Uncertainties can be generally modeled in different ways in the state-space representation. For example, in some research works, the uncertainty has been modeled via norm-bounded forms (e.g.,[17]). As a well-known fact, robust control approaches constructed on basis of norm-bounded modeling of uncertainty often lead to over-conservative results in dealing with uncertainties. In some other cases, uncertainty has been modeled by an affine polytopic structure (e.g., [18]). In polytopic models, system parameters are modeled as uncertain linear combinations of some known quantities. Although the polytopic modeling can cover linear parameters and multimodel uncertainties, it seems that the element-wise (or interval) modeling can provide a richer framework to describe the model in the presence of different sources of uncertainties.Moreover, a great advantage of element-wise modeling is its ability to simply express all systems included by this type of models. Considering these capabilities, element-wise models(or interval matrices in the state-space representation) have received a great attention in control systems literature (for example, in order to benefiting from their abilities in modeling of uncertain plants [19], [20] and stability analysis and stabilization of uncertain interval systems [21]–[23]). Dealing with uncertain multi-agent systems, two approaches are prevalent to model the uncertainties by element-wise structures. The first approach is constructed based on that the uncertainties are assumed to be different for each agent (e.g.,[24], [25]). Another approach is based on the assumption that the uncertainties on the dynamic models of the agents are due to the same but uncertain factors. Some research works, such as [26]–[28], have considered this assumption in element-wise modeling of the under-study multi-agent system. In the present paper, we follow the second aforementioned approach.

Related Literature:There are different topology design methods for multi-agent systems in the literature constructed based on performance optimization issues. It has been shown that the eigenvalues of the Laplacian matrix of the communication graph play a significant role in determining the properties and performance of a wide range of multi-agent network systems. Considering this point, [29] has tried to optimize some specific functions of graph Laplacian eigenvalues by appropriately choosing the edge weights via applying semi-definite programming. Some other relevant research works have solved constrained versions of this problem. For example, [30] has introduced an algorithm to find a graph with weighted edges which maximizes the convergence speed under the constraint that the number of edges with nonzero weight is less than or equal to a given positive integer. By considering another case, the mentioned work has solved the problem under the constraint that the Laplacian graph’s second eigenvalue is greater than or equal to a given positive value. Also, [31] deals with the problem of finding optimal communication graphs with a fixed number of vertices and edges that maximize the convergence speed.Moreover, [32] has investigated the problem of removing some links such that the largest eigenvalue of the resulting graph’s adjacency matrix is minimized. Recently, [33] has introduced a method to optimize any cost function defined based on Laplacian eigenvalues for a directed graph. As another example, [34] has solved the convergence rate problem subject to the constraints limiting the weighted degree of graph nodes.

The majority of the relevant research papers, such as the above-cited works, have focused only on optimizing the network parameters and have not simultaneously optimized the other factors (e.g., free parameters of the controller or the different factors influencing the security issues) which may be effective on the performance of the multi-agent systems. Even though there are a few works in which combined objectives have been satisfied in a unified framework. For example, [35]has introduced an algorithm to balance between convergence rate and security level for an undirected graph. As another example, [36], [37] have considered a discrete-time multiagent system and proposed an algorithm that minimizes the sum of the quadratic infinite horizon cost and the communication one.

Various research works have tried to design consensus algorithms for uncertain multi-agent systems to deal with the model uncertainties. In some papers, such as [38], [39] have considered multi-agent models with norm-bounded additive uncertainties in the frequency domain and used analytical tools like small-gain theorem to propose robust consensus algorithms. As another example, [40] has analyzed scalable consensus for a class of scalar uncertain multi-agent systems.Also, some other papers have studied consensus in the multiagent systems that are modeled with uncertain state-space models. Reference [41] has proposed a consensus algorithm for double integrators’ networks with parametric uncertainties.Moreover, [42] has considered a network of scalar uncertain linear time-invariant agents and designed a consensus algorithm for them. Multi-agent models with norm-bounded uncertainties have been considered in [43], [44], and [45] has considered consensus in multi-agent systems with polytopic uncertainty. To the best of the authors’ knowledge, multiagent models with element-wise uncertainty have not received much attention, and consequently, the present paper tries to address this gap. More precisely, in this paper, we will propose a linear matrix inequality (LMI) based method to codesign a network topology and a robust controller for a multiagent system with element-wise uncertainties such that the preservation of the convergence rate and reducing the communication costs are simultaneously met. The main novelty of the present research work in comparison with the existing literature, including the relevant works discussed above, is that the targets of optimizing the network topology and finding an appropriate controller to ensure consensus with a reasonable convergence rate in uncertain multi-agent systems are simultaneously achieved by solving a single optimization problem. Such a unified optimization-based framework to achieve the aforementioned targets in consensus of multi-agent systems with element-wise uncertainties has not been introduced in previous research works.

Contributions:As discussed, this paper provides a unified computational framework for simultaneously optimizing the network topology and designing robust controllers in uncertain multi-agent systems such that communication costs are reduced with no unfavorable effect on the convergence speed. It is assumed that the uncertainties in the under-study multi-agent systems are modeled in an element-wise form.The main contributions of the paper can be summarized as follows:

1)Unified Framework for the Design of Robust Controllers and Optimizing the Network Topology:An optimization-based framework that introduces a sufficient condition that helps us to find robust controllers for consensus in multi-agent systems with element-wise uncertainties and the weights of the edges in the corresponding optimized communication graph is introduced (Theorem 1).

2) Convex Optimization Relaxation:It is justified that the problem discussed in the previous item (the problem addressed by Theorem 1) is NP-hard. Benefiting from the state-of-the-art in literature, the obtained optimization-based sufficient condition is relaxed such that it can be verified by using regular LMI solvers (Theorem 2).

Organization:The remainder of the paper is organized as follows. Section II briefly introduces the notations and definitions used in this paper. The under-study problem is formulated with some basic assumptions in Section III. In Section IV, firstly, some preliminary results from previous works are restated, and then by using them, the main results of the paper are presented. Examples are given in Section V to illustrate the theoretical results of the paper. Finally,Section VI concludes the paper and suggests some directions for future research works in continuation of the work done in this paper.

II. NOTATIONS AND DEFINITIONS

III. PROBLEM STATEMENT

Consider a multi-agent system withnagents such that each agent updates its state vector by the dynamic model

In this paper, we intend to simultaneously find a simple controller and a subgraph for graph G under which system (1)reaches to consensus at an appropriate convergence rate.Naturally, we expect a trade-off between the communication graph edges’ weight values and the convergence speed.Generally speaking, this means that the convergence rate can be improved for a given controller if the weights of the graph edges are increased. Finding the optimal subgraph and the robust controller guaranteeing consensus is the main focus of this paper in Section IV. The corresponding problem can be formulated as follows.

IV. MAIN RESULTS

Theorem 1 (Solving Problem 1):Consider the multi-agent system (1) satisfying Assumptions 1 and 2. Also, consider the optimization problem which can be used to verify the consensusability in the considered multi-agent system. From definition (7) and dynamic model (1), it is obtained that

The optimization problem (6) in Theorem 1, in its general form, is non-convex. The non-convexity originates from the fact that the last constraint in this optimization problem should be satisfied for a family of matrices. It is worth noting that, as a special case, if the system matrices (A⋆andB⋆) are fixed and known, then the problem reduces an LMI and can be solved by using regular LMI solvers. But, unfortunately, when these matrices are uncertain, finding the exact solution of the aforementioned optimization problem is provably intractable.In order to clarify the point, let us consider the problem of checking the stability of system

The problem (16) is a special case of the problem of stability checking of an interval matrix [48], which is strongly NP-hard [49, Corollary 2.6]. It is clear that the problem (16)has a solution if and only if the solution of the optimization problem (10) forj=2 and a fixedKis non-negative.Consequently, it is expected that there is no polynomial-time algorithm for solving problem (16) (or problem (6)). A conservative approach for relaxing the situation is to use a common Lyapunov function in (16), which yields in the following problem:

Inequality (17) is a special form of the problems, which are known as the “matrix cube problems” in [50]. Unfortunately it has been proved that this class of problems are also NP-hard[50, Proposition 4.1]. Hence, we have to resort to approximation methods for solving such problems. Existing results in this area offer effective conservative approximations such that the resulted conservatism is bounded independently of the size of the problem [51]. Benefiting from such developments, the following theorem provides a conservative (but computationally tractable) convex optimization to be solved instead of the optimization problem (6).

Reusing the Schur complement for (23) leads to the conclusion that these inequalities are equivalent to

V. NUMERICAL EXAMPLES

In this section, numerical examples illustrating the applicability of the main results of the paper are presented.

Example1:Consider a group of 5 homogeneous uncertain agents described by dynamic model (1), which satisfies Assumption 1, withAb=0.1(⊗14)Bb=0.1(⊗14)

and (The nominal matrices are selected from “REA2” example inCompliblibrary of MATLAB2http://www.complib.de/).

Fig. 1. Communication topology in Example 1.

Fig. 2. The trade-off between the weight of edges and the convergence speed for different values of parameter ζ.

The following example, borrowed from [28] with some modifications, verifies the applicability of the obtained results in consensus analysis in a platoon of homogeneous vehicles with boundary uncertainties.

Example2:Consider a platoon of 10 automated vehicles, as a multi-agent system with 10 agents. Using an inverse model compensation based approach, such agents have been modeled by uncertain linear models in [28]. The reduced uncertain linear dynamic model of agenti∈{1,...,10} is of the form

where

Fig. 3. Communication topology in Example 2.

Let the aim in this problem be to optimize the network topology such that the convergence rate in consensus of the agents is not considerably affected. For this purpose, the optimization problem (18) with the objective function in the form (14) and ζ=30 has been solved. By solving the optimization problem with the specified objective function,the sum of the weight of the graph edges is reduced to 1.9541.In addition, starting from the initial positions [1 2 3 ... 10]⊤,the agents converge to consensus after about 7 seconds, as that shown in Fig. 4.

Fig. 4. The position, velocity, and acceleration of the vehicles in Example 2 under the controller and the optimized network topology obtained by solving the optimization program (18).

VI. CONCLUSION

In this paper, an optimization-based framework was introduced to solve the consensus problem for an uncertain homogeneous linear multi-agent system. The main advantage of this framework, introduced in Theorem 1, is that in addition to synthesizing a robust controller for ensuring consensus with an adjustable convergence rate, it can simultaneously reduce the communications between the agents. Furthermore, it was shown that the optimization problem that was introduced in Theorem 1 is NP-hard. To deal with this challenge, the corresponding optimization problem was conservatively relaxed in the Theorem 2 such that the alternative conservative problem can be solved by applying the regular LMI solvers. There are some interesting lines, which invite further research works in the continuation of the research done in this paper. For instance, a relevant research work in future can be to propose a distributed algorithm for solving the optimization problem (18). It seems that the idea ofProjected Primal-Dual Gradient Flow, which has been introduced in[53], can be helpful to propose such a distributed algorithm.As another relevant future work, similarly to the frameworks surveyed in [54], the obtained results can be extended to balance the convergence rate and the communication load in consensus of heterogeneous multi-agent systems.