冯元珍
(南京理工大学自动化学院,江苏 南京 210019;南京人口管理干部学院基础部,江苏 南京 210042)
多智能体系统一致性问题综述
冯元珍
(南京理工大学自动化学院,江苏 南京 210019;南京人口管理干部学院基础部,江苏 南京 210042)
系统地论述了多智能体系统一致性问题,重点对不同阶动力学智能体系统的一致性协议进行了总结。最后对一致性问题的相关应用进行了简单总结,并探讨了未来的研究方向。
多智能体系统;一致性;协议
近年来,多智能体系统由于在无人驾驶飞机协作控制、编队控制、分布式传感器网络等多个领域的广泛应用,引起了许多研究学者的关注。
一致性问题的相关研究在计算机科学领域特别是分布式计算方面已经有比较长的历史。1962年,Dr DeGroot 首次将统计学中的一致性理论应用于多个传感器不确定性问题的融合。在与多智能体系统相关的许多应用中都要求网络中每个智能体对一定的量达成一致,这些量可能与智能体本身的运动轨迹是没有关系的。因此,以系统的理论框架对一致性问题的研究具有重要的理论意义和实际意义。目前,许多学科的研究人员都开展了多智能体系统一致性相关问题的研究,如多智能体分布式一致性协议、多智能体协作、蜂拥问题、聚集问题等等。下面,笔者主要对现有文献中多智能体一致性协议进行了总结,并对相关应用进行了简单介绍❶。
多智能体系统是指由多个具有独立自主能力的智能体通过一定的信息传递方式相互作用形成的系统;如果把系统中的每一个智能体看成一个结点,任意2个有信息传递的智能体之间用有向边来连接的话,智能体的拓扑结构就可以用相应的有向图来表示[1]。
用G=(V,E,A)来表示一个有向加权图,其中V={v1,v2,…,vn}代表图的n个顶点;E⊆V×V是边集合,如果存在从第i个顶点到第j个顶点的信息流,则有eij=(vi,vj)∈E;A是非负加权邻接矩阵eij∈E⟺aij>0;结点vi的邻居集定义为Ni={vj|(vi,vj)∈E},Ni的势称为结点vi的出度,记作deg(vi),D=diag{deg(v1),deg(v2),…,deg(vn)}称为G的度矩阵。如果对所有的eij∈E意味着eji∈E,则称G是无向图。
2个不同的结点vi和vj之间有有向路径是指存在1个有序结点序列(vi,vk1),(vk1,vk2),…,(vkl,vj);如果图G中任意2个不同的结点间都存在1条有向路径,则称G是强连通图;如果G是无向的,则称G是连通图。图G有有向生成树指的是图G中存在1个包含所有顶点的子图,除了唯一的根结点外,其余结点有且仅有1个父结点。
分布式一致性协议就是指采用状态反馈ui=ki(xj1,xj2,…,xjl)或输出反馈ui=ki(yj1,yj2,…,yjl),使(G,x)实现一致性,其中{vj1,vj2,…,vjl}⊆{i}∪Ni(l 3.1一阶一致性 在早期关于一致性问题的研究中,绝大多数研究工作针对智能体为一阶智能体的情形,分析不同网络拓扑结构下实现一致性需要满足的条件和一致性实现时的收敛值[3]。 1)连续时间情形 当网络中的智能体均具有形如: (1) 的状态方程时,经常采用一致性协议为: (2) 在固定拓扑结构下,一致性的相关结论为: 许多场合下,由于结点间连接的建立或失败,多智能体系统的拓扑结构往往是动态发生变化的。拥有动态变换网络的系统一般称之为切换网络,切换网络可以用Gσ(t)来表示,其中σ(t):R→J={1,2,…,m}为切换信号,{G1,G2,…,Gm}为所有可能的拓扑结构组成的集合。在协议(2)的作用下,具有切换拓扑结构的闭环系统为: (3) 如果上述系统仅在离散时刻τ1,τ2,…,τn(0<τ1<τ2<…τn≤t)处切换,则系统(3)的解为: x(t)=e-L(Gσ(h))(t-τh)e-L(Gσ(h-1))(τh-τh-1)…e-L(Gσ(2))(τ2-τ1)e-L(Gσ(1))τ1x(0) 系统一致性分析转化为多个具有非负对角元的随机矩阵乘积的极限问题的分析。 在切换拓扑结构下,一致性的相关结论为: 定理2假定切换网络在任意长度有上界的时间间隔内均有一个有向生成树,则在协议(2)作用下,切换多智能体系统可渐近实现一致性。 2)离散时间情形 当网络中的智能体均具有形如: xi(k+1)=xi(k)+ui(k) (4) 的状态方程时,采用一致性协议: (5) 因此,在上述一致性协议下形成的闭环系统为: x(k+1)=Px(k) (6) 在固定拓扑和切换拓扑结构下,多智能体系统有类似定理1和定理2相应的结论。 3)其他研究热点 除了上述关于一致性的经典结论外,还有学者分别考虑带时滞的一致性、有一个动态领导者、多个静态或者动态领导者的一致性问题。还有一些研究工作针对实现一致性时不同的一致性值来分析网络应当具备的结构。具体结论不再详述,感兴趣的读者可以参阅相关文献[4]。 3.2二阶一致性 多智能体系统二阶一致性[5]的研究中假设智能体具有下列形式的状态方程: (7) 采用一致性协议: (8) 则闭环系统的矩阵形式为: 以Jordan标准形理论为基础分析闭环线性系统的一致性,相应结论为: 在上述结论的基础上,有学者进一步拓展了上述一致性算法,考虑了有界控制输入,无相对速度测量时的各种二阶一致性问题[6]。 3.3高阶一致性 近来,许多研究人员对多智能体系统一致性问题的研究转移到了智能体为n阶智能体[7,8]的情况,并以线性矩阵不等式形式给出系统一致性需要满足的条件,在一定假设下分析给出线性矩阵不等式的可解性,并通过实例验证了算法的有效性。 考虑智能体具有状态方程: (9) 或: (10) 对方程(9)用状态反馈: 对方程(10)静态输出反馈: 或动态输出反馈: 其中,LC=L⊗In。 4.1一致性在协作控制中的应用 一致性是多智能体实现协同合作、完成共同制定任务的基础。目前,有许多学者开展了关于一致性应用问题的研究,如聚集问题、蜂拥问题、编队控制问题等。聚集问题要求每一个智能体同时到达指定的位置,文献[9]采用一致性搜索思想讨论了同步情形和异步情形下的聚集问题;文献[10]分别就固定拓扑结构和切换拓扑结构下,分别讨论了一类速度恒定,通过局部反馈校正移动方向的智能体系统蜂拥问题。 4.2同步问题 同步问题主要是在假定信息交换拓扑结构在完全图的情况下,通过智能体之间的信息交换,修正智能体的动力学,最终实现同步性。 对现有文献中的一致性协议进行了比较详细的总结和分析,由于多智能体一致性相关研究问题的多样性,笔者仅是对具有代表性的单积分器智能体,二阶智能体以及高阶智能体相关的一致性协议进行了综述。此外,关于多智能体系统一致性还有许多的研究方向和研究热点如随机一致性,非线性一致性协议等,感兴趣的读者可以查阅相关的文献。关于多智能体一致性问题,还有许多的问题亟待研究和解决,比如在噪声扰动下和考虑模型不确定性时对不同系统的一致性问题等值得研究的探讨。 [1]Royle G, Godsil C. Algebraic Graph Theory[M]. New York:Springer, 2001. [2] Ren W, Beard R W, Atkins E. A survey of consensus problems in multi-agent coordination[J]. Proceedings of the 2005 American Control Conference, 2005:1859-1864. [3] Saber R O, Fax J A, Murray R M. Consensus and cooperation in networked multi-agent systems[J]. Proceedings of the IEEE, 2007, 95(1):215-233. [4] Xiao F, Wang L. Consensus protocols for discrete-time multi-agent systems with time-varying delays[J]. Automatica, 2008, 44:2577-2582. [5] Ren W, Atkins E. Second-order consensus protocols in multiple vehicle systems with local interactions[J]. Proceedings of AIAA Guidance, Navigation, and Control Conference and Exhibit, 2005, AIAA 2005-6238. [6] Ren W. Consensus based formation control strategies for multiple-vehicle systems[J]. Proceedings of the 2006 American Control Conference, 2006:4237-4242. [7] Zhai G, Okuno S, Imae J, Kobayashi T. Consensus algorithms for multi-agent systems: a matrix inequality based approach[J]. Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, 2009: 891-896. [8] Zhai G, Okuno S, Imae J, Kobayashi T. A new consensus algorithm for multi-agent systems via dynamic output feedback control[J].2009 IEEE International Symposium on Intelligent Control, 2009:890-895. [9] Lin J, Morse A S, Anderson B D O. The multi-agent rendezvous problem[J]. Proceedings of the 42nd IEEE Conference on Decision and Control, 2003:1508-1513. [10] Saber R O. Flocking for multi-agent dynamic systems: algorithms and theory[J]. IEEE Transaction on Automatic Control, 2006, 51(3):401-419. [编辑] 洪云飞 10.3969/j.issn.1673-1409.2011.03.029 TP18 1673-1409(2011)03-0084-043 一致性协议
4 一致性的应用
5 结 语