多智能体一致性理论研究进展

2010中国制导、导航与控制学术会议(CGNCC2010)2010年10月16~18日中国上海40多智能体一致性理论研究进展张庆杰1朱华勇1沈林成1,2（1.国防科学技术大学机电工程与自动化学院，湖南长沙410073；2.国防科学技术大学研究生院，湖南长沙410073）摘要：从理论探索和实际应用两个方面介绍了多智能体一致性理论的研究现状，总结了一致性理论在收敛条件、平衡状态和收敛速度、时滞系统、信息不确定性以及异步通信等方面的最新进展情况，并阐述了其在多机器人系统编队控制、蜂拥和聚集、融合估计、协同决策以及耦合振子系统同步中的应用情况。最后，结合当前研究进展探讨了多智能体一致性理论发展趋势。关键词：多智能体系统；一致性理论；研究进展ASurveyofConsensusTheoryinMulti-AgentSystemZHANGQing-jie1,ZHUHua-yong1,SHENLin-cheng1,2(1.MechatronicEngineeringandAutomation,NationalUniversityofDefenseTechnology,Changsha410073,China;2.GraduateSchoolofNationalUniversityofDefenseTechnology,Changsha410073,China)Abstract：Asurveyofconsensustheoryinmulti-agentsystemisstudiedfromtheoreticalandapplicationaspects.Consensustheoryinconvergencecondition,equilibriumandtheconvergencerate,time-delaysystems,informationuncertainty,aswellasasynchronouscommunicationissummarized.Meanwhile,theapplicationofconsensustheorysuchasformationcontrol,flockingandrendezvousprobleminmulti-robotsystems,fusionestimation,collaborativedecision-makingandcoupledoscillatorsynchronizationaredescribedindetail.Atlast,thetrendofconsensustheoryisdiscussedconsideringthelastedresults.Keywords：multi-agentsystem；consensustheory；researchdevelopment引言1随着网络技术的发展成熟与广泛应用，网络环境下的多平台协调与控制已逐渐成为多机器人系统研究中的热点问题。尽管传统的集中控制方式和分散控制方式在系统结构、计算和决策等方面具有一定的优势，但终究无法回避单点失效而导致系统鲁棒性降低以及全局通信带来的复杂代价等问题。分布式控制策略的出现使得多机器人系统在多平台协调与控制方面具有更好的灵活性和鲁棒性。近年来，分布式人工智能、群集智能等理论的发展促进并形成了一个崭新的研究领域——多智能体分布式一致性理论。相比于分层递阶控制方式而言，基于一致性理论的分布式控制策略采用自下而上(Bottom-up)的思想，主要研究在没有组织者和协调者情况下，如何通过个体对环境的动态反应以及多个个体之间简单协调而涌现出整体行为的一致，因此也有文献称之为群体基金项目：国防基础研究项目(A2820080247)；国家安全基础研究项目(6138101001)作者简介：张庆杰(1981-),男,辽宁海城,汉,博士研究生,研究方向为多智能体一致性；朱华勇(1971-),男,浙江舟山,汉,博士,副教授，研究方向为多平台协同控制;沈林成(1965-),男,江苏吴江人,博士,教授,研究方向为飞行器导航与规划、智能控制等。系统一致性理论[1,2]。多智能体一致性理论的基本任务是，基于多个智能体可能相冲突的输入信息，采用一致性控制策略使群体系统产生一致公共输出，并且在理论上证明达到一致性所需轮数的上界和下界相同。由于分布式一致性理论具有无中心控制节点、局部信息交换和简单行为协调的特点，因此，越来越多的学者对一致性理论表现出了浓厚的兴趣。经过二十余年的发展，多智能体一致性理论的研究经历了三个阶段：第一阶段：生物群体机制模拟阶段(1987-1995)，主要模拟自然界群体一致性现象以Boid模型[3]和Vicsek模型[4]为代表；第二阶段：理论探索研究阶段(1995-2004)，Jadbabaie等人对Vicsek模型的一致性行为给出了理论证明[5]，开辟了多智能体一致性理论研究的探索之路，而加州理工学院的Fax、Murray和Saber等人在多智能体一致性理论方面取得的研究成果[6~9]标志着多智能体一致性问题的理论框架初步形成；第三阶段：理论日臻完善阶段(2004-)，逐渐探索并完善了一致性理论在有向/无向通信网络、固定/动态拓扑、时滞系统、信息不确定以及异步通信中的相关问题，已形成了相对完善的系统理论。此外，多智能体一致性理论在多机器人系统编队控41制、蜂拥和聚集以及耦合振荡器同步等多个领域得到了广泛应用。本文将从收敛性条件分析、收敛速度和平衡状态、时滞系统、信息不确定以及异步通信等多个角度，介绍国内外在多智能体一致性理论方面的最新研究成果及其应用情况。1数学描述通常，多智能体间的交互关系可以由一个加权的有向图G(,,)A来描述。其中，1n{,,}为图的节点集，且节点序号属于有限集合{1,2,,n}I，为图的边集，ij(,)表示图的边，ij[a]A为邻接矩阵，其非负元素ija的取值与图中的边相对应。例如，ijij(,)a0。假定，iii,a0I。若对于任意i,jI且ij，有ijjiaa成立，则有向图转变为无向图。此时，无向图则也可以看作是有向图的一种特例。若节点i的紧邻节点的集合定义为：ijij{:(,)}N(1)令ix为节点i的状态值(如位置、速度等状态信息)，那么G(G,x)x是指状态值为T1n(x,,x)x，拓扑结构为G的多智能体系统。从宏观角度出发，对群体而言，图中的每个节点都可以看作是一个简单的动力学单元，它可以描述为iiixf(x,u),iI(2)那么，整个图的动力学可描述为如下形式F(,)xxu(3)其中，表示微分算子(连续时间系统)或者差分算子(离散时间系统)。F(,)xu可以由iif(x,u)，i1,2,,n组成。在多智能体一致性问题的研究中，通常会撇开个体复杂的动力学性质，抽象其最基本的性质。因此，广泛采用单积分器模型(iixu，iI)和双积分器模型((0)(1)(1)iiiixxxu，iI)用来表征智能体动力学，并用于理论探索研究，但应用一致性理论解决实际问题时，则需要考虑复杂动力学模型(如Unicycle轮式机器人模型[10]，链式模型[11]，非线性模型[1])对一致性策略的影响以及是否能够实际应用的可行性。定义1：(多智能体一致性)是指输入iu仅依赖节点i和紧邻节点的信息进行分布式求解：令1miijj1muk(x,,x),j,,jI(4)为网络拓扑G的输入。其中，1mijjJ,,，并且满足iii}J{N。因此，输入iu能够渐近求解一致性问题当且仅当ijlimx(t)x(t)0,i,jtI‖‖(5)也就是说，F(,k())xx存在一个渐近稳定平衡点x，且满足ini(),ixaI。其中，n:为1nx,,x的函数映射，ini(0)ax为系统初值。可以看出，x不仅与系统动力学F()有关，也与个体的初始状态inia有关。特别地，当nijii1()Ave(x)(1/n)axx、ii(x)maxx和ii(x)minx，iI时，分别称为平均一致性、最大一致性和最小一致性。2一致性理论研究现状2.1收敛条件分析在时不变通信网络条件下，对于任意一个智能体i来说，它的近邻节点集合iN是固定不变的。以连续时间单积分器智能体模型的一致性问题为例，若采用一致性控制协议iijijjiua(xx)N，则多智能体系统模型F(,k())xx为(t)L(t)xx(6)其中，T12n(t)[x(t),x(t),,x(t)]x，矩阵ijL[l]为网络图的Laplacian矩阵。当ij时，ijijla；否则，nijj1,ijijla。借助图论知识，L的特征根总是具有非负实部，并且至少有一个零特征根，即12M0Re{(L)}Re{(L)}Re{(L)}，M为L的特征根个数。Saber和Murry给出了无向图时不变通信拓扑条件下多智能体一致收敛的充分必要条件[8]：拓扑图是连通的(Connected)；对有向拓扑图，Ren认为只要网络网络拓扑图中存在生成树结构(SpanningTree)[12]，则多智能体能实现全局一致收敛。总而言之，多智能体一致收敛分析主要关注判断Laplacian矩阵是否具有单个零特征根[8,10]，其代数判据为：多智能体系统(6)能够实现一致性的充分必要条件是2Re{(L)}0。类似的，连通性或生成树结构的收敛条件对于离散时间系统的多智能体一致性同样适用，其代数判据为判断邻接矩阵的谱半径是否为单特征根1|()|1A且2|()|1A。针对时变通信网络，Ren和Beard提出了离散和连续的一致性更新策略不同表达形式，得到了动态拓扑结构条件下信息一致性收敛的充分必要条件[13]：若以某个时间间隔变化的通信拓扑图在变化过程中具有一个生成树结构，则多智能体系统可以实现一致性收敛。该结论弱化了Jadbabaie提出的具有足够连通特性[5](ConnectedFrequentlyenough)条件，降低了对通信拓扑图的连通性要求。同样，Saber在讨论动态拓扑(SwitchTopology)网络下的平均一致性中也给出了同样的结论[8]。尽管上述讨论针对时变通信拓扑网络，但要确保系统动态变化过程中网络满足连通性/生成树结构的要求，这与时不变网络并无本质区别。事实上，动态通信拓扑的连通性往往是无法保障的。42Jadbabaie[5]和Bertsekas等人[14]在研究离散时间多智能体在时变网络条件下的一致性问题时提出了联合连通性(JointlyConnected)的概念，认为系统只要满足分段的联合连通而不必每个时刻都是连通的，同样可以实现全局渐近一致收敛。对于时变权重系数、时变网络条件下的一致性的问题。Moreau[15,16]作了更进一步的研究，提出了-连通的概念：网络是连通的，而且具有足够强度的连通性，亦即是当去掉图中那些权重系数小于的边后，仍然是连通的。对于多智能体系统(6)，且L是时变的，若存在0及0T，使得tTtt[0,),L(s)ds是-连通，那么多智能体系统能够实现全局一致收敛[15]。Moreau的结论表明：对于一个动态变化的通信拓扑图在任意时刻可能是不连通的，但只要是积分连通的，它将不影响系统实现最终的一致性。2.2平衡状态和收敛速度Ren指出[12]：若有向网络拓扑图中存在生成树结构，则有LtTntlime1v成立。其中，T1n[v,,v]v为L的零特征值所对应的n1非负左特征向量，并且满足njj1v1。那么，一致性收敛的平衡状态为每个智能体初始状态的加权，即当t时，nijjj1x(t)vx(0)。不失一般性，向量v中元素可为零元素。当向量v中不含零元素时，多智能体取得平均一致性，同时它也是研究最为广泛一种类型。也就是说，如果节点能够与图中所有其它节点连通，那么该节点的