Consensus Protocols - Introduction, Applications, and Analysis

Consensus protocols Prof. Tamara Petrović Prof. Đula Nađ Prof. Stjepan Bogdan Ana Milas, Marijana Peti, Marko Križmančić Grading system ▪ Midterm exam (obligatory) - 20 points (must get 5 to pass) ▪ Project (1st part) – 30 points ▪ Project (2nd part) –...

Consensus protocols Prof. Tamara Petrović Prof. Đula Nađ Prof. Stjepan Bogdan Ana Milas, Marijana Peti, Marko Križmančić Grading system ▪ Midterm exam (obligatory) - 20 points (must get 5 to pass) ▪ Project (1st part) – 30 points ▪ Project (2nd part) – 30 points ▪ Final exam – 20 points ▪ For students that fail to get >50 points (or want better grade) ▪ written exam - 80 points Grades 2 – [51 - 61] 3 – [62 - 77] 4 – [78 - 90] 5 – [91 - 100] 2 Literature Ren, Wei, and Randal W. Beard. Distributed consensus in multi-vehicle cooperative control. Vol. 27. No. 2. London: Springer London, 2008. Mesbahi, Mehran, and Magnus Egerstedt. "Graph theoretic methods in multiagent networks." Graph Theoretic Methods in Multiagent Networks. Princeton University Press, 2010. Olfati-Saber, Reza, J. Alex Fax, and Richard M. Murray. "Consensus and cooperation in networked multi-agent systems." Proceedings of the IEEE 95.1 (2007): 215-233. 3 Introduction In network of agents, consensus means to reach an agreement regarding a certain quantity of interest that depends on the state of all agents. A consensus (agreement) protocol = interaction rule that specifies information exchange among agents 4 Example application heterogenous marine monitoring – distributed sensing, acoustic communication 5 Example application Formation control 6  Local Agent Interaction 1. Local communication Limited range, bandwith 2. Local sensing Limited sensor FoV Graph-based interaction modelling Interactions as edges Directed vs. Undirected Static vs. Dynamic (switching)  Consensus Protocol 𝑛 vehicles - communication topology defined with graph 𝐺𝑛 = 𝑉𝑛 , 𝐸𝑛 Vehicle state 𝑥𝑖 𝑡 , 𝑥𝑖 (0) Single integrator dynamics: 𝑥ሶ 𝑖 = 𝑢𝑖 Consensus protocol: 𝑛 𝑥ሶ 𝑖 𝑡 = ෍ 𝑎𝑖𝑗 𝑡 [𝑥𝑗 𝑡 − 𝑥𝑖 𝑡 ], 𝑖 = 1, … , 𝑛 𝑗=1 𝑎𝑖𝑗 - elements of adjacency matrix for 𝐺𝑛 Consensus is reached if ∀𝑥𝑖 (0) and ∀𝑖, 𝑗 ∈ 1, … , 𝑛 , 𝑥𝑗 (𝑡) − 𝑥𝑖 (𝑡) → 0 as 𝑡 → ∞ limites (voir graphe) Consensus Protocol  Rendezvous problem In the rendezvous application, multiple mobile robots simultaneously arrive at a common a priori unknown location determined through team negotiation 𝑟𝑖 = [𝑥𝑖 , 𝑦𝑖 ]𝑇 ∈ 𝑅2 𝑛 𝑟𝑖ሶ = ෍ 𝑎𝑖𝑗 (𝑟𝑗 − 𝑟𝑖 ) 𝑗=1 Rendezvous problem  Graph Theory Recap Directed graph 𝑉𝑝 , 𝐸𝑝 , 𝑉𝑃 = {1, … , 𝑝} , 𝐸𝑝 ⊆ 𝑉𝑝 × 𝑉𝑝 edge 𝑖, 𝑗 ∈ 𝐸𝑝 - vehicle 𝑗 can obtain info from vehicle 𝑖 𝑁𝑗 - neighbor set of vehicle 𝑗 2 Undirected graph edge 𝑖, 𝑗 ∈ 𝐸𝑝 - both directions 1 3 5 4  Graph Theory Recap Adjacency matrix 𝐴 = 𝑎𝑖𝑗 ∈ 𝑅𝑝×𝑝 𝑎𝑖𝑗 > 0 𝑖𝑓 𝑗, 𝑖 ∈ 𝐸𝑝 , 𝑎𝑖𝑗 = 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑎𝑖𝑗 - weight for the edge (𝑗, 𝑖) (or 1 if weight is not relevant) Balanced graph 𝑝 𝑝 σ𝑗=1 𝑎𝑖𝑗 = σ𝑗=1 𝑎𝑗𝑖 , ∀𝑖 ∈ 𝑉𝑝 every undirected graph is balanced  Graph Theory Recap Laplacian matrix 𝐿 = 𝑙𝑖𝑗 ∈ 𝑅𝑝×𝑝 𝑝 𝑙𝑖𝑖 = ෍ 𝑎𝑖𝑗 , 𝑙𝑖𝑗 = −𝑎𝑖𝑗 , 𝑖 ≠ 𝑗 𝑗=1,𝑗≠𝑖 Laplacian has the following property: 𝑝 ෍ 𝑙𝑖𝑗 = 0, 𝑖 = 1, … , 𝑝 𝑗=1 For undirected graphs Laplacian is symmetrical  Graph Theory Recap Connected graph Undirected graph is connected if there is a path between each two nodes Strongly connected graph Directed graph is strongly connected if there is a path between each two nodes Directed tree Directed graph where each node has exactly one parent (except for the root node) Spanning tree Subgraph 𝑉𝑝𝑠 , 𝐸𝑝𝑠 of a directed graph 𝑉𝑝 , 𝐸𝑝 that is a directed tree, and it holds that 𝑉𝑝 = 𝑉𝑝𝑠 Directed graph 𝑉𝑝 , 𝐸𝑝 has a spanning tree if and only if it has at least one node with a directed path to all other nodes Consensus Protocol – Convergence Analysis Static communication topology Undirected topology 𝐺𝑛 System reaches consensus if and only if 𝐺𝑛 is connected Directed topology 𝐺𝑛 System reaches consensus if and only if 𝐺𝑛 has a directed spanning tree Consensus Protocol – Convergence Analysis Static communication topology Derivation of the convergence condition for the undirected case: 𝑥ሶ 𝑡 = −𝐿𝑥(𝑡) 𝑥 𝑡 = 𝑒 −𝐿𝑡 𝑥 0 Laplacian eigenvalues 𝜆1 , 𝜆2 , … , 𝜆𝑛 , corresponding normalized eigenvectors 𝜈1 , 𝜈2 , … , 𝜈𝑛 ∈ 𝑅𝑛 By using spectral factorization of Laplacian we can get: 𝑥 𝑡 = 𝑒 −𝜆1 𝑡 𝑣1 𝜈1𝑇 𝑥 0 + 𝑒 −𝜆2 𝑡 𝑣2 𝜈2𝑇 𝑥 0 + ⋯ + 𝑒 −𝜆𝑛 𝑡 𝑣𝑛 𝜈𝑛𝑇 𝑥 0 If 𝐺𝑛 is connected, 0 = 𝜆1 ≤ 𝜆2 ≤ ⋯ ≤ 𝜆𝑛 so we can conclude: a) 𝑥 𝑡 𝑐𝑜𝑛𝑣𝑒𝑟𝑔𝑒𝑠, 𝑎𝑠 𝑡 → ∞ b) convergence speed is determined mainly with 𝜆2 (algebraic connectivity Similar procedure & conclusions can be made for the directed case Consensus protocol – Consensus Value Static communication topology If the protocol is reaching consensus, what is the equilibrium state? Undirected case 1 If 𝐺𝑛 is connected, average consensus is reached 𝑥𝑖 𝑡 → σ𝑛𝑗=1 𝑥𝑖 0 𝑛 Directed case If 𝐺𝑛 has a spanning tree consensus value is 𝑥𝑖 𝑡 → σ𝑗 𝑤1𝑗 𝑥 0 𝑤1 normalized left eigenvector corresponding to 𝜆1 = 0 If and only if 𝐺𝑛 is strongly connected and balanced, average consensus is reached Rendezvous problem Rendezvous problem Ren, Wei, and Randal W. Beard. Distributed consensus in multi-vehicle cooperative control. Vol. 27. No. 2. London: Springer London, 2008. Consensus protocol - Convergence analysis Switching communication topology Realistic for multi robot systems, unreliable communication etc. consensus is asymptotically reached if there exist an (infinite) sequence of connected time-intervals such that the union of communication graphs 𝐺𝑛 during each interval is connected/has a spanning tree For multi-robot system it is important that the network is repeatedly reconnected  Rendezvous problem Random switching between the topologies → union of graphs will be reconnected over time → consensus will be reached  Discrete form of consensus Difference equation: 𝑥 𝑘 + 1 = 𝑥 𝑘 + 𝜖 σ𝑛𝑗=1 𝑎𝑖𝑗 (𝑥𝑗 (𝑘) − 𝑥𝑖 (𝑘)) or: 𝑥 𝑘 + 1 = 𝑃𝑥 𝑘 , 𝑃 = 𝐼 − 𝜖𝐿 𝜖 – step size 𝑃 - Perron matrix of graph 𝐺𝑛 the major conclusions regarding convergence hold also for the discrete case  Discrete form of consensus Alternative form of discrete consensus (one of many): 𝑛 1 𝑥𝑖 𝑘 + 1 = 𝑥𝑖 𝑘 + ෍ 𝑎𝑖𝑗 (𝑥𝑗 𝑘 − 𝑥𝑖 𝑘 ) 1 + 𝑑𝑖 𝑗=1 Where 𝑑𝑖 equals to outdegree of node 𝑖. Matrix form: 𝑥 𝑘+1 = 𝐼+𝐷 −1 𝐼+𝐴 𝑥 𝑘  Formation control with consensus How to specify a formation? Feasible formation 𝐷 = {𝑑𝑖𝑗 ∈ 𝑅 | 𝑑𝑖𝑗 > 0, 𝑖, 𝑗 = 1, … , 𝑛, 𝑖 ≠ 𝑗} s.t. 𝑑𝑖𝑗 - distance between vehicles in formation ∃𝜉1 , … , 𝜉𝑛 ∈ 𝑅𝑝 , 𝜉𝑖 − 𝜉𝑗 = 𝑑𝑖𝑗 ∀𝑖, 𝑗 𝜉𝑖 - position of vehicle 𝑖 Scale invariant formation 𝐷′ = 𝛼𝐷 Translationally invariant formation (rotationally not invariant) Ξ = {𝜉1 , … , 𝜉𝑛 } ∈ 𝑅𝑝 s.t. 𝑥𝑖 = 𝜉𝑖 + 𝜏 𝜏 – arbitrary translation, 𝜏 ∈ 𝑅𝑝  Formation control with consensus Formation: {𝜉1 , … , 𝜉𝑛 } ∈ 𝑅𝑝 𝑠. 𝑡. 𝑥𝑖 = 𝜉𝑖 + 𝜏 Derivation from formation positions: 𝜏𝑖 𝑡 = 𝑥𝑖 𝑡 − 𝜉𝑖 𝑡 → we want agents to agree on this value, hence: 𝑛 𝜏𝑖ሶ 𝑡 = ෍ 𝑎𝑖𝑗 (𝜏𝑗 𝑡 − 𝜏𝑖 (𝑡)) → 𝑗=1 𝑛 𝑥ሶ 𝑖 𝑡 = ෍ 𝑎𝑖𝑗 [ 𝑥𝑗 𝑡 − 𝑥𝑖 𝑡 − (𝜉𝑗 𝑡 − 𝜉𝑖 (𝑡))] 𝑗=1 Formation with a virtual leader: Leader - one vehicle in the formation (connected to other vehicles) that does not run consensus protocol  Pinning control Introducing leader agent 𝑥𝑜 , which is an uncontrolled (stubborn) agent 𝑥ሶ 0 = 0 Leader is pinned (connected) to (possibly only a fraction) of all the agents Continuous form of consensus with a pinned leader: 𝑛 𝑥ሶ 𝑖 𝑡 = ෍ 𝑎𝑖𝑗 𝑡 [𝑥𝑗 𝑡 − 𝑥𝑖 𝑡 ] + 𝑔𝑖 (𝑥0 − 𝑥𝑖 ), 𝑖 = 1, … , 𝑛 𝑗=1 Where 𝑔𝑖 represents pinning gains (𝑔𝑖 > 0 if leader is directly connected to agent 𝑖) Discrete form: 𝑛 1 𝑥𝑖 𝑘 + 1 = [𝑥𝑖 𝑘 + ෍ 𝑎𝑖𝑗 𝑥𝑗 𝑘 + 𝑔𝑖 𝑥0 ], 𝑖 = 1, … , 𝑛 1 + 𝑑𝑖 + 𝑔𝑖 𝑗=1  Different consensus protocols Consensus over acoustic network B. Arbanas, T. Petrovic and S. Bogdan, "Consensus Protocol for Underwater Multi-Robot System Using Scheduled Acoustic Communication," 2018 OCEANS - MTS/IEEE Kobe Techno-Oceans (OTO), 2018, pp. 1-5,. Median consensus for tracking different values G. Vasiljević, T. Petrović, B. Arbanas and S. Bogdan, "Dynamic Median Consensus for Marine Multi-Robot Systems Using Acoustic Communication," in IEEE Robotics and Automation Letters, vol. 5, no. 4, Oct. 2020 Trust based consensus Haus, T., Palunko, I., Tolić, D., Bogdan, S., Lewis, F. L., & Mikulski, D. G. (2014). Trust‐based self‐organising network control. IET Control Theory & Applications, 8(18), 2126-2135. Questions? 30