1
Decentralized Laplacian Eigenvalues Estimation of the Network Topology of a Multi-Agent System Mauro Franceschelli, Andrea Gasparri, Alessandro Giua, Carla Seatzu.
Abstract In this paper we present the first known decentralized algorithm to estimate the eigenvalues of the Laplacian of the network topology of a multi-agent system. We provide formal proofs for the algorithm convergence properties and simulations to substantiate its effectiveness. The algorithm and the related theory are presented in continuous time. We finally show some numerical simulations and discuss the practical implementation of the proposed algorithm from a digital signal processing perspective.
Published as: M. Franceschelli, A. Gasparri, A. Giua, C. Seatzu, "Decentralized Laplacian Eigenvalues Estimation of the Network Topology of a Multi-Agent System," 48th IEEE Conference on Decision and Control, (Shanghai, China), Dec. 2009. This work has been partially supported by the European Community’s Seventh Framework Programme under project DISC (Grant Agreement n. INFSO-ICT-224498). M. Franceschelli, A. Giua and C. Seatzu are with the Dept. of Electrical and Electronic Engineering, University of Cagliari, Piazza D’Armi, 09123 Cagliari, Italy. Email: {mauro.franceschelli,giua,seatzu}@diee.unica.it. Andrea Gasparri is with the Department of Computer Science, University of “Roma Tre”, Via Vasca Navale 79, Roma 00146, Italy. Email:
[email protected]. October 26, 2010
DRAFT
I. I NTRODUCTION Nowadays the research community of Control System Theory is making a great effort to provide algorithms for coordination and estimation in networks of multi-agent systems [1], [2], [3], [4]. Such systems represent an ideal abstraction of actual networks of mobile robots that are envisioned to perform the most various kind of tasks in the future. Whatever the actual implementation of networked multi-agent systems is, they must always share one common feature, namely the existence of a network topology. Algebraic graph theory [5] is widely known to provide powerful tools and abstractions to represent and model networks of agents such as proximity graphs [6], to name one. In particular, the representation of the network topology of a multi-agent system through graphs [7], where the nodes represent the agents and the edges represent the existence of an interaction between them, has proven to be a powerful modeling tool and has been exploited in the most various ways. In algebraic graph theory a great effort is made in trying to characterize the properties of a graph through the study of the eigenvalues of the Laplacian matrix defined over the adjacency matrix, i.e., a matrix representation of the graph. This approach has clearly a great application in evaluating the performance and converge properties of algorithms running on networks modeled in such a way. To name one, the second smallest eigenvalue of a Laplacian matrix, called the algebraic connectivity of the graph, is known to play a major role in the convergence time of various control and estimation algorithms [8]. Unfortunately this information up to now can be obtained only by centralized algorithms where a global knowledge about the network topology is available. In this paper we present a novel algorithm that through only local interactions between agents is able to retrieve information concerning the eigenvalues of the whole network and make such information available for the design of new control and estimation applications enriched by the availability of this new kind of information. The basic idea of the algorithm, is to provide a local interaction rule among agents whose goal is to make their state oscillate at all and only at the frequencies corresponding to the eigenvalues of the network topology. In this way, the problem of decentralized eigenvalue identification is mapped into a problem of signal processing that each agent can efficiently and independently solve by applying the Fast Fourier Transform (FFT) algorithm to its state trajectory. We present our theory in continuous time. The approximation and practical implementation from a digital signal processing perspective are discussed and simulations are shown. An implementation of such an algorithm on real mobile robots will be object of future research. Paper content This paper is structured as follows. • In Section II some basic concepts concerning graph Laplacians are reviewed. • In Section III the main result of this paper is presented, namely a decentralized algorithm to identify the eigenvalues of a network, together with its analysis. • In Section IV some basic properties of the spectrum of the graph Laplacian and some elementary links with the topology of the network are shown.
•
•
•
In Section V the observability of the network topology is discussed giving a straight link between the observability properties of the proposed algorithm and the observability of the graph Laplacian, which has been characterized in [9] from a graph theoretical point of view. In Section VI some simulations are shown and issues of the practical implementation of the algorithm are discussed regarding the digital signal processing involved. In Section VII we finally give the concluding remarks. II. BACKGROUND
Let us consider a network of agents whose interactions can be described by a time varying graph G(t) = {V, E(t)}. V = {1, . . . , n} is the set of nodes, where n is the number of agents. E(t) ⊆ {V × V } is the set of edges: an edge ei,j (t), with i 6= j, exists between nodes i and j at time t if agent i interacts with agent j at time t. We define A(t) the time varying adjacency matrix: it is a n × n matrix whose generic element ai,j (t) = 1 if i 6= j and ei,j (t) ∈ E(t), ai,j (t) = 0 otherwise. The number of the incoming edges ∆i of node i is called the indegree. We define ∆(t) as the degree matrix: it is a n × n time varying diagonal matrix whose elements are ∆i (t), i.e., the indegree of node i at time t. In the following we will refer to Ni (t) as the neighborhood of agent i, namely the set of indices of the agents directly connected through an edge with agent i at time t. Clearly, it is |Ni (t)| = ∆i (t). Finally we define the time varying Laplacian of graph G as L(G(t)) = ∆(t)−A(t). To simplify the notation we will refer to it as L(t) implying its dependence on G(t). Let us now review some properties of the Laplacian of an undirected graph. First of all, L is a weakly diagonal dominant symmetric matrix by construction. Furthermore we have that the row sum and the column sum are each equal to zero. In particular any graph Laplacian has always at least one null structural eigenvalue whose corresponding eigenvector is the vector of ones 1 of appropriate dimensions; in other words ∀G, L(G)1 = 0 and 1T L(G) = 0T . The number of null eigenvalues corresponds to the number of connected components of G and Rank(L(G)) = n − c where n is the number of nodes and c is the number of connected components of G [2]. All the eigenvalues of the Laplacian are real and positive as it can be proved by applying the Gershgorin disc theorem as in [2]. Due to the Gershgorin theorem all the Laplacian eigenvalues are in [0, 2∆max ], where ∆max is the maximum degree between the nodes in the graph. An agent can be of any kind, for instance a mobile robot, a sensor node, a software agent or else. We assume that each agent i can handle the numerical update of two state variables, namely xi and zi . Furthermore we assume that if an edge exists between two agents, they can communicate to each other the values of their internal state at each instant of time in which they are connected, for instance through a wireless connection, a wired connection, a virtual local area network, sonar, ultrasound or else. We finally point out that the following results can be straightforwardly extended to the case of weighted graphs. III. E IGENVALUE IDENTIFICATION The proposed algorithm consists of each agent performing the following state updating rule:
(
P x˙ i (t) = j∈Ni (t) zi (t) − zj (t), P z˙i (t) = − j∈Ni (t) xi (t) + xj (t).
(1)
The behavior of the network state when each agent performs the above updating rule can be described by the following time varying autonomous linear system: · ¸ · ¸ x(t) ˙ x(t) = A(t) · (2) z(t) ˙ z(t) where
· A(t) =
0 −L(t) L(t) 0
¸ (3)
and 0 is the null n × n matrix. This is basically a linear switching system, where the linear autonomous dynamics changes to a different linear autonomous dynamics abruptly when an edge is added or removed from the network. If no edge is added or removed for a time interval ∆t, then during such a time interval the dynamics becomes time-invariant. In the following we will refer to A as the matrix governing the dynamics of the linear system during an interval of time in which no topology change occurs. In this case, the state space trajectory of each agent is a linear combination of the modes of the system. Note that matrix A is skew symmetric (i.e., AT = −A) for any network topology being the Laplacian of undirected graphs symmetric by definition. Moreover, any skew symmetric matrix has eigenvalues only on the imaginary axis of the Gauss plane. Therefore, as proved in the following theorem, the eigenvalues of A can be calculated analytically, as a function of the eigenvalues of the Laplacian matrix. Theorem 1: Let G be an undirected graph with Laplacian L. Let matrix A be defined as in eq. (3). To any eigenvalue λL of L it corresponds a couple of eigenvalues ¯ = ±jλL . λ, λ
Proof: By definition, the eigenvalues of A are the solutions of µ· ¸¶ λI L(t) det(λI − A) = det = 0. −L(t) λI Since A is a block matrix whose blocks commute, then ¡ ¢ det(λI − A) = det λ2 I + L2 . Now, since the eigenvalues λL of the Laplacian are solution of the equation det(λL I − L) = 0, and the eigenvalues of matrix L2 are equal to λ2L , it holds that λ2 = −λ2L .
Finally, since the eigenvalues of the Laplacian of an undirected graph are all real and positive, we have that q ¯ λ, λ = −λ2L = ±jλL , thus proving the statement. ¥ By Theorem 1 it follows that if the topology does not change during a certain time interval, then each state of each agent follows an oscillating trajectory which is a linear combination of sinusoids oscillating at and only at the frequencies corresponding to the eigenvalues of the network at time t. The following theorem formalizes this. In the following we assume that the Laplacian eigenvalues are 0 = λ1 ≤ λ2 , . . . ≤ λn . Theorem 2: Let us consider a system described by eq. (2) relative to a network whose graph G is connected. The module of the Fourier transform of the ith state component xi (t), i = 1, . . . , n, is equal to |F[xi (t)]| = |Xi (f )| = a0 δ(0) +
n X aj j=2
2
δ(f ± λj /2π).
where δ(·) is the Dirac’s delta function. Proof: The state trajectory of xi (t) is a linear combination of the system modes. Since A is skew symmetric, thanks to the Spectral Theorem it is always diagonalizable through a unitary matrix1 . Thus all the eigenvalues have geometric multiplicity equal to their algebraic multiplicity (or equivalently, unitary index). By Theorem 1 to each Laplacian eigenvalue λj it corresponds ¯ = ±jλj . Therefore a couple of pure imaginary eigenvalues of A that is equal to λ, λ xi (t) = a0 +
n X
aj sin(λj t + φj ),
j=2
i.e., it is equal to a dc component plus a linear combination of sinusoids whose amplitudes and phase shifts are obviously function of the initial conditions and of the graph topology. Now, the module of the Fourier transform of xi (t) can be straightforwardly computed term by term, being it composed of a finite number of impulses at the frequencies corresponding to the eigenvalues of L, thus proving the statement. ¤ The above theorem states the key result of this paper. In fact, it implies that each agent can solve the eigenvalue identification problem independently and in an efficient way by simply using the Fast Fourier Transform (FFT) algorithm. Note that this result can be also extended to the case of network topology switching slowly with respect to the ability of the agents to pick up the frequency peaks in the spectrum of their state trajectory. In fact, it allows to detect in a decentralized way changes in the network topology, such as network disconnections, changing in the formation of the agents, lost of crucial links 1
A unitary matrix U is a complex matrix such that U ∗ U = U U ∗ = I, where U ∗ is the complex conjugate of U .
that decrease the network algebraic connectivity making it more vulnerable to disconnection, and so on. Remark 1: Two important remarks need to be done. — The value of xi (t) can be seen as the output of the ith node. Now, if the system is not observable from the output xi (t) then some coefficients aj can be null and thus the corresponding mode cannot be detected by agent i. This implies that the corresponding Laplacian eigenvalue λj cannot be identified by agent i. — Since we are looking at the modulus of the spectrum of xi (t), if an eigenvalue has algebraic multiplicity greater than one it will result in a single line of higher amplitude and it might not be possible to identify its multiplicity by only looking at its spectrum. ¥ The following theorem shows that using the proposed state updating rule, each agent can also compute the average value of the initial conditions (as in the consensus problem) in an independent and efficient way, by simply looking at the dc component of the Fourier transform. Theorem 3: Let G be a connected graph. Assume that the state updating rule follows eq. (2) where A(t) = A is a constant matrix. Let x(0) = x0 and z(0) = z0 be the state initial conditions. Then the dc component of the Fourier transform of the state trajectory of the generic agent i is equal to: Pn T Xi (0) = a0 = 1n z0 = n1 i=1 z0,i , P T n Zi (0) = b0 = 1n x0 = n1 i=1 x0,i , where 1 denotes the n-dimensional column vector of ones. Proof: Let us preliminary observe that matrix A has two null eigenvalues whose corresponding right eigenvectors · ¸ · ¸ 1 1 0 1 vr,1 = √ , vr,2 = √ 1 n n 0 are linearly independent. Now, let J be a Jordan matrix relative to A, thus A = V JV −1 and eAt = V eJt V −1 , where V is a matrix whose columns are the right eigenvectors of A. In particular, we assume that the first two columns of V are equal to vr,1 and vr,2 , respectively. Since eJt is block diagonal with blocks made either by constant terms corresponding to null eigenvalues (with unitary index) or blocks corresponding to pure imaginary eigenvalues, then we can write it as the sum of two matrices: one constant matrix A0 , plus one time-varying matrix As (t), i.e., eJt = A0 + As (t). In particular, A0 contains the two blocks corresponding to the null eigenvalues, thus it only differs from the null matrix for the first two unitary entries in its diagonal; As (t) contains the blocks corresponding to the oscillatory terms. Therefore, matrix eAt can be written as eAt = V (A0 + As (t))V −1 = V A0 V −1 + V As (t)V −1 , showing that the state trajectory of each agent contains a dc component due to A0 and a combination of oscillatory components due to As (t).
Moreover, let us denote as Vl the matrix whose columns are the left eigenvectors of A, and let vl,i be the generic i-th column of Vl . Now, being matrix A skew symmetric, its left eigenvectors are equal (apart from a constant) to the corresponding right eigenvectors. Additionally, since the system is skew symmetric, V is unitary, V −1 = V T = Vl and V −1 V = I, where I is the 2n-dimensional identity matrix. Therefore, we have vl,1 = vr,1 and vl,2 = vr,2 , which allows to state the following result: V A0 V −1 =
h
i vr1 vr2 0 . . . 0
· V −1
T
T
1 0 T T 0 1 0 1 0 ... 0 1 1 T = √n · √n vl,3 1 0 0 ... 0 .. . T vl,n T 00T 11n , = T 11T 00 n
thus proving the statement. IV. W HAT CAN BE INFERRED FROM
¤ THE SPECTRUM OF A NETWORK ?
A consistent number of contributions coming from the graph theory area can be found in the literature concerning the characterization of a graph by its spectrum. In [10] a survey of many results regarding the spectrum of graphs are presented. In this section we review some of them remanding the reader to the literature cited in [10], [5] for a more comprehensive discussion. The second smallest eigenvalue of the Laplacian, named algebraic connectivity has emerged as a critical parameter that influences the stability and robustness properties of dynamic systems that operate over an information network. The algebraic connectivity is clearly a main object of interest, as the knowledge of convergence times for unknown networks is clearly a great added value for control and identification problems on networks. In [11], [12], [13] and therein references, the shape of the spectrum of a given network is used to characterized its topology. For instance the shape of the spectrum of a random graph is different from the one of a scale free or a small world network. The eigenvalues of a regular lattice can be worked out analytically and so if a team of agents has to fly following that shape using decentralized algorithms, we can identify whether that shape has actually been achieved by looking at the spectrum; with our approach it becomes an information locally available. In [14] is studied how the Laplacian spectral radius changes when a graph changes by adding some edges, or removing some edges from one vertex to another. From the spectrum of a network we can possibly estimate the number of agents if such number is not know a priori, for instance because many of them have been disabled after long operations.
Such number is clearly greater or equal to the number of eigenvalues. Furthermore we have the following two formulas that if inverted allow us to estimate this number if the max and min degree on the network are known (or if the number of agents is known, they can estimate the max and min degree): n n min ∆i , and λn ≥ max ∆i . n−1 i n−1 i Finally, a major issue in telecommunication networks is the time delay. In a network of agents, the time delay is greatly influenced by the number of “hops” a packet must do before reaching a destination. In general the worst case time delay is bounded by the longest path in the network between any pair of points, namely the diameter D of the graph. Indeed, this parameter can be estimated by the spectrum of the Laplacian being r 4 maxi ∆i , and D ≤ lg2 n 2 . D≥ nλ2 λ2 λ2 ≤
If such information is available, together with the algebraic connectivity, the maximum time delay can be estimated online on the network and so it can be managed by algorithms properly designed. V. O BSERVABILITY OF THE SYSTEM MODES The observability and controllability of the graph Laplacian taking as output the state of an agent and at most the one of its neighbors, has been studied in [9], [15]. Regarding observability, the authors of [9] develop a framework to study the observability of L based on the graph topology. In particular, they find out that equitable partitions are a relevant topological feature that affects observability. Furthermore, their result is relevant to the case in which we want to build a network that is observable. Moreover, while topological features can be checked possibly locally, the observability of the system can be checked only if the whole topology is known by each agent, that in the case of distributed large scale systems with switching topology is an infeasible requirement. Our work in this paper can be envisioned as a decentralized way to effectively analyze observability, and by duality controllability, by looking at how the observable modes change during topology changes. In fact, if a network implements the local updating rule in eq. (1) the states of all the agents oscillate at the frequencies given by the eigenvalues of L. If system (2) is not observable with respect to a given output matrix then its outputs oscillate only at the frequencies given by the observable modes of L. The following theorem enables us to conclude that the observability properties of system (2) are strictly related to the observability properties of the graph Laplacian, and so to the results regarding observability in [9]. Theorem 4: Let A be an n × n symmetric matrix and C be a p × n matrix. Let · ¸ · ¸ 0 −A C 0 ˆ ˆ A= and C = . A 0 0 C
ˆ C) ˆ is observable iff (A, C) is observable. (A, Proof: The observability matrix of the augmented systems is Cˆ Cˆ Aˆ 2 ˆ= O Cˆ Aˆ .. . Cˆ Aˆ2n−1 and one can readily verify that for k ∈ N it holds · ¸ CA2k 0 2k k ˆ ˆ C A = (−1) 0 CA2k and
· ˆ2k+1
Cˆ A
k
= (−1)
0 −CA2k+1 CA2k+1 0
¸ .
Hence by simple row permutation (and multiplication by −1 if required) it holds O 0 n 0 ˆ = rank OA = 2 rank O rank O 0 O 0 OAn where O(A, C) is the observability matrix of (A, C). ˆ C) ˆ is observable iff (A, C) is observable. Thus, it follows that (A, ¤ The above theorem points out that, even if the system is not observable from a single agent perspective, it will always be observable if matrix C is the identity matrix, i.e., if we consider all the information that agents locally retrieve. Moreover, even if each agent cannot observe all the eigenvalues in a decentralized way, a specific consensus algorithm can be implemented on certain particularly significant eigenvalues, e.g., the largest one, or the second smallest one. This opens up the scenario of consensus on the eigenvalues. VI. I MPLEMENTATION
ISSUES AND SIMULATIONS
In order to corroborate the mathematical results, several simulations have been performed by exploiting a framework developed by the authors using Matlab. In this framework the RungeKutta method for the approximation of solutions of ordinary differential equations has been adopted for the dynamic of the linear system described in eq. (2). Indeed, Runge-Kutta methods can be specified with respect to the order of derivative to be considered [16]. In the proposed scenario, the 4th Order Method (RK4) has been adopted as a good compromise between accuracy of solution approximation and computational overhead. It is worthy to mention that the proposed algorithm has been implemented in a fully decentralized fashion, i.e., each agent uses only information coming from its neighborhood.
In the developed framework all agents send and receive information simultaneously. Note that, this does not effect the correctness of the theoretical analysis proposed before. On the other hand, in a real scenario, the proposed algorithm could be implemented by adopting any channel synchronization technique for parallel computing coming from the computer science field, e.g., system of barriers [17]. A technical discussion concerning the distributed implementation of the Runge-Kutta method along with the implementation of the proper channel synchronization technique will be object of a future paper. In the following, simulation results for two different network topologies involving respectively 6 agents and 20 agents are given. For sake of visualization, in both cases the embedding has been obtained by using an algorithm which attempts to embed the topology graph in the plane so that the graph-theoretic distance between vertices matches the Euclidean distance. With respect to the algorithm implementation, a particular attention should be paid to the setting regarding the FFT algorithm. In particular, three aspects must be carefully taken into account: the sampling frequency fs , the frequency resolution ∆f and the choice of the windowing function. Note that, for sake of simplicity the sampling time for the Runge-Kutta method has been chosen equal to the sampling time for the FFT algorithm. As far as the sampling frequency fs is concerned, according to the Nyquist-Shannon sampling theorem, the sampling rate must exceed 2B samples per second, where B is the highest frequency in the original signal. Now, as the highest frequency is related to the highest eigenvalue of the Laplacian matrix, the following relationship holds: λmax . π Moreover, by exploiting the Gershgorin disc theorem [2], the previous relationship becomes: fs ≥
2 ∆max π which highlights an interesting correspondence between the sampling frequency of the FFT and the maximum node degree of the graph. Indeed, this is an important result as it leads to a twofold consideration: • a proper estimation of the sampling frequency fs is always possible for a connected graph; • the algorithms scales well with the size of the network. The first consideration gives a way to minimize the computational demand for the FFT algorithm, while the second consideration underlines the usability of the algorithm regardless of the size of the graph. Note that, if the graph is connected, a global knowledge of the highest degree ∆max is always possible simply by performing a max-consensus algorithm [18]. As far as the frequency resolution ∆f is concerned, according to the FFT formulation, the following relationship holds: fs ≥
∆f =
fs M
where M is the number of samples to be recorded. Therefore, once the sampling rate fs is fixed according to the bandwidth of the system (λmax ), the resolution of the frequency spectrum is just a function of the number of samples recorded. As far as the windowing function is concerned, it must be recalled that FFT based measurements are subject to errors from an effect known as leakage. This effect occurs anytime the FFT is computed from of a block of data which is not periodic. Leakage results in the signal energy smearing out over a wide frequency range in the FFT when it should be in a narrow frequency range. To correct this problem appropriate windowing functions must be applied. Indeed, this is the case for the proposed algorithm where a node record M samples with no guarantee of having a periodic block of data. Note that, even though the leakage effect can be significantly reduced by applying a windowing function, it cannot be completely eliminated. In the proposed simulations, the Hamming windowing function has been applied [19]. Fig. 1 shows a possible embedding of the first network topology involving 6 agents. 1
2 4
5
6
3
Fig. 1.
Network topology with 6 agents.
Fig. 2 shows the related spectrum observed by the node with ID = 1 with respect to the output associated to the state variable z1 (t). In particular, it can be noticed that the Fourier transform has a dc component equal to zero. This is obtained according to Theorem 3 by having each agent i initializing its xi = 0. Moreover, the nested box in Fig. 2, gives a more detailed view of the peaks. Indeed, these are exactly all the eigenvalues of the Laplacian matrix associated to this network topology (neglecting the structural eigenvalue λ1 = 0): eig(L) = [0, 0.88, 1.45, 2.53, 3.86, 5.36]. In addition, as previously discussed, a leakage effect is experienced due to the non periodic nature of the block of the data recorded. Fig. 3 shows the second network topology involving 20 agents. Fig. 4 shows the related spectrum observed by the node with ID = 3 with respect to the output associated to the state variable z3 (t). In this case it can be noticed that, in order to recognize all the peaks, a higher resolution is required for the FFT algorithm. This implies that a higher number of samples M
1 0.4
0.9
0.35
0.8
0.3 0.7 0.25 0.6 0.2 0.5
0.15
0.4
0.1
0.3
0.05 0
0.2
1
2
3 [rad/sec]
4
5
6
0.1 0
0
50
100
150
[rad/sec]
Fig. 2. Spectrum of the dynamic matrix describing the first network topology composed of 6 agents computed by the agent with ID = 1 with respect to the output associated to the state variable z1 (t). Eigenvalues of the Laplacian matrix are: eig(L) = [0, 0.88, 1.45, 2.53, 3.86, 5.36].
must be recorded. Also in this case, the nested box in Fig. 4, gives a more detailed view of the peaks highlighting again the equivalence with the eigenvalues of the Laplacian matrix associated to this network topology (neglecting the structural eigenvalue λ1 = 0): eig(L) = [0, 1.63, 2.11, 2.75, 3.62, 4.09, 4.26, 4.75, 5.10, 5.75, 6.52, 6.74, 7.37, 7.63, 8.30, 8.39, 9.32, 9.69, 10.75, 11.18]. So far, two possible network topologies have been considered and related spectrums have been analyzed. In the following, a switching topology for a network composed of 6 agents is investigated. Fig. 5 depicts the topology variation over time. In detail, starting from the topology depicted in Fig. 5-a, a few connections among agents are dropped and a few new connections are created over time in such a way to reach the ring topology given in Fig. 5-d. Fig. 6 shows how the spectrum varies over time according to the topology variation, with respect to the output z1 (t) observed by the agent with ID = 1. In particular, besides the dc component which is null according to Theorem 3, 5 peaks are observed in the starting topology (Fig. 6-a). After the first and second variations happen, it can be observed how the number of peaks remains equal to 5 while their location change in frequency according to the variation of the eigenvalues associated to the related Laplacian graphs (Fig. 6-b and Fig. 6-c). A different scenario is obtained once the ring topology is reached as only 3 peaks are recognized (Fig. 6-d). Indeed, the related Laplacian graph has two eigenvalues with algebraic multiplicity equal to 2, namely λ1 = 1 and λ2 = 3. Finally, a transition step should be noticed in the spectrogram for each topology variation where peaks are not clearly defined. Indeed, this can be explained by the fact that during a topology transition the block of data used for the FFT algorithm is composed of data related to two different topologies. This information, as previously stated,
18
16
12
9 14 11
3 7 8 13
15 6
10
17
2 20
4 19
5
Fig. 3.
1
Network with 20 agents.
could be effectively used as a reliable indicator to recognize when a variation happens. To conclude, it is worthy to mention that the system described by eq. (2) does not model a physical system and therefore it is not affected by any kind of noise. Indeed, it is a numerical implementation of the solution of an ordinary differential equation. VII. C ONCLUSIONS In this paper a novel decentralized algorithm to estimate the Laplacian spectrum of a network has been proposed. The key idea of the algorithm is to provide a local interaction rule among agents whose goal is to make their state oscillate at all and only at the frequencies corresponding to the eigenvalues of the network topology. In this way, the problem of decentralized eigenvalues identification is mapped into a problem of signal processing that each agent can efficiently and independently solve by applying the Fast Fourier Transform algorithm to its state trajectory. The algorithm convergence properties have been formally described and its approximation and practical implementation from a digital signal processing perspective have been discussed. Simulations have been shown to corroborate the analytical results. Future work, apart from an
1.8
1.6
0.5 0.45 0.4
1.4 0.35 1.2
1
0.3 0.25 0.2
0.8
0.6
0.15 0.1 0.05
0.4 0
2
3
4
5
0.2
0 0
20
40
60
6
7 [rad/sec]
80 [rad/sec]
100
8
9
120
10
140
11
12
160
Fig. 4. Spectrum of the dynamic matrix describing the first network topology composed of 6 agents computed by the agent with ID = 3 with respect to the output associated to the state variable z3 (t).
1
1
b)
a)
1
c)
Fig. 5.
1
d)
Topology variation with respect to time for a network composed of 6 agents.
implementation of the algorithm on a real team of networked robots, will be focused on the investigation of novel coordination and estimation algorithms that use the information about the eigenvalues of a network now available with a decentralized and thus scalable algorithm.
0
a)
10 20
Time
30
b)
40 50
c) 60 70
d)
80
0
1
2
3
4
5
6
rad/sec Fig. 6. Spectrogram of the time varying topology shown in Fig. 5 computed by the agent with ID = 1 with respect to the output associated to the state variable z1 (t).
R EFERENCES [1] V. Blondel, J. Hendrickx, A. Olshevsky, and J. Tsitsiklis, “Convergence in multiagent coordination, consensus, and flocking,” in CDC05, Seville, Spain, Dec. 2005, pp. 2996–3000. [2] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. on Automatic Control, vol. 49, pp. 1520–1533, 2004. [3] R. Olfati-Saber, “Flocking for multi-agent dynamic system: Algorithms and theory,” IEEE Trans. on Automatic Control, vol. 51, pp. 401–420, 2006. [4] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Trans. Autom. Control, vol. 48, pp. 988 –1001, 2003. [5] C. Godsil and G. Royle., “Algebraic graph theory,” Springer, 2001. [6] J. Cortes, S. Martinez, and F. Bullo, “Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions,” Automatic Control, IEEE Transactions on, vol. 51, no. 8, pp. 1289–1298, 2006. [7] A. Muhammad and M. Egerstedt, “Connectivity graphs as models of local interactions,” CDC04, vol. 1, pp. 124–129, 2004. [8] X. Lin and S. Boyd, “Fast linear iterations for distributed averaging,” Systems and Control Letters, vol. 53, pp. 65–78, 2004. [9] M. Ji and M. Egerstedt, “Observability and estimation in distributed sensor networks,” CDC07, pp. 4221–4226, Dec. 2007. [10] B. Mohar, “The laplacian spectrum of graphs,” in Graph Theory, Combinatorics, and Applications. Wiley, 1991, pp. 871–898. [11] R. Grone, R. Merris, and V. S. Sunder, “The laplacian spectrum of a graph,” SIAM Journal on Matrix Analysis and Applications, vol. 11, no. 2, pp. 218–238, 1990. [12] R. Grone and R. Merris, “The laplacian spectrum of a graph ii,” SIAM J. Discret. Math., vol. 7, no. 2, pp. 221–229, 1994. [13] J. V. D. Heuvel, “Using laplacian eigenvalues and eigenvectors in the analysis of frequency assignment problems,” 2001. [14] J.-M. Guo, “The laplacian spectral radius of a graph under perturbation,” Comput. Math. Appl., vol. 54, no. 5, pp. 709–720, 2007. [15] S. Martini, M. Egerstedt, and A. Bicchi, “Controllability decompositions of networked systems through quotient graphs,” CDC08, Dec. 2008.
[16] J. C. Butcher, The numerical analysis of ordinary differential equations: Runge-Kutta and general linear methods. New York, NY, USA: Wiley-Interscience, 1987. [17] P. B. Hansen, “An evaluation of the message-passing interface,” SIGPLAN Not., vol. 33, no. 3, pp. 65–72, 1998. [18] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” Automatic Control, IEEE Transactions on, vol. 49, no. 9, pp. 1520–1533, 2004. [19] A. Oppenheim and R. Schafer, Discrete-Time Signal Processing. Prentice-Hall, 1989, pp. 447–448.
