PAGE 1
CONSENSUS ALGORITMS FOR FLOCKING AND SYNCHRONIZATION by ASHOR M. QBLIA B.S. G aryounis U niversity 1995 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master of Science Electrical Engineering 201 4
PAGE 2
ii This thesis for the Master of Science degree by Ashor M. Qblia has been approved for the Electrical Engineering Program by Miloje Radenkovic Chair Hamid Fardi Tim Lei April 1 8 201 4
PAGE 3
iii Qblia Ashor M ( M.S. Electrical Engineering) Consensus Algorithms for Flocking and Synchronization Thesis directed by Professor Miloje Radenkovic ABSTRACT Recently consensus problems ha ve attracted many researchers in different areas of interest such as biological systems, sensor networks, and multi agent coordinati on. Flocking behavior of mu l ti agent system is one of the problems that can be solved using consensus algorithms. Synchronization of coupled oscillators is a related problem to consensus which can be achiev ed by applying a consensus protocol. The focus of this thesis is on the flocking and synchronization problems. A flocking model pr oposed by Cucker and Smale has been introduced and simulated. New consensus algorithms are presented to solve the problem of flock forma tion of multi agent system and the problem of phase synchronization of coupled oscillators. These algorithms are based on the adaptive estimation techniques in which the parameters of the consensus protocols are estimated to achieve convergence and stability of the system. Different communication graph topologies are used to simulate these algorithms a flock and the phase synchronization of coupled oscillators. The form and content of this abstract are approved. I recommend its publication. Approved: Dr. Miloje Radenkovic
PAGE 4
iv DEDICATION I dedicate this thesis to my precious mother, dear sister and brothers for their support, prayers, and encouragement. I also dedicate this thesis to my lovely wife, son, and daughters for their help, support, and understandi ng
PAGE 5
v ACKNOWLEDGMENTS First, thanks to ALLAH who gives me all the help to be able to finish this thesis. T hanks to my advisor Prof. Miloje Radenkovic for his contribution in this work, advice, and suggestions throughout the work of this thesis.
PAGE 6
vi TABLE OF CONTENTS CHAPTER I. INTRODUCTION ................................ ................................ ................................ ........... 1 Thesis Objectives ................................ ................................ ................................ .... 2 Thesis Orientation ................................ ................................ ................................ ... 2 II. GRAPH THEORY ................................ ................................ ................................ ........ 4 Graph Definition ................................ ................................ ................................ .... 5 Graph Connectivity ................................ ................................ ................................ 6 Directed and Undirected Graphs ................................ ................................ ............ 8 Adjacency Incidence, Degree, and Laplacian Matrices ................................ ........ 9 III. CONSENSUS THEORY ................................ ................................ ........................... 11 Consensus Definition ................................ ................................ ........................... 11 Continuous time Consensus ................................ ................................ ................. 11 Discrete time Consensus ................................ ................................ ...................... 1 3 Extended Consensus Protocols ................................ ................................ ............ 13 Consensus with Communication Time Delay ................................ ................ 1 4 Consensus for Switching Topology Networks ................................ .............. 14 Dou ble Integrator Consensus ................................ ................................ ......... 14 Consensus Applications ................................ ................................ ....................... 1 5 Rendezvous Problem ................................ ................................ ..................... 1 5 Formation Control ................................ ................................ .......................... 1 6 Sensor Networks ................................ ................................ ............................ 1 6 Flock Formation ................................ ................................ ............................. 1 7 Synchronization of Coupled Oscillators ................................ ....................... 1 7
PAGE 7
vii IV. FLOCK FORMATION ................................ ................................ .............................. 1 8 Literature Review ................................ ................................ ................................ 1 8 Cucker and Smale Flocking Model ................................ ................................ ...... 1 9 Simulation Example of Cucker and Smale Model ................................ ......... 21 Adaptive Flocking Algorithm ................................ ................................ .............. 2 4 Five A gents S ystem with C omplete Graph ................................ .................... 2 6 Ten Agents System with Undirected Graph ................................ .................. 2 8 Five Agents System with Strongly Connected Directed Graph ..................... 30 F ive Agents System with not Strongly Connected Directed Graph .............. 3 1 Five Agents System with Directed Graph without a Spanning Tree ............. 3 3 V. RELATED TO SYNCHRONIZATION OF COUPLED OSCILLATORS AND THE KURAMOTO MODEL ................................ ................................ ................................ .... 36 Adaptive Phase Synchronization ................................ ................................ ......... 3 7 Five Oscillators System with Complete Graph ................................ .............. 3 8 Five oscillators System with Strongly Connected Directed Graph ............... 3 9 Five Agents System with not Strongly Connected Directed Graph .............. 40 Five Oscillators System with Directed Graph without a Spanning Tree ....... 4 1 VI. CONCL U SION ................................ ................................ ................................ .......... 43 REFERENCES ................................ ................................ ................................ ................ 4 4 APPENDIX ................................ ................................ ................................ ...................... 4 7 Simulation Codes ................................ ................................ ........................... 4 7
PAGE 8
viii LIST OF FIGURES Figure 2 .1 The K nigsber g bridges ................................ ................................ ............................... 4 2 .2 A graph representing the Knigsberg bridges problem ................................ ................ 5 2 .3 A graph of three agents ................................ ................................ ................................ 6 2 .4 Connected graph and disconnected graph ................................ ................................ .... 7 2 .5 Spanning tree of a graph ................................ ................................ .............................. 7 2 .6 Undirected graph and directed graph ................................ ................................ ........... 8 2 .7 A graph as an example to show graph matrices ................................ ........................... 9 4 1 The consensus of the five birds velocities ................................ ................................ 22 4 2 The consensus of the velocities as components versus iteration ............................... 2 2 4 3 ................................ ................................ 2 3 4 4 The positions and directions of the five bird s in 3 dimension s ................................ .. 2 4 4 5 A complete graph of f ive agents ................................ ................................ ................. 2 6 4 6 The v elocity consensus for the complete graph ................................ ......................... 2 7 4 7 Positions and directions of all agents at different iterations ................................ ....... 2 7 4 8 Un directed connected graph of t en agents ................................ ................................ .. 2 8 4 9 The v elocity consensus for the undirected graph ................................ ........................ 29 4 10 Positions and directions of all agents at different iterations ................................ .... 29 4 11 S trongly connected directed graph of f ive agents ................................ ..................... 3 0 4 12 The v elocity consensus for the strongly connected directed graph ......................... 3 0 4 13 Positions and directions of all agents at different iterations ................................ ..... 3 1 4 14 D irected graph not strongly connected of f ive agents ................................ .............. 3 1 4 15 The v elocity consensus for the directed graph not strongly connected ................... 3 2
PAGE 9
ix 4 16 Positions and directions of all agents at different iterations ................................ .... 33 4 1 7 D irected graph without a spanning tree of f ive agents ................................ ............. 3 4 4 1 8 The v elocity consensus for the directed graph without a spanning tree ................... 3 4 4.1 9 Positions and directions of all agents at different iterations ................................ ..... 3 5 5.1 Five oscillators with complete graph ................................ ................................ ......... 3 8 5 .2 The p hase synchronization for the complete graph ................................ ................... 3 9 5 .3 Five oscillators with strongly connected directed graph ................................ ............. 3 9 5 .4 The p hase synchronization for the strongly connected directed graph ...................... 40 5 .5 Five oscillators with directed graph not strongly connected ................................ ...... 40 5 .6 The p hase synchronization for the directed graph not strongly connected ................ 4 1 5 .7 Five oscillators with no spanning tree directed graph ................................ ................ 4 1 5 .8 The p hase synchronization for the directed graph without a spanning tree ................ 4 2
PAGE 10
1 CHAPTER I INTRODUCTION The centralized control or the conventional control refer s to control systems in which a central control unit monitors, communicates, and controls all elements through a communication network, which needs high level of connectivity and energy due to the needs of a communication link between each element and the c entral control unit [ 1 ] In contrast, cooperative control for multi agent system s use s local controllers on each agent Each agent communicate s with its neighbors and control s status. This approach gives reliable communication links but more complicated network structure. In recent decades, cooperative control for multi agent system s such as synchronization, consensus, swarming, and flocking has attracted many researchers because of their broad applications in biological systems, sensor networks, unmanned air vehicle formations, robotic cooperation teams, and mobile communication systems [1] Cooperative control studies multi agent dynamic system s connected through a communication network represented by different graph topologies The graph shows the information flow between the agents. In c ooperative systems, there are algorithms or protocols to control each agent to reach synchronized behavior with the states of all other agents called consensus In these protocols each agent uses the available information from its neighbors according to the graph topology [ 2 ] In this thesis, some of these consensus and synchronization protocols are presented and simulated to confirm the convergence of a group of agents to a common velocity in a
PAGE 11
2 flock or a common phase in a group of oscillators The simulation is done fo r different communication graph topologies and given the expected results. Thesis Objective s A set of objectives was specified to fulfill the goals of this thesis; those objectives are as the following: 1. Introducing and s imulat ing the flock behavior modeled by Cucker and Smale in [ 3 ] 2. Introduc ing a new adaptive algorithm proposed by Radenkovic and Bose in [4] This algorithm estimate s the adjacency matrix entries of a flock model 3. S imulat ing the algorithm mentioned in 2 to confirm the convergence of a group of agents velocities in a flock with different communication network topologies 4. Introduc ing a new adaptive algorithm proposed by Radenkovic in [5] This algorithm estimate s the adjacency matrix entries of a synchronization protocol based on the Kuramoto model for synchronizing the phase of coupled oscillators. 5. S imulat ing the algorithm mentioned in 4 to confirm the phase synchronization of a group of oscillators with different communication network topologies. Thesis Orientation This thesis is organized as follows: a background about the graph theory in chapter 2 is provided including the definition of a graph going through some terms that are important in understanding consensus theory which will be introduced in chapter 3 This chapter start s with the definition of consensus and
PAGE 12
3 then provid es some details about the most comm on protocols in both continuous and discrete time, a brief describtion of some more complicated consensus protocols which are used in different applications The chapter ends with a brief describtion of some consensus applications. Chapter 4 discusses flock formation as one of the applications of consensus This chapter start s with a definition of flocks and a literature review and then present s Cucker and Smale model that describ es the evolution of a flock A simulation of the model is provided T h is chapter ends with presenting a new adaptive algorithm to estimate the adjacency matrix entries of Cucker and Smale flocking model and analyzing the algorithm properties via simulation experiments. In chapter 5, the synchronization of couple d oscillators which is related to consensus problems is introduced A new adaptive algorithm to solve the phase synchronization of coupled oscillators is presented and analyzed by means of simulations A conclusion is driven in c hapter 6.
PAGE 13
4 CHAPTER II GRAPH THEORY The K nigsberg Bridge Problem is the birth of graph theory as considered by many scientists. The city of Knigsberg was located on the Pregel river in Prussia, and the river divided the city into four separate regions (W, X, Y, and Z) which were 7) ; as shown in Figure 2.1 The problem states that is it possible to start a trip through the city starting from one region crossing each bridge exactly once and back to the starting region ? [ 6 ] [ 7 ] [ 8 ] Figure 2.1 The Knigsberg b ridges T he above figure is dr a wn as points for the regions and lines for the br i d g es as in the model shown in Figure 2.2 I t is clear that it needs an even number of lines at each point to cross each line exactly once in a trip starting from a point and return to the same point This i s not the case for Knigsberg bri dge problem [ 8 ]
PAGE 14
5 F igure 2.2 A graph representing t he Knigsberg bridges p roblem The Swiss mathematician Leonhard Euler (1707 1783) has introduced th e first theorem in graph theory which is, for a given graph; one can start from an arbitrary vertex, transverse every edge exactly once, and come back to the original vertex, if and only if every vertex has an even degree T he vertex, edge, and degree of vert ic es will be defined in the next section s This path in the graph, if o ne exists, is referred to as the Eulerian cycle [ 9 ] Graph Definition A graph G is a triple consisting of a vertex set V(G), an edge set E(G), and a relation that associates with each edge two vertices (not necessarily distinct) called its endpoints [ 8 ] Sometimes, vertices are called nodes, and edges are lines or arcs. A s an example, the graph of Knigsberg Bridge Problem can be expressed as the following G = (V, E), E (V x V) where V(G)={W, X, Y, Z}, and E(G)={e 1 e 2 e 3 e 4 e 5 e 6 e 7 } In general, there are a lot of examples of graphs, such as the World Wide Web ( www ) which can be represented by a graph that contains all web pages as vertices and
PAGE 15
6 hyperlinks as edges S ocial networks as a graph is formed by vertices represent ing people who are connected through these networks and edges represent ing email s phone calls, instant messaging, etc [ 10 ] I n engineerin g, a graph G can represent a wireless computer network where the computers are the vertices and the wireless links among computers are the edges, or unmanned air vehicles group where vertices represent these vehicles and edges are the communication links that connect them, and so on. In this thesis the graph represents a group of agents such as a flock of birds or coupled oscillators, where these agents are the vertices and the communication links that connect them are the edges. A s an example Figure 2.3 shows three autonomous agents connected through three communication links. Figure 2.3 A graph of three agents Graph C onnectivity F or any pair of vertices in a graph V (G) if there is a path that links them as its end vertices then the graph G is connected If this is not the case, the graph is called disconnected [ 7 ] [ 9 ]. Figure 2.4 shows an example of connected and disconnected graphs v 2 v 3 v 1 e 1 e 3 e 2
PAGE 16
7 (a) Connected Graph (b) Disconnected Graph Figure 2.4 Connected g raph and d isconnected g raph The weighted graph is a graph in which a nonnegative number is assigned to each edge [7]. If each ve r t e x in a graph is connected to all vertices in the graph, this graph is called complete graph [ 11 ] A nother important term in graph connectivity is called a spanning tree of a graph. A tree is a sub graph where every pair of vertices is connected with only one edge A spanning tree of a graph is a tree in which its edges connect all the vertices of the graph [ 6 ], [ 7 ], [ 8 ] An example of a graph and one of its spanning trees is shown in Fig 2.5 Figure 2.5 Spanning t ree of a g raph 3 4 5 3 4 5 2 1 2 1 4 1 3 5 2 3 4 6 2 1 5
PAGE 17
8 Directed and Undirected Graphs The directed and undirected graphs come from the direction of information flow between vertices. In the undirected graph, the edges that connect the vertices are not directionally fixed or the edges set has unor dered edges [ 12 ] This means, there is an information flow between each two vertices in both directions T he direction from a node n i to a node n j is represented by a line with or without an arrowhead in both line ends, as shown in Figure 2.6 (a). On the other hand, in the directed graph, also referred to as the digraph, the edge that con nects two vertices is directed or ordered [ 12 ] Therefore, the information flow is in one direction only The edge direction from a node n i called the tail node to a node n j called the head node is represented by an arrowhead that always points to the head node as show in Figure 2.6 (b) (a) Undirected Graph (b) Directed Graph Figure 2.6 Undirected g raph and d irected g raph In another expression, for a graph G = ( V, E ) where and E (V x V), the graph G is undirected if, for all i, j V we have (i, j) E and (j, i) E And the graph G is directed otherwise [ 12 ] 4 1 3 5 2 1 2 3 4 5
PAGE 18
9 Adjacency, Incidence, Degree and Laplacian Matrices For a graph G with vertices set V(G) = {v 1 n } and edge s set E(G) = {e 1 e m } any two distinct vertices of the graph G are adjacent if there is an edge joining them These two vertices are then incident with such an edge [7], [8] The adjacency matrix A(G) of the graph G is n by n matrix in which its element a ij is the number of edges in G with endpoints {v i v j } [ 7 ], [ 8 ] The incidence matrix M(G) of the graph G is n by m matrix in which its element m ij is 1 if the vertex v i is an endpoint of the edge e j and 0 otherwise [ 7 ], [ 8 ] The degree of a vertex v i of G is the number of edges that link to it and can be written as deg(v i ) And the degree matrix D(G) of the graph G is n by n diagonal matrix in which its diagonal elements are deg(v) [ 7 ], [ 8 ] For a directed graph, there are in degree D in and out degree D out matrices depending on the direction of the edges that are connected to each vertex T he in and out matrices also apply for the adjacency and the incidence matrices, more details are in [ 7] [8] [9] To explain all the above terms, Figure 2.7 below shows an example for an undirected graph G with vert ices set V(G) = {a, b, c, d, e} and edge s set E(G) = {1, 2, 3, 4, 5 6 } Figure 2.7 A graph as an example to show graph matrices d e 5 3 4 c 2 b 1 a 6
PAGE 19
10 In this example, n=5 and m=6 so The adjacency matrix of the above graph is A(G) 5 x 5 = The incidence matrix is M(G) 5 x 6 = And the degree matrix is D(G) 5 x 5 = Laplacian matrix, also known as the Kirchhoff matrix, is very important in graph theory It is the difference between the degree matrix D and the adjacency matrix A L = D A Or For a connected undirected graph, the Laplacian matrix is symmetric positive semi definite. For directed graphs, the Laplacian matrix is defined using the in and out matrices as the following [ 13 ] [ 14 ] L in = D in A in L out = D out A out
PAGE 20
11 CHAPTER III CONSENSUS THEORY Consensus Definition In networks of agents consensus consensus algorithm between an agent and all of its neighbors in the network. [ 15 ] [ 16 ] Continuous time Consensus To understand the concept of consensus as in [ 1] [ 15 ] [ 17 ] [ 18 ] consider that there are n agents system represented by a graph G=(V n E n ) where V n is the vertices set and En V n x V n is the edge set, and let x i (t) is the information state of the i th agent T his information state may be agent position, velocity, oscillation phase, etc Agent i can get the state information of agent j if there is an edge between them which means that the edge (i, j) E n T his leads to a set of neighbors of the agent i let it be N i and defined by (3.1) Then, the most common continuous time consensus algorithm is (3.2) w here is the ( i, j) th entry of the system adjacency matrix A(t) = [ ] at time 0 if no communication exist s between the two nodes i and j where i, j = 1,2, . n a nd if ( i, j) E n From this protocol the adjacency
PAGE 21
12 matrix represents the communication network among all agents in the system The matrix entries a ij are the weights assigned to the edges of the graph G [ 1] [ 14 ] [ 17 ] The consensus algorithm in (3 .2) can be written in matrix form as (3.3) where x = [x 1 x 2 . ., x n ] T and L =[l ij ] is the Laplacian matrix of the graph defined by From (3.2), the information state of each agent is driven toward the states of its neighbors. So, consensus is achieved or reached, if, for all x i (0) and all [ 1] [ 14 ] [ 17 ] This means that all the nodes or states approach to a common value of interest. C onsensus is achieved if and only if either the directed graph has a directed spanning tree or the undirected graph is connected [ 17 ]. Furthermore, this common value is the weighted average of the initial conditions x i (0) for undirected strongly connected graphs In this case, it is called Average Consensus Algorithm [ 16 ]. It is also average consensus, if and only if the directed graph is balanced. Balanced directed graph is a graph in which the total weight of edges enter ing a node and leaving the same node is equal for all node s in the graph in mathematical form [ 16 ] [ 19 ]. The consensus protocol is called static or time invariant, if is constant, and called dynamic or time varying if is time varying.
PAGE 22
13 Discrete time Consensus For discrete time consensus, the information state is updated using a difference equation and the most common discrete time consensus algorithm is (3.4) where k is the discrete time index, and d ij [k] is the (i,j) entry of a row stochastic matrix D=[ d ij ] nxn where the row stochastic matrix entries are defined as the following: d ii [k] > 0 for all d ij [k] > 0 for all if the information flows from agent j to agent i d ij [k] = 0 otherwise [ 17 ] Algorithm (3.4) shows that the information state of each agent is updated to the weighted average of its current state and the current states of its neighbors. This algorithm can be written in matrix form as (3.5) T he same as in continuous time, consensus is achieved or reached, if, for all x i [0] and all [ 14 ], [ 17 ] More extended consensus protocols have been proposed and their convergence has been analyzed by researchers Extended Consensus Protocols The most common simple consensus protocol has been extended to various forms to meet the proper application used for A brief description of some of them is in the following sections.
PAGE 23
14 Consensus with C ommunication D elays This is the case when the time delay of the communication channels needs to be considered, and the continuous time consensus protocol is (3.6) where is the time delay for information exchange between agents i and j including the message transmission time and the processing time [ 16 ] [ 17 ]. For undirected graph and balanced directed graph, average consensus is still reached if and only if max max 16 ], [ 19 ]. Consensus for Switching T opology N etworks In general networks of moving agents are dynamically changed in topology by time because of communication links failure This failure is subject to disturbances, obstacles between agents, and/or communication range limitations. Moreover, new links between nearby ag ents are created if the agents come to an effective range of detection with respect to each other This network is called a switching topology network [ 14 ] [ 16 ]. In this case consensus is achieved asymptotically if the union of the information exchange graphs for the agents is connected most of the time as the system evolves [ 14 ] Double I ntegrator C onsensus The protocol in (3.2) is called single integrator consensus protocol (First order consensus protocol), and is extended to a double integrator consensus protocol or a second order consensus protocol which is given by (3.7)
PAGE 24
15 w here > 0 is the coupling strength between the information state derivatives T his protocol shows that both and are exchanged between agents. The consensus for (3.7) can be reached if the directed graph has a spanning tree and the coupling strength is sufficiently large [ 17 ] [ 21 ]. Consensus Applications In this section, a brief description of some consensus algorithms applications is provided. Flocking and synchronizations of coupled oscillators are discussed in more details in the following chapters. Rendezvous Problem The rendezvous problem for a group of vehicle s in a network is to meet at a time or a location determined by the group negotiation. Consensus algorithms can be used to perform the negotiation in a way that is robust to environmental disturbances [17]. To explain this, consider a group of vehicles pla nned to arrive at the same time to a specified location known to all vehicles. Because the rendezvous time is not given and may need to be adjusted in a response to environmental disturbances, the group needs to reach consensus on the rendezvous time. To perform this, each vehicle initiates an information state x i that represents the i th arriving time to the location So, x i (0) is the time in which each vehicle is able to rendezvous with the group. T hen e ach vehicle communicates with its neighbo rs and negotiates a group arrival time using the consensus algorithm given in (3.2) In other words, each vehicle adjusts its information state to rendezvous at the negotiated arrival time. If environmental conditions change d all vehicles would reset their information state and thus cause the negotiation process to start again Note that if the communication topology is fixed and the gains a ij in (3.2) are
PAGE 25
16 time invariant, then the rendezvous time is a linear combination of the initial informati on states [17] The rendezvous problem for a group of mobile autonomous vehicles is studied in [ 2 2 ], [2 3 ], where synchronous and asynchronous cases are considered. Formation Control Formation control for a group of mobile agents is to achieve and maintain a pre designed geometric shape. I n the centralized control, all agents know the desired shape and location of the formation. On the other hand, in the decentralized formation control problem, each agent knows the desired formation shap e, but the location of the formation needs to be negotiated among the agents The center of the formation for this problem is the information state. Each agent initiates its information state by proposing a proper formation center. The consensus algorithm is then used by the agents to negotiate a formation center known to all agents [17] In [ 2 4 ], a method for decentralized information exchange between vehicles was proposed Formation stabilization for multiple unicycles is studied in [ 2 5 ] using a consensus algorithm to achieve point, line, and general formation patterns. Sensor N etworks One of the applications in s ensor networks is the surveillance and monitoring of an environment, and collecting scientific data from distributed sources for environmental modeling and protection [26] The relation to consensus here is to develop a distributed algorithm that allows the nodes of a sensor network to track the average of all of their measurements. T his problem is referred as dynamic average consensus [2 6 ] In [2 6 ], a distributed low pass filter is develop ed to solve this tracking problem via reaching an
PAGE 26
17 average consensus. In [27], a scheme for asynchronous distributed sensor fusion based on average cons ensus was developed Flock Formation A group of mobile agents uses a consensus algorithm to align their velocities and avoid collisions to form a flock. To reach a common velocity, it needs each mobile agent to negotiate and adjust its information s tates with its neighbors through a consensus algorithm [14], [16]. More details are presented in the next chapter. Synchronization of C oupled O scillators Synchronization phenomena in systems of coupled oscillators are related to consensus problems. The Kuramoto model of coupled oscillators assumes full connectivity of the network In other words, a complete graph connection between the oscillators exists T his can be generalized to any connected graph for information exchange S ynchronization is achieved if the coupling is above a critical value [17]. More details are presented in chapter 5.
PAGE 27
18 CHAPTER I V FLOCK FORMATION Flocking is a form of collective be havior of a large number of interacting agents with a common group objective [ 18 ]. During the last few decades, flocking, swarming, and schooling in groups of agents with local interactions have received considerable attention by scientists in the fields o f animal behavior, physics, biophysics, social sciences, and computer science. Examples of these groups cover flocks of birds, schools of fish, herds of land animals, and so on. These groups are examples of self organized networks of mobile agents with loc al coordination [ 18 ] [ 2 8 ] [ 2 9 ]. Members of these groups are referred as agents [ 18 ]. Literature Review In 1987, Reynolds introduced a computer model to simulate a flock using three author) to form a flock The three flocking rules of Reynolds are : 1) Flock Centering: attempt to stay close to nearby flockmates; 2) Collision Avoidance: avoid collisions with nearby flockmates; 3) Velocity Matching: attempt to match velocity with nearby flockmates. W ith these rules the computer animation shows the agents moving in flocks and avoiding collisions [ 2 8 ] These rules are also known later as Cohesion, Separation, and Alignment respectively. In 1995, Vicsek et al. focus e d on the alignment of s elf driven particle s with a constant absolute velocity and provide d a flocking model in which particles adjust their [ 30 ] Later, some mo dels of
PAGE 28
19 swarms were proposed by Mogilner and Edelstein Keshet in 1999 [ 31 ] Levine et al. in 200 0 [ 32 ] and Topaz and Bertozzi in 2004 [ 33 ] Tanner et al. in 2003 modeled a stable flocking motion for mobile agents using local controllers or a set of control laws in a fixed and dynamic communication network t opologies that allow the exchange of state information between interconnected agents [ 34 ], [ 35 ] Recently, the considerable attention in distributed control and consensus algorithms by researchers has led the m to provide a large amount of literature Such as, in 2005, Ren and Beard showed that information consensus under dynamic topology can be reacheded if the union of the directed graphs have a spanning tree [ 21 ] In 2006, Olfati Saber proposed three algorithms and proved that migration of flocks can be performed using a peer to peer network of agents [ 18 ] Cucker and Smale in 2007, provided a flocking model and showed the convergence of the flock to a common velocity [ 3 ] This model was extended by Cucker and Dong in 2010 to avoid collision by keeping a minimum distance among agents [ 36 ] In the next section, the flocking model that was proposed by Cucker and Smale in 2007 [ 3 ] is introduced and simulated The simulation codes are shown in appendix A. Cucker and Smale Flocking Model Cucker and Smale based the i r model on the postulation that every bird adjusts its velocity by adding to it a weighted average of the differences of its velocity with those of the other birds. The following consensus protocol represents this. At time t N and for bi rd i, where (4.1) where is the velocity of the i th bird at time t
PAGE 29
20 is the velocity of the i th bird at time t+1 is the velocity of the j th neighbor of the i th bird { } is the weights used by birds to adjust their velocity which is a function of the distance between birds, and they are the N x N adjacency matrix A x elements Cucker and Smale assumed that (4.2) where is the position of the i th bird And 2 +y) (4.3) where K and are some constants. Then, from (4.2) and (4.3) (4.4) If the degree N x N matrix is D x which is a diagonal matrix whose i th diagonal entry is then, the Laplacian matrix is defined as L x = D x A x Equation (4.1) can be simplified as the following Note that and it is the same for L x B y adding the position changes of the birds, the complete system is
PAGE 30
21 (4. 5 ) (4. 6 ) From the system in (4. 5 ) and (4. 6 ) and for 0, 0 2 Cucker and Smale proved that all the birds will converge to the same velocity if and they will converge in some conditions of the initial velocity v(0) and position x(0) if Simulation Example of Cucker and Smale Model T he simulation was started assuming arbitrary initial conditions for the velocities and positions of five birds in 2 dimensions, using the equations (4.1), (4. 4 ), and (4. 5 ) which are where x i 2 v i 2 and and 1. In this case let = 0.1, =0.3, and N =5. The simulation shows that there is a consensus in the velocities, where they were converged to the average of the initial velocites of the five birds, which is 32.42. Figure 4.1 shows this consensus and the calculated average of the initial velocit ies are shown at the top of the plot. Figure 4.2 shows this convergence in 3 dimension s plot.
PAGE 31
22 Figure 4.1 The c onsensus of the 5 birds velocities Figure 4.2 The consensus of the velocit ies as components versus iteration
PAGE 32
23 In the se cond case, the same number of birds is assumed, but the initial positions and velocities are in 3 dimesions where where x i 3 v i 3 and and 1 I n this case let = 0.1, = 0.5. Figures 4.3 show s the consensus of the velocities where all birds converge to the average velocity of their initial velocities. Figure 4.3 The c onsensus of the five Figure 4.4 shows the positions and directions of the five birds in 3 dimension s In the first three iterations, the birds are heading to different directions and trying to adjust to the same direction which shown in the forth plot of the figure that shows the positions and directions at the 10th iteration The simulation codes are shown in appendix A.
PAGE 33
24 Figure 4.4 The positions and directions of the five birds in 3 dimens ions Adaptive Flocking Algorithm The algorithm that will be introduced in this section is proposed by Radenkovic and Bose in [4] An adaptive algorithm is used to estimate the consensus protocol entries instead of computing them using a mathematical model as in the equation (4.4) for Cucker and Smale model This estimation started with properly suggested initial values of the entries then the adaptive algorithm will estimate the se elements to reach consensus In this algorithm, is the estimated (i,j) th element of the adjacency matrix N is the number of agents, and Starting with the system equations
PAGE 34
25 (4.7) (4.8) Define the vectors Based on the above the consensus algorithm can be written as (4.9) The n, the following adaptive algorithm will be used to estimate (4.10) the error is the difference between the i th (4.11) where (4.12) where N i is the neighbor set defined in (3.1) and S i is the number of neighbors. The error part of (4.10) will be normalize d by dividing it by to guarantee the stability of the system Then, (4.10) becomes The algorithm in (4.7), (4.9), and (4.13) h as been simulated to analyze the consensus problem of different groups of agents with different communication graph topologies The following sections show these cases and the results. All these simulations are in 2 dimensions and the simulation codes are shown in appendix A.
PAGE 35
26 Five A gents S ystem with C omplete G raph First, we assume that the graph is complete as shown in Figure 4.5 A complete graph is defined in chapter 2 where e ach agent is connected with all other agents This is not the case in a flock of moving agents due to communication links range limitations Figure 4.5 A c omplete graph of f ive agents The case shows that if the initial values of all = 1/N, the convergence will be in one step. In this case, the number of agents N = 5, the initial values of = 1/ N =0.2, and the initial positions and velocities are arbitrary chosen Figure 4. 6 shows the convergence of the velocities of all agents to the average velocity of the initial velocities in one step This average velocity is 2.9732 which is calculated in the code and shown at the top of the plot to compare it with the converged one. Figure 4.7 shows the positions and directions of the agents at different iteration s 4 3 2 1 5
PAGE 36
27 Figure 4. 6 The velocity consensus for the complete graph Figure 4. 7 Positions and directions of all agents at different iterations In the next sections, various graphs with different topologies are used in the implementation of the adaptive algorithm to analyze it The results confirmed the expected results
PAGE 37
28 Ten Agents S ystem with Undirected Graph In this case, 10 agents are assumed to simulate mobile agents in three neighbor groups, the first two groups have three agents and the third one has four agents; the groups are connected through the agents 2, 4 and 6, 7 as show n in Figure 4. 8 The informa tion flow is in both directions T h is undirected graph is connected So, consensus can be reach ed as discussed in chapter 3. Figure 4. 8 Undirected connected graph of t en agents The i nitial positions and velocities are arbitrary chosen T he adaptive algorithm estimates the adjacency matrix entries to achieve the consensus for all agents as shown in F igure 4.9. Figure 4.10 shows the positions and directions of the agents at different iterations. 8 10 9 7 6 5 4 3 1 2
PAGE 38
29 Figure 4. 9 The velocity consensus for the undirected graph Figure 4. 10 Positions and directions of all agents at different iterations
PAGE 39
30 Five A gents S ystem with Strongly Connected D irected G raph If there is a directed path from each node to all the other nodes, the directed graph is strongly connected The following graph in Figure 4.1 1 is strongly connected. It was implemented in t he simulation and the adaptive algorithm estimated the adjacency matrix entries for consensus. Figure 4.1 1 Strongly connected directed graph of five agents The velocity consensus for arbitrary chosen initial values of positions and velocities is shown in Figure 4.12. Figure 4.1 2 The velocity consensus for the strongly connected directed graph 3 1 2 5 4
PAGE 40
31 The positions and directions of the five agents at different iterations are shown in Figure 4.13. Figure 4.1 3 Positions and directions of all agents at different iterations Five A gents S ystem with not Strongly Connected D irected G raph Figure 4.1 4 shows a directed graph with two spanning tree s with root nodes 1 and 2 note that the information flow between agent 1 and agent 2 is in both directions. This graph is not strongly connected because the nodes 3, 4, and 5 do not have directed paths to all of the other nodes. Figure 4.1 4 D irected graph not strongly connected of f ive agents 4 5 1 2 3
PAGE 41
32 Although this graph is not strongly connected, still we have a consensus. Figure 4.1 5 shows the velocity convergence to 42.1 and the average velocity of the arbitrary chosen initial velocities is 33 8133 And Figure 4.16 shows the positions and directions for the five agents at different iterations. Figure 4.1 5 The velocity consensus for the d irected g raph not strongly c onnected
PAGE 42
33 Figure 4.1 6 Positions and directions of all agents at different iterations Five Agents System with D irected Graph without a S p anning T ree For the directed graph with out a spanning tree, the agents may converge to more than one common velocities or may not converge at all. The convergence depend s on the connections and information flow among them. For the graph in Figure 4.1 7 agents 1 and 3 will converge to the velocity of agent 2 which will remain constant because it has no information received from any agent A gent 5 also has no information to converge its velocity which will let it stay in the same initial velocity A nd agent 4 will be confused between the information comes from agent 3 and agent 5 which will drive it to adjust its velocity to some value in between
PAGE 43
34 Figure 4.1 7 D irected graph without a spanning tree of f ive agents For arbitrary chosen initial positions and velocities, Figure 4.1 8 shows the convergence status of the five agents and confirms the above discussion. Figure 4 .19 shows the positions and directions of the five agents at different iterations. Figure 4.1 8 The velocity consensus for the directed graph without a spanning tree 5 4 3 2 1
PAGE 44
35 Figure 4.1 9 Positions and directions of all agents at different iterations From the above results, the simulation of the algorithm confirms th at there is a consensus of the agents for the connected graphs and shows the expectations for the last graph.
PAGE 45
36 CHAPTER V RELATION TO SYNCHRONIZATION OF COUPLED OSCILLATORS AND KURAMOTO MODEL Researchers from different fields including physics, mathematics, biology, and neuroscience had a lot of contributions in the problem of synchronization of coupled oscillators. The Kura moto model, proposed by the Japanese physicist Yoshiki Kuramoto, describes the synchronization behavior of a generalized system of interacting oscillators. For a large number of osci llators, the Kuramoto model postulates that, if the se oscillators have a s trong interact ion they will oscillat e at the same rate [ 3 2 ]. The model for n coupled oscillators is given by (5.1) where is the phase of the i th oscillator, is the natural frequency of the i th oscillator, and k is the coupling strength. There is a close relation between this model and the consensus protocol s discussed in chapter 3. The model in (5.1) considers a complete graph connection of all oscillators. This can be generaliz ed to a set of neighbors that can exchange information depending on the adjacency matrix entries This model can be written as [ 3 8 ] (5.2) In [ 3 8 ], the stability of the generalized model in (5.2) has been studied and proved that all oscillators can be synchronized if the coupling is above a critical value.
PAGE 46
37 Adaptive Phase Synchronization This section presents an adaptive algorithm for phase synchronization proposed by Radenkovic in [5] In this algorithm, w ith the assumption of a set of natural frequencies for n coupled oscillators, the adaptive algorithm gives zero phase difference among all oscillators. The syst em i n this algorithm is (5.3) where and are the estimated natural frequencies, and is defined as where S i is the number of elements in N i . Define the vectors Based on the above, the consensus algorithm can be written as (5.4) From the adaptive algorithm, the parameters will be estimated from (5.5) where > 0 is a scalar to increase the speed of convergence, and is the average phase of the neighbors oscillators.
PAGE 47
38 In th is simulation the same different cases that have been implemented in chapter 4 are used in the simulation of this algorithm and all the oscillators have been synchronized to the same phase in all the graphs except the one without a spanning tree The following sections show the results of the algorithm simulation and the simulation codes are shown in appendix A For all cases the plot represents the phase difference between the oscillator number 1 and all the other oscillators. Five O scillators System with C omplete G raph The following graph shown in Figure 5.1 represents the five coupled oscillators connection topology which is a complete graph Figure 5.1 Five oscillators with c omplete graph Figure 5. 2 shows that the phase difference between oscillator 1 and oscillators is converge d to zero. This means all oscillators are synchronized to the same phase. 4 3 2 1 5
PAGE 48
39 Figure 5. 2 The phase synchronization for the complete graph Five O scillators System with Strongly Connected D irected G raph Figure 5.3 Five oscillators with strongly connected directed graph For the strongly connected directed graph in Figure 5 3 the connection leads to phase synchronization as shown in Figure 5. 4 3 1 2 5 4
PAGE 49
40 Figure 5. 4 The phase synchronization for the strongly connected directed graph Five O scillators System with not Strongly Connected D irected G raph Figure 5.5 Five oscillators with directed graph not strongly connected T he directed graph shown in Figure 5 5 is not strongly connected and still leads to phase synchronization Figure 5. 6 shows the phase synchronizatio n 4 5 1 2 3
PAGE 50
41 Figure 5. 6 The phase synchronization for the directed graph not strongly connected Five O scillators System with D irected G raph without a S panning T ree Figure 5.7 Five oscillators with no spanning tree directed graph Because of the missing of a spanning tree in the directed graph shown in Figure 5 7 only three oscillators are synchronized as shown in Figure 5. 8 5 4 3 2 1
PAGE 51
42 Figu re 5. 8 The phase synchronization for the directed graph without a spanning tree From all the above results, the simulation of the algorithm confirms the phase synchronization for the connected graphs
PAGE 52
43 CHAPTER V CONCLUSION T his thesis has presented some consensus and synchronization algorithms with a background of graph and consensus theo r ies. These algorithms ha ve been simulated to prove that flocking and synchronization are achieved O ne of the flocking model s proposed by Cucker and Smale is introduced and simulated to show the consensus in velocity of a flock of birds. A new approach for solving consensus and synchronization problems is presented. This approach us ed an adaptive algorithm to estimate the elements of the adjacency matrix instead of using the mathematical models to compute them as in Cucker and Smale model. This new concept has been simulated The simulation has approved the expected results for velocity convergence in flocks and phase synchronization in a system of coupled oscillators. In the simulation s various communication graph topologies have been used to confirm velocity consensus and phase synchronization The complete, connected undirected, strongly connected directed and the not strongly conne cted directed graphs have reached velocity consensus and phase synchronization. The directed graph that does not have a spanning tree has not reached velocity consensus and phase synchronization. For a future work, dynamic network topologies should be considered in the simulation of the adaptive algorithms to confirm the stability of the system.
PAGE 53
44 REFERENCES multi Consensus and Synchronization in Complex Networks Springer, 2013, pp. 51 68. [2] F. L. Lewis, H. Zhang, K. Hengster Control of Multi Agent Systems Springer, 2014, pp. 23 71. IEEE Trans. Autom. Control vol. 52, no. 5, pp. 852 862, May 2007. Automatica 2013. to Control Systems Letters [ 6 ] R. Diestel, Graph theory 3rd ed. Berlin ; New York: Springer, 2005. [ 7 ] R. J. Wilson, Introduction to graph theory 3rd ed. Harlow, Essex, England: Longman, 1985. [ 8 ] D. B. West, Introduction to graph theory 2nd ed. Upper Saddle River, N.J.: Prentice Hall, 2001. [ 9 ] M. Mesbahi and M. Egerstedt, Graph theoretic methods in multiagent networks Princeton: Princeton Un iversity Press, 2010. [ 10 Notices of the AMS vol. 57, no. 6, pp. 726 732, 2010. [ 11 ] J. A. Bondy and U. S. R. Murty, Graph theory with applications London: Macmillan, 1976. [ 12 ] H. Alfagee, "Consensus algorithm in smart grid and communication networks M.S. Thesis, University of Colorado at Denver, 2013. [ 13 [ 14 ] American Control Conference 2005. Proceedings of the 2005. IEEE 2005, pp. 1859 1864.
PAGE 54
45 [ 15 ] A. Stanoev and D. Smilkov Consensus and Synchronization in Complex Networks Springer, 2013, pp. 1 22. [ 16 ] R. Olfati networked multi in Proceedings of t he IEEE vol. 95, no. 1, 2007 pp. 215 233. [ 17 ] W. Ren and R. W. Beard, Distributed consensus in multi vehicle cooperative control : theory and applications London: Springer, 2007. [ 18 ] R. Olfati agent dynamic systems: Algori thms and IEEE Trans. Autom. Control vol. 51, no. 3, pp. 401 420, Mar. 2006. [ 19 ] R. Olfati Saber and R. M. Murray. Consensus problems in networks of agents with switching topology and time delays. IEEE Transactions on Automatic Control vol. 49, no. 9, pp. 1520 1533, 2009. [ 20 ] W. Ren R. W. Bread, and E. M. Atkins cooperative IEEE Control systems magazine vol. 27, no. 2, pp. 71 82, 2007. [ 21 agent systems under IEEE Trans. Autom. Control vol. 50, no. 5, pp. 655 661, May 2005. [22] J. Lin, A. S. Morse, and B. D. O. Anderson The multi agent re ndezvous problem. Part 1: The synchronous case SIAM Journal on Control and Optimization vol. 46, no. 6 pp. 2096 2119 December 2007 [23] J. Lin, A. S. Morse, and B. D. O. Anderson The multi agent rendezvous problem. Part 2 : The synchronous case SIAM Journal on Control and Optimization vol. 46, no. 6 pp. 2 120 21 47, December 2007 [24] J. A. Fax and R M. Murray Information flow and cooperative control of vehicle formations Automatic Control, IEEE Transactions vol. 49, no. 9, pp. 1465 1476 September 2004 [25] Z. Lin, B. Francis, and M. Maggiore Necessary and sufficient graphical conditions for formation control of unicycles Automatic Control, IEEE Transactions vol. 50, no. 1 pp. 121 127 2005 [26] R Olfati Saber and J S. Shamma Consensus filters for sensor networks and distributed sensor fusion i n 4 4th IEEE Conference on Decision and Control Seville Spain 200 5, pp. 6698 6703
PAGE 55
46 [27 ] L. Xiao, S. Boyd, and S. Lall A scheme for asynchronuous distributed sensor fusion based on average consensus Fourth International Symposium on Information Processing in Sensor Networks April 2005. [ 2 8 Comp. Graphics vol. 21, pp. 25 34, 1987. [ 29 ] H. Yu and Y. International Journal of Automation and Computing vol. 3, no. 1, pp. 8 16, 2006. [ 30 ] T. Vicsek, A. Czirk E. Ben in a system of self Phys. Rev. Lett. vol. 75, pp. 1226 1229, 1995. [ 31 ] A. Mogilner and L. Edelstein J. Math. Biol. vol. 38, pp. 5 34 570, 1999. [ 32 ] H. Levine, W. J. Rappel. Self organization in systems of self propelled particles Physical Review E vol. 63, no. 2, pp. 208 211, 2001. [ 33 dimensional kinematic model for SIAM J. Appl. Math. May 2004. [ 34 ] H. G. Tanner, A. Jadbabaie, G. J. Pappas. Stable Flocking of Mobile Agents, Part I: Fixed Topology 42nd IEEE Conference on Decision and Control Maui, Hawaii USA, 2003 pp. 2010 2015. [ 35 ] H. G. Tanner, A. Jadbabaie, G. J. Pappas. Stable Flocking of Mobile Agents, Part II: Dynamic Topology 42nd IEEE Conference on Decision and Control Maui, Hawaii USA, 2003 pp. 2016 2021. [ 36 ] F. Cucker and J. IEEE Trans. Autom. Control vol. 55, no. 5, pp. 1238 1243, May 2010. [ 37 SIAM Journal on Control and Optimization vol. 50, no. 3, p p. 1616 1642, 2012. [ 38 Proc. of ACC (Boston, MA), 2004 pp. 4296 4301.
PAGE 56
47 A PPENDIX Simulation Codes T his appendix shows the MATLAB codes that have been implemented for the simulations presented in chapter 4 and chapter 5. 2 dimensional Cucker and Smale Flocking Model clear all ;close all ; clc; %the model parameters, no. of birds and iterations segma=0.1;beta=0.3;N=5;iteration=500 ; %the initial positions and velocites x=5*rand(N,1);y=10*rand(N,1); vx=10*rand(N,1);vy=5*rand(N,1); %calculating the parameter K K=((segma^(2*beta)/((N 1)*sqrt(N))) 0.1); for n=1:iteration %birds adjusting their positions for i=1:N x(i,n+1)=x( i,n)+vx(i,n); y(i,n+1)=y(i,n)+vy(i,n); end X=cat(3,x,y); for i=1:N sum_x=0;sum_y=0; for j=1:N %the adjacency matrix elements a(i,j)=K/(segma^2+(X(i,n,1) X(j,n,1))^2+(X(i,n,2) X(j,n,2))^2)^beta; %birds adjusting their velocities sum_x=sum_x+a(i,j)*(vx(i,n) vx(j,n)); sum_y=sum_y+a(i,j)*(vy(i,n) vy(j,n)); end vx(i,n+1)=vx(i,n)+sum_x; vy(i,n+1)=vy(i,n)+sum_y; end end V=cat(3,vx,vy); %3 D matrix for calculating the norm and plot it for n=1:iteration for i=1:N norm(i,n)=sqrt(V(i,n,1)^2+V(i,n,2)^2); end end %the plots of velocities for i=1:N plot(norm(i,:)); hold on ;grid on ; end xlabel ( 'iteration' ); ylabel ( 'Amplitude of velocities' ) %the plots of x and y components of velocity figure;
PAGE 57
48 for n=1:iteration for i=1:N plot3(n,V(i,n,1),V(i,n,2)); hold on ;grid on end end xlabel( 'iteration' );ylabel( 'vx' );zlabel( 'vy' ) 3 dimensional Cucker and Smale Flocking Model clear all ;close all ; clc; segma=0.1;beta=0.5;N=5; %the parameters of the model and no. of birds x=[0;0.5;0;1;0]; %the initial conditions of positions y=[0;0.5;0.5;1;0]; z=[0.5;1;1;1;1]; vx=[1;0;0;0.25;0]; %the initial conditions of velocities vy=[0;1;0;0.25;0]; vz=[0.5;0.5;1;1.25 ;1]; %Calculating the average velocity of the initial conditions av=sqrt((sum(vx(:,1))/N)^2+(sum(vy(:,1))/N)^2+(sum(vz(:,1))/N)^2); %calculating the parameter K K=((segma^(2*beta)/((N 1)*sqrt(N))) 0.05); iteration=200; for n=1:iteration %next positions for i=1:N x(i,n+1)=x(i,n)+vx(i,n); y(i,n+1)=y(i,n)+vy(i,n); z(i,n+1)=x(i,n)+vz(i,n); end for i=1:N sum_x=0;sum_y=0;sum_z=0; for j=1:N %adjacency matrix elements a(i,j)=K/(segma^2+(x(i,n) x(j,n ))^2)^beta; b(i,j)=K/(segma^2+(y(i,n) y(j,n))^2)^beta; c(i,j)=K/(segma^2+(z(i,n) z(j,n))^2)^beta; %adjusting the velocitis according to neighbors sum_x=sum_x+a(i,j)*(vx(i,n) vx(j,n)); sum_y=sum_y+b(i,j)*(vy(i,n) vy(j,n)); sum_z=sum_ z+c(i,j)*(vz(i,n) vz(j,n)); end %next velocities vx(i,n+1)=vx(i,n)+sum_x; vy(i,n+1)=vy(i,n)+sum_y; vz(i,n+1)=vz(i,n)+sum_z; end end %preparing for plots v1=[vx(1,:);vy(1,:);vz(1,:)]; v2=[vx(2,:);vy(2,:);vz(2,: )]; v3=[vx(3,:);vy(3,:);vz(3,:)]; v4=[vx(4,:);vy(4,:);vz(4,:)]; v5=[vx(5,:);vy(5,:);vz(5,:)];
PAGE 58
49 for n=1:iteration norm1(n)=norm(v1(:,n)); norm2(n)=norm(v2(:,n)); norm3(n)=norm(v3(:,n)); norm4(n)=norm(v4(:,n)); norm5(n)=norm(v5(:,n)); end %the plots of velocities plot(norm1, 'k' );grid on ; hold on plot(norm2, 'k' ) hold on plot(norm3, 'k' ) hold on plot(norm4, 'k' ) hold on plot(norm5, 'k' ) title([ 'Average of the initial velocities is ,num2str(av)]) xlabel ( 'iteration' ); ylabel ( 'Amplitude of velocities' ) %the plots of positions and directions figure;grid on axis tight ; quiver3(x(:,1),y(:,1),z(:,1),vx(:,1)/norm(vx(:,1)),vy(:,1)/norm(vy(:,1) ),vz(:,1)/norm(vz(:,1)),0.5, 'k' ) title( positions and directions of birds at first iteration' ) xlabel( 'x axis' ) ylabel( 'y axis' ) zlabel( 'z axis' ) figure;grid on quiver3(x(:,2),y(:,2),z(:,2),vx(:,2)/norm(vx(:,2)),vy(:,2)/norm(vy(:,2) ),vz(:,2)/norm(vz(:,2)),0.5, 'k' ) title( positions and directions of birds at second iteratio n' ) xlabel( 'x axis' ) ylabel( 'y axis' ) zlabel( 'z axis' ) figure;grid on quiver3(x(:,3),y(:,3),z(:,3),vx(:,3)/norm(vx(:,3)),vy(:,3)/norm(vy(:,3) ),vz(:,3)/norm(vz(:,3)),0.5, 'k' ) title( positions and directions of birds at third iteration' ) xlabel( 'x axis' ) ylabel( 'y axis' ) zlabel( 'z axis' ) figure;grid on quiver3(x(:,10),y(:,10),z(:,10),vx(:,10)/norm(vx(:,10)),vy(:,10)/norm(v y(:,10)),vz(:,10)/norm(vz(:,10)),0.1, 'k' ) title( positions and directions of bird s at 10th iteration' ) xlabel( 'x axis' ) ylabel( 'y axis' ) zlabel( 'z axis' )
PAGE 59
50 5 agents with different graph topologies adaptive flocking algorithm clear all ;close all ; clc; %Initializing the algorithm with the scalar mu and no. of agents mu=0.5;N=5;iteration=100; %initial positions and velocities x=[.5;1;1.5;2;2.5]; y=[2;2;2;2;2]; vx=[0;1;4;3;3]; vy=[3;2;1;3;1]; %the adjacency matrix that describes the agents' connection %A=ones(N,N);%complete A=[0 0 1 0 0; %strong 1 0 0 0 0; 0 1 0 0 1; 0 0 1 0 0; 0 0 0 1 0]; % A=[0 1 0 0 0;%no spanning % 0 0 0 0 0; % 0 1 0 0 0; % 0 0 1 0 1; % 0 0 0 0 0]; % A=[0 1 0 0 0;%not strong % 1 0 0 0 0; % 0 1 0 0 0; % 1 0 0 0 0; % 0 1 0 1 0]; %the initial parameters of the algorithm for i=1:N rx(i,1)=1;ry(i,1)=1; for j=1:N theta_x(i,j)=0.2*A(i,j);theta_y(i,j)=0.2*A(i,j); end end %calculating the average velocity of the initial agent' velocities av=sqrt((sum(vx(:,1))/N)^2+(sum(vy(:,1))/N)^2); for n=1 :iteration %agents' position updating for i=1:N x(i,n+1)=x(i,n)+vx(i,n); y(i,n+1)=y(i,n)+vy(i,n); end %3 D matrix for positions X=cat(3,x,y); %seting up the phi vectors for i=1:N for j=1:N phi_x(j,i)=[vx(j,n) vx(i,n)]*A(i,j); phi_y(j,i)=[vy(j,n) vy(i,n)]*A(i,j); end %agents' velocities updating vx(i,n+1)=vx(i,n)+theta_x(i,:)*phi_x(:,i); vy(i,n+1)=vy(i,n)+theta_y(i,:)*phi_y(:,i); %calculating the av erage velocity of the neighbors vx_av(i,n)=0;vy_av(i,n)=0;c=0;
PAGE 60
51 for j=1:N if A(i,j)==1 c=c+1; vx_av(i,n)=vx_av(i,n)+vx(j,n); vy_av(i,n)=vy_av(i,n)+vy(j,n); end end vx_av(i,n)=(vx_av(i,n)+vx(i,n))/(c+1); vy_av(i,n)=(vy_av(i,n)+vy(i,n))/(c+1); %estimating the elements of the adjacency matrix rx(i,n+1)=1+(norm(phi_x(:,i)))^2; ry(i,n+1)=1+(norm(phi_y(:,i)))^2; theta_x(i,:)=theta_x(i,:) (mu*phi_x(:,i)'*(vx(i,n+1) vx_av(i,n)))/rx(i,n+1); theta_y(i,:)=theta_y(i,:) (mu*phi_y(:,i)'*(vy(i,n+1) vy_av(i,n)))/ry(i,n+1); end end %3 D matrix for velocities V=cat(3,vx,vy); for n=1:iteration for i=1:N Norm(i,n)=sqrt(V(i,n,1)^2+V(i,n,2)^2); end end %plots of velocities for i=1:N plot(Norm(i,:), 'k' ); hold on ;grid on ;axis tight ; title([ 'The average of the initial velocities is ,num2str(av)]) xlabel ( 'iteration' ); ylabel ( 'Amplitude of velocities' ) end %plots of positions and directions figure;grid on k=1:7:15; h=quiver(X(:,k,1),X(:,k,2),V(:,k,1),V(:,k,2),1, 'k' );grid on xlabel( 'x axis' );ylabel( 'y axis' );title( 'positions and directions of agents at different iteration' ); %checking the stochastic matrix and its eign values s(1:N)=0; for l=1:N for k=1:N s(l)=s(l)+theta_x(l,k); end end for i=1:N for j=1:N if i==j Ad(i,j)=1 s(i); else Ad(i,j)= theta_x(i,j); end end end
PAGE 61
52 disp( 'Ad' );disp(Ad) l=ones(N,1); %disp('Ad*l');disp(Ad*l); disp( 'eig(Ad)' );disp(eig(Ad)); 10 agents with undirected graph adaptive flocking algorithm clear all ;close all ; clc; %Initializing the algorithm with the scalar mu and no. of agents mu=0.5;N=10;iteration=200; x=[2;1;1;3;4;2;1;1;3;4]; %initial positions and velocities y=[5;5;6;2;1;5;1;4;1;1]; vx=[2;1;1;3;4;2;1;1;5;2]; vy=[5;5;4;2;1;5;1;4;1;4]; %the adjacency matrix that describes the A=[0 1 1 0 0 0 0 0 0 0; 1 0 0 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0; 0 1 0 0 1 1 0 0 0 0; 0 0 0 1 0 0 0 0 0 0; 0 0 0 1 0 0 1 0 0 0; 0 0 0 0 0 1 0 1 1 0; 0 0 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 1 0 0 1; 0 0 0 0 0 0 0 0 1 0]; %the initial parameters of the algorithm for i=1:N rx(i,1)=1;ry(i,1)=1; for j=1:N theta_x(i,j)=0.1*A(i,j);theta_y(i,j)=0.1*A(i,j); end end %calculating the average velocity of the initial agent' velocities av=sqrt(( sum(vx(:,1))/N)^2+(sum(vy(:,1))/N)^2); for n=1:iteration %agents' position updating for i=1:N x(i,n+1)=x(i,n)+vx(i,n); y(i,n+1)=y(i,n)+vy(i,n); end %3 D matrix for positions X=cat(3,x,y); %seting up the phi vectors for i=1:N for j=1:N phi_x(j,i)=[vx(j,n) vx(i,n)]*A(i,j); phi_y(j,i)=[vy(j,n) vy(i,n)]*A(i,j); end %agents' velocities updating vx(i,n+1)=vx(i,n)+theta_x(i,:)*phi_x(:,i); vy(i,n+1)=vy( i,n)+theta_y(i,:)*phi_y(:,i); %calculating the average velocity of the neighbors vx_av(i,n)=0;vy_av(i,n)=0;c=0;
PAGE 62
53 for j=1:N if A(i,j)==1 c=c+1; vx_av(i,n)=vx_av(i,n)+vx(j,n); vy_a v(i,n)=vy_av(i,n)+vy(j,n); end end vx_av(i,n)=(vx_av(i,n)+vx(i,n))/(c+1); vy_av(i,n)=(vy_av(i,n)+vy(i,n))/(c+1); %estimating the elements of the adjacency matrix rx(i,n+1)=1+(norm(phi_x(:,i)))^2; r y(i,n+1)=1+(norm(phi_y(:,i)))^2; theta_x(i,:)=theta_x(i,:) (mu*phi_x(:,i)'*(vx(i,n+1) vx_av(i,n)))/rx(i,n+1); theta_y(i,:)=theta_y(i,:) (mu*phi_y(:,i)'*(vy(i,n+1) vy_av(i,n)))/ry(i,n+1); end end %3 D matrix for velocities V=cat(3,vx,vy); for n=1:iteration for i=1:N Norm(i,n)=sqrt(V(i,n,1)^2+V(i,n,2)^2); end end %plots of velocities for i=1:N plot(Norm(i,:), 'k' ); hold on ;grid on ;axis tight ; title([ 'The average of the initial velocities is ,num2str(av)]) xlabel ( 'iteration' ); ylabel ( 'Amplitude of velocities for agents' ) end %plots of positions and directions figure;grid on k=2:60:122; quiver(X(:,k,1),X(:,k,2),V(:,k,1)/norm(V(:,k,1)),V(:,k,2)/norm(V(:,k,2) ),0.5, 'k' );grid o n ; xlabel( 'x axis' );ylabel( 'y axis' );title( 'positions and directions of agents at different iterations' ); %checking the stochastic matrix and its eign values s(1:N)=0; for l=1:N for k=1:N s(l)=s(l)+theta_x(l,k); end end for i=1:N for j=1:N if i==j Ad(i,j)=1 s(i); else Ad(i,j)=theta_x(i,j); end end
PAGE 63
54 end disp( 'Ad' );disp(Ad) l=ones(N,1); disp( 'Ad*l' );disp(Ad*l); disp( 'eig(Ad)' );disp(eig(Ad)); 5 oscillators with different graph topologies adaptive synchronization algorithm clear all ;close all ; clc; %Initializing the algorithm with the scalar mu and no. of oscillators mu=0.5;N=5;iteration=70; %natural frequencies of the oscillators w(:,1)=[1;1.5;2;2.5;2.3]; for i=1:N x(i,1)=2*i; %initial phases of the oscillators end %the adjacency matrix that describes the oscillators' connection A=ones(N,N); %complete A=[0 0 1 0 0; %strong 1 0 0 0 0; 0 1 0 0 1; 0 0 1 0 0; 0 0 0 1 0]; A=[0 1 0 0 0; %no spanning 0 0 0 0 0; 0 1 0 0 0; 0 0 1 0 1; 0 0 0 0 0]; A=[0 1 0 0 0; %not strong 1 0 0 0 0; 0 1 0 0 0; 1 0 0 0 0; 0 1 0 1 0]; %the initial parameters of the algorithm for i=1:N r(i,1)=1;r(i,1)=1; for j=1:N theta(i,j)=0.2*A(i,j);theta(i,j+1)=0.2; end end for n=1:iteration %seting up the phi vectors for i=1:N for j=1:N phi(j,i)=[x(j,n) x(i,n)]*A(i,j); end phi( N+1,i)= 1; %calculating the average phase x_av(i,n)=0;c=0; for j=1:N if A(i,j)==1 c=c+1; x_av(i,n)=x_av(i,n)+x(j,n); end
PAGE 64
55 end x_av(i,n+1)=(x_av(i,n)+x( i,n))/(c+1); %estimating the natural frequencies w_hat(:,n)=theta(:,N+1); Omega_hat(:,1)=w_hat(:,n); for k=1:40 for j=1:N phi_w(j,i)=[Omega_hat(j,k) Omega_hat(i,k)]*A(i,j); end Omega_hat(i,k+1)=Omega_hat(i,k)+(1/(c+1))*sum(phi_w(:,i)); end %estimating the elements of adjacency matrix and synchronizing the %phase x(i,n+1)=x(i,n)+w(i)+Omega_hat(i,k)+theta(i,:)*phi(:,i); r(i,n )=(norm(phi(:,i)))^2; theta(i,:)=theta(i,:) (mu*phi(:,i)'*(x(i,n+1) x_av(i,n+1) Omega_hat(i,k)))/r(i,n); %calculating the phase difference between oscillator 1 and the %other oscillators e(i,n)=x(i,n) x(1,n); end end %plots of phase difference n=1:iteration for i=1:N plot(n,e(i,n));grid on ;hold on ;axis tight xlabel( 'Iteration' );ylabel( 'The phase difference between oscillator 1 and all the others' ) end %checking the stochastic matrix and its eign values s(1:N)=0; for l=1:N for k=1:N s(l)=s(l)+theta(l,k); end end for i=1:N for j=1:N if i==j Ad(i,j)=1 s(i); else Ad(i,j)=theta(i,j); end end end disp( 'Ad' );disp(Ad) l=ones(N,1); disp ( 'Ad*l' );disp(Ad*l); disp( 'eig(Ad)' );disp(eig(Ad));
