Optimal Weights for Consensus of Networked Multi-Agent Systems

INTRODUCTION

Recent years have seen the emergence of consensus of swarm agents as a topic of significant interest to the controls community. Multi-agent systems have appeared widely in many applications including cooperative control of Unmanned Air Vehicles (UAVs), formation control (Fax and Murray, 2004), flocking (Saber, 2006), distributed sensor network, attitude alignment of clusters of satellites and congestion control in communication networks (Paganini et al., 2001).

Consensus problem has attracted many scientists and researchers in the fields of physics and mathematics and computers. In fact, the consensus phenomena in the nature presented in schooling fish, flocking birds, herds, have motivated the researchers (Hanspeter et al., 2003; Simon et al., 2004; Couzin et al., 2002; Cucker and Smale, 2007; Okubo, 1986; Couzin and Franks, 2003; Inada, 2001; Breder, 1954). The earliest computer model of flocks is set up by Reynolds (1987). Reynolds (1987) proposed the famous boid model. Individuals in the swarm interacting with each other are based on local information and obey the following three rules:

Collision avoidance: Each boid avoids collisions with nearby flockmates.

Velocity matching: Each boid attempts to match velocity with nearby flockmates.

Flock centering: Each boid attempt to stay close to nearby flockmates. A special version of the model introduced by Reynolds (1987) is the Vicsek model proposed by Vicsek et al. (1995). Some very interesting simulation results are provided by Vicsek et al. (1995). The results show that all agents eventually move in the same direction based on local information without any central control or leaders. Flocking behaviors have been analyzed in detail (Jadbabaie et al., 2003; Saber and Murray, 2003, 2004; Moreau, 2005; Ren and Beard, 2005; Saber et al., 2007). A theoretical explanation for Vicsek model is presented by Jadbabaie et al. (2003). Moreover, convergence results for case of leader following are also provided. Consensus problems for networks of dynamic agents with fixed and switching topologies are discussed by Saber and Murray (2003, 2004). A theoretical framework for design and analysis of distributed flocking algorithms is presented by Saber (2006) in the view of control engineering. Stability analysis of swarm agents are considered mainly in (Moreau, 2005; Saber, 2006; Fax and Murray, 2004).

Analysis on convergence speed and time-delays is very important for consensus. Obviously with fast convergence speed the states of multi-agent systems reach consensus very fast, that is, the performance of agreement is good. The convergence speed of consensus protocol is bounded by the second smallest eigenvalue of graph Laplacian matrix that is called algebraic connectivity. At the same time, the existence of time-delays in communication networks must be considered. When the network topology composed by multi-agent systems is fixed, undirected and connected, the maximum time-delay the system can tolerate is inversely proportional to the largest eigenvalue of graph Laplacian matrix (Saber and Murray, 2004).

The goal of consensus algorithm is to get high performance and robustness to time delays. And there is a trade-off between performance and robustness. In some applications, consensus algorithms must satisfy given requirements or optimize performance criteria. For example, when a Unmanned Arial Vehicles (UAV) or Micro-Air Vehicles (MAV) swarm consists of hundreds or thousands of vehicles, it might be desirable to make the states of swarm reach consensus in a given time interval and tolerate maximum time delay in communication. This problem can be solved by designing the optimal weights of the network so as to make states of swarm achieve agreement fast and robustness to delay as long as possible.

This study mainly focuses on designing optimal weights of network when the graph composed of swarm agents is connected and symmetric. With the weights the states of the swarm agents can achieve consensus at a given speed as well as the smallest value of delay such that the system can not converge to a consensus is maximized. The method to design optimal weights is based on linear matrix inequality theory. In order to make the second smallest eigenvalue of Laplacian matrix to be given value as well as make the largest eigenvalue as small as possible, the order of Laplacian matrix is reduced. Then designing optimal weights is equivalent to minimizing condition number of a positive definite matrix.

PRELIMINARIES

Here, we introduce some basic concepts and notation in graph theory (Diestel, 2000). A survey on properties of Laplacians of graph is stated here.

Algebraic graph theory and matrix theory: Let G = (V, E, A) be a weighted directed graph of order n with the set of agents V = (v₁, …, v_n), set of edges E⊆VxV and a weighted adjacency matrix A = (a_ij) with nonnegative adjacency elements a_ij. The agent indices belong to a finite index set I = (1, 2, …, n). An edge of G is denoted by e_ij = (v_i, v_j). The adjacency elements associated with the edges of the graph are positive, i.e., e_ijεE⇔ α_ij>0. Moreover, we assume a_ij = 0 for all iεI. The set of neighbors of agent v_i is denoted by Ni = (v_jεV: (v_i, v_j)εE ). The in-degree and out-degree of agent v_i are, respectively, defined as follows:

For a graph with 0-1 adjacency elements, degout (v_i) = |N_i|. The degree matrix of the digraph G is a diagonal matrix D = (d_ij) where, d_ij = 0 for all i ≠ j and d_ij = deg_out (v_i). The graph Laplacian associated with the digraph G is defined as:

For undirected graph, the adjacency matrix is symmetric, i.e., a_ij = a_ji. Its in-degree and out-degree are equal, i.e., deg_in (v_i) = deg_out (v_i). Then the Laplacian matrix is symmetric and defined by:

Consensus protocol: Let x_iεR denote the value of agent v_i. We refer to G_x = (G, x) with x = (x₁, …, x_n) as a network with value xεRⁿ and topology G. The value of a agent might represent physical quantities including attitude, position, temperature, voltage and so on. We say agents v_i and v_j agree in a network if and only if x_i = x_j. We say the agents of a network have reached a consensus if and only if x_i = x_j for all i, jεI, i ≠ j.

In this study, we consider the linear system

(1)

If there is communication time-delay τ_ij>0 corresponding to the edge e_ijεE, we use the following linear time-delayed consensus protocol:

(2)

The dynamics of system (1) can be expressed in a compact form as

where, L is known as the graph Laplacian of G. We note that zero is a eigenvalue of L and the associated eigenvector is 1_mx1. If graph G is strongly connected, 0 is an isolated eigenvalue of L. Spectral properties of Laplacian matrix L are instrumental in analysis of convergence of the class of linear consensus algorithms in (1). For undirected graphs, L is a symmetric matrix with real eigenvalues and therefore the set of eigenvalues of L can be ordered sequentially in an ascending order as:

For a connected graph G, λ₂>0. The second smallest eigenvalue of Laplacian λ₂ is a measure of performance of consensus algorithms. The largest eigenvalue is inversely proportional to the maximum time delay the algorithm can tolerate. We introduce two theorems by (Saber and Murray, 2004).

Theorem 1: (Performance of agreement) Consider a network with a fixed topology G that is strongly connected digraph. Given protocol (1), the states of the network globally asymptotically convergences with a speed equal to μ = λ₂.

Theorem 2: Consider a network of agents with equal communication time-delay τ>0 in all links. Assume the network topology G is fixed, undirected and connected. Then, protocol (2) with τ_ij = τ globally asymptotically solves the consensus problem if and only if either of the following condition is satisfied:

Moreover, for τ = τ* the system has a globally asymptocially stable oscillatory solution with frequency ω = λ_n.

According to Theorem 1 and 2, if we want to acquire high performance and robustness to time-delay we should make λ₂ as large and λ_n as small as possible. When the network is fixed, undirected, we can design weights of network, i.e., elements of Laplacian to increase performance and robustness.

OPTIMAL WEIGHTS FOR NETWORK

Here, we consider the network of system (2) with equal communication time-delay τ>0 in all links. Assume the network topology G is fixed, undirected and connected. The linear consensus protocol (2) can be repressed as:

(3)

In Eq. 3,

Our goal is to design weights of network (elements of L) to make the second smallest eigenvalue λ₂ be a given value as well as make the largest eigenvalue λ_n as small as possible. We transform system (3) into another form. Let α be 1/ (1…1)T, then Lα = 0. Let , be orthonormal complement of be the transpose of α. Then we can get = 0. States of system (3) can be:

where, δεR^p, θεR^n-p, we rewrite system (3) as follows:

Because (α_⊥, α) is unitary matrix, system (3) is equivalent to this equation:

(4)

Eigenvalues of system matrix in (4) are composed of 0 and eigenvalues of positive matrix and the eigenvalues of are non-zero eigenvalues of L. So designing optimal weights is equivalent to minimizing condition number of given that λ₂ is desirable to be a certain value.

Theorem 3: Consider a network of agents with equal communication time-delay τ>0 in all links. Assume the network topology G is fixed, undirected and connected. Then, protocol (2) with τ_ij = τ globally asymptotically converges to consensus with a speed equal to μ>0 as well as the maximum time-delay can be tolerated if and only if the following conditions are satisfied.

Minimize λ

Subject to

μI<<λμI/td>

aij≠¥ 0

τε (0, τ*) with τ* = π(2λμ). Moreover, for τ = τ* the system has a globally asymptotically stable oscillatory solution with frequency ω = λμ.

Remark 1: When the graph is completely connected, a_ij>0. When the graph are not complete, but connected, a_ij = 0 if agent v_j is not neighbor of agent v_i.

NUMERICAL SIMULATIONS

Figure 1 shows two different networks each with n = 3 agents. Two cases are considered. The graph G_a is complete and G_b is not complete, but connected. The graphs is undirected with the weights a_ij to be designed.

The Laplacians of graph G_a and G_b are, respectively as follows.

Now if the convergence speed of system (3) is required to be μ, then we can design the weights of the network by Theorem 3. The conditions in Theorem 3 can be solved by linear matrix inequality theory. If μ = 2, we can get the results:

when, λ₂ = λ₃ = μ = 2, λ = 1, τ_max = 0.7854

correspondingly, λ₂ = μ = 2, λ₃ = 6, λ = 3, τ_max = 0.2618

Figure 2 and 3 clearly show that the states of swarm agents reach consensus with a speed equal to μ when time-delay is less than the maximum time-delay τ_max. When communication time-delay is equal to τ_max, the state trajectories of all agents have become asymptotically stable oscillatory solutions with frequency ω = λμ.

Fig. 1:	Two examples of undirected graph: (a) Ga and (b) Gb

Fig. 2:	State trajectories of all agents corresponding to network on graph Ga with given convergence speed μ = 2 and different time-delays: (a) τ = 0, (b) τ = 0.5τ max and (c) τ = τmax

Fig. 3:	State trajectories of all agents corresponding to network on graph Gb with given convergence speed μ = 2 and different time-delays: (a) τ = 0, (b) τ = 0.5τmax and (c) τ = τmax