2012-IJC-Constrained Agreement Protocols for Tree Graph Topologies

This article was downloaded by: [Peking University]On: 21 March 2012, At: 08:13Publisher: Taylor & FrancisInforma Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 37-41 Mortimer Street, London W1T 3JH, UKInternational Journal of ControlPublication details, including instructions for authors and subscription information:/loi/tcon20Constrained agreement protocols for tree graphtopologiesRahul Chipalkatty a & Magnus Egerstedt aa Georgia Institute of T echnology, Atlanta, GA 30332, USAAvailable online: 07 Feb 2012PLEASE SCROLL DOWN FOR ARTICLEInternational Journal of Control 2012,1–18,iFirstConstrained agreement protocols for tree graph topologiesRahul Chipalkatty *and Magnus EgerstedtGeorgia Institute of Technology,Atlanta,GA 30332,USA (Received 11March 2011;final version received 7January 2012)This article presents a novel way of manipulating the initial conditions in the consensus equation such that a constrained agreement problem is solved across a distributed network of agents,particularly for a network represented by a tree graph.The presented method is applied to the problem of coordinating multiple pendula attached to mobile bases.The pendula should move in such a way that their motion is synchronised,which calls for a constrained optimal control problem for each pendulum as well as the constrained agreement problem across the network.Simulation results are presented that support the viability of the proposed approach as well as a hardware demonstration.Keywords:consensus algorithm;optimal control;graph-based multi-agent control;constrained agreement protocol1.IntroductionThe agreement protocol (or consensus equation)has by now emerged as a standard way to achieve agreement among agents in a distributed network.It can be utilised for anything from agreement in embedded physical systems like mobile robots or UAVs,to distributed computer networks, e.g.Tanner,Jadbabaie,and Pappas (2000),Ren and Beard (2004),Dimarogonas and Kyriakopoulos (2007),Olfati-Saber and Murray (2003),Jadbabaie,Lin,and Morse (2003)and Mesbahi and Egerstedt (2010).And,as the value on which the agents agree is dependent on the agents’initial conditions,it is not overly surprising that this dependency can be employed such that the final agreement state is guaranteed to satisfy certain constraints.This work seeks to address the problem of finding an agreement state that satisfies a global state con-straint given only local interactions among distributed agents.Specifically,within a group of agents,con-straints exist between certain pairs of agents together with an information exchange,resulting in what is referred to in this article as pairwise constraints.The pairwise constraints naturally lead to a network topology where nodes represent agents and edges represent pairwise constraints and information exchange.The pairwise constraints that involve a particular agent are called that agent’s local constraints and this particular agent only exchanges information with the agents with which it shares a pairwise constraint,hence the ‘local’descriptor.Subsequently,the global con-straint for the entire group is the constraint that all agents satisfy their respective local constraints.Each agent can communicate its own state as well as its ‘opinion’of what the other agents’states should be (i.e.state opinions)such that the entire network’s pairwise constraints are met.As such,the goal of this work is to utilise the consensus equation to arrive at an agreement on the state opinions of every agent in the network such that every pairwise constraint in the network is satisfied (global constraint)given that only the local constraints are initially satisfied.We apply this constrained agreement protocol to the problem of controlling a collection of cart-driven pendula in a coordinated fashion.In particular,their mobile bases are to be controlled in such a way that,at some specified terminal time,they move in unison (with the same frequency and phase)at a fixed inter-pendula distance.This should be achieved using only local information,i.e.the control actions are only to be controlled based on information from neighbouring pendula.The problem is ensuring that the agreement proto-col results in final state opinions for all pendula such that these final states satisfy the global constraint.Although running the standard consensus equation (e.g.Jadbabaie et al.2003;Olfati-Saber and Murray 2003)–or versions of the gossip algorithm Boyd,*Corresponding author.Email:chipalkatty@ISSN 0020–7179print/ISSN 1366–5820online ß2012Taylor &Francis/10.1080/00207179.2012.656288D o w n l o a d e d b y [P e k i n g U n i v e r s i t y ] a t 08:13 21 M a r c h 2012Ghosh,Prabhakar,and Shah (2005)and Xiao,Boyd,and Lall (2005)–will result in an agreement,the agreed upon states are not guaranteed to satisfy the global constraint.However,in this work,we will demonstrate that the initial conditions for the agreement protocol can be manipulated such that the resulting state opinions will satisfy the global constraints.Relevant work on agreement protocols for systems with oscil-lating dynamics include (Jadbabaie,Motee,and Barahona 2004).The authors investigate the stability of the Kuromoto model for coupled nonlinear oscilla-tors;however,they do not address constraints on the agreement state.Although optimal control techniques are used in the control formulation presented in this article,the problem is,at heart,a distributed agreement problem rather than a distributed optimal control problem.For more on the latter problem see,for example,Rotkowitz and Lall (2006),Motee and Jadbabaie (2008),Bamieh,Paganini,and Dahleh (2002),Rantzer (2009)and the references therein.These works seek to solve distributive optimal control problems over a network while the work presented in this article simply utilises optimal control to drive the system to a desired state as determined through an agreement protocol.Any form of control could,in principle,have been used here.However,optimal control provides an effective method for solving the types of constrained problems under consideration in this article.Relevant works on constrained agreement proto-cols include Moore and Lucarelli (2005)and Nedic,Ozdaglar,and Parrilo (2008).Moore and Lucarelli (2005)address the problem of leader-driven agreement where the agreement state can be driven to a set-point and thus agreement states can be driven to satisfy hard constraints.In Nedic et al.(2008),the authors present agreement protocols where the agreed upon states are constrained to lie in a convex set.In both of these works,the resulting algorithms require that the con-sensus update law be modified over time with time-varying weights.In contrast to this,Chipalkatty,Egerstedt,and Azuma (2009)presents a simple,static update law for achieving agreement while satisfying the constraints for a line topology network.In this article,we will present a novel method of using a static update law to satisfy global constraints over not just a line topology,but any arbitrary directed tree graph topol-ogy.The novelty of this method is that it only requires a priori knowledge of the graph topology and local information exchange to initialise the agreement state.This results in a static update law,using local infor-mation,to reach an agreement state that satisfies a global constraint.We will also present the viability of this approach through both simulation and hardware demonstration.The outline of this article is as follows:in Section 2,we introduce the distributed network of agents and its constraints,followed by a discussion in Section 3about the constrained consensus problem.In Section 4,we show how selecting the initial conditions appropriately leads to an agreement state that satisfies the global constraints and in Sections 5and 6,we show how this method is applied to the networked pendulum exam-ple.Simulation results are presented in both Sections 5and 6as well as hardware results in Section 5.2.Problem formulation 2.1NotationA graph,G ,is defined by a node set,V ¼{1,2,3,...,N }of N nodes and an edge set E &V ÂV of unordered node pairs.Two nodes,i and j ,are adjacent,or neighbours,if (i ,j )2E .The neighbourhood set of a node i 2V ,N i ,is the set of nodes j 2V adjacent to node i .A tree graph is a specific type of graph in which there exists only one path from a particular node to any other node in the graph.Note that for tree graphs,the number of edges,M ,in the graph is given by M ¼N À1.Edges can be given an orientation using :E !{À1,1},resulting in a directed graph,G ,for which an associated incidence matrix,D ¼[D ij ]2R N ÂM ,has elements given byD ij ¼1if vertex i is the tail of edge j ,À1if vertex i is the head of edge j ,0otherwise,8><>:ð1Þfor i ¼1,...,N and j ¼1,...,M .2.2Multi-agent networkThe multi-agent network in this article is modelled by atree graph,G ¼(V ,E )where the N nodes correspond to N agents.The M edges of the network correspond to information exchange between agents as well as a pairwise constraint.Each edge is assigned an arbitrary orientation,as given by ,resulting in an associated incidence matrix,D .Note,however,that the graph is still an undirected one,so the information exchange is undirected.Representing the network through an incidence matrix is key here because the incidence matrix will be utilised to construct formal definitions of the local and global constraints.In order to illustrate the operations used later,an example network is presented and the prescribed operations will be performed on this network through-out this article.2.2.1Example graphThe example tree graph,^G¼ð^V ,^E Þwith ^V ¼f 1,2,3,4,5g and ^E¼{(1,2),(1,4),(4,3),(4,5)},is given 2R.Chipalkatty and M.EgerstedtD o w n l o a d e d b y [P e k i n g U n i v e r s i t y ] a t 08:13 21 M a r c h 2012with arbitrary edge orientations as presented inFigure 1.The corresponding incidence matrix,^D,is ^D ¼1100À100000À100À111000À12666666437777775:ð2Þ2.3States and opinionsEach agent in the network has an associated state and we let x ii 2R l denote agent i ’s state for all i 2V .The double indices are used here to denote agent i ’s opinion of itself,which coincides with its state,and this notation is now used again to denote an agent’s opinions of other agents.Each agent in the network will form a state opinion of all the other agents in the network and share those opinions with its neighbours.Let x ij (t )2R l be agent i ’s opinion of what agent j ’s state should be such that all the pairwise constraints in the network are satisfied (i.e.agent i ’s’state opinion of agent j ).The collection of these opinions is denoted by the state opinion vector,x i ,for each agent,where x i ¼[x i 1,...,x ii ,...x iN ]for all i 2V .A form of this vector will eventually become the quantity used in the proposed agreement protocol.2.4Pairwise constraintsLet each edge with arbitrary orientation denote an associated linear pairwise constraint on agents i and k for all nodes i ,k 2V where (i ,k )2E .This linear pairwise constraint between agents is defined asP ðx ii Àx kk Þ¼b ,ð3Þwith vertex i being the tail of the edge,b 2R p and P 2R p Âl .Note that P has full row rank.This particular form for the pairwise constraints was chosen because it is linear with respect to the difference in the agent’s states,allowing for relative constraints, e.g.for synchronising movement between the agents.2.5Constraint definitionGiven a pairwise constraint for every edge,the globalconstraint for the network is defined as the collection of all pairwise constraints and is satisfied when the state of every node in the network satisfies all pairwise constraints.An agent’s local constraints are defined as the set of all pairwise constraints it shares with its neighbours.When a particular node’s state satisfies all the pairwise constraints with its neighbours,this agent’s state satisfies its local constraints.The following is a discussion on how to construct the local constraints for each node and the global constraints for the network given the graph,G ,and the incidence matrix,D .Since the incidence matrix gives us a representation of all the edges in the network,the incidence matrix will first be utilised to construct an expression for the global constraint on the network.Let x g 2R lN be a state opinion vector such that all its state opinions satisfy all the pairwise constraints in the network.Then,the global constraint is defined asðD T P Þx g ¼1 b ,ð4Þwhere denotes the Kronecker product and 1is an M -dimensional vector with all entries being 1.From the example network G ,the global con-straint,(D T P )x g ¼1 b ,is satisfied if,for x g ¼[x 11,...,x 55]T ,P ÀP 000P 00ÀP 000ÀP P 0000P ÀP2666437775x 11x 22x 33x 44x 552666666437777775¼b b b b 2666437775:ð5ÞHere,since each row corresponds to an edge,this expression represents every pairwise constraint in the network.The following operations isolate the rows of the transposed incidence matrix that correspond to edges that node i is incident with and apply the pairwise constraints to these edges to arrive at an expression for the local constraints of agent i .For all i 2V ,we define the diagonal matrix,F i2R M ÂM ,whose m th diagonal element is 1if D im ¼0and 0otherwise,as well as the complement,F ic 2R M ÂM ,which is a diagonal matrix whose m th diagonal element is 0if D im ¼0and 1otherwise,for i ¼1,...,N and m ¼1,...,M .To illustrate this fur-ther,the F i and F ic matrices are shown for agent 4forthe example graph ^Gas ^F 4¼00000100001000012666437775,^F 4c ¼10000000000000002666437775:Figure 1.Tree graph example,^G.International Journal of Control3D o w n l o a d e d b y [P e k i n g U n i v e r s i t y ] a t 08:13 21 M a r c h 2012Note ^F4contains a 1in the column or row corre-sponding to the edges agent 4is incident with and viceversa for ^F4c Then,let T i 2R M ÂN be defined asT i ¼F i DTwith the compliment,T c i ,beingT c i ¼F ic D T :Note that F i þF ic ¼I ,where I is the M ÂM identity matrix.Again,the example is worked further to show the matrices resulting from these operations.T i and T c i for agent 4are^T 4¼00000100À1000À1100001À12666437775,^T c 4¼1À100000000000000002666437775:Lemma 2.1:Given matrices T i and T c i for every agent i in the network for i ¼1,...,N ,then T c i þT i ¼D T .Proof:T c i þT i ¼F i D T þF ic D T¼ðF i þF ic ÞD T ¼ID T ¼D T :œHere,the rows of T i 2R M ÂN encode only the edges that node i is incident with while the remaining rows have all elements as zero.Similarly,the rows of T c i encode the edges that vertex i is not incident with and edges incident with node i have all zero elements.Additionally,a vector is needed to equate the appropriate constraints in each row to b .In other words,each non-zero row in (T i P )x must equal b .The vector,f i ¼½f i m Mm ¼12R M ,is defined as having its m th element be 1if T im ¼0or 0otherwise,for i ¼1,...,N and m ¼1,...,M .Continuing with our example network,^f 4¼½0111 T .Lemma 2.2:Given the vector ,f i ,for every agent i in the network for i ¼1,...,N ,thenX N i ¼1f i ¼21:Proof:For every edge j in the network,there are two agents incident with that edge.Therefore,a 1will appear in the j -th element for two agents,resulting in a2in every element of the sum of f i ’s.œThe matrix,T i ,can now be used to define the local constraints on agent i .Let x i satisfy pairwise con-straints that involve agent i ,such thatðT i P Þx i ¼f i b ,ð6Þfor i ¼1,...,N .In other words,only the pairwise constraints agent i can satisfy are represented in (6).The local constraints for agent 4in the graph example ^G,would be satisfied if,for x 4¼[x 41,...,x 45]T ,ð^T4 P Þx 4¼^f 4 b or 00000P 00ÀP 000ÀP P 0000P ÀP2666437775x 41x 42x 43x 44x 452666666437777775¼0b b b 2666437775:Note that in the example,agents 2and 4are not neighbours so agent 4has no basis on which value to assign to x 42.Also note that this value is not required for agent 4’s local constraints to be satisfied.However,in order to utilise the consensus equation,these agents must assign state opinions to non-adjacent agents.In summary,each agent assigns a state opinion value to neighbours based on the initial state values communicated such that they meet the local con-straints,(6).Then,the consensus equation will be used to reach an agreement on what the state opinion vectors should be.This agreed upon state opinion vector needs to satisfy the global constraint,(4).So the problem,here,is to determine how each agent should initialise their state opinion vectors so that the global constraint is satisfied by the result of the consensus equation.3.Applying the consensus equationAgain,the goal of this work is to find a state opinionvector that satisfies the global constraint among distributed agents using only local interactions.In order to accomplish this,the consensus algorithm will be used to have the agents come to an agreement on such a state.It should be noted that each agent’s initial state opinions will satisfy the local constraints for that agent only.Recall x i is the quantity over which the consensus equation will run and it is desired that the resulting quantity satisfies the global constraint.For agents in the neighbourhood of agent i ,the initial state opinions are made based on the states of the agent as commu-nicated by those agents.However,for agents not in the neighbourhood of agent i ,state opinions are still required to construct the state opinions vector and utilise the consensus equation.However,the lack of4R.Chipalkatty and M.EgerstedtD o w n l o a d e d b y [P e k i n g U n i v e r s i t y ] a t 08:13 21 M a r c h 2012communication means that initialising the state opin-ion vector with state opinions for non-adjacent agents is a problem.The following section discusses how to deal with this problem by first simply setting these values to zero and showing why the resulting agree-ment state does not satisfy the global constraint.3.1Attempt 1:filling the state opinion vector with 0’sFor undirected connected graphs,the consensus equa-tion,as given by_x i ðt Þ¼ÀXk "N iðx i ðt ÞÀx k ðt ÞÞfor i ¼1,...,N ,ð7Þconverges to the invariant centroid,x c 2R Nl ,wherex c ¼1N X Ni ¼1x i ð0Þð8Þ(see,e.g.Mesbahi and Egerstedt 2010).Note that the consensus algorithm requires that agents communicate their state opinion vectors with their neighbours and vice versa.Suppose the initial state opinions of non-adjacent agents are simply set to ing the example graph,it will be shown that the resulting agreement state does not satisfy the global constraint although the initial conditions of each agent’s state opinion vector satisfy that agent’s local constraints.Let the initial state opinion vectors bex 1¼x 11x 120x 1402666666437777775,x 2¼x 21x 220002666666437777775,x 3¼00x 33x 3402666666437777775,x 4¼x 410x 43x 44x 452666666437777775,x 5¼000x 54x 552666666437777775:So,the resulting agreement state isx c ¼x 11þx 21þx415x 12þx 225x 33þx 435x 14þx 34þx 44þx 545x 45þx 555266666666666664377777777777775:ð9ÞGiven that the initial state opinion vectors satisfy the local constraints,ð^T 1 P Þx 1¼^f 1 b ¼Px 11ÀPx 12Px 11ÀPx 1402666437775¼b b 002666437775,ð10Þð^T 2 P Þx 2¼^f 2 b ¼Px 21ÀPx 22002666437775¼b 0002666437775,ð11Þð^T 3 P Þx 3¼^f 3 b ¼00Px 34ÀPx 3302666437775¼00b 02666437775,ð12Þð^T 4 P Þx 4¼^f 4 b ¼0Px 41ÀPx 44Px 44ÀPx 43Px 44ÀPx 452666437775¼0b b b2666437775,ð13Þandð^T 5 P Þx 5¼^f 5 b ¼000Px 54ÀPx 552666437775¼000b 2666437775:ð14ÞThe result of plugging values from the local constraints into the global constraint is thatð^D T P Þx c ¼25b þ1Px 41b þ12P ðx 21Àx 34Àx 54Þb þ12P ðx 14þx 54Þb þ12P ðx 14þx 34Þ266666666664377777777775¼b b b b 2666437775ð15Þand therefore the agreement state does not satisfy the global constraint.As a result,it is proposed that local information (i.e.the state opinion vector shared by an agent’sInternational Journal of Control5D o w n l o a d e d b y [P e k i n g U n i v e r s i t y ] a t 08:13 21 M a r c h 2012neighbours)be used to initialise the state opinions fornon-adjacent agents such that the extra terms in each row of (15)will be cancelled,i.e.x 41in row 1,x 21,x 34,x 54in row 2,x 14,x 54in row 3and x 14,x 34in row 4.In addition,a gain value will be needed to cancel the 25term in (15).By doing this,it will be shown that the resulting agreement state satisfies the global constraint.3.2Attempt 2:initial condition definition bypropagationIt is proposed that the state opinions of agents not adjacent to agent i should be assigned values in x i such that the equationðT c i P Þx i ¼0Mð16Þis satisfied,where 0M is an M -dimensional vector with all elements being zero.Note that this requires that each agent a priori knows the structure of the network in the form of the incidence matrix.For each agent,this equation is sufficient to choose state opinion values for every non-adjacent agent.For any agent i ,there are d i agents adjacent to agent i .Therefore,there are N À1Àd i agents not adjacent to agent i,which implies (N À1Àd i )l state opinions are undefined.T c i contains (M Àd i )l rows that represent pairwise constraints.This results in (M Àd i )l equations and (N À1Àd i )l unknowns.As a result,effectively choosing initial state opin-ions is feasible only if M ¼N À1,i.e.G is a tree graph.For graphs with cycles,M 4N À1,therefore,the system of equations is overdetermined.For incomplete graphs,M 5N À1,resulting in a system of equations that is insufficient to solve for all the initial state opinions.To give further insight on the resulting state opinion assignments,we will return to the examplegraph,G .The intermediate matrix T c4results inT c 4¼1À100000000000000000026643775:So,we assign non-adjacent agents state opinions according toðT c4 P Þx 4¼P ðx 41Àx 42Þ002666437775¼00002666437775:x 41is a communicated value because agent 1isadjacent to agent 4,so x 42is initially assigned the same value as x 41,i.e.it is assigned the value of theagent adjacent to agent 4that is in the path from agent 2to agent 4.Similarly for agent 5,ðT c5 P Þx 5¼P ðx 51Àx 52ÞP ðx 51Àx 54ÞP ðx 54Àx 53Þ02666437775¼00002666437775revealing that,as x 54is defined through communica-tion,x 51and x 53are set to x 54.As a result,x 52is also set to the value of x 54.Figures 2and 3show this graphically for agents 4and 5.Nodes of the same hatching denote that the initial state opinions are equal from the view of the solid coloured node.In other words,the state opinion assignments propagate out into the network from the neighbour-hood of agent i as shown in Figure 4.By setting the state opinion of a non-adjacent agent j to the same value an adjacent agent on the path from agent i to the non-adjacent agent j ,we are guaranteeing that the pairwise constraints on that agent results in 0l in agent i ’s opinion.As a result,each element of x i is defined and it will now be shown that this choice of initial conditions for the consensus equation will result in an agreement state that satisfies the global constraint.The quantity used in the consensus equation is now denoted,X i (0)¼ x i for i ¼1,...,N with X i 2R Nl and gain 2R .The consensus equation,_Xi ðt Þ¼ÀXk "N iðX i ðt ÞÀX k ðt ÞÞfor i ¼1,...N ð17ÞFigure 3.Initial conditions propagation for example graph agent 5.The state opinion for non-adjacent agents 1,2and 3are assigned the value of adjacent agent4.Figure 2.Initial conditions propagation for example graph agent 4.The state opinion for non-adjacent agent 2is assigned the same value as adjacent agent 1.6R.Chipalkatty and M.EgerstedtD o w n l o a d e d b y [P e k i n g U n i v e r s i t y ] a t 08:13 21 M a r c h 2012results inX c ¼1N X N i ¼1X i ð0Þ¼ N X N i ¼1x ið18Þas the final agreement state,X c 2R Nl .It is required that this agreement state satisfies the global constraint where each agent’s state opinion vector satisfies the pairwise constraint for each edge in the graph.Therefore,it is needed thatðD T P ÞX c ¼1 b :ð19ÞTo verify that the agreement state satisfies the global constraint,we can plug in the RHS of (18)for X c and rewrite the global constraint,(19),asðD TP ÞX c ¼ðD TP Þ N XN i ¼1x i¼ N X N i ¼1ðD T P Þx i :ð20ÞUsing (6),(20)can be written as¼ N X N i ¼1ððT i þT c i Þ P Þx i :ð21ÞBy the distributive property of the Kronecker product and (6),(21)becomes¼N X N i ¼1ðT i P Þx i þ N XN i ¼1ðT c i P Þx i ¼ N X N i ¼1f i b þ N X N i ¼1ðT c i P Þx i :ð22ÞRecalling Lemma 2.2,(22)is rewritten as¼ N 21 b þ N X Ni ¼1ðT c i P Þx i :ð23ÞPlugging (16)into (23)results inðD T P ÞX c ¼21 b :Plugging in ¼N 2,it is shown thatðD T P ÞX c ¼1 b :Therefore,the global constraint is satisfied by the final agreement state through the manipulation of the initial conditions of the consensus equation.This leads us to the following theorem.Theorem 3.1:If the state opinions of agents not adjacent to agent i in X i are assigned values such thatðT c i P Þx i ¼0M and ¼N 2,then the resulting agreement state satisfiestheglobalconstraint ,(D T P )X c ¼1 b .4.2D pendulum dynamics and controlTo investigate the viability of this approach,we apply the algorithm to the synchronisation of a distributed network of planar mass-cart pendula.The planar dynamics of the system allow us to analyse a network that is modelled by a simple form of the tree graph,a line graph.4.1DynamicsThe dynamics of a single cart-pendulum system (referred to as an agent)can be derived using Lagrange’s equations (e.g.Spong 1989)d d t @L @_q À@L@q ¼Q ,L ¼K ÀT ,where K is the kinetic energy of the system,T is thepotential energy of the pendulum,Q is the param-etrised forces acting on the system and L is the Lagrangian,where q is the vector of parameters,[v ]T as shown in Figure5.Figure 4.Directed tree graph example for initial conditions propagation.The figure represents the view of the graph from the perspective of agent X.Agent X assigns state opinions for non-adjacent agents according to the colours/hatchings shown in this diagram:in agents X’s state opinion vector,values of non-adjacent agents are set to values of agents adjacent to agent X that are in the path from the non-adjacent agent to agentX.Figure 5.Pendulum diagram.International Journal of Control7D o w n l o a d e d b y [P e k i n g U n i v e r s i t y ] a t 08:13 21 M a r c h 2012。