**ABSTRACT**

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**

*Information Technology Journal, 8: 77-82.*

**DOI:**10.3923/itj.2009.77.82

**URL:**https://scialert.net/abstract/?doi=itj.2009.77.82

**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_{1}, …, 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:

L(G) = D-A |

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_{1}, …, x_{n}) as a network with value xεR^{n} 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, λ_{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:

(3) |

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, δε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 λ_{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.

Minimize λ |

Subject to |

μI<<λμI/td> |

a_{ij}≠¥ 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} = λ_{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) G_{a} and (b) G_{b} |

Fig. 2: | State trajectories of all agents corresponding to network on graph G _{a} 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 G_{b} with given convergence speed μ = 2 and different time-delays: (a) τ = 0, (b) τ = 0.5τ_{max} and (c) τ = τ_{max} |

**CONCLUSION**

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.

**ACKNOWLEDGMENT**

This project is sponsored by the National Natural Science Foundation of China under Grant No. 60574088 and 60874053.

####
**REFERENCES**

- Breder, C.M., 1954. Equations descriptive of fish schools and other animal aggregation. Ecology, 35: 361-370.

CrossRefDirect Link - Couzin, I.D. and N.R. Franks, 2003. Self-organized lane formation and optimized traffic flow in army ants. Proc. R. Soc. London B. Biol. Sci., 270: 139-146.

CrossRefPubMedDirect Link - Couzin, I.D., J. Krause, R. James, G.D. Ruxton and N.R. Franks, 2002. Collective memory and spatial sorting in animal groups. J. Theor. Biol., 218: 1-11.

CrossRefPubMedDirect Link - Cucker, F. and S. Smale, 2007. Emergent behavior in flocks. IEEE Trans. Automat. Control, 52: 852-862.

CrossRefDirect Link - Fax, J.A. and R.M. Murray, 2004. Information flow and cooperative control of vehicle formations. IEEE Trans. Autom. Control, 49: 1465-1476.

CrossRefDirect Link - Hanspeter, K. and K.H. Charlotte, 2003. Artificial fish schools: Collective effects of school size, body size and body form. Artifi. Life, 9: 237-253.

CrossRefDirect Link - Jadbabaie, A., L. Jie and A.S. Morse, 2003. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Automat. Control, 48: 988-1001.

CrossRefDirect Link - Moreau, L., 2005. Stability of multi-agent systems with time-dependent communication links. IEEE Trans. Automat. Control, 50: 169-182.

CrossRefDirect Link - Okubo, A., 1986. Dynamical aspects of animal grouping: Swarms, schools, flocks and herds. Adv. Biophys., 22: 1-94.

CrossRefDirect Link - Paganini, F., J. Doyle and S. Low, 2001. Scalable laws for stable network congestion control. Proceedings of the 40th Conference on Decision and Control, December 4-7, 2001, Orlando, FL., USA., pp: 185-190.

CrossRefDirect Link - Ren, W. and R.W. Beard, 2005. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Trans. Automat. Control, 50: 655-661.

CrossRefDirect Link - Reynolds, C.W., 1987. Flocks, herds and schools: A distributed behavioral model. Comput. Graph., 21: 25-34.

CrossRefDirect Link - Olfati-Saber, R., 2006. Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Trans. Automatic Control, 51: 401-420.

CrossRefDirect Link - Saber, R.O., J.A. Fax and R.M. Murray, 2007. Consensus and cooperation in multi-agent networked systems. Proc. IEEE, 95: 215-233.

CrossRefDirect Link - Olfati-Saber, R. and R.M. Murray, 2004. Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans. Autom. Control, 49: 1520-1533.

CrossRefDirect Link - Saber, R.O. and R.M. Murray, 2003. Consensus protocols for networks of dynamic agents. Proceedings of the American Control Conference, June 4-6, 2003, Denver, Colorado, pp: 951-956.

Direct Link - Simon, H., B. Petro, S.T. Sven and G.M. Kjartan, 2004. A model of the formation of fish schools and migrations of fish. Ecol. Model., 174: 359-374.

CrossRefDirect Link - Vicsek, T., A. Czirok, E. Ben-Jacob, I. Cohen and O. Sochet, 1995. Novel type of phase transition in a system of self-driven particle. Phys. Rev. Lett., 75: 1226-1229.

CrossRefPubMedDirect Link