蜂拥控制研究现状

摘 要:群体系统蜂拥控制研究近年来受到了国内外众多领域高度重视,目前主要借鉴生物学领域关于群体蜂拥行为的研究成果,集中在个体之间交互形成的网络拓扑结构已知条件下的控制问题,分析了群体系统蜂拥控制研究的几个发展阶段,总结了群体蜂拥行为的理论研究趋势及其在工程领域中的应用研究现状,并指出了今后的发展方向。关键词:群体系统;蜂拥控制;仿生0 引言群体系统隶属于复杂系统的研究范畴,它是一个由大量自治个体组成的集合,在无集中式控制和全局模型的情况下,一般通过个体的局部感知作用和相应的反应行为使得整体呈现出涌现行为。群体系统具有个体自治、非集中式控制、局部信息作用等特征。在自然界中,群体现象无处不在,在几乎所有的尺度上,从非生命界的分子到星系,从生物界的简单细菌到高等动物,都普遍存在着群体现象。它也是目前复杂性科学研究的一个核心问题,生物学家和物理学家曾对此作了大量研究,计算机科学家通过人工生命方法揭示了其从主体的简单运动规则到整体的优化性质。如何对这种群体行为进行数学建模并将其应用于人造世界,如一组机器人、车流、无人驾驶飞机群的协作编队等社会行为控制,是目前复杂性科学的前沿课题。1 群体系统蜂拥控制研究的发展阶段 大致来说,对群体系统蜂拥控制的研究经历了三个阶段1:第一阶段是生物学家作了大量研究,发现了许多生物群体特有的动态行为。例如:a)雁群蜂拥行为,大雁群从一地蜂拥到另一地点时,它们会排成整齐的一字形或人字形队伍,而这种团队行为有利于大雁的自我调整以避开天敌或障碍等;b)鹿群逃避行为,某些野生动物群体在逃避天敌时,常能以合理的队形统一行动,如鹿群在逃避老虎时,它们不是胡乱分散,而是形成一个合理的队形,其中每一只鹿可以根据邻近的其他鹿的奔跑方向来决定自己的行动方式;c)蜜蜂筑巢行为,在没有可供参考的设计蓝图或领导者指导的情形下,蜂群能构建具有结构强度最优的蜂巢;d)蚁群觅食行为,蚁群在觅食的时候能够通过信息素的传递在巢穴与食物之间形成一条最优路线,当路上出现障碍物时,它们会设法绕过,并在不同信息素浓度的路径中选优。蚁群间的这种信息交流和优化思想,是群体行为的一个代表性的例子。 生物群体的这些动态行为常常具有以下特征2:a)简单性(simplicity),表现在个体的智能相对简单;b)鲁棒性(robustness),表现在它没有中心的控制,不会由于一个或某几个个体的故障影响整个群体行为;c)分散性(decentralized characteristics),表现在群体中相互合作的个体是分布的; d)自组织 (self organized),表现在经个体自主的演化使得群体表现出显著的整体性质,即涌现(emergence)。 第二阶段36是实验物理学家和计算机专家做了许多实验和仿真,用模拟仿生的方法证明这种生物群体现象可以由个体的简单行为规律获得。从目前大量群体系统的研究成果来看,由大规模简单的、同类型的个体自组织地形成某种模式、存储信息或完成联合决策所表现出来的群体涌现特性将是毫不稀奇的。就算是更加简单的个体规则,个体之间非线性的交互也能导致大规模群体内部产生复杂的涌现行为。 第三阶段715就是利用数学对群体行为进行严格建模及分析。对复杂群体行为的数学建模是群体系统研究走向量化的关键步骤,而这一阶段的研究工作只是处于起步。与此同时,工程领域关于自动或半自动智能群体的协调合作行为的动态性能及控制问题的研究也取得了越来越多的成果,生物领域中对诸如兽群的联合狩猎行为、鸟群的迁徙行为以及鹿群的群体防御行为之类的研究都曾经是工程领域群体系统研究的推动因素。因此在这一阶段的研究过程中,可以考虑综合生物领域与工程领域的研究成果,一方面使得受自然生物群体的协调行为启发而研究的工程智能群体行为能够获得这些自然现象中表现的某些特性,如群体涌现的协调性(由简单的局部个体行为产生的基于目标的全局群体行为)、自适应性(即在变化的环境中能自行选择和跟踪新目标的能力)、鲁棒性(不依赖于固定的“领导者”,面对扰动时能继续保持搜索目标的行为);另一方面通过研究实际复杂工程群体系统的控制与设计工作,有可能帮助研究人员对生物群体动态行为的涌现机制产生新的理解和认识。 目前关于群体系统协调行为的研究工作已各自从生物学、数学、机器人学以及计算机科学的角度全面展开,其根本仍在于对生物群体动态行为的理解。因为生物群体动态行为的进化过程可以看做是一种算法的设计过程,该算法就是要设计生物的行为使之最适合它们所处的环境。也就是说,进化过程就是一个优化生物行为的过程,而这个过程已经历了百万年的发展。通过研究生物群体系统可以揭示控制这些系统运作的一般规则,而这些规则将会对发展类似的工程群体应用系统极为重要。特别是从这些生物系统的研究中得来的运作规则将可用来发展分布式协调控制以及自动化多智能体系统如多机器人应用、海/陆/空中机动群体的学习策略。这些高度自动化的系统将在很大程度上受益于生物系统中包括生物群体的建模、协调策略的确定、实现群体目标的动态性能分析等各方面的研究进展。总之,对群体系统中交互个体之间的协调机制与群体所涌现出来的协调行为的内在关联的研究无论是对生物群体涌现行为的理解,还是对工程群体的应用都具有重大意义,因此综合多学科的工作成果而发展综合性的方法来理解群体行为的研究势在必行。2 群体蜂拥行为的研究现状群体蜂拥行为(flocking behavior),即一群运动自主的个体能够保持成团队的形式向某一目标地迈进,是一组有着共同目标的大量智能个体的团队行为。在对个体行为建模时,一方面需要有使得群体保持集聚在一起的能力;另一方面也要使得个体具有对环境所施于的刺激(如群体所要跟踪的目标物的位置信息)作出适当反应的能力。蜂拥(flocking)从英文字面上解释就是“大数量的个体一起移动”。蜂拥的一些典型的自然界例子包括鸟群、鱼群、细菌群落、蚁群、蜂群等,它能帮助生物躲避天敌,增加寻觅到食物的概率等13。从系统的观点看,蜂拥行为具有适应性、鲁棒性、分散性和自组织性,它的一个重要特点就是从简单的局部规则涌现出协调的全局行为。近十几年来,生物学、物理学、计算机和控制等领域的学者对自然界的蜂拥行为产生了浓厚的兴趣,他们正在努力地从相应领域角度探索蜂拥行为的涌现机制。 在文献16中,Reynolds首先提出一种经典的群体蜂拥模型,该模型中所有个体的运动必须遵循以下三条规则: a)趋向群体中心的集聚规则,即每个个体的运动有向群体中其他邻近个体的平均位置集聚的趋势; b)与群体中其他个体的避碰规则,即每个个体的运动有避免与群体中其他邻近个体产生碰撞的趋势; c)与邻近个体的匹配规则,即群体中每个个体都有与邻近个体的运动方向保持一致的趋势。 这些规则描述了每个个体与群体中其他邻近个体交互作用的动态行为。在这三条规则的共同作用下,群体中所有的个体将在避开碰撞并保持集结的同时有着共同的运动方向。Reynolds的贡献在于他提出的三条行为规则是研究群体蜂拥行为的开创性成果。而目前关于群体蜂拥行为的研究工作也大都是建立在Reynolds模型的基础之上。 Vicsek等人17在Reynolds模型的基础上提出了改进的群体蜂拥模型。Vicsek模型可以说是Reynolds模型的一种特殊形式,文中重点讨论了一类位置匹配规则(即每个个体向群体中其他邻近个体位置的平均方向移动并尝试与邻近个体速度匹配的趋势)。在该群体蜂拥模型中,所有个体以相同的速度移动,且只执行位置匹配规则,每个个体的运动方向按照个体本身运动方向及其邻近个体运动方向再加上某些附加的噪声信息平均值来实时更新。该文献中的数字仿真实现了群体的蜂拥行为,最后所有个体的位置方向也都趋向于一个共同值。 Jadbabaie等人11基于最邻近个体的规则研究了群体的蜂拥行为。同样地,所有个体以相同的速度移动,且只执行位置匹配规则。他们证明了在所有个体均能保持相互可检测的假设条件下,群体中所有个体的运动方向将趋向一致,也即讨论了Vicsek模型中群体蜂拥行为收敛性的数学证明问题。 Olfati-Saber18讨论了如何用动态网络来进行群体蜂拥行为建模的方法,并提出一种称之为(,)协议的网络协议。该协议包容了Reynolds所提出的三种行为规则,并为这三种行为规则提供了一种几何图形学上的解释。文中将该网络模型中执行(,)协议的个体称为型个体,而粗略地讲,型个体的运动目标就是为了维持它本身与其他邻近的型个体之间的平衡距离。 文献19中Olfati-Saber将基于动态网络方法为群体蜂拥行为建模的思想推广到多障碍物空间中的建模问题。当出现障碍物时,型个体的运动目标除了要求维持它本身与其他邻近的型个体之间的平衡距离外,同时还要求避免与环境空间中的障碍物相碰撞。但是在很多情况下,由于障碍物的分布状况, 型个体将不得不对它本身所需执行的各类任务进行优先权的划分,而对避碰任务往往具有最高的优先权,群体可能不得不出现分裂或再集结的情形。同时文中还提出两类新型虚拟个体(型个体和型个体)来模拟障碍物。通过将型个体在障碍物空间中的蜂拥行为还原到类似于无障碍物空间中的情形来进行分析。其中和型个体对型个体的吸引力或排斥力作用都是在型个体出现在障碍物作用范围内才起作用。另外,笔者曾对生物群集行为的研究现状进行了总结20。群集行为(aggregating behavior)是生物群体活动的一个重要现象,定义为在某一区域内初始随机分布的个体能聚集在一起的行为。自然界中由菌类等低级生物到哺乳类高级生物常常以群体的形式完成协调集结行为,如细菌的聚集、鱼群的聚集等都是自然界中生物群集的事例,这些行为的出现有着几种不同的产生机制。一种情况是个体直接面向局部的吸引源如食物的集中区域或其他个体释放的化学信息素引发的个体行为,这个过程称之为生物的趋化现象(chemotaxis),并多见于一些菌类及昆虫的群体行为;另一种情况是在一些高级生物群中比较多见的个体直接面向其他的个体(而不是其他个体留下的关于它们运动情况的化学线索)行为而产生各自的行为。这些个体间的作用力包括实现群集的吸引力和避免碰撞的排斥力。 由群体蜂拥行为和群集行为的定义可以知道,蜂拥行为实际上是在群集行为的基础上增加了对群体需要在向目标区域运动的同时保持集结的要求。因此也有很多关于群体蜂拥行为的建模工作都是建立在群集行为建模的研究成果之上。例如文献12中所研究的群体蜂拥模型实际上是在文献7中所介绍的群集模型的基础之上增加了环境作用项,而该项除了可以描述个体趋向目标的行为之外,还可以包含驱使个体远离障碍物的行为。整个群体涌现的蜂拥行为即是群体中个体之间交互作用及个体与环境之间交互作用联合作用下的结果。文中同时也分析了分别由一次型吸引力/排斥力分布函数plane attractive/repellent profiles)、二次型吸引力/排斥力分布函数 (quadratic attractive/repellent profiles)、高斯型吸引力/排斥力分布函数(Gaussian attractive/repellent profiles)等几类不同的函数描述的环境中群体蜂拥行为的稳定性问题,即群体的全局目标位置与其他障碍物位置对群体中个体的运动方程产生的作用力将满足上述几种函数的描述。关于其他一些特殊环境(如异步、不确定环境)中群体蜂拥行为的稳定性研究,文献1315中给出了很好的结论。其中Liu Yang等人13分别就一维、二维及更高维空间中的异步群体蜂拥行为的稳定性分析作出了重要贡献。由于二维及更高维空间中处于“领导者”位置(可定义为距离目标位置最近的个体位置)的个体具有无限多个可行的运动方向,为了使群体在运动中保持集结特性,需要对“领导者”个体的运动作合理的限制,文献14中提出了在群体中个体成员之间设计一组固定的链式通信结构,即每个个体只与固定的几个邻近个体产生交互作用,并在此基础上分析了异步群体的蜂拥行为的稳定性。文献15中则着重研究了不确定环境中群体蜂拥行为的稳定性问题,其中的不确定性包括个体对其他邻近个体的位置信息的不确定性(即感知的位置信息与其实际位置信息有偏差)以及对群体目标信息的不确定性。 3 群体蜂拥控制理论在工程领域中的应用现状近年来,工程领域中对于自动或半自动智能群体的协调合作行为的动态性能及控制问题的研究越来越受到人们的关注,特别是在机器人研究领域,将生物学领域关于群体动态行为的理解应用到多机器人群体系统的建模与控制任务上来是当前群体系统的研究热点。文献2126中的研究都是直接基于前面所述的生物学领域群体行为的建模研究之后的控制器设计及相关分析问题。 Reif等人21首先提出了超大规模机器人系统(very large scale robotic system)的概念, 并提出一种使用人工势能场(artificial potential field)作为控制律的分布式控制方案。这种控制方案的生物学基础是来自于基于拉格朗日法的群体建模思想,通过设计描述机器人之间相互作用力(吸引力/排斥力作用)的人工势能场函数的参数,可以调整机器人群体的协调行为以完成各种不同的任务。文中讨论了完成群集、群体蜂拥以及群体保护(形成环状结构,将受保护对象包围在环中)等联合行为的人工势能场函数的参数选择问题,并将这类实现群体联合行为的人工势能场方案称之为联合势能场方案(social potential fields)。这是一项很有意义的工作,但文中没有给出该方案的稳定性证明。 文献2227研究了群体蜂拥行为的控制实现和稳定性证明。该群体系统由一组具有双积分特性(double integrator dynamics)的智能个体(机器人属于此类个体)组成。作者提出的控制律建立在生物学中Reynolds模型的基础之上,包含了个体之间的吸引力/排斥力作用以及位置匹配控制力作用。其中文献22讨论了个体间的控制架构保持固定的状况,即每个个体基于一个固定的邻居组(即在群体蜂拥运动中,个体邻域内的其他个体不会变更)调整各自的位置和方向。在这种情况下,作者提出的控制律输入是平滑的,各智能个体能协调自身与邻近个体之间的运动,使得所有个体能收敛至一个共同的运动方向,顺利实现群体蜂拥行为。文献23讨论了个体的邻居组随时间变化的状况,邻居组中的元素依赖于个体间的实际距离而定。个体的控制律由其邻居组元素的状态决定,当个体跟踪其邻居组元素的变化时,将引起个体之间形成一种动态的控制交互结构以及一组开关控制率。尽管只利用到个体的局部信息,个体交互作用的时变特性也影响了局部控制器的作用,但文中的数学分析和仿真实验都表明,只要由个体邻近关系组成的邻接图能保证连通性(即假设个体间能保持相互可检测性),在上述开关控制律的作用下,群体蜂拥行为的实现仍将得以保证。文献24中所做的主要工作是将前面的结果推广到具有多个静态障碍物的环境中,在障碍物环境中,智能个体需要在完成群体蜂拥任务的同时避开障碍物。文中介绍了一组非平滑的控制律来使得一组机动群体实现速度同步,并在避开障碍物及个体之间碰撞的同时完成群体的蜂拥行为。Wang Long等人25研究的控制对象仍然是具有双积分特性的智能个体组成的群体系统,区别在于增加了对个体组成的群体系统和对个体速度的控制项,在提出的控制器作用下,群体系统将会以一个期望的速度完成蜂拥行为,并且个体之间能保持一个定常的距离。Gazi26基于他在文献7,12中提出的关于群集模型和蜂拥模型,将先前提出的群体模型视做理想的运动学模型,研究了当实际智能个体的动力学特性满足理想运动学方程时,智能群体实现这些动态行为的控制器设计问题。 文献2729分别研究了带虚拟领导者的蜂拥控制算法,可避免出现群体分裂的现象,但虚拟领导者的信息并非完全意义上的局部信息,将影响群体系统在实际应用中的机动性和可扩展性。陈世明等人30,31提出了一类基于最小外接圆方法的群体行为模型,该模型中每个个体朝着包围其邻域范围内所有其他个体的最小外接圆圆心位置移动,在不需要知道群体全局信息(所有个体的位置信息)的情况下能实现全局无分裂的蜂拥行为,体现了局部控制策略影响全局群体行为的思想。Zavlanos等人32讨论了群体保持连通的重要性,在设计个体的运动控制方程中提出了一类势能场函数来保持个体之间的连通性,即在个体之间的相对距离处于临界最远距离时使得势能作用力为无穷大,从而使之保持连通。 4 结束语对生物群体动态行为产生机制的理解不仅可以作为参考用于设计实用的工程群体模型,而且其基于个体之间简单交互而导致群体复杂行为的涌现机制对于工程系统的优化设计也是具有很大的启发作用。例如当前流行的粒子群优化算法(particle swarm optimization)就是1995年由美国社会心理学家 James Kennedy 和电气工程师Russell Eberhart 基于鸟群的群体蜂拥行为的产生机制而提出的,这种方法也正在显示着巨大的潜在用途。因此在今后的研究过程中,考虑综合生物领域与工程领域的研究成果,一方面可以使得受自然生物群体的协调行为启发而研究的工程智能群体行为能够获得这些自然现象中表现的某些特性,如群体涌现的协调性、自适应性、鲁棒性,另一方面通过研究实际复杂工程群体系统的控制与设计工作,可以帮助研究人员对生物群体动态行为的涌现机制产生新的理解和认识。参考文献:1程代展,陈翰馥.从群集到社会行为控制J.科技导报,2004(8):4-7.2PARRISHJK,EDELSTEIN-KESHETL.Complexity,pattern,and evolutionary trade-offs in animal aggregationsJ.Science,1999,284(2):99-101.3ERMENTROUT G B,EDELSTEIN-KESHET L.Cellular automata approaches to biologicalmodelingJ.Journal of Theoretical Biology,1993,160(1):97-133. 4VABOE R,NOETTESTAD L.An individual based model of fish school reactions:predictingantipredatorbehaviouras observedinnatureJ.Fisheries Oceanography,1997,6(3):155-171. 5周登勇,戴汝为.适应性行为与仿真J.系统仿真学报,2000,12(6): 578-583.6MORALE D.Modeling and simulating animal groupingindividual-based modelsJ.Future Generation Computer Systems,2001,17(7):883-891. 7GAZI V,PASSINO K M.Stability analysis of swarmsJ.IEEETrans on Automatic Control,2003,48(4):692-697.8GAZIV,PASSINOKM.A class of attraction/repulsionfunctionforstable swarm aggregationC/Proc of the 41st IEEE Conference on Decision and Control.S.l.:IEEE Press,2002:2842-2847.9CHU Tian-guang,WANG Long,MU Shu-mei.Collectivebehavior analysis of an anisotropicswarmmodelC/Proc of the 16th InternationalSymposiumonMathematical TheoryofNetworkandSystems.Berlin:Springer,2004:1-13. 10SHI Hong,WANG Long,CHU Tian-guang.Swarming behavior of multi-agent systemsJ.Journal of Control Theory and Applications,2004,2(4):313-318. 11JADBABAIE A,LIN Jie,MORSE A S.Coordination of groups of mobile autonomous agentsusing nearest neighbor rulesJ.IEEETrans on Automatic Control,2003,48(6):988-1001. 12GAZI V,PASSINO K M.Stability analysis of social foraging swarmsJ.IEEE Trans on Systems,Man,and Cybernetics part B:Cybernetics,2004,34(1):539-556. 13LIU Yang,PASSINO K M,POLYCARPOU M M.Stability analysis of one-dimensional asynchronous mobile swarmsC/Proc of IEEE Conference on Decision and Control.2001:1077-1082.14LIU Yang,PASSINO K M,POLYCARPOU M M.Stability analysis of M-dimensional asynchronous swarms with a fixed communicationtopologyJ.IEEE Trans on Automatic Control,2003,48(1):76-95. 15LIU Yan-fei,PASSINO K M.Stable social foraging swarms in a noisy environmentJ.IEEE Trans on Automatic Control,2004,49(1):30-44. 16REYNOLDS C.Flocks,herds, and schools:adistributedbehavioralmodelJ.Computer Graphics,1987,21(4):25-34.17VICSEK T,CZIROK A,BEN-JACOB E,et al.Novel type of phase transitions in a systemofself-drivenparticlesJ.Physical Review Letters,1995,75(6):1226-1229. 18OLFATI-SABER R.A unified analytical look at Reynolds flocking rules,Technical Report 2003-014R.California:California Institute of Technology,2003. 19OLFATI-SABER R.Flockingwithobstacle avoidance,Technical Report 2003-006R.California:Institute of Technology,2003. 20陈世明.群集行为的建模与控制方法综述J.计算机工程与科学,2007,29(7):102-105.21REIF J H,WANG Hong-yan.Social potential fields:a distributed behavioral control forautonomous robotsJ.Robotics and Autonomous Systems,1999,27(3):171-194.22TANNER H G,JADBABAIE A,PAPPAS G J.Stable flocking of mobile agents, part I:fixed topologyC/Proc of the 42nd IEEE Conference on Decision and Control.S.l.:IEEE Press,2003:2010-2015.23TANNER H G, JADBABAIE A,PAPPAS G J.Stable flocking of mobile agents, part :dynamic topologyC/Proc of the 42nd IEEE Conference on Decision and Control.S.l.:IEEE Press,2003:2016-2021. 24TANNERHG.Flockingwithobstacle avoidance in switching networks of interconnectedvehiclesC/Proc of IEEE International Con-ference on Robotics and Automation.S.l.:IEEE Press,2004:3006-3011.25WANG Long,SHI Hong,CHU Tian-guang.Flocking control of groups of mobile autonomous agents via local feedbackC/Proc of IEEE International SymposiumonIntelligentControl.S.l.:IEEE Press,2005:441-446. 26GAZI V.Swarmaggregationsusing artificialpotentialsandslidingmode controlC/Proc ofIEEE Conference on Decision and Control.S.l.:IEEE Press,2003:2041-2046.27TANNER H G,JADBABAIE A,PAPPAS G J.Flockinginfixedandswitching networksJ.IEEE Trans on Automatic Control,2007,52(5):863-868.28OLFATI-SABER R.Flocking for multi-agent dynamic systems:algorithms and theoryJ.IEEE Trans on Automatic Control,2006,51(3):401-420.29SHIHong,WANGLong,CHUTian-guang.Virtualleaderapproachtocoordinated controlofmultiplemobileagentswith asymmetricinteractionsJ.PhysicaD,2006,213(1):51-65. 30陈世明,方华京.大规模智能群体的建模及稳定性分析J.控制与决策,2005,20(5):490-494.31CHEN Shi-ming,FANG Hua-jing.Modeling and stability analysis of emergent behavior of scalableswarmsystemJ.Journalof Zhejiang University:Science A,2006,7(6):952-959.32ZAVLANOS M M, JADBABAIE A,PAPPAS G J.Flockingwhilepreservingnetwork connectivityC/Proc of the 46th IEEE Conference on Decision and Control.S.l.:IEEE Press,2007:2919-2924.开题报告格式