In this study, a way to design the optimal weights associated with edges of undirected graph composed of multi-agent systems is presented. The optimal weights are designed to make the states of the multi-agent systems converge to consensus with a fast speed as well as the maximum communication time-delay can be tolerated. The method used in our research is based on linear matrix inequality theory. The convergence speed which is determined by the second-smallest eigenvalue of graph Laplacian matrix is assumed to be a given value, at the same time the maximum communication time-delay which is decided by the maximum eigenvalue of Laplacian matrix can be got. In order to get required second-smallest eigenvalue and optimal maximum eigenvalue, the order of Laplacian matrix is reduced by variable decomposition. Moreover, designing the optimal weights is equivalent to minimizing condition number of a positive-definite matrix. Simulation results are coincidental with theoretical analysis.
PDF Abstract XML References Citation
How to cite this article
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.
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 = (v1, , vn), set of edges E⊆VxV and a weighted adjacency matrix A = (aij) with nonnegative adjacency elements aij. The agent indices belong to a finite index set I = (1, 2, , n). An edge of G is denoted by eij = (vi, vj). The adjacency elements associated with the edges of the graph are positive, i.e., eijεE⇔ αij>0. Moreover, we assume aij = 0 for all iεI. The set of neighbors of agent vi is denoted by Ni = (vjεV: (vi, vj)εE ). The in-degree and out-degree of agent vi are, respectively, defined as follows:
For a graph with 0-1 adjacency elements, degout (vi) = |Ni|. The degree matrix of the digraph G is a diagonal matrix D = (dij) where, dij = 0 for all i ≠ j and dij = degout (vi). The graph Laplacian associated with the digraph G is defined as:
L(G) = D-A
For undirected graph, the adjacency matrix is symmetric, i.e., aij = aji. Its in-degree and out-degree are equal, i.e., degin (vi) = degout (vi). Then the Laplacian matrix is symmetric and defined by:
Consensus protocol: Let xiεR denote the value of agent vi. We refer to Gx = (G, x) with x = (x1, , xn) as a network with value xεRn and topology G. The value of a agent might represent physical quantities including attitude, position, temperature, voltage and so on. We say agents vi and vj agree in a network if and only if xi = xj. We say the agents of a network have reached a consensus if and only if xi = xj for all i, jεI, i ≠ j.
In this study, we consider the linear system
If there is communication time-delay τij>0 corresponding to the edge eijεE, we use the following linear time-delayed consensus protocol:
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 1mx1. 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, λ2>0. The second smallest eigenvalue of Laplacian λ2 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 μ = λ2.
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 λ2 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:
In Eq. 3,
Our goal is to design weights of network (elements of L) to make the second smallest eigenvalue λ2 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, δεRp, θεRn-p, we rewrite system (3) as follows:
Because (α⊥, α) is unitary matrix, system (3) is equivalent to this equation:
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 λ2 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.
τε (0, τ*) with τ* = π(2λμ). Moreover, for τ = τ* the system has a globally asymptotically stable oscillatory solution with frequency ω = λμ.
Remark 1: When the graph is completely connected, aij>0. When the graph are not complete, but connected, aij = 0 if agent vj is not neighbor of agent vi.
Figure 1 shows two different networks each with n = 3 agents. Two cases are considered. The graph Ga is complete and Gb is not complete, but connected. The graphs is undirected with the weights aij to be designed.
The Laplacians of graph Ga and Gb 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 = λ3 = μ = 2, λ = 1, τmax = 0.7854
correspondingly, λ2 = μ = 2, λ3 = 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 ω = λμ.
Sτ = 0
|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|
This study provides a theoretical analysis for designing optimal weights of a network composed of swarm agents. For consensus problem of multi-agent systems, the goal of designing optimal weights is to make the states of all agents agree with certain speed required in practical application, at the same time, the communication time-delays between agents the network can tolerate must be maximized. We design optimal weights based on linear matrix inequality theory. The problem can be equivalent to designing the elements of Laplacian matrix of graph with some constraints. A method to reduce the order of Laplacian matrix is discussed. In order to solve the optimal weights, the way to minimizing the condition number of a positive-definite matrix is stated. Two cases that graph is complete and not complete, but connected are considered. Theorem 3 is concluded. Finally, simulation results are given to show that the results are in line with theoretical analysis.
This project is sponsored by the National Natural Science Foundation of China under Grant No. 60574088 and 60874053.