多智能体系统一致性综述

多智能体系统一致性综述一引言多智能体系统在20世纪80年代后期成为分布式人工智能研究中的主要研究对象。研究多智能体系统的主要目的就是期望功能相对简单的智能体系统之间进行分布式合作协调控制，最终完成复杂任务。多智能体系统由于其强健、可靠、高效、可扩展等特性，在科学计算、计算机网络、机器人、制造业、电力系统、交通控制、社会仿真、虚拟现实、计算机游戏、军事等方面广泛应用。多智能体的分布式协调合作能力是多智能体系统的基础，是发挥多智能体系统优势的关键，也是整个系统智能性的体现。在多智能体分布式协调合作控制问题中，一致性问题作为智能体之间合作协调控制的基础，具有重要的现实意义和理论价值。所谓一致性是指随着时间的演化，一个多智能体系统中所有智能体的某一个状态趋于一致。一致性协议是智能体之间相互作用、传递信息的规则，它描述了每个智能体和其相邻的智能体的信息交互过程。当一组智能体要合作共同去完成一项任务，合作控制策略的有效性表现在多智能体必须能够应对各种不可预知的形式和突然变化的环境，必须对任务达成一致意见，这就要求智能体系统随着环境的变化能够达到一致。因此，智能体之间协调合作控制的一个首要条件是多智能体达到一致。近年来，一致性问题的研究发展迅速，包括生物科学、物理科学、系统与控制科学、计算机科学等各个领域都对一致性问题从不同层面进行了深入分析，研究进展主要集中在群体集、蜂涌、聚集、传感器网络估计等问题。目前，许多学科的研究人员都开展了多智能体系统的一致性问题的研究，比如多智能体分布式一致性协议、多智能体协作、蜂涌问题、聚集问题等等。下面，主要对现有文献中多智能体一致性协议进行了总结，并对相关应用进行简单的介绍。1.1图论基础多智能体系统是指由多个具有独立自主能力的智能体通过一定的信息传递方式相互作用形成的系统；如果把系统中的每一个智能体看成是一个节点，任意两个节点传递的智能体之间用有向边来连接的话，智能体的拓扑结构就可以用相应的有向图来表示。用)(AE,V,G来表示一个有向加权图，其中}{n21v,,v,vV代表图的n个顶点；VVE是边集合，如果存在从第i个顶点到第j个顶点的信息流，则有Ev,vejiij)(；A是非负加权邻接矩阵0ijijaEe；节点iv的邻居集定义为})({Ev,v|vNjiji。如果对所有的Eeij意识着Eeji，则称G是无向图。2个不同的节点iv和jv之间有有向路径是指存在1个有序节点序列)()()(jkkkk1v,vv,vv,vl211，，，；如果图G中任意两个不同的结点间都存在1条有向路径，则称G是强连通图；如果G是无向的，则称G是连通图。图G有有向生成树指的是图G存在1个包含所有定点的子图，除了唯一的根节点以外，其余节点有且仅有1个父节点。二．主要研究内容2.1多智能体系统一致性问题描述令qiRx表示图中第i个顶点iv的状态且满足)u,f(xxii，这样可利用二元组)(xG,来表示动态多智能体网络系统，其中TTnT2T1x,,x,xx)(，系统状态方程为u)F(x,x。如果对于所有的ji,，都有0)()(txtxlimjit，则称多智能体系统实现一致性。2.2一致性协议2.2.1一阶一致性在早期关于一致性问题的研究中，绝大多数研究工作针对智能体为一阶智能体的情形，分析不同网络拓扑结构下实现一致性需要满足的条件和一致性实现时的收敛值。（1）连续时间情形当网络中的智能体均具有形如：iiux)(Rxi（1）的状态方程时，经常采用一致性协议为：Niijijixxau)(（2）因此，在上述一致性协议下的闭环系统为Lxx，系统（1）的解为)()(0xetxLt，可以利用线性系统理论来分析系统的一致性问题。在固定拓扑结构下，一致性的相关结论为：定理1假定G有一个有向生成树，L为其拉普拉斯矩阵且有01L，0LT，11T，则在协议（2）作用下，多智能体系统可实现一致性，且(0))(xγtxlimTit。特别地，当G为无向连通图或强连通平衡图时，多智能体系统可实现平均一致性，即n1iiitxtxlim(0))(。许多场合下，由于节点间连接的建立或失败，多智能体系统的拓扑结构往往是动态发生变化的。拥有动态网络的系统一般称之为切换网络，切换网络可以用)(tG0来表示，其中m},{1,2,JR:)(t为切换信号，}{m21G,,G,G为所有可能的拓扑结构组成的集合。在协议（2）的作用下，且有切换拓扑结构的闭环系统为：xGLxk)(（3）如果上述系统仅在离散时刻)(02121t,,,nn处切换，则系统（3）的解为：(0)eeee)t(x10(1)120(2)1-1)0()0()L()-)(L()-)(L()))(L(xGτGτGτtGhhhhh系统一致性分析转化为多个具有非负对角的随机矩阵乘积的极限问题的分析。在切换拓扑结构下，一致性的相关结论为：定理2假定切换网络在任意长度有上界的时间间隔内均有一个有向生成树，则在协议（2）作用下，切换多智能体系统可渐进实现一致性。（2）离散时间情形当网络中的智能体均具有形如：)((k))(kux1kxiii（4）的状态方程时，采用一致性协议：iNjijijikxkxau))(-)((（5）因此，在上述一致性协议下形成的闭环系统为：)()(kPx1kx（6）式中，10εL,IP，是网络节点的最大出度。在固定拓扑和切换拓扑结构下，多智能体系统有类似定理1和定理2相应的结论。（3）其他研究热点除了上述关于一致性的经典结论外，还有学者分别考虑带时滞的一致性、有一个动态领导者、多个静态或者动态领导者的一致性问题。2.2.2二阶一致性多智能体系统二阶一致性的研究中假设智能体具有下列形式的状态方程：iiiiuxvxni,1,2,（7）采用一致性协议：iNjijijii)x(xakvu（8）则闭环系统的矩阵形式为：BFLBKAIn-)(其中，0010A，10B，kK0,，1,0F，Tn21n21v,v,v,x,,x,x以Jordan标准型理论为基础分析闭环线性系统的一致性，相应结论为：定理3当系统具有固定无向连通拓扑结构时，协议（8）可实现平均一致性，即当t时，0)(v)(n1)t(xi1it,0xnii。当网络结构在无向连通图之间切换时，协议（8）可解决平均一致性。在上述结论的基础上，有学者进一步拓展了上述一致性算法，考虑了有界控制输入，无相对速度测量时的各种二阶一致性问题。2.2.3高阶一致性近来，许多研究人员对多智能体系统一致性问题的研究转移到了智能体为n阶智能体的情况，并以线性矩阵不等式给出系统一致性需要满足的条件，在一定假设分析给出线性矩阵不等式的可解性，并通过实例验证了算法的有效性。考虑智能体具有状态方程：iiiBuAxx（9）或：iiiBuAxxiiCxy（10）对方程（9）用状态反馈：iNjjbiibiixKxKu对方程（10）静态输出反馈：iNjjbiibiiyKyKu或动态输出反馈：yBxAxDDLcyDxCuDD其中，ncILL2.3一致性的应用2.3.1一致性在协作控制中的应用一致性是多智能体实现协同合作、完成共同制定任务的基础。目前，有许多学者开展了关于一致性应用问题的研究，如聚集问题、蜂涌问题、编队控制问题等。聚集问题要求对每一个智能体同时达到指定的位置，文献[9]采用一致性搜索思想讨论了同步情形和异步情形下的聚集问题；文献[10]分别就固定拓扑结构和切换拓扑结构下，分别讨论了一类速度恒定，通过局部反馈校正方向的智能体系统的峰拥问题。2.3.2同步问题同步问题主要是在假定信息交换拓扑结构在完全图的情况下，通过智能体之间的信息交换，修正智能体的动力学，最终实现同步性。笔者所研究的随机连接的多智能体系统，和以往确定性的框架不同的是多智能体系统中的多智能体是具有马尔科夫性质，行为是随机的。每个多智能体的状态随时间变化建模成一个有限维的连续马尔科夫链。在这种情形下，一致性是当所有多智能体的概率向量达到一个共同的稳定的概率向量，因此在完全随机的背景下，讨论概率一致性才是有意义的。三．结束语对现有文献中的一致性协议进行了比较详细的总结和分析，由于多智能体一致性相关研究问题的多样性，本文仅对具有代表性的一部分智能体相关的一致性协议进行了综述。此外，关于多智能体系统一致性问题，还有许多的研究方向和研究热点如随机一致性，非线性一致性协议等。关于多智能体一致性问题，还有许多的问题亟待研究和解决。四．参考文献[1]CvetkovicD,RowlinsonP,SimicS,etal.AlgebraicGraphTheory[M]//Algebraicgraphtheory.CambridgeUniversityPress,1974:xvi+298[2]RenW,BeardRW,AtkinsEM.Asurveyofconsensusproblemsinmulti-agentcoordination[C]//AmericanControlConference,2005.Proceedingsofthe.IEEE,2005:1859-1864vol.3[3]Olfati-SaberR,FaxJA,MurrayRM.ConsensusandCooperationinNetworkedMulti-AgentSystems[J].ProceedingsoftheIEEE,2007,95(1):215-233[4]XiaoF,WangL.Consensusprotocolsfordiscrete-timemulti-agentsystemswithtime-varyingdelays[J].Automatica,2008,44(10):2577-2582[5]RenW,AtkinsE.Second-orderconsensusprotocolsinmultiplevehiclesystemswithlocalinteractions[C]//AIAAGuidance,Navigation,andControlConferenceandExhibit.2005:6238[6]RenW.Consensusbasedformationcontrolstrategiesformulti-vehiclesyst-ems[C]//AmericanControlConference,2006.IEEE,2006:6pp[7]ZhaiG,OkunoS,ImaeJ,etal.Consensusalgorithmsformulti-agentsystems:Amatrixinequalitybasedapproach[C]//Networking,SensingandControl,2009.ICNSC'09.InternationalConferenceon.IEEE,2009:891-896[8]ZhaiG,OkunoS,ImaeJ,etal.Anewconsensusalgorithmformulti-agentsystemsviadynamicoutputfeedbackcontrol[C]//ControlApplications,(CCA)&IntelligentControl,(ISIC),2009IEEE.IEEE,2009:890-895[9]LinJ,MorseAS,AndersonBDO.Themulti-agentrendezvousproblem.Part2:Theasynchronouscase[J].SIAMJournalonControlandOptimization,2007,46(6):2120-2147[10]RenW,BeardRW.Distrib