Delay Robustness in Cooperative Control Von der Fakultät Konstruktions-, Produktions-, und Fahrzeugtechnik der Universität Stuttgart zur Erlangung der Würde eines Doktors der Ingenieurwissenschaften (Dr.–Ing.) genehmigte Abhandlung Vorgelegt von Ulrich Münz aus Stuttgart-Bad Cannstatt Hauptberichter: Prof. Dr.-Ing. Frank Allgöwer Mitberichter: Dr. Antonis Papachristodoulou Dr. Silviu-Iulian Niculescu, DR at CNRS (HDR) Tag der mündlichen Prüfung: 1. Juni 2010 Institut für Systemtheorie und Regelungstechnik Universität Stuttgart 2010 ii >EpeÈ dà tä êk tinoc svÔnjeton oÕtwc ¹svte ãn eÚnai tä p�n, [�n] m� ±c svwräc�llþ ±c � svullab  – � dà svullab� oÎk êsvti t� svtoiqeØa, oÎdà tÄ taÎtä tä kaÈ (oÎdþ � sv�rx pÜr kaÈ g¨) dialujèntwn g�r t� màn oÎkèti êsvtin, [15] oÙon � sv�rxkaÈ � svullab , t� dà svtoiqeØa êsvti, kaÈ tä pÜr kaÈ � g¨�; Since that which is compounded out of something so that the whole is one, not like a heap but like a syllable — now the syllable is not its elements, ba is not the same as b and a, nor is flesh fire and earth (for when these are separated the wholes, i.e. the flesh and the syllable, no longer exist, but the elements of the syllable exist, and so do fire and earth). Das was aus Bestandteilen so zusammengesetzt ist, daß es ein einheitliches Ganzes bildet, nicht nach Art eines Haufens, sondern wie eine Silbe, das ist offenbar mehr als bloß die Summe seiner Bestandteile. Eine Silbe ist nicht die Summe ihrer Laute; ba ist nicht dasselbe wie b plus a, und Fleisch ist nicht dasselbe wie Feuer plus Erde. Denn zerlegt man sie, so ist das eine, das Fleisch und die Silbe, nicht mehr vorhanden, aber wohl das andere, die Laute, oder Feuer und Erde. Aristoteles (384 - 322 BC): Metaphysica VII 17, 1041 b iii iv Acknowledgements This thesis is the result of my five year dive into the academic world. This period of my life has been very intense, exciting, fruitful, and enriching. After all, I would like to thank several people who enabled and strongly supported my progress in this time. My first thanks go to Prof. Dr.-Ing. Frank Allgöwer for supervising my thesis. He offe- red me a position as research and teaching assistant at the Institute for Systems Theory and Automatic Control with a much stronger emphasis on research than on teaching. Therefore, I was able to keep my mind focused on research. He opened several doors to the academic world for me, such as a summer school on time-delay systems. Moreover, he supported my trips to many international conferences and workshops in order to pre- sent my work, to see the most recent results of other researchers, and to get in contact with other scientist in my field. Moreover, he created a highly productive atmosphere at the institute with numerous national and international visitors and highly talented young researchers. On the other hand, he gave me the opportunity to study further on university didactics and improve my skills in classroom teaching and e-learning. Second, I want to thank Dr. Antonis Papachristodoulou. He introduced me to the most exciting and challenging problems in networked systems. He pointed to those me- thodologies that could help to solve these problems. And he always encouraged me to continue on my way, even in the most tricky situations. Finally, I very much enjoyed our professional and personal friendship. I would like to thank Dr. Silviu-Iulian Niculescu for his constructive comments on how to improve my thesis and for joining the committee of my PhD defense. I also thank him and Prof. Dr. ir. Wim Michiels for a very intensive and instructive one-week-course on time-delay systems in 2006. Both of them accompanied and supported my steps into the field of time-delay systems. Moreover, I would like to thank Prof. Dr. Pedro Zufiria. He stimulated my interest in system theoretic problems; and he was the first one to show me the pleasure of solving such problems during our work on my master thesis. My time at the institute would have been by far less relaxing, enjoyable, and produc- tive without all my colleagues. They created an open atmosphere full of most interesting discussions on and off the job. I owe them many thanks for all I learned from them on ma- ny different control topics. Especially, I want to thank my office mates Jørgen Johnsen, Jan Hasenauer, Martin Löhning, and Peter Wieland, my collaborators on different rese- arch topics Tobias Schweickhardt, Peter Schumm, Christian Ebenbauer, Rainer Blind, Marcus Reble, Jochen Rieber, Christoph Maier, Gerd Schmidt, Christoph Böhm, and Simone Schuler, and the proofreaders of this thesis Simone Schuler, Matthias Bürger, Peter Wieland, Rainer Blind, Marcus Reble, Gerd Schmidt, and Steffen Waldherr. Mo- reover, I would like to thank my students over all the years who supported my research and teaching assistance: Angela Schöllig, Marcus Reble, Andreas Wiesebrock, Yi Liu, Thomas Haag, Ekaterini Kourti, Rainer Blind, Maxime Carré, Jing Jin, Sandro Bücheler, Johannes Eck, Jingbo Wu, and Gregor Goebel. I would like to thank the Priority Programme 1305 Control Theory of Digitally Net- worked Dynamical Systems of the German Research Foundation (DFG) for their support v and many interesting and fruitful discussions with fellow PhD students. I also would like to thank The MathWorks Foundation in Science and Engineering at the University of Stuttgart for their support of my research, in particular Bernd Kanamüller for interesting discussions on my work. Last but not least, I would like to thank my family for their patience and support. Especially, my wife Kledy and my kids Jasmin and Leonhard had to cut back their own interests and I’m deeply indebted to them. vi Contents Symbols and Acronyms xiii Abstract xvii Deutsche Kurzfassung (German Abstract) xix 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Focus and Contributions of this Thesis . . . . . . . . . . . . . . . . . . . . 2 1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Problem Statement 9 2.1 Multi-Agent System Dynamics . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Agent Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Multi-Agent System Networks . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Output Interconnection on Networks with Delays . . . . . . . . . . . . . . 13 2.5 Cooperative Control Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.6 Delay Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Linear Multi-Agent Systems 21 3.1 Agent Dynamics and Delay-Interconnection Matrices . . . . . . . . . . . . 21 3.1.1 Agent Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1.2 Delay-Interconnection Matrices . . . . . . . . . . . . . . . . . . . . 22 3.2 Consensus of Undelayed Multi-Agent Systems . . . . . . . . . . . . . . . . 24 3.3 Consensus and Flocking Solutions . . . . . . . . . . . . . . . . . . . . . . 25 3.3.1 Closed Loop Dynamics with Initial Conditions . . . . . . . . . . . 25 3.3.2 Consensus Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.3 Flocking Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.4 Average Consensus and Average Flocking . . . . . . . . . . . . . . 29 3.4 Generalized Nyquist Consensus Condition . . . . . . . . . . . . . . . . . . 33 3.4.1 Generalized Nyquist Criterion for Multi-Agent Systems . . . . . . 33 3.4.2 Spectrum of 2I − Γr(jω) . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4.3 Generalized Nyquist Consensus Condition . . . . . . . . . . . . . . 43 3.5 Linear Single Integrator Multi-Agent Systems . . . . . . . . . . . . . . . . 48 3.6 Relative Degree Two Multi-Agent Systems . . . . . . . . . . . . . . . . . . 49 vii Contents 3.7 Consensus Controller Design . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.8 Convergence Rate of Linear Single Integrator Multi-Agent Systems . . . . 55 3.8.1 Robust, Scalable Convergence Rate Conditions . . . . . . . . . . . 55 3.8.2 Maximal Guaranteed Convergence Rate . . . . . . . . . . . . . . . 58 3.8.3 Example: Maximal Guaranteed Convergence Rate . . . . . . . . . 59 3.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4 Nonlinear Multi-Agent Systems with Relative Degree One 61 4.1 Multi-Agent Systems with Relative Degree One . . . . . . . . . . . . . . . 61 4.1.1 Agent Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1.2 Interconnection with Delays . . . . . . . . . . . . . . . . . . . . . . 62 4.2 Rendezvous on Constant and Switching Topologies . . . . . . . . . . . . . 65 4.3 Particular Multi-Agent Systems with Relative Degree One . . . . . . . . . 73 4.3.1 Nonlinear, Input Affine Relative Degree One Multi-Agent Systems 73 4.3.2 Euler-Lagrange Systems . . . . . . . . . . . . . . . . . . . . . . . . 76 4.3.3 Linear, Relative Degree One Multi-Agent Systems . . . . . . . . . 77 4.4 Synchronization of Kuramoto Oscillators . . . . . . . . . . . . . . . . . . . 78 4.4.1 Analysis of Kuramoto Oscillators . . . . . . . . . . . . . . . . . . . 79 4.4.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5 Nonlinear Multi-Agent Systems with Relative Degree Two 85 5.1 Multi-Agent Systems with Relative Degree Two . . . . . . . . . . . . . . . 85 5.2 Rendezvous on Constant Topologies . . . . . . . . . . . . . . . . . . . . . 87 5.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.3.1 Rendezvous in Euler-Lagrange Systems . . . . . . . . . . . . . . . 94 5.3.2 Flocking in Car-Following Models . . . . . . . . . . . . . . . . . . 95 5.4 Comparison with Generalized Nyquist Consensus Condition . . . . . . . . 97 5.4.1 Agent Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.4.2 Comparison of Consensus Conditions . . . . . . . . . . . . . . . . . 98 5.4.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6 Conclusions 105 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.2 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 A Fundamentals of Retarded Functional Differential Equations 109 B Fundamentals of Graph Theory 113 C Technical Proofs 115 C.1 Proof of Corollary 3.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 C.2 Proof of Corollary 3.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 C.3 Proof of Corollary 3.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 viii Contents C.4 Proof of Corollary 3.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 C.5 Proof of Theorem 3.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 C.6 Proof of Theorem 3.18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 C.7 Proof of Theorem 3.19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Bibliography 125 Index 137 ix Contents x List of Figures 2.1 Exemplary multi-agent system network with N = 5 agents and delays. . . 10 2.2 Agent i with dynamics (2.1a) and corresponding interconnection (2.1b) depending on the network’s topology and delay as well as on the coupling functions kij . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1 Simulation results for MAS without self-delay and with identical self-delay withN = 10 agents, dynamicsH(s) = 0.7s+0.7 s2 , ring topology, and random delays τij ≤ T = 0.5, see Example 3.3. . . . . . . . . . . . . . . . . . . . . 32 3.2 Average output y(t) for MAS with and without self-delay with N = 10 agents, dynamics H(s) = 0.7 s , ring topology, and random delays τij , Tij ≤ T = 0.5, see Example 3.4 for more details on the solid and dashed lines. . 33 3.3 General negative feedback interconnection. . . . . . . . . . . . . . . . . . . 35 3.4 Constructive illustration of sets Ωr(ωT ) (3.23) for ωT > 0. . . . . . . . . 36 3.5 Sets Ωr(ωT ) (3.23) for ω = 3 and T = 0.5 and eigenvalues of 50× 50 ring topology matrix with 150 randomly chosen sets of delays. . . . . . . . . . 37 3.6 Sets Ω1(ωT ) for ω = {0.5, 1, 2, 3} and T = 0.5 and eigenvalues of 50× 50 ring topology matrix with 150 randomly chosen sets of delays. . . . . . . . 42 3.7 Illustation of Equation (3.33) with dashed line L(ω), two circular convex sets − 1 2+H−1 i (jω) Ωr(ωT ), i = 1, 2, and convex hull of these two sets. . . . . 45 3.8 Illustration of Ω1(ωT ), (3.23a), for ω = 2.5 and T = 0.5 and 2+H−1(jω) with H(s) given in (3.37) with K = 1 for ρ = 1 (red solid line) and ρ = 1.5 (blue dashed line), respectively. . . . . . . . . . . . . . . . . . . . . . . . . 50 3.9 Simulation results for MAS with identical self-delay with dynamics P (s) = s+2 s2+s , ring topology, and random delays τij ≤ 5 for different numbers of agents N and different values of c0, see Example 3.16. . . . . . . . . . . . 54 3.10 Roots of characteristic polynomial ∆0 (denoted ◦) and characteristic quasi- polynomial ∆ (denoted ×) for particular τij < T (left) and corresponding roots of ∆(s− ψ) (right). . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.11 Maximal convergence rate ψ and optimal gainKopt vs. connectivity bound λ2 for MAS without self-delay (solid lines), MAS with identical self-delay (dashed lines), and MAS with different self-delay (dash-dotted lines) for different delay bounds T = 0.2 (blue), T = 0.5 (green), and T = 2 (red). The arrow indicates how ψ and Kopt decrease as T increases. . . . . . . . 59 4.1 Exemplary illustration of hyper-rectangle Υ(t) for a MAS with four agents and yi(t) ∈ R 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 xi List of Figures 4.2 Schematic illustration of two iterations of the contraction argument. . . . 68 4.3 Schematic illustrations for alternating and consecutive intervals as dis- cussed in the proof of Theorem 4.5. . . . . . . . . . . . . . . . . . . . . . . 71 4.4 Motion of robot i heading for robot j with compensation of centrifugal forces (solid line) and without compensation (dashed line). . . . . . . . . . 76 4.5 Phases θi of different Kuramoto oscillators on a circle, see (4.21), and graph topology of the network considered in Section 4.4.2. . . . . . . . . . 78 4.6 Exemplary histograms for simulated packet delays depending on the scal- ing parameter β and the sampling period Ts. . . . . . . . . . . . . . . . . 81 4.7 Simulation result for synchronization of Kuramoto oscillators (4.22) with initial condition θ(1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.8 Standard deviation of phases θi of Kuramoto oscillators (4.22) over time. 82 4.9 Simulation result for synchronization of Kuramoto oscillators (4.22) with initial condition θ(2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.1 Block diagram of nonlinear RD2 agent dynamics Σi, see (5.1). . . . . . . . 86 5.2 Contour plot of delay bound T (indicated as numbers on the lines) with re- spect to the coupling gain κ and the damping parameter ρ for MAS (5.17). For parameter triples (T , κ, ρ), Corollary 3.11 guarantees rendezvous if the point (κ, ρ) is above the solid line corresponding to T . The solid lines are given by (5.20). Similarly, Theorem 5.3 guarantees rendezvous if the point (κ, ρ) is above the dashed line corresponding to T . The dashed lines are given by (5.21). Finally, the parameter set (κ, ρ) where delay-independent rendezvous is guaranteed by Corollary 3.11 is above the dash-dotted line, indicated as boundary between delay-independent and delay-dependent (DI/DD) parameter sets according to (5.19). See Section 5.4.2 for more details. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.3 Topology of MAS with adjacency matrix (5.24). . . . . . . . . . . . . . . . 101 5.4 Simulation result of MAS (5.17a), (5.23) with ρ = 0.1 on the slow network with τ ij ≈ 0.075s. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.5 Simulation result of MAS (5.17a), (5.23) with ρ = 0.1 on the fast network with τ ij ≈ 0.0375s. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 C.1 Illustration for proof of Corollary 3.10. . . . . . . . . . . . . . . . . . . . . 116 C.2 Illustration of Ω1(ωT ), (3.23a), for ω = 2.5 and T = 0.5 and 2+H−1(jω) with H(s) given in (3.37) with K = 1 for ρ = 1 (red solid line) and ρ = 1.5 (blue dashed line), respectively. . . . . . . . . . . . . . . . . . . . . . . . . 117 C.3 Illustration of 2K−ψ+jω K as red dash-dotted line and sets Ω̃1 and Ω̃4 for the proofs of Theorem 3.17 and 3.18. . . . . . . . . . . . . . . . . . . . . . 120 C.4 Illustration of 2K−ψ+jω K as red dash-dotted line and set Ω̃3 for the proof of Theorem 3.19. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 xii Symbols and Acronyms Symbols R set of reals R +(R−) set of positive (negative) reals R + 0 (R − 0 ) set of non-negative (non-positive) reals C +(C−) set of complex numbers with positive (negative) real part C + 0 (C − 0 ) set of complex numbers with non-negative (non-positive) real part C +j 0 set of complex numbers with non-negative imaginary part Cn([a, b],Rn) Banach space of continuous functions mapping [a, b] to R n, see Ap- pendix A Cn Banach space of continuous functions mapping [−T , 0] to R n Re(z) real part of z ∈ C Im(z) imaginary part of z ∈ C v∗ complex conjugate of v ‖ · ‖ Euclidean vector norm λ(M) eigenvalue of matrix M σ(M) spectrum of matrix M F(M) field of values of matrix M, see proof of Lemma 3.5 on page 38 det(M) determinant of matrix M diag(vi) diagonal matrix with elements vi ∈ C yi[k](t) k-th element of yi(t) y (ι) i (t) ι-th derivative of yi(t) L(y(t)) Laplace transform of y(t) L−1(Y (s)) inverse Laplace transform of Y (s) Co{·} convex hull of a set N number of agents in the MAS N index set of N agents Ni index sets of all neighbours of agent i xi(t) state of agent i ui(t) input of agent i Ui(s) Laplace transform of ui(t) yi(t) output of agent i y(t) average output of all agents Yi(s) Laplace transform of yi(t) Σi dynamics of agent i Hi = νi(s) δi(s) transfer function of agent i xiii Symbols and Acronyms kij(·) coupling function between agent j and i kij(·) gain of coupling function kij(z) = kij(‖z‖) z ‖z‖ Γr(s) delay-interconnection matrix, see Equation (3.5) on page 23 Gr(s) network return ratio, see Equation (3.21) on page 34 Ωr(ωT ) convex sets containing σ(2I − Γr(jω)) for τij , Tij ≤ T , see Equa- tion (3.21) on page 34 ∆0(s) characteristic polynomial of undelayed MAS ∆(s) characteristic quasi-polynomial of MAS with delays ϕ ∈ C∑ni initial condition, C∑ni = C([−T , 0],R ∑ ni) G = (V, E) graph V = {vi} vertex set E ⊆ V × V edge set G = {Gp} finite sets of graphs Gp G([t1, t2]) union graph over the interval [t1, t2] hDW dwell-time A = [aij ] adjacency matrix Aτ (s) adjacency matrix including delays, see Equation (3.4) on page 23 D = diag(di) degree matrix Dτ (s) degree matrix including identical self-delays, see Equation (3.4) on page 23 DT (s) degree matrix including different self-delays, see Equation (3.4) on page 23 L = D −A Laplacian matrix L = I −D−1A normalized Laplacian matrix Lτ (s) Laplacian matrix including identical self-delays, see Equation (3.5) on page 23 LτT (s) Laplacian matrix including different self-delays, see Equation (3.5) on page 23 λ2 algebraic connectivity, second smallest eigenvalue of L = I −D−1A λ2 lower bound on the second smallest eigenvalue of L = I −D−1A Tij : Cm → R m delay operator for delay from agent j to agent i, see Section 2.6 Tij : Cm → R m delay operator for self-delay of agent i, see Section 2.6 τij constant delay in the channel from j to i Tij self-delay of agent i with respect to agent j τij(t) time-varying delay in the channel from j to i Tij upper bound of time-varying delay τij(t) φij(η) kernel of the distributed delay from agent j to agent i, see Equa- tion (2.16) on page 18 τ ij average delay of distributed delay T upper bound of all delays, delay range yi,t ∈ Cm segment of trajectory yi(t), t ∈ [t− T , t] yi,t(η) = yi(t+ η), η ∈ [−T , 0], element of segment yi,t Υ hyper-rectangle for contraction argument, see Section 4.2 xiv ∂Υ boundary of set Υ Mi(yi) inertia matrix Ci(yi, ẏi)ẏi centrifugal and Coriolis forces Si(xi) storage function of agent i Acronyms CDMA code-division multiple access LTI linear, time-invariant MAS multi-agent system OVM optimal velocity model PSCN packet-switched communication network RD1, RD2 relative degree one, relative degree two RFDE retarded functional differential equation TDS time-delay system xv Symbols and Acronyms xvi Abstract The robustness of various cooperative control schemes on large scale networked sys- tems with respect to heterogeneous communication and coupling delays is investigated. The presented results provide delay-dependent and delay-independent conditions that guarantee consensus, rendezvous, flocking, and synchronization in different classes of multi-agent systems (MAS). All conditions are scalable to arbitrarily large multi-agent systems with non-identical agent dynamics. In particular, conditions for linear agents, for nonlinear agents with relative degree one, and for a class of nonlinear agents with relative degree two are presented. The interconnection topology between the agents is in most cases represented by an undirected graph. The results for nonlinear agents with relative degree one hold also for the more general case of directed graphs with switching topologies. Different delay configurations are investigated and compared. These config- urations represent different ways how the delays affect the coupling between the agents. The presented robustness analysis considers constant, time-varying, and distributed de- lays in order to take different sources of delays into account. The results are applied to several typical applications and simulations illustrate the findings. The main contributions of this thesis include: (i) Consensus and rendezvous in single integrator MAS are robust to arbitrarily large delays even on switching topologies. How- ever, the convergence rate of this MAS is delay-dependent and scalable convergence rate conditions are presented. (ii) Consensus and rendezvous in relative degree two MAS are robust to sufficiently small delays. Local, scalable conditions are derived for these MAS that guarantee consensus and rendezvous for bounded delays. (iii) Finally, the derived delay robustness analysis for general linear MAS allows for the first time to compare different delay configurations in a unifying framework. xvii Abstract xviii Deutsche Kurzfassung (German Abstract) In dieser Dissertation wird die Robustheit von verschiedenen kooperierenden Regelungen bezüglich heterogener Kommunikations- und Kopplungsverzögerungen untersucht. Es werden skalierbare Analysemethoden für Konsens, Rendezvous, Herdenverhalten (engl. flocking) und Synchronisation für verschiedene Klassen von linearen und nichtlinearen Agentensystemen (engl. multi-agent systems) vorgestellt. Die Ergebnisse werden auf ver- schiedene typische Anwendungen übertragen und durch Simulationen veranschaulicht. Motivation Bei vielen Phänomenen in der Natur spielt die Kooperation zwischen Individuen einer Gruppe eine wesentliche Rolle. Beispielhaft seien hier das Verhalten von Fisch- und Vo- gelschwärmen, die Nahrungsbeschaffung bei Ameisenvölkern sowie die Synchronisation der Nervenzellen, die den Herzschlag vorgeben, genannt. Eine gute Einführung in dieses Thema mit zahlreichen weiteren Beispielen gibt Strogatz (2004) (englische Originalfas- sung Strogatz (2003)). Es ist eine wesentliche Eigenschaft dieser Kooperation, dass das Verhalten der Gruppe nicht von einzelnen Individuen vorgegeben wird. Vielmehr ergibt sich das Verhalten aufgrund der lokalen Interaktion zwischen jedem Mitglied der Gruppe und dessen Nachbarn. So orientiert sich jeder Fisch in einem Schwarm an den Bewegun- gen der anderen Fische in seiner Umgebung. Aber er weiß nicht, wohin der Schwarm als ganzes schwimmt. Dennoch bleiben die Fische im Schwarm und bewegen sich gemeinsam in eine bestimmte Richtung (Couzin et al., 2005; Pöppe, 2005; Reynolds, 1987). Zahlreiche technische Systeme bestehen ebenfalls aus vielen kooperierenden dynami- schen Teilsystemen. Beispielhaft seien hier drei Anwendungen genannt: Kommunika- tionsnetze wie das Internet setzen sich aus vielen Routern zusammen, die Information von Millionen von Quellen zu ebenso vielen Anwendern übertragen und dabei die Kapa- zität der einzelnen Übertragungskanäle berücksichtigen (Srikant, 2004). Verkehrsnetze bestehen aus vielen Zügen, Fahrzeugen oder Flugzeugen mit dem gemeinsamen Ziel, Passagiere und Waren von einem Ort zum anderen zu bringen (Helbing, 2001). In Ener- gieversorgungsnetzen kooperieren die Generatoren um im gesamten Netz eine konstante Spannung und Frequenz unabhängig von der Zahl der Verbraucher zu gewährleisten (Pa- vella and Murthy, 1994). Weitere Anwendungen werden in Murray (2002) vorgestellt. Diese kooperierenden dynamischen Systeme werden in der englischsprachigen Lite- ratur multi-agent systems (MAS) genannt. Im deutschen Sprachgebrauch hat sich der Begriff Agentensystem in Anlehnung an kooperierende Systeme in der Automatisierungs- technik etabliert. In der Automatisierungstechnik bezeichnen Agentensysteme Gruppen von Agenten, die interagieren, um gemeinsame Ziele zu erreichen, siehe VDI-Richtlinie xix Deutsche Kurzfassung (German Abstract) ” Agentensysteme in der Automatisierungstechnik“ ((VDI), 2009). Diese Definition ent- spricht im wesentlichen dem Gebrauch des Begriffs multi-agent system in der englisch- sprachigen Literatur. Einen Überblick über dieses schnell wachsende Gebiet der Rege- lungstechnik geben die Sonderausgaben verschiedener Zeitschriften (Antsaklis and Bail- lieul, 2007; Roy et al., 2007; Hu et al., 2008; Shima and Pagilla, 2007) sowie die Bücher (Ren and Beard, 2008; Qu, 2009; Shamma, 2007; Shima and Rasmussen, 2009; Bullo et al., 2009). Agentensysteme in der Regelungstechnik haben zwei charakteristische Eigenschaften: • Sie bestehen aus einer Vielzahl von dynamischen Teilsystemen, deren Anzahl sich mit der Zeit ändern kann, und • die genaue Verknüpfungstopologie zwischen den Agenten ist normalerweise unbe- kannt und manchmal ebenfalls zeitvariant. Diese Eigenschaften machen in den meisten Fällen eine zentrale Regelung des Agenten- systems unmöglich. Daher versuchen Ingenieure von der Natur zu lernen, wie koope- rierende Regelungen für Agentensysteme entworfen werden können. Diese Regelungen sollen ein globales Verhalten der Gruppe durch lokale Interaktion zwischen den Agenten garantieren. Man spricht in diesem Zusammenhang oft von Schwarmintelligenz (Bischoff, 2009; Miller, 2007b) (englische Originalversion Miller (2007a)). Die Interaktion zwischen den Agenten erfordert einen Informationensaustausch über ein Netzwerk. Dieser Informationsaustausch kann ein inhärenter Teil des Agentensy- stems sein, wie z.B. die Phasenkopplung zwischen Generatoren in einem Energiever- sorgungsnetz. Bei anderen Anwendungen tauschen die Agenten Informationen über ein digitales Kommunikationsnetzwerk aus, wie z.B. bei der aktiven Warteschlangenregelung im Internet (engl. active queue management (AQM)). Eine dritte Form des Informati- onsaustauschs sind Messungen, wie z.B. Abstandsmessungen bei Fahrzeugkolonnen. In den meisten Fällen wird die Information beim Datenaustausch verzögert, sei es durch die endliche Ausbreitungsgeschwindigkeit in Energieversorgungsnetzen, durch Warte- schlangen in digitalen Netzen oder durch Messzeiten bei Abstandsmessungen. Daher sind diese Verzögerungen wesentlicher Bestandteil vieler Agentensysteme. Auch wenn diese Verzögerungen sehr klein sind, können sie ein kooperatives Verhalten verhindern. Ein Beispiel hierfür wird in Kapitel 5.4 vorgestellt. Daher sind Methoden für die Ro- bustheitsanalyse von kooperierenden Systemen bezüglich dieser Totzeiten1 sehr wichtig. Eine ausführliche Übersicht über den Forschungsstand in diesem Bereich befindet sich in der englischsprachigen Einleitung in Kapitel 1. In dieser Arbeit werden die elementarsten kooperative Verhaltensweisen eines Agen- tensystems auf ihre Robustheit bezüglich Totzeiten untersucht. Diese sind • Konsens, z.B. wenn Mikroprozessoren mit lokalem Takt sich auf einen einheitlichen Takt einigen, 1In der Nachrichtentechnik bezeichnet man Zugriffs- und Übertragungszeiten als Verzögerungen. Diese Effekte werden in der Systemtheorie Totzeiten genannt. In dieser Kurzfassung werden Fachbegriffe beider Fachbereiche verwendet. Daher werden die Begriffe Verzögerung und Totzeit synonym verwen- det. xx • Rendezvous, z.B. wenn Roboter sich an einem Punkt treffen oder eine Formation einnehmen, • Herdenverhalten (engl. flocking), z.B. wenn Fahrzeuge in einer Kolonne mit der gleichen Geschwindigkeit und einem bestimmten Abstand zueinander fahren und • Synchronisation, z.B. die Phasensynchronisation der Generatoren in Energiever- sorgungsnetzen. Eine formale Definition dieser Eigenschaften wird in Kapitel 2 gegeben. Komplexere kooperierende Verhaltensweisen können meist aus einer dieser vier elementaren Verhal- tensweisen abgeleitet werden. Um Aussagen über beliebig große Agentensysteme treffen zu können, darf die Komple- xität der Robustheitsanalyse nur leicht oder überhaupt nicht mit der Zahl der Agenten, der Zahl der Verbindungen zwischen den Agenten und der Zahl der Totzeiten zunehmen. Diese Eigenschaft wird Skalierbarkeit genannt, siehe z.B. Bondi (2000). Darüber hinaus ist es wünschenswert, dass die Robustheitsbedingungen lokale Bedingungen sind, d.h. sie setzen die Dynamik jedes Agenten mit der Dynamik seiner benachbarten Agenten und den Verbindungen zu diesen Agenten in Beziehung. Gleichzeitig sind diese Bedin- gungen unabhängig von der Dynamik anderer Agenten oder von anderen Verbindungen im Netzwerk. Somit stellen lokale Bedingungen die Idealform skalierbarer Bedingungen dar. Sie erlauben einen lokalen Entwurf der Regler anstelle eines globalen Entwurfs. Dies ist insbesondere dann von Vorteil, wenn Teilsysteme zu dem Agentensystem hinzusto- ßen oder dieses verlassen. Wenn zum Beispiel ein neuer Generator mit einem Energie- versorgungsnetz verbunden wird, ist es nicht möglich, die Regler aller Generatoren im Energieversorgungsnetz neu zu entwerfen. Stattdessen sollte nur der Regler des neuen Generators und gegebenenfalls die Regler seiner Nachbarn angepasst werden. Gliederung und Forschungsbeiträge dieser Dissertation In diese Dissertation werden verschiedene Methoden zur skalierbaren Robustheitsanalyse von kooperierenden Reglern bezüglich Totzeiten entwickelt. Die Agentensysteme beste- hen aus Agenten mit zeitkontinuierlichen, linearen oder nichtlinearen Dynamiken. Die Verbindungen zwischen den Agenten wird mittels eines Graphen beschrieben, der in den meisten Fällen ungerichtet ist. Die Ergebnisse in Kapitel 4 gelten allerdings auch für den allgemeineren Fall von gerichteten und schaltenden Graphen. Darüber hinaus werden verschiedene Konfigurationen untersucht und verglichen, welche sich darin unterschei- den, wie die Verzögerungen die Interaktion zwischen den Agenten beeinflussen. Dabei werden konstante, zeitvariante und verteilte Totzeiten betrachtet, um unterschiedliche Quellen für die Totzeiten zu berücksichtigen. In der gesamten Arbeit werden heterogene Totzeiten angenommen, d.h. die Totzeiten können in jeder Verbindung zwischen zwei Systemen unterschiedlich sein. Weite Teile dieser Dissertation befassen sich mit Konsens und Rendezvous in Agen- tensystemen. Dies ist teilweise der Tatsache geschuldet, dass viele Agentensysteme mit Totzeiten kein Herdenverhalten erzielen können, was ebenfalls in dieser Arbeit näher xxi Deutsche Kurzfassung (German Abstract) untersucht wird. In Anwendungsbeispielen wird gezeigt, wie die vorgestellten Methoden dennoch verwendet werden können, um die Synchronisation von Kuramoto-Oszillatoren (Kuramoto, 1984) oder das Folgeverhalten von Fahrzeugen (Helbing, 2001) zu untersu- chen. Eine detaillierte Einführung in die untersuchten Agentendynamiken, Verknüpfungs- topologien, Totzeitmodelle und kooperative Regelziele wird in Kapitel 2 gegeben. Für dieses breite Spektrum an Agentendynamiken und Regelzielen werden drei un- terschiedliche Methoden basierend auf dem verallgemeinerten Nyquistkriterium, einem Kontraktionsargument und Summen positiv definiter Lyapunov-Krasovskii Funktiona- le entwickelt. Jedes der nachfolgenden Kapitel dieser Arbeit ist einer dieser Methoden gewidmet. Tabelle 1.1 auf Seite 3 gibt einen Überblick über die betrachteten Agenten- systeme in diesen Kapiteln. Die Forschungsbeiträge in den einzelnen Kapiteln sind im folgenden zusammengefasst: Kapitel 3: Verallgemeinertes Nyquistkriterium Es wird eine skalierbare, mengenba- sierte Methode für die Robustheitsanalyse von Konsensproblemen in linearen Agenten- systemen entworfen. Die Agenten sind über Netzwerke verknüpft, die durch ungerichtete, konstante Graphen und konstante Totzeiten beschrieben werden. Drei unterschiedliche Konfigurationen, wie die Totzeiten die Verbindungen zwischen den Agenten beeinflussen, werden untersucht: Totzeiten, die nur die Informationen der Nachbaragenten betreffen, und Totzeiten, die sowohl die Nachbarn als auch die Informationen des Agenten selbst betreffen, wobei im zweiten Fall unterschieden wird, ob die Totzeiten der Nachbarn und des Agenten selbst identisch sind oder nicht. Mithilfe dieser mengenbasierten Metho- de werden Robustheitsbedingungen für verschiedene Klassen linearer MAS entwickelt, z.B. für Agentensysteme bestehend aus Einfachintegratoren. Darüber hinaus wird ei- ne skalierbare Bedingung für die Konvergenzrate von Agentensystemen bestehend aus Einfachintegratoren hergeleitet. Kapitel 4: Kontraktionsargument Es wird gezeigt, dass nichtlineare Agenten mit rela- tivem Grad eins und beliebig langen Verzögerungen ein Rendezvous erreichen, sofern die Kopplung zwischen den Agenten ein integrierendes Verhalten garantiert. Dabei werden Agenten betrachtet, die ihren eigenen Ausgang ohne Verzögerung bestimmen können. Unter den drei in Kapitel 3 untersuchten Konfigurationen ist dies die robusteste gegen Totzeiten. Das Rendezvous dieser Systeme wird mithilfe eines Kontraktionsarguments für ein allgemeines Netzwerk mit gerichteten, schaltenden Topologien und konstanten, zeitvarianten oder verteilten Totzeiten nachgewiesen. Ausgehend von dieser sehr allge- meinen Systemklasse werden Bedingungen für wichtige Unterklassen des betrachteten Agentensystems abgeleitet, wie Agenten mit Euler-Lagrange-Dynamik oder Einfachin- tegratoren. Schließlich wird sowohl theoretisch gezeigt als auch durch Simulationen ver- anschaulicht, dass Kuramoto-Oszillatoren unter gewissen Voraussetzungen auch dann synchronisieren, wenn die Kopplungen mit Übertragungsverzögerungen behaftet sind. Kapitel 5: Summe positiv definiter Lyapunov-Krasovskii Funktionale Es werden lo- kale, skalierbare, totzeitabhängige Bedingungen an die Kopplungsfunktionen hergeleitet, xxii so dass für eine große Klasse von nichtlinearen Agenten mit relativem Grad zwei Ren- dezvous garantiert werden kann. Dabei wird angenommen, dass der zugrundeliegende Graph konstant und ungerichtet ist. Die betrachtete Klasse von nichtlinearen Agenten mit relativem Grad zwei ist praxisrelevant, sie beinhaltet beispielsweise Euler-Lagrange Systeme. Ähnlich wie in Kapitel 4 werden konstante, zeitvariante und verteilte Totzeiten berücksichtigt, wobei der Agent seinen eigenen Ausgang ohne Totzeit bestimmen kann. Die vorgestellten Bedingungen werden mithilfe von Summen positiv definiter Lyapunov- Krasovskii Funktionale hergeleitet. Diese Bedingungen garantieren darüber hinaus eine Robustheit gegenüber Modellunsicherheiten und hängen lediglich von lokalen Totzeiten ab, d.h. von einer oberen Schranke für die Totzeiten zu den Nachbarn jedes Agenten aber nicht von allen Totzeiten im gesamten Netzwerk. Daher sind diese Rendezvousbe- dingungen gut für große Netzwerke mit unterschiedlichen Agentendynamiken geeignet. Ausgehend von diesem allgemeinen Resultat werden Bedingungen für spezielle System- klassen abgeleitet, wie Fahrzeugfolgemodelle oder Agenten mit Euler-Lagrange-Dynamik. Darüber hinaus werden die Ergebnisse mit ähnlichen Bedingungen basierend auf dem verallgemeinerten Nyquistkriterium in Kapitel 3 verglichen. Schließlich werden die Er- gebnisse anhand von Simulationen veranschaulicht. Diese zeigen, dass auch sehr kleine Verzögerungen ein Rendezvous von Agenten verhindern können. Dabei wird ebenfalls deutlich, wie die hier vorgestellten Methoden helfen können, kooperierende Regler so zu entwerfen, dass sie robust gegenüber Totzeiten sind. Zusammenfassung Diese Dissertation umfasst mehrere Methoden, mit denen die Robustheit von koope- rierenden Reglern bezüglich Totzeiten untersucht werden kann. Diese Methoden decken ein breites Spektrum an unterschiedlichen Agentendynamiken, kooperativen Regelzielen, Netzwerktopologien, sowie Totzeitmodellen und -konfigurationen ab. Darüber hinaus sind die Ergebnisse skalierbar auf beliebig große Agentensysteme mit heterogenen Tot- zeiten. Eine ausführliche Diskussion der Ergebnisse dieser Dissertation und ein Ausblick auf zukünftige Forschungsthemen in diesem Bereich finden sich in Kapitel 6. xxiii Deutsche Kurzfassung (German Abstract) xxiv Chapter 1 Introduction 1.1 Motivation Cooperative behavior in large groups of individuals can be found abundantly in nature. Well-known examples are schools of fish, flocks of birds, collective food-gathering in ant colonies, as well as synchronization of flashing fireflies and pacemaker cells, see Strogatz (2003) for a nice introduction with many examples. A fundamental property of this cooperation is that the group behavior is not dictated by one of the individuals. On the contrary, this behavior results implicitly from the local interaction between the individuals and their neighbours. For instance, every fish in a school knows where the other fish in its neighbourhood are heading, but it does not know the average heading of all fish in the school. Nonetheless, the fish in the school stay together and move as a group in a certain direction (Couzin et al., 2005; Reynolds, 1987). Many engineering systems also consist of large groups of cooperating dynamic systems. They are called multi-agent systems (MAS) in the literature, see Olfati-Saber et al. (2007); Ren and Beard (2008) for recent overviews. Various applications are provided in Murray (2002); we mention here only three examples: Communication networks like the Internet are composed of many routers with the aim to transmit information from millions of sources to equally many users respecting the capacity of each link of the network (Srikant, 2004). Transport systems consist of many trains, cars, or airplanes with the common aim to bring people and goods from one point to another, see Helbing (2001) for an overview on car-following. In power networks, the power generators have to cooperate in order to provide a constant voltage and frequency irrespective of how many consumers are connected to the network (Pavella and Murthy, 1994). These applications show two main characteristics of MAS: • the group consists of a large number of subsystems and their number may even be time-varying as new agents join or leave the group, and • the interconnection topology between the agents is usually unknown and changing over time. These properties often render a centralized control of the MAS very difficult. Therefore, engineers seek to learn from nature how to implement a decentralized cooperative control strategy that achieves global goals based on local couplings (Miller, 2007a). 1 Chapter 1 Introduction These cooperative control strategies require that the agents exchange information with their neighbours over a network. This exchange of information can be an implicit prop- erty of the MAS, e.g. the inherent phase coupling of power plants in power grids. In other applications, the agents exchange information using digital communication net- works in order to fulfill a cooperative control task, e.g. in Internet congestion control. Finally, there are applications where the information is exchanged using measurements, e.g. relative distance measurements in multi-vehicle applications. Many of these net- works introduce some sort of delay when information is exchanged between the agents, either propagation delays as in power grids, or access and queuing delays in digital com- munication networks, or measurement delays as in the multi-vehicle example. These delays are an intrinsic property of many MAS. Even though these delays are often small, they might impede that the MAS fulfills the cooperative control task; an example is given in this thesis. Therefore, the robustness of cooperative control strategies with respect to delays is very important. We investigate in this thesis the delay robustness of the most fundamental cooperative control tasks: • consensus, e.g. micro controllers with local clocks agreeing on a common time, • rendezvous, e.g. robots meeting at a point or achieving a certain formation, • flocking, e.g. cars moving with the same velocity and with a certain distance between each other, and • synchronization, e.g. phase synchronization of generators in power networks. A formal definition of these cooperative control tasks is given in Chapter 2. More sophisticated tasks can be usually reduced to one of these problems. In order to provide conditions for arbitrarily large networks, the complexity of delay robustness analysis should be independent of the number of agents, the number of inter- connections, and the number of delays, or it may only increases very slowly with these parameters. This property is called scalability, e.g. Bondi (2000). Moreover, it is desir- able that delay robustness conditions are local conditions, i.e. they relate the dynamics of every agent to its neighbouring agents and the interconnections to these neighbours. Yet, these conditions are independent of other agents or other interconnections in the network. Thus, local conditions are the ideal case of scalable conditions. They allow for a local design of the couplings, avoiding a global design of the whole MAS. This is particularly useful if some agents join or leave the network. For instance, if a new power plant is connected to a power grid, it is not viable to redesign the controllers of all power plants in the network. 1.2 Focus and Contributions of this Thesis We present scalable methods for delay robustness analysis in cooperative control. We consider various cooperative control tasks for a wide spectrum of MAS with different 2 1.2 Focus and Contributions of this Thesis Table 1.1: Overview of different MAS models and cooperative control tasks in this thesis. agent dynamics cooperative control task self-delay graph delay models Ch. 3 linear consensus, flocking no, identical, different undirected, constant constant Ch. 4 nonlinear, RD1, integrating be- havior consensus, rendezvous, synchronization no directed, switching constant, time-varying, distributed Ch. 5 nonlinear, RD2, special structure consensus, rendezvous, flocking no undirected, constant constant, time-varying, distributed kinds of delays. All results are scalable to large MAS. Moreover, we present several local conditions for delay robustness. The methods are applied to several practical examples and illustrated in simulations. More precisely, we consider MAS with continuous-time, linear or nonlinear agent dy- namics. The topology of the network between the agents is described in most cases by an undirected graph. The results in Chapter 4 hold also for the more general case of directed, switching graphs. Moreover, we take different delay configurations into ac- count that reflect different ways how the delays affect the coupling between the agents. In addition, we consider constant, time-varying, and distributed delay models to cover different sources of delays, like access delays, propagation delays, and measurement de- lays. Throughout this thesis, we consider heterogeneous delays, i.e. the delays can be different for each interconnection link. Large parts of this thesis concentrate on consensus and rendezvous in MAS. This is also due to the fact that many MAS with delays cannot achieve flocking and synchronization with the standard cooperative control laws, as will be shown in this thesis. In addition, we show exemplarily how the derived results can be used to investigate synchronization of Kuramoto oscillators and flocking in car-following models. A more detailed introduction to the agent dynamics, the interconnection topologies, the delay models, as well as the cooperative control tasks is given in Chapter 2. In order to cope with such a broad range of MAS and cooperative control tasks, we develop three different methodological approaches based on the generalized Nyquist criterion, a contraction argument, and sums of Lyapunov-Krasovskii functionals. Each of the subsequent chapters is dedicated to one of these approaches. An overview of the considered MAS in these chapters is given in Table 1.1. The contributions of the individual chapters are summarized next: Chapter 3: Generalized Nyquist Criterion We develop a set-valued method to investi- gate the delay robustness of consensus and flocking in linear MAS on undirected graphs with heterogeneous, constant delays. We consider three types of output feedback delays: delays affecting only the output of the agents’ neighbours as well as delays affecting both 3 Chapter 1 Introduction the agents’ own output and the output of their neighbours, distinguishing whether the self-delays and the neighbours’ delays are identical or different. The applicability of the set-based method is demonstrated for several special cases like consensus in MAS with single integrator agent dynamics and consensus controller design for a class of linear MAS. Moreover, we derive scalable and robust convergence rate conditions for MAS with single integrator agent dynamics. The main contributions of this chapter are: • a unifying framework for delay robustness analysis of linear MAS with different delay configurations, • consensus conditions for single integrator MAS with different delay configurations, and • convergence rate conditions for single integrator MAS with heterogeneous delays. Chapter 4: Contraction Argument We show that MAS consisting of nonlinear agents with relative degree one (RD1) eventually reach output rendezvous for arbitrarily large delays if the coupling functions between the agents guarantee an integrating behavior. In this chapter, we concentrate on MAS without self-delay. Among the three delay configu- rations in Chapter 3, this is the most robust one to delays. Rendezvous is proven using a contraction argument. Thereby, we consider the most general network with constant, time-varying, or distributed delays and switching, directed topologies. From this general result, we derive rendezvous controller for MAS with nonlinear, input affine agents, for agents with Euler Lagrange dynamics, and for single integrator agent dynamics. The latter corresponds to the standard MAS for rendezvous and consensus in the literature, e.g. Olfati-Saber et al. (2007); Ren and Beard (2008). Finally, we show theoretically and by simulations that delay-coupled, identical Kuramoto oscillators synchronize. The main contribution of this chapter is: • proof of delay-independent rendezvous in nonlinear MAS with integrating behavior under the same conditions as for undelayed MAS, even if the underlying graph is directed and switching. Chapter 5: Sums of Lyapunov-Krasovskii functionals We provide local, scalable, delay-dependent conditions on the coupling functions such that MAS consisting of a class of nonlinear agents with relative degree two (RD2) achieve rendezvous on constant, undirected graphs. The class of nonlinear RD2 agents is relevant for rendezvous problems and includes, for example, systems with Euler Lagrange dynamics. As in Chapter 4, we concentrate on delay configurations without self-delay and take all three delay models into account: constant, time-varying, and distributed delay. The conditions are derived using sums of Lyapunov-Krasovskii functionals. These conditions are robust to model uncertainties and only depend on local parameters, e.g. on upper bounds on the delays to the agent’s neighbours but not on a global upper bound on the delays in the whole network. Thus, these local rendezvous conditions are scalable to large networks of non-identical agents. 4 1.3 Related Work From this general result, we derive specific conditions for Euler Lagrange MAS and car-following models. Moreover, we compare these conditions to similar conditions for MAS composed of linear agents with relative degree two derived in Chapter 3. Finally, simulation results illustrate that even very small delays may impede rendezvous. These simulations also show how rendezvous can be guaranteed in these cases using the methods presented in this thesis. The main contributions of this chapter are: • local, delay-dependent rendezvous conditions for MAS consisting of a class of non- linear agents with relative degree two and • application of these results to Euler Lagrange MAS and a car-following model. In summary, we present in this thesis a variety of methods and conditions for a scalable delay robustness analysis of different cooperative control tasks in a broad range of MAS. 1.3 Related Work Cooperative behavior has been studied for the first time more than 300 years ago when Christiaan Huygens discovered synchronization of pendulum clocks (Huygens, 1673). However, the mechanisms behind this and other synchronization phenomena have only been revealed in the last 50 years, mainly using computer simulations and strong simpli- fications, see Strogatz (2003) for a nice review. One of the first publications on consensus dates back roughly 50 years, when Eisenberg and Gale (1959) investigated the consensus of individual probability distributions of bettors on horse races. Early consensus con- ditions for linear discrete-time MAS based on stochastic matrices have been published in DeGroot (1974). A nice overview of early works on cooperating systems is given in Vámos (1983) and one of the first PhD theses on this topic in the control community is Tsitsiklis (1984). In the last five years, cooperative control has become one of the most active research areas in the control community. It is beyond the scope of this thesis to review all important publications in this area. The interested reader is referred to following special issues and books: Antsaklis and Baillieul (2007); Roy et al. (2007); Hu et al. (2008); Shima and Pagilla (2007); Ren and Beard (2008); Qu (2009); Shamma (2007); Shima and Rasmussen (2009); Bullo et al. (2009). Our literature review will be focused on MAS with delays. Consensus in discrete-time single integrator MAS with linear coupling and delays has been studied extensively in the past. The main publications show that consensus is reached on uniformly quasi-strongly connected graphs1, even if the agents communicate asynchronously, see Xiao and Wang (2008a,b); Cao et al. (2008); Fang and Antsaklis (2005); Almeida et al. (2009). In order to derive these results, the state space is extended by delayed states. Then, results on ergodic matrices are applied in order to prove consensus. Similar methods have been applied to discrete-time second order MAS in Liu and Passino (2006); Lin and Jia (2009). Alternative approaches use the generalized 1See Definition 4.2 on page 63 for more details on uniformly quasi-strongly connected graphs 5 Chapter 1 Introduction Nyquist criterion and Gershgorin’s circle theorem to proof consensus (Tian and Liu, 2008). Generally speaking, the main results on delay robustness analysis for discrete- time MAS heavily rely on the fact that these MAS are finite dimensional systems. Thus, these methods are not applicable to infinite dimensional systems like continuous-time MAS with delays. In Chapter 4, we generalize these results to continuous-time MAS with delays using a contraction argument. In continuous time, delay robustness in cooperative control can be investigated in the frequency domain, e.g. using small gain arguments or the generalized Nyquist crite- rion, and in the time-domain, e.g. using Lyapunov-Krasovskii functionals or Lyapunov- Razumikhin functions. We first review different results in the frequency domain which are always restricted to linear MAS. In this case, frequency- and delay-dependent feed- back matrices are defined depending on the topology and the heterogeneous delays. Then, convex sets are determined which contain the eigenvalues of the feedback ma- trices for arbitrary topologies and bounded delays. One possibility to compute such a set is Gershgorin’s circle theorem, e.g. Horn and Johnson (1985). Consensus conditions based on Gershgorin’s circle theorem typically apply a small gain condition and lead to delay-independent results because Gershgorin’s circles contain the eigenvalues of the feedback matrices for arbitrary large delay values, e.g. Wang and Elia (2008); Lee and Spong (2006); Charalambous et al. (2008); Stefanovic and Pavel (2009a). In Liu and Tian (2007), the generalized Nyquist criterion is combined with Gershgorin’s circles and consensus conditions are derived for single integrator MAS with arbitrary large commu- nication delays but bounded computation delays. In Lestas and Vinnicombe (2007b,a, 2006), frequency-dependent sets are determined and set-valued stability and consensus conditions are derived similar to the results in Chapter 3. This approach uses simi- lar methods as our results in Chapter 3, a detailed comparison is given in Section 3.4. The method proposed in Chapter 3 develops relatively simple frequency-dependent and delay-dependent convex sets that contain the eigenvalues of the feedback matrix. These sets are much more accurate than Gershgorin’s circles. The resulting consensus condi- tions based on these sets also apply for a much more general class of linear MAS with delays and, hence, contain most previous results as special case. In particular, these con- ditions consider for the first time different delay configurations in a unifying framework and provide robust convergence rate conditions for MAS with heterogeneous delays. In the time-domain, delay robustness of MAS has been studied using small-µ analysis (Yang et al., 2008), input-to-state stability (Fan and Arcak, 2006), or techniques for partial differential equations (Bliman and Ferrari-Trecate, 2008). In Kao et al. (2009); Jönsson and Kao (2009), parameterized convex sets are defined and it is assumed that the eigenvalues of the feedback matrix are contained in this convex set. The feedback matrix is defined in a similar way as in the frequency-domain approaches mentioned above. Then, stability conditions are derived based on integral quadratic constraints (IQC) using the parameters of this convex set. In order to determine the parameters of this convex sets, the authors propose Gershgorin’s circle theorem and derive delay- independent results. It is however not clear how delay-dependent results can be obtained, e.g. using delay-dependent convex sets similar to those in Chapter 3. Most publications on MAS without self-delay rely on sums of Lyapunov-Krasovskii 6 1.4 Outline of the Thesis functionals or a contraction argument, see Moreau (2004) for a nice comparison. Sums of Lyapunov-Krasovskii functionals consist of arbitrarily large but finite sums of pos- itive definite terms, each of them related to one agent or one interconnection link. This approach has been used to investigate single integrator MAS (Chellaboina et al., 2006; Ghabcheloo et al., 2007; Papachristodoulou and Jadbabaie, 2005), Internet con- gestion control (Papachristodoulou and Peet, 2008; Papachristodoulou and Jadbabaie, 2010), and MAS consisting of passive agents or nonlinear agents with relative degree one (Chopra and Spong, 2008, 2006; Chopra et al., 2008). The main disadvantage of this method is that the underlying graph has to be undirected or at least balanced, i.e. the number of incoming and outgoing links of each node are the same. More general results for MAS with single integrator agent dynamics are obtained using a contraction argu- ment (Papachristodoulou and Jadbabaie, 2006; Papachristodoulou et al., 2010) because they only require directed, uniformly quasi-strongly connected graphs, the weakest pos- sible connectivity assumption allowing for consensus. In contrast to Papachristodoulou and Jadbabaie (2006) and our previous publications Münz et al. (2009b,d, 2008a); Pa- pachristodoulou et al. (2010), we use a completely different proof technique in Chapter 4 that makes some technical assumptions obsolete, see Papachristodoulou et al. (2010) for details. Moreover, we consider the more general case of MAS consisting of non-scalar integrators or relative degree one agents with integrating behavior. The presented theo- rems extend previous results on undelayed single integrator MAS in Lin (2006); Lin et al. (2007) to single integrator MAS with arbitrarily large delays. In contrast to previous publications, we use sums of Lyapunov-Krasovskii functionals for MAS with relative de- gree two agents in Chapter 5. For these MAS, the contraction argument is not applicable, and the delay robustness of these MAS has not been investigated so far. 1.4 Outline of the Thesis The thesis starts with a detailed problem statement in Chapter 2, including a motivation for the different delay models. The robustness analysis based on the generalized Nyquist criterion is presented in Chapter 3. Rendezvous in MAS with nonlinear RD1 agents is investigated in Chapter 4. The same problem in MAS with nonlinear RD2 agents is studied in Chapter 5. The thesis is concluded in Chapter 6. Appendix A and B provide introductions to functional differential equations and graph theory. Technical proofs are summarized in Appendix C. 7 Chapter 1 Introduction 8 Chapter 2 Problem Statement In this chapter, we describe the MAS and the cooperative control tasks considered in this thesis. We first present the multi-agent system dynamics in Section 2.1. Then, we explain the different parts of these dynamics. In Section 2.2, we describe the agent dynamics. The interconnection network between the agents is introduced in Section 2.3 with a focus on the network properties topology and delay. The coupling between the agents is explained in Section 2.4. In Section 2.5, we define different cooperative control tasks, namely consensus, rendezvous, flocking, and synchronization. Finally, the different delay models considered in this thesis are motivated and explained in Section 2.6. This chapter is summarized in Section 2.7. 2.1 Multi-Agent System Dynamics A multi-agent system (MAS) consists of agents Σi, i ∈ N = {1, . . . , N} that are coupled through their outputs in order to achieve a cooperative behavior, see Figure 2.1. In this work, we consider MAS with agent dynamics Σi : { ẋi(t) = fi(xi(t), ui(t)) yi(t) = hi(xi(t)) , i ∈ N = {1, . . . , N}, (2.1a) and the interconnection ui(t) = − N∑ j=1 aij di kij ( Tij(yi,t)− Tij(yj,t) ) , (2.1b) where xi(t) ∈ R ni , ui(t) ∈ R m, yi(t) ∈ R m are the state, input, and output of agent i, respectively. The functions fi : R ni × R m → R ni and hi : R ni → R m describe the agent dynamics. The topology of the network between the agents is described by the elements of the adjacency matrix of the underlying graph A = [aij ] ∈ R N×N , where aij > 0 if there is a link from agent j to agent i are connected and aij = 0 otherwise. The degree of agent i is di = ∑N j=1 aij . The coupling functions kij : R m → R m describe the portion of the input ui of agent i because of its interaction with agent j. Its argument is the difference between the delayed outputs of agent i and agent j. The delay operators Tij : Cm → R m and Tij : Cm → R m describe the self-delay and the neighbouring delay of the link from agent j to i, where Cm = C([−T , 0],Rm) is 9 Chapter 2 Problem Statement Σ1 T12 y1y2 y5 Σ2 T 32 Σ4 Σ3 y3 T25 Σ5 y3 T53 T 3 1 T 43 Figure 2.1: Exemplary multi-agent system network with N = 5 agents and delays. the Banach space of continuous functions mapping the interval [−T , 0] into R m for a given delay range T , see Appendix A for details. The argument of Tij is yj,t ∈ Cm, which denotes the segment of length T of current and past outputs of agent j. Particular values of the segment yj,t are given as yj,t(η) = yj(t+η) for any η ∈ [−T , 0]. The delay operators represent different delay models like constant, time-varying, or distributed delays. For instance, if the channel introduces a constant delay τij , then Tij(yj,t) = yj(t− τij). The delay operators Tij,Tij are associated to the link from agent j to agent i, see Figure 2.1 where we only depict Tij. The structure of the MAS (2.1) is summarized in Figure 2.2, which shows a single agent with dynamics (2.1a) and its interconnection to the other agents, depending on the topology and delay of the network as well as on the coupling functions kij . The closed loop system (2.1) is a retarded functional differential equation (RFDE), see Appendix A for an introduction to RFDEs. Its initial condition is ϕ ∈ C∑ni = C([−T , 0],R ∑ ni). Throughout this thesis, we assume that ϕ is continuous. In the following sections, we describe the individual parts of the MAS in detail. 2.2 Agent Dynamics In this work, we consider MAS that consist of agents with dynamics (2.1a) where the functions fi and hi are sufficiently smooth to guarantee existence, uniqueness, and con- tinuity of solutions of the closed loop system (2.1) for sufficiently smooth coupling func- tions kij , see Hale and Lunel (1993). In general, the agents can be non-identical, i.e. with different dynamics fi, hi and different number of states ni. Yet, all agents have the same number of inputs and outputs m. It is in fact necessary to assume that all of them have the same number of outputs if we consider the standard cooperative control tasks where eventually yi = yj for all i, j, see Section 2.5 below. In addition, it is a natural assumption for MAS that each agent has the same number of inputs and out- puts because we want to steer all elements of yi independently by the control input ui. 10 2.3 Multi-Agent System Networks y1 y2 yN Ti1 Ti2 TiN + + + − − − ai1 di coupling topology ki2(·) ki1(·) ai2 di kiN(·) aiN di ui interconnection yi(t) = hi(xi(t)) ẋi(t) = fi(xi(t), ui(t)) yi(s) = Hi(s)ui(s) yi agent dynamics delay Ti2 Ti1 TiN Figure 2.2: Agent i with dynamics (2.1a) and corresponding interconnection (2.1b) de- pending on the network’s topology and delay as well as on the coupling functions kij. This assumption excludes, for example, underactuated Euler-Lagrange MAS (Dong and Farrell, 2009; Ortega et al., 1998). The differential equation (2.1a) contains most agent dynamics considered in the lit- erature as special cases, e.g. single-integrator and double-integrator agent dynamics (Tanner et al., 2007; Jadbabaie et al., 2003; Olfati-Saber et al., 2007; Olfati-Saber, 2006; Ren and Beard, 2008) as well as linear and nonlinear higher order dynamics (Fax and Murray, 2004; Arcak, 2007; Chopra and Spong, 2006; Wieland et al., 2010, 2008). In Chapter 3, we concentrate on MAS with linear single-input single-output (SISO) agent dynamics with transfer function Hi(s), i.e. Σi : Yi(s) = Hi(s)Ui(s), i ∈ N = {1, . . . , N}, (2.2) where Ui(s) and Yi(s) are the Laplace transform of ui(t) ∈ R and yi(t) ∈ R, respectively, see Figure 2.2. Chapter 4 provides results for MAS consisting of nonlinear agents (2.1a) with relative degree one and integrating behavior. In Chapter 5, we investigate a class of nonlinear agents (2.1a) with relative degree two. 2.3 Multi-Agent System Networks The agents are interconnected on a network. Examples for a network are digital packet- switched communication networks (PSCN), power grids, or measurement-based networks as in multi-vehicle applications, where the network links indicate which distances between the vehicles can be measured. In this thesis, we reduce the network to two fundamental properties: the topology and the communication or coupling delays, see Figure 2.1 for an illustration. 11 Chapter 2 Problem Statement We describe the topology of the network by a graph G(V, E) with vertex set V = {vi}, i ∈ N = {1, . . . , N}, representing the agents and an edge set E ⊆ V×V representing the links between the agents. The adjacency matrix of the graph is A = [aij ] ∈ R N×N . We have aij > 0 if agent i receives information from agent j, i.e. ui depends on yj,t, and aij = 0 otherwise, see also (2.1b). For example, a possible adjacency matrix of the graph in Figure 2.1 is A =   0 2 0 0 0 0 0 0 0 4 1 3 0 0 0 0 0 1 0 0 0 0 2 0 0   . (2.3) The degree of agent i is di = ∑N j=1 aij . Note that di is in fact the in-degree of agent i, but we just call it degree for simplicity. The degree matrix is thus defined as D = diag(di) and the Laplacian matrix of the graph is L = D − A. We also define the normalized Laplacian matrix L = D−1L = I −D−1A. Throughout this thesis, we assume that the graph does not have self-loops, i.e. aii 6= 0. The results in Chapter 3 and 5 apply for constant, undirected graphs with symmetric weights, i.e. aij = aji and A = AT . The results in Chapter 4 also hold for switching, directed graphs, i.e. aij = aji is not required and the adjacency matrices A(t) is time-varying. If aij > 0, then agent j is called parent of agent i. In undirected graphs, we call agent i and j neighbours if aij = aji > 0. We briefly recall the fundamental connectivity concepts for directed and undirected graphs. An undirected graph is connected if any two nodes vi, vj of the graph are connected by a path, i.e. a sequence of neighbouring nodes starting at vi and ending at vj. A directed graph is quasi-strongly connected if there exists a vertex vR, called the root, such that there exist directed paths from vR to all other nodes vi of the graph. A directed path from vi to vj is a sequence of edges out of E that takes the following form (vi, vi1), (vi1 , vi2), . . . , (vip , vj). Recall that a graph is quasi-strongly connected if and only if it contains a spanning tree. A more detailed introduction to graph theory is given in Appendix B. If aij > 0, agent i receives information about agent j using a link (vj , vi). All links of the network are affected by delays. These delays can originate from different sources such as transmission delays, scheduling delays, or measurement delays. A more detailed discussion of different kinds of delays is given in Section 2.6 below. The delay from agent j to agent i is modeled using the delay operator Tij : Cm → R m. Hence, the signal at the receiver node vi at time t is Tij(yj,t) where yj(t) is the signal at the sender node vj at time t. Remember that yj,t ∈ Cm denotes the segment of length T of current and past outputs of agent j. Note that Tij is not a function but a functional on the segment yj,t ∈ Cm. A more detailed introduction to functionals and functional differential equations is provided in Appendix A. 12 2.4 Output Interconnection on Networks with Delays 2.4 Output Interconnection on Networks with Delays So far, we have established the agent dynamics as well as the network properties topology and delay. It remains to explain the coupling between the agents (2.1b). In Chapter 3, we consider the following delay configurations without self-delay ui(t) = − N∑ j=1 aij di (yi(t)− Tij(yj,t)), (2.4a) with identical self-delay ui(t) = − N∑ j=1 aij di (Tij(yi,t)− Tij(yj,t)) (2.4b) with different self-delay ui(t) = − N∑ j=1 aij di ( Tij(yi,t)− Tij(yj,t) ) , (2.4c) where the coupling functions are kij(η) = η and the delays affect either only the neigh- bouring output yj,t (2.4a) or also the agent’s own output yi,t (2.4b), (2.4c). The first configuration (2.4a) is denoted without self-delay because agent i’s own out- put yi is not delayed. This configuration models, for example, communication delays for data sent from agent j to agent i, see Section 2.6 for a more detailed motivation of this delay configuration. It has been investigated previously for example in Lee and Spong (2006); Liu and Passino (2006); Papachristodoulou and Jadbabaie (2006, 2005); Chopra and Spong (2006, 2008); Yang et al. (2008). The second configuration (2.4b) is called with identical self-delay because the delay of the output of agent i and of the output of its neighbour j are identical. This configuration is usually proposed for MAS with coupling delays where the delays affect the difference of the agents’ outputs yi,t− yj,t, e.g. Bliman and Ferrari-Trecate (2008); Xiao and Wang (2008a); Liu and Tian (2008); Tian and Liu (2008); Lestas and Vinnicombe (2007b); Xiao and Wang (2006). Another motivation for (2.4b) are agents with computation or measurement delays, assuming that both the agent’s own output and the neighbouring output are affected by the same delay. This has been proposed, for instance, for traffic flow models, see Sipahi and Niculescu (2007); Brackstone and McDonald (1999); Orosz (2005) and references therein. The third configuration (2.4c) is denoted with different self-delay because the delay of the output of agent i and of the output of agent j are different. Motivating applications include different reaction delays to the agent’s own behavior and the behavior of its neighbours or computation delays in combination with communication delays, e.g. Xiao and Wang (2008a); Tian and Liu (2008). A major contribution of Chapter 3 is the analytical comparison of the three delay configurations (2.4) in a unified framework. It turns out that the configuration without self-delay (2.4a) is in general more robust to delays than the other configurations (2.4b), 13 Chapter 2 Problem Statement (2.4c). Note that (2.4a) can be written in the following form ui(t) = − N∑ j=1 aij di (yi(t)− Tij(yj,t)) = −yi(t) + N∑ j=1 aij di Tij(yj,t), (2.5) i.e. the control input is the error between the current output yi(t) of agent i and a weighted average of the delayed outputs of its parents. If the coupling functions kij are chosen appropriately, the control input of the nonlinear generalization of (2.4a) ui(t) = − N∑ j=1 aij di kij (yi(t)− Tij(yj,t)) , (2.6) which is investigated in Chapter 4 and 5, also corresponds to the error between the agent’s own output and a weighted average of the delayed outputs of its parents. This property guarantees that the output yi moves toward the delayed outputs of its parents if the agent dynamics (2.1a) have an integrating behavior, which is exploited in Chapter 4. This behavior is very intuitive: if people try to meet with their friends, they move toward them or their last known position. The interconnection (2.6) is fairly simple because it is static and does not require to estimate the states of the neighbours. The possibly nonlinear functions kij are such that different nonlinearities may affect each link. This is particularly useful for local, scalable design conditions as presented in Chapter 5, where particular bounds on kij depend on the delays Tij of the corresponding channel. Finally, (2.6) includes typical feedback interconnections in the literature as special cases, e.g. the interconnection of Kuramoto oscillators (Strogatz, 2000; Kuramoto, 1984), of car-following models (Helbing, 2001), and in power networks (Pavella and Murthy, 1994). 2.5 Cooperative Control Tasks The aim of the MAS (2.1) is to achieve a cooperative behavior of the agents. We call this aim a cooperative control task . There are many different cooperative control applications as described in the Introduction. In this work, we focus on the most fundamental tasks consensus, rendezvous, flocking, and synchronization. These terms are not used consistently in the literature. Throughout this thesis, we rely on the following definitions: Consensus describes a behavior where agents achieve an agreement on a scalar value. Rendezvous refers to agents arriving at the same point in a higher dimensional space, e.g. underwater vehicles that meet somewhere in the sea. Flocking is a more complex, swarm like behavior where all agents eventually move in the same direction, i.e. they achieve an agreement on the velocity, and end up in a particular formation. This formation problem is often simplified to all agents being at the same point and moving in the same direction. Here, we also consider this simplified flocking problem. Synchronization refers to a set of oscillators that eventually oscillate with the same frequency and phase. A formal definition of consensus, rendezvous, flocking, and synchronization is given next. Thereby, ‖ · ‖ denotes the Euclidean norm. 14 2.5 Cooperative Control Tasks Definition 2.1 (Consensus). A MAS consisting of agents (2.1a) with yi(t) ∈ R, ui(t) ∈ R, i.e. m = 1, achieves a consensus asymptotically if lim t→∞ (yi(t)− yj(t)) = 0, for all i, j, lim t→∞ ẏi(t) = 0, for all i. (2.7) Definition 2.2 (Rendezvous). A MAS consisting of agents (2.1a) with yi(t) ∈ R m, ui(t) ∈ R m, m ≥ 1, achieves a rendezvous asymptotically if lim t→∞ ‖yi(t)− yj(t)‖ = 0, for all i, j, lim t→∞ ẏi(t) = 0, for all i, (2.8) where ‖ · ‖ is the Euclidean vector norm. Definition 2.3 (Flocking). A MAS consisting of agents (2.1a) achieves flocking asymp- totically if lim t→∞ ‖yi(t)− yj(t)‖ = 0, for all i, j, lim t→∞ ‖ẏi(t)− c(t)‖ = 0, for all i, (2.9) for any in general nonzero c : R → R m. Definition 2.4 (Synchronization). A MAS consisting of agents (2.1a) achieves syn- chronization asymptotically if lim t→∞ ‖yi(t)− yj(t)‖ = 0, for all i, j, lim t→∞ ‖ẏi(t)− c(t)‖ = 0, for all i, (2.10) where c : R → R m is the derivative of the periodic synchronized orbit of yi with period Tp > 0, i.e. ∫ t+Tp t c(η)dη = 0 for all t. Note that these definitions are not unambiguous, e.g. flocking includes synchronization as special case. However, comparing Definition 2.1 and 2.2 to Definition 2.3 and 2.4, we see that consensus and rendezvous describe a static terminal state, i.e. all outputs are constant as soon as consensus or rendezvous is reached. On the contrary, flocking and synchronization denote a dynamic terminal state where the agents still move when flocking or synchronization is achieved. It is worth mentioning that there is a fundamental difference between standard stabil- ity problems and cooperative control problems like consensus and rendezvous. Standard stability problems analyse the asymptotic stability of isolated steady states, i.e. the goal is to prove that all trajectories in the neighbourhood of this steady state converge toward 15 Chapter 2 Problem Statement this steady state. Rendezvous and consensus problems usually exhibit unbounded, con- nected sets of steady states. The challenge is to prove that all trajectories starting in the neighbourhood of this set of steady states asymptotically converge toward this set, i.e. the set of steady states is asymptotically attracting. Note however that the individual steady states in this set are not asymptotically stable because in every arbitrarily small neighbourhood of any element of this set are further steady states. The exact point in the set, where the system converges to, is in many cases irrelevant. In the literature on MAS with constant delays τij , an alternative condition for ren- dezvous and flocking has been proposed: lim t→∞ ‖yi(t)− yj(t− τij)‖ = 0, ∀i, j, (2.11) e.g. Chopra and Spong (2008, 2006). For rendezvous, this condition is equivalent to the condition (2.8) because yj(t − τij) = yj(t) if ẏj(t) ≡ 0. Yet, condition (2.11) is only suitable for dynamic cooperative control tasks under additional assumptions on the delays, which is illustrated in the following example: Example 2.5. Consider a MAS consisting of two agents with scalar output yi(t). If flocking is reached according to (2.11), then the outputs eventually satisfy y1(t) = c̃(t) + y10 y2(t) = c̃(t) + y20, (2.12) for some c̃(t) = ∫ t 0 c(η)dη with c(t) as in (2.9). Solving (2.11) with (2.12) gives y1(t)− y2(t− τ21) = 0 = c̃(t)− c̃(t− τ21) + y10 − y20 y2(t)− y1(t− τ12) = 0 = c̃(t)− c̃(t− τ12) + y20 − y10, and combining these two equations, we see that flocking requires 2c̃(t)− c̃(t− τ21)− c̃(t− τ12) = 0. (2.13) For flocking with constant derivatives c(t) = c0 6= 0, i.e. c̃(t) = c0t, Equation (2.13) holds only for zero delays τ21 = τ12 = 0. For non-constant derivatives c(t) 6= const., Equation (2.13) holds, e.g., for periodic functions c(t) = c(t−τ21) = c(t−τ12) such as c(t) = sin(ω0t), ω0 > 0, if τ21 = 2πn1 ω0 , τ12 = 2πn2 ω0 , n1, n2 ∈ N. Note however that these periodic solutions only exist in very particular cases with suitable agent dynamics, e.g. harmonic oscillators, and perfectly tuned delays, i.e. these solutions are not robust to uncertain delays. This simple example shows that condition (2.11) imposes additional assumptions on the delays if dynamic cooperative control tasks are considered. These assumptions are even more complicated if large MAS with many heterogeneous delays are studied. There- fore, Definitions 2.3 and 2.4 are preferable. In Chapter 3, we mainly focus on consensus problems. We also show that flocking in MAS with delays is only possible in particular configurations. Chapter 4 and 5 provide solutions to consensus and rendezvous problems with application examples on synchronization in Section 4.4 and on flocking in Section 5.3.2. 16 2.6 Delay Models 2.6 Delay Models Delays appear in many interconnection networks. In “biological” MAS like schools of fish or car-following scenarios, we often encounter reaction delays that stem from the reaction time of the biological agents with respect to the movement of their fellow agents. Reaction delays are typically in the range of several hundreds of milliseconds. We know from the literature on car-following that reaction delays are important in this area for ac- curate modeling (Brackstone and McDonald, 1999; Orosz, 2005). In man-made networks like power networks, propagation delays are induced because of the long links between different power suppliers and consumers. Simplifying models reduce these propagation delays to complex admittances at the driving frequency 50Hz or 60Hz (Pavella and Murthy, 1994). Finally, digital PSCN introduce queuing delays and access delays. Ac- cess delays emerge because many digital PSCN use a shared communication medium. Hence, information cannot be transmitted instantaneously from node i to node j but only if node i has access to the communication medium. In some PSCN, access is given to the nodes by scheduling algorithms like token-passing, which induces delays because node i has to wait for the token before it may transmit data. Other PSCN allow for random access which might result in collisions. The necessary collision arbitration or avoidance procedures usually induce access delays in the range of at least several hun- dreds of microseconds even in small networks, see Moyne and Tilbury (2007). Queuing delays result from the queuing of packets in routers of PSCN. Both access and queuing delays are also usually randomly distributed depending on the network load. We see that delays are an important characteristic of networks. In the MAS literature, delays are often neglected because they are assumed to be small. Yet, we have seen that reaction delays in biological MAS are usually around several hundreds of milliseconds, and in some cases, they are essential for an accurate modeling. Moreover, if access and queuing delays are in the range of hundreds of microseconds, we may only neglect them if we are sure that the MAS is robust to these delays. Hence, the important question arises: When are these delays sufficiently small such that they do not affect the cooperative control task? The answer to this question is given by the delay robustness analysis in this thesis. This thesis is focused on communication and coupling delays between the agents. There is another important source of delays in MAS that we consider here only as special cases of the different feedback delay configurations (2.4): computation delays, i.e. the time an agent needs to compute the control input ui from the available outputs yi(t) and yj(t). An interesting discussion on the range and influence of computation and communication delays in industrial PSCN is given in Moyne and Tilbury (2007). In this thesis, we consider three different kinds of delays, namely constant delays, time-varying delays, and distributed delays, in order to model different sources of delays. These delays are introduced in the following: 17 Chapter 2 Problem Statement Constant delays The simplest delay model for a link between two agents is a constant delay τij ∈ [0,T ] with corresponding delay operator Tij(yj,t) = yj(t− τij). (2.14) Constant delays are usually a first step to investigate the robustness of a MAS to delays. They are an accurate model for reaction and propagation delays in some cases. For reaction delays, we have to assume that the reaction time is not changing, e.g., due to changing concentration on the cooperative control task. For propagation delays, we have to assume that the distance between the nodes i and j remains constant. This might contradict the idea of consensus and rendezvous if yj(t) − yi(t) describes the distance between agent i and j. In this case, we expect that the propagation delay decreases as rendezvous is approached. Constant delays are in general unsuited for access delays, which are usually random delays depending, e.g., on the network load. Time-varying delays An appropriate generalization of constant delays, e.g. for random access delays, are time-varying delays τij : R → [0,Tij ], with maxi,j Tij = T and delay operator Tij(yj,t) = yj(t− τij(t)). (2.15) Throughout this thesis, we consider deterministic, piecewise continuous time-varying delays τij such that discontinuities in τij are separated by a dwell time hτij > 0, i.e. consecutive discontinuity points tl+1 > tl satisfy tl+1 − tl ≥ hτij for all l. This delay model covers reaction, propagation, queuing, and access delays equally well. Yet, its major drawback is conservativity if some information about the evolution of τij is known. For example, in PSCN with random access, the majority of the data is transmitted with a rather small delay whereas very few data is heavily delayed with delays close to the delay bound Tij (Moyne and Tilbury, 2007). Intuitively, we expect that the consensus properties of a MAS using this network depend rather on the usual small delays than on the seldom large delays. However, delay-dependent stability and consensus conditions for systems with time-varying delays usually depend only on the maximal delay Tij. Since larger delays usually deteriorate consensus properties, time-varying delays often lead to conservative conditions for rendezvous. This is shown in an example in Section 5.4.3. Distributed delays A compromise between accurate time-varying delay models and less conservative consensus conditions are distributed delays, where the delay operator is Tij(yj,t) = ∫ Tij 0 φij(η)yj(t− η)dη. (2.16) The output Tij(yj,t) of a distributed delay channel depends on the weighted average of the input yj(η) in the interval η ∈ [t−Tij, t]. The weighting function is the delay kernel φij : R → R that satisfies φij(η) ≥ 0 for all η ∈ [0,Tij ] and ∫ Tij 0 φij(η)dη = 1. It has been shown in Michiels et al. (2005) that fast time-varying delays can be approximated 18 2.6 Delay Models by distributed delay with an appropriate kernel φij . Moreover, the resulting distributed delay model may lead to less conservative stability conditions than the time-varying delay model, e.g. Michiels et al. (2005). We have shown in Münz et al. (2009b) that distributed delays are also a suitable model for continuous streams of packets in PSCN. In this context, φij(η) describes the probability density that a packet is delayed by η, which in turn implies ∫ Tij 0 φij(η)dη = 1. Similarly, distributed delays are often used to model stochastic delays, e.g. the reproduction delay in population dynamics (Cushing, 1977). We will show in Chapter 5 that delay-dependent rendezvous conditions for MAS on PSCN modeled with distributed delays depend on the average delay τ ij = ∫ Tij 0 ηφij(η)dη of the communication link. Yet, the same condition depends on the maximal delay Tij if the PSCN is modeled with time-varying delays. Hence, distributed delay models may lead to less conservative conditions than time-varying delay models, see also the example in Section 5.4.3. Distributed delays (2.16) can also be interpreted as a convolution between φij and the elements of yj. Thus, they also describe networks with general linear, time-invariant (LTI) channel dynamics. This interpretation is particularly suited for propagation de- lays, e.g. in power networks. In this context, φij is the impulse response of the channel. Modeling delays in networks This short presentation of the different delay models already indicated for what kind of delays these models are adequate. In general, the analysis based on constant delays is suitable if the delays are indeed constant or only slowly time-varying. This is however not the case in many MAS with delays where the delays are often randomly time-varying. For these MAS, delay robustness analysis for constant delays can be used as a first indicator about the delay robustness of the MAS with time-varying delays because constant delays are a special case of time-varying de- lays. Yet, a correct delay robustness analysis can only be obtained using time-varying delay models. However, time-varying delays lead often to quite conservative results. Therefore, distributed delays are preferable if consecutive time-delays are uncorrelated and if the distribution of the time-varying delays is known. In these cases, the delay ro- bustness analysis based on distributed delay models is usually less conservative than the analysis based on time-varying delays. In view of these advantages and disadvantages of the different delay models, it is a major advantages of the results presented in Chapter 4 and 5 that they apply equally to all three delay models. Especially, the conditions in Chapter 5 show the influence of the different delay models on the delay robustness. Most publications on stability analysis and control of time-delay systems consider constant delays, see for example (Gu, 2003; Jarlebring, 2008; Gouaisbaut and Peaucelle, 2006; Münz et al., 2009a, 2007a; Haag et al., 2009; Maier et al., 2010; Mahboobi Esfan- jani et al., 2009), less results are available for time-varying and distributed delays, e.g. (Fridman et al., 2004; Mehdi et al., 2002; Gu et al., 2003; Morărescu et al., 2007; Michiels et al., 2005; Münz et al., 2009f, 2008c; Münz and Allgöwer, 2007; Goebel et al., 2010), see also Niculescu (2001); Gu et al. (2003); Richard (2003); Michiels and Niculescu (2007); Loiseau et al. (2009) and references therein. Considering the literature on MAS, there are only few publications on delay robustness. A detailed overview has been given in 19 Chapter 2 Problem Statement the Introduction. Most publications deal with constant delay models, e.g. Olfati-Saber and Murray (2004); Moreau (2004); Papachristodoulou and Jadbabaie (2006); Chopra and Spong (2006). Time-varying and distributed delays are only considered in very rare publications (Bliman and Ferrari-Trecate, 2008; Yang et al., 2008; Michiels et al., 2009). MAS with general LTI channels have been considered in Wang and Elia (2008); Lestas and Vinnicombe (2007b). 2.7 Summary In this chapter, we have introduced the setup of the cooperative control tasks considered in this thesis. We presented all parts of the multi-agent system: the agent dynamics, the network topology, the feedback interconnection, and different cooperative control tasks. Moreover, we provided a detailed motivation and description of the different delay models considered in this thesis. 20 Chapter 3 Linear Multi-Agent Systems In this chapter, we develop a method to analyse the delay robustness of consensus and flocking algorithms in linear multi-agent systems (MAS). We investigate and compare different feedback delay configurations. Using this method, we study the delay robustness of several special cases, like single integrator MAS. We start with an introduction of the agent dynamics and different feedback delay configurations in Section 3.1. In Section 3.2, we recall consensus conditions for the undelayed MAS. Then, we investigate if the different feedback delay configurations have consensus and flocking solutions in Section 3.3. The main result of this chapter is presented in Section 3.4: a method to analyse the delay robustness of consensus and flocking in linear MAS. The following sections consider special cases of linear MAS: In Section 3.5, we apply this method to single integrator MAS. In Section 3.6, we investigate the delay robustness of a class of relative degree two MAS. A consensus controller design algorithm is presented in Section 3.7. Finally, we analyse the convergence rate of linear single integrator MAS in Section 3.8. A summary is given in Section 3.9. Preliminary results of this chapter have been published in Münz et al. (2010c, 2009c,e). 3.1 Agent Dynamics and Delay-Interconnection Matrices 3.1.1 Agent Dynamics In this chapter, we consider MAS consisting of N linear, single-input, single-output (SISO) agents described by strictly proper transfer functions Hi(s) Yi(s) = Hi(s)Ui(s) = νi(s) δi(s) Ui(s), i ∈ N = {1, 2, . . . , N}, (3.1) where Ui(s) and Yi(s) are the Laplace transform of the input ui(t) and output yi(t) of agent i, see (2.1a), (2.2). These agent dynamics include the most typical MAS models like single or double integrator MAS as special case. We assume the following on Hi: Assumption 3.1. The numerator polynomials νi(s) = νi0 + νi1s+ . . .+ νiñis ñi , νil ∈ R, for all l = 1, . . . , ñi, and denominator polynomials δi(s) = δi0+δi1s+. . .+δinis ni , δil ∈ R, for all l = 1, . . . , ni, of the rational transfer functions Hi(s) = νi(s) δi(s) satisfy the following: • all polynomials δi(s), i ∈ N , have a root at the origin, possibly with multiplicity larger than one; 21 Chapter 3 Linear Multi-Agent Systems • νi(s) and δi(s) are coprime and the transfer functions Hi(s) are strictly proper, i.e. ni > ñi; and • δi(s) + %νi(s) is Hurwitz for all i ∈ N and for all % ∈ (0, 2], which implies that all nonzero roots of δi(s) are in the open left half plane C −. We briefly motivate these assumptions. The main focus of this chapter are consensus problems, i.e. the output differences yi(t) − yj(t) vanish over time. This is trivially satisfied without any coupling if all agents are asymptotically stable, i.e. all outputs yi(t) converge to the origin. In order to exclude this trivial consensus problem, we as- sume that the polynomials δi(s) have a root at the origin. Therefore, the agents are not asymptotically stable. If this zero root is a single root, all outputs yi(t) eventually approach constant, in general nonzero values if ui(t) ≡ 0, for all i ∈ N . The cooperative control objective is that all outputs end up at the same value. Similar arguments apply for multiple poles at the origin, see also Section 3.3. The second item in Assumption 3.1 is not restrictive because we consider controllable and observable agent dynamics. In this case, there always exists a transfer function with coprime νi(s) and δi(s). More- over, we assume that the transfer functions Hi are strictly proper which is necessary in the undelayed case in order to exclude algebraic loops in the output interconnection described below. Finally, the Hurwitz assumption on δi(s)+ %νi(s), % ∈ (0, 2], in the last item guarantees that consensus is achieved in MAS (3.1) without delays and arbitrary topology, which is shown in Lemma 3.2 below. This also implies that all modes of each agent are asymptotically stable, except for those modes with zero eigenvalue. 3.1.2 Delay-Interconnection Matrices In this chapter, we investigate output consensus and flocking conditions for MAS (3.1) as defined in Definition 2.1 and 2.3, i.e. the aim of the MAS is lim t→∞ ‖yi(t)− yj(t)‖ = 0, for all i, j. (3.2) For simplicity of presentation, we often say consensus in this chapter when referring to consensus or flocking. In order to achieve consensus, the agents exchange their outputs yi using a network with constant, undirected, connected topology with symmetric weights aij = aji, i.e. the adjacency matrix of the underlying graph is symmetric A = AT . Since the graph is connected, all agents have at least one neighbour, i.e. the degree of each node is di > 0. We investigate and compare three cases how delays affect the coupling 22 3.1 Agent Dynamics and Delay-Interconnection Matrices between the agents. The corresponding interconnections are denoted without self-delay ui(t) = − N∑ j=1 aij di (yi(t)− yj(t− τij)), (3.3a) with identical self-delay ui(t) = − N∑ j=1 aij di (yi(t− τij)− yj(t− τij)), (3.3b) with different self-delay ui(t) = − N∑ j=1 aij di (yi(t− Tij)− yj(t− τij)), (3.3c) where we focus on constant time-delays. Since time-varying delays cannot be trans- formed into the Laplace domain, the derived conditions are not applicable for MAS with time-varying delays. We will briefly explain in the Conclusions of this thesis how the results of this chapter can be extended to analyse MAS with distributed delays. We denote MAS (3.1) with interconnection (3.3a) MAS without self-delay , with interconnec- tion (3.3b) MAS with identical self-delay , and with interconnection (3.3c) as MAS with different self-delay . Note that (3.3c) includes (3.3b) for Tij = τij and (3.3a) for Tij = 0 as special cases. Later on, we will in fact differentiate between four cases because we obtain different conditions for MAS with symmetric identical self-delay τij = τji, for all i, j and with asymmetric identical self-delay τij 6= τji for some i, j. Now, we can introduce the initial condition of the MAS with agents (3.1) and inter- connection (3.3): ϕ ∈ C∑ni = C([−T , 0],R ∑ ni), see also Section 2.1. We assume that ϕ is continuous. In order to transform the interconnections (3.3) in the Laplace domain, we define the delay-dependent adjacency and degree matrices Aτ (s) = [ aije −τijs] , Dτ (s) = diag   N∑ j=1 aije −τijs   , DT (s) = diag   N∑ j=1 aije −Tijs   . (3.4) Note that Aτ ,Dτ , andDT contain the full information about network properties topology and delay. Now, we can define the delay-interconnection matrices Γr : C → C N×N , r = 1, 2, 3, 4, that result from the Laplace transform of the interconnections (3.3): without self-delay U(s) = −Γ1(s)Y (s) = −(I −D−1Aτ (s))Y (s), (3.5a) with identical self-delay U(s) = −Γ2(s)Y (s) = −D−1Lτ (s)Y (s), (3.5b) with different self-delay U(s) = −Γ3(s)Y (s) = −D−1LτT (s)Y (s), (3.5c) with symmetric identical self-delay U(s) = −Γ4(s)Y (s) = −D−1Lτ (s)Y (s), (3.5d) i.e. τij = τji, where U(s) = [U1(s), . . . , UN (s)] T , Y (s) = [Y1(s), . . . , YN (s)] T , Lτ (s) = Dτ (s) − Aτ (s), LτT (s) = DT (s) − Aτ (s) and D = diag(di). The only difference between Γ2 and Γ4 is 23 Chapter 3 Linear Multi-Agent Systems that Γ4 requires symmetric delays τij = τji and Γ2 allows also for asymmetric delays. This distinction will become important later on. An important feature of the feedback matrices Γr is the right eigenvector 1 = [1 1 . . . 1]T . Note that Γr(0)1 = 0 for r = 1, 2, 3, 4, and (3.6a) Γr(s)1 = 0 for all s ∈ C, r = 2, 4. (3.6b) Yet, Γr(s)1 = 0 for all s ∈ C and for r = 1, 3 is not true in general. This already indicates a fundamental difference between MAS with identical self-delay, i.e. Γ2,Γ4, and MAS without or with different self-delay, i.e. Γ1,Γ3, which will be further investigated in Section 3.3. In Section 3.4, we develop a methodology to analyse the consensus properties of general linear MAS (3.1) with interconnections (3.5). The method is based on the generalized Nyquist criterion (Desoer and Wang, 1980) and provides sufficient set-valued conditions. This approach allows for a detailed comparison of the different delay configurations. 3.2 Consensus of Undelayed Multi-Agent Systems Before we study the consensus problem of MAS with delays, we want to recall the consensus properties of MAS with identical agents and without delay, i.e. with Hi(s) = H(s) = ν(s) δ(s) and interconnection matrix Γ0 = L = I −D−1A. This MAS corresponds to (3.1) with interconnection (3.5) with zero delay τij = Tij = 0 for all i, j. This consensus problem has been studied previously in Fax and Murray (2004); Wieland et al. (2008, 2010); Ren and Beard (2008) and is presented here for completeness. The characteristic polynomial of the closed loop system is ∆0(s) = det ( δ(s) + ν(s)L ) = N∏ l=1 ( δ(s) + ν(s)λl(L) ) , (3.7) where λl(L) are the eigenvalues of L such that 0 = λ1(L) < λ2(L) ≤ . . . ≤ λN (L). Since the graph is undirected and connected, all eigenvalues of L are real, see Appendix B, and λ2(L) > 0. The largest eigenvalue of the normalized Laplacian matrix satisfies λN (L) ≤ 2. This can be shown using Gershgorin’s circle theorem, see Horn and Johnson (1985) for example, and noting that all diagonal elements of L are 1 and the row elements sum up to zero. The eigenvector of L corresponding to λ1(L) = 0 is 1, see Appendix B, which corresponds to the consensus solutions with y1(t) = y2(t) = . . . = yN (t). The attractivity of this consensus solution depends only on the nonzero eigenvalues of L. Sufficient conditions for reaching consensus asymptotically without delays are provided in the next lemma. Lemma 3.2 (Consensus of undelayed MAS). Consider a MAS consisting of agents dynamics (3.1) with identical dynamics Hi(s) = H(s) and symmetric interconnection matrix without delays Γ0 = L = I −D−1A. This MAS achieves consensus for arbitrary, undirected, connected topologies if δ(s) + %ν(s) is Hurwitz for all % ∈ (0, 2]. 24 3.3 Consensus and Flocking Solutions Proof. As we are interested in the convergence toward the consensus set, we only consider the nonzero eigenvalues of L. Thus, the MAS achieves consensus if and only if N∏ l=2 ( δ(s) + ν(s)λl(L) ) 6= 0. for all s with Re{s} ≥ 0. Since λl(L) ∈ (0, 2], δ(s) + %ν(s), % ∈ (0, 2], being Hurwitz guarantees consensus. In Lemma 3.2, consensus has to hold for arbitrary large networks with arbitrary topologies. For arbitrary t