多智能体群集系统分群行为研究进展

李成凤， 张阳伟， 邵俊倩， 高 亮

(绥化学院，a.电气工程学院; b.信息工程学院，黑龙江 绥化 152000)

0 引言

群集是自然界中普遍存在的一种现象[1]，受此启发，多智能体系统的群集行为近年来也成为多智能体系统研究中的热点问题[2]。随着研究的深入，学者们发现完备的群集系统协同行为应分为组群和分群两种形式。其中：组群是传统意义上的群集行为，即要求某一区域内随机分布的多个智能体能无碰撞地聚集并以相同的速度和运动方向共同执行任务；而分群则是群集系统在各类分群诱因作用下分裂成为若干个子群的行为[3]。目前，对群集系统组群行为的研究已经取得了丰硕的成果，而对分群控制的研究仍处于初步开展阶段，并主要集中在理想环境下分群算法的研究。鉴于此，本文将从系统组成、信息交互机制及分群的稳定性分析方法3个角度对分群行为的研究现状进行总结及分析，以期对分群控制的研究起到促进作用。

1 群集系统的组成

在研究群集系统分群行为时，首先要明确系统的组成。一般从构成群集系统的智能体异同角度来说，能够实现分群的群集系统主要可以分为异构群集系统和同构群集系统两类。

1.1 基于异构的群集系统分群

异构群集系统是指群体中的智能体之间存在结构或功能上的差异，如配备不同的传感器导致感知能力不同，或物理属性的差异导致动力学模型不同，但正是这些差异使得异构群集系统能够完成相对复杂的任务[4]。现对异构群集系统的分群研究成果进行总结，相关简介见表1。表中：d为期望间距;r为感知半径。

表1 异构群集系统的分群研究成果

文献[5]智能体的异构体现为期望间距和感知范围不同，提出了具有多个虚拟领导者的群集算法，认为分群可看作是相邻个体或个体与虚拟静态/动态障碍物之间的避障问题，且期望距离在分群过程中起关键作用。虽然该算法能够有效地实现分群，但各子群却需要按照期望间距事先划分。

文献[6]借鉴异质细胞的差异黏附模型，使个体间的差异体现在相互作用势能上，即同类型个体、不同类型个体之间的相互作用势能具有不同参数值，实现了两种异构智能体的分群控制，但所设计的算法存在易陷入局部极小而导致分群失败的问题。

文献[7]提出了新型的势能函数，进一步实现了具有多种类型的异构机器人的分群控制，并解决了文献[6]的算法失效问题，但仅实现了全局交互下同等子群规模的分群行为。

文献[8]受巴西果效应启发，设计了每个个体的运动由随机游动、趋同性和被其他个体排斥3种反应行为控制，从而实现了由不同虚拟尺寸机器人组成的异构群集系统的自组织分群行为。

文献[9]基于粒子群算法(PSO)和最优交互避碰(ORCA)算法，设计了具有多种类型的异构机器人分群算法，能够实现任意子群规模、任意子群数量的分群，但未能给出算法的收敛性证明。

文献[10]中个体差异体现在感知距离、期望距离和目标不同，II型智能体用于获取真实目标信息并主动跟踪真实目标，I型智能体仅需要给定的II型智能体信息以辅助II型智能体，对两类智能体分别设计基于Reynolds规则[11]的控制输入，实现分群跟踪。但每个I型智能体所跟踪的II型智能体也是事先分配的，即子群是事先划分的。

1.2 基于同构的群集系统分群

同构的群集是指构成群集系统的所有智能体都被假设具有相同的模型结构和功能。目前基于同构假设的分群文献居多，如文献[12-22]均假设个体无差别，均具有相同的数学模型和环境感知能力等。与异构群集系统依靠异构属性进行分群不同，由于个体无差别，故需引入不同分群诱因来实现分群目的。现将同构群集系统的分群研究成果进行总结，相关简介见表2。

表2 同构群集系统的分群研究成果

文献[12]中设计距离概率项和概率密度项作为个体进行领导者选择的依据，文献[13]中个体利用蚁群算法规则选择所要跟随的领导者，并分别基于同一子群个体间和不同子群个体间的势能函数设计控制策略，使群体分裂成跟踪不同领导者的子群。但领导者作用范围为全局，这与实际生物群体和工程应用相悖[23]，因此只适用于小规模的群集。此外，文献[13]中个体根据接收到的领导者子群规模需求信息和周围邻居跟踪不同领导者的情况选择领导者，因此，需要个体具有一定的通信能力。

文献[14]提出了基于领导者-跟随者的分群控制算法，其中的领导者是群体中的真实个体，根据跟随者到不同领导者的层级大小，采用广播应答形式实现子群规模可控的分群控制，但既需广播又需应答的信息交互增加了个体之间交互的复杂度，因此仅适合于具有广播应答条件的小规模分群。

文献[15-21]中的分群诱因均为外界环境刺激(如障碍物、危险等)，通过设计使边缘个体感知到的外界环境刺激能在群内实现有效快速传播的信息交互机制，结合经典的“分离-结对-聚集”规则[1]设计分群算法，实现自组织分群运动。虽然所设计的分群策略对群集的规模没有约束，但子群规模和速度均不可控，仅适用于对称刺激下等规模分群。

文献[24-32]基于群体内部作用实现分群，其中，文献[24]设计了同子群速度协同力、避免碰撞力和子群内聚力来实现多分群。但子群需事先划分，因此，需要有高级控制中心进行协调。文献[25-27]中个体间相互作用为远程吸引、近程排斥和类高斯中程排斥作用，前两者实现内聚和避免碰撞，后者实现群体分裂，并通过参数设置实现子群规模预测和设定。但该方法中每个个体都受预先设定的子群个数、排斥距离等全局分群参数控制，需引入集中式协调机制，故不适合大规模群集，并且所实现的分群通常为规模对称分布的子群，未能实现按任务需求自发产生相匹配的子群规模，故其应用范围有所局限[3]。文献[28-29]基于内部作用实现二分群(分成速度大小相同、方向相反的两个子群)。前者设计不同群体之间的作用力和相同群体内部作用力实现分群，后者设计包含排斥-吸引力以及摩擦力的两群体相互作用模型实现分群。但该类方法仅能实现二分群，使其应用范围受到较大限制。文献[30-32]根据内部作用和初始条件约束实现基于C-S模型的分群。文献[30-31]实现了二分群，受此启发，文献[32]实现了等级C-S模型的多分群，虽然通过计算初始数据，可确定有多少子群出现和哪些个体在同一个子群，但此方法仅在内部作用参数满足一定条件且初始位置和速度具有有序关系时才能实现分群。因此，需要有高级控制中心对群体的初始状态进行协调，不适合大规模群集。

文献[33-36]基于合作对抗网络实现分群，利用符号图描述个体之间的合作竞争关系。文献[33]基于合作对抗网络，利用结构平衡的符号图理论和指定的势函数，在虚拟领导者和无领导者的情况下实现了二分群。文献[34]实现了固定时间的二分群，文献[35]针对文献[34]推导过程中存在的缺陷，改进了协议证明推导方法，并降低控制策略参数取值的保守性，推广了策略的应用范围。文献[36]针对文献[30-34]分群过程中个体之间可能存在碰撞问题，利用新的固定时间稳定定理和结构平衡符号图理论，在固定时间内实现了无碰撞的二分群，并根据协议参数、网络连通性和系统初始状态，估计出每个不连通子群的规模上限。尽管该类方法能够实现渐近和固定时间二分群，但群体中的合作对抗关系必须满足结构平衡的假设条件。因此，需高级控制中心事先确立结构平衡的合作对抗关系，这使其应用范围在二分群基础上进一步增加了限制。

2 信息交互机制

与组群行为的形成类似，群集系统分群行为的产生也与智能体之间的信息交互密切相关。目前,分群行为研究中常用的信息交互机制主要包括基于固定邻居距离的信息交互和选择性信息交互。

2.1 基于固定邻居距离的信息交互

基于固定邻居距离的信息交互是指群集系统中的每个个体均与其感知范围内的所有其他个体进行信息交互。这是通常意义上的局部信息交互，是群集系统组群行为研究中采用最多的信息交互机制[22]，目前大多数分群控制研究也都继续沿用该信息交互机制。采用该机制的优势在于：1)更符合工程实际，因为实际的无人自主控制系统配备的传感器或通信设备的探测范围是有限的，个体只能通过传感器探测到其感知范围内的其他个体的运动状态信息，或利用通信设备进行局部范围内的信息交互；2)便于进行分群控制方法的理论分析，由于在该信息交互机制下，若个体1为个体2的邻居，则个体2也为个体1的邻居，整个群体所构成的信息交互拓扑图为无向图，个体的邻接矩阵是元素为0和1的对称阵，使得组群控制研究中广泛使用的邻接矩阵及拉普拉斯矩阵的对称性等重要结论在分群控制研究中依然成立，进而可在分群控制中继续沿用组群控制中的稳定性分析方法。

但群集系统的群体规模通常较大，若采用基于固定邻居距离的信息交互机制，个体要与感知范围内的所有邻居个体都进行信息交互，容易造成系统通信量过高、计算量过大的问题，进而导致算法速度降低。此外，为实现速度协同，通常采用的以固定邻居距离的信息交互机制为基础的速度平均方法，会导致群集系统难以实现应激分群行为[16]。

2.2 选择性信息交互

与基于固定邻居距离的信息交互不同，选择性信息交互不是盲目地与感知范围内的所有邻居个体都进行信息交互，而是按照一定的规则或指标选择感知范围内的部分邻居个体进行信息交互[37]。选择性交互是在固定邻居距离的交互基础上，进一步结合生物群集现象所得出的信息交互机制，已成为多智能体群集研究的一个趋势。现将选择性信息交互机制进行总结，并对其各自的交互对象、不足及适用场合等进行详细分析与讨论，相关简介见表3。

表3 选择性信息交互机制研究成果

文献[15]中位置信息采用基于固定邻居距离方式进行交互，而速度信息则在邻域跟随机制和固定邻居距离交互机制之间进行切换，执行跟踪行为时个体选择其感知范围内相对位置变化最大且距离较近的邻居进行速度信息交互，当跟随行为达到作用时限时，自动切换为固定邻居距离交互。通过对个体跟随目标的选择和切换实现外界刺激的有效信息在群内定向传播，达到分群目的。可见，速度信息交互模式的切换在一定程度上减少了个体间的信息交互量，控制规律也得到简化。但在选择局部跟随目标时，会用到邻居个体上一采样时刻的位置信息，故需要群集内个体具有一定的记忆能力。

文献[16]提出了一种结合邻居运动方向、速度大小、距离、邻居个数和自身感知距离等信息的综合定量指标“信息耦合度(ICD)”，并基于ICD提出“min-max”速度信息交互机制，使个体仅选择与ICD最大和最小的两个邻居进行速度信息交互，从而使个体能同时对邻居中呈现的有序运动和异常变化情况保持敏感，满足组群和分群行为两方面的协同需求，并在大规模群集中体现出更高效的组群优势。与文献[15]的速度信息交互切换模式相比，控制律得到了进一步简化。但ICD涉及的信息较多，且定义相对复杂，因此，在文献[17-19]中对其进行不同程度的简化，以减少计算量，降低计算复杂度。

文献[17]定义的ICD包括位置耦合项和速度耦合项，前者与个体及其邻居相对位置有关，后者与个体和邻居相对速度以及邻居速度均值有关。但是,此ICD定义仍相对复杂，且由于ICD最大个体信息的融入，控制律也相对复杂。文献[18]的ICD包括位置耦合项和相对运动耦合项，前者与个体相对位置有关，后者由采样时间间隔内相对位置变化来表征。可见，ICD仅由自身及邻居位置信息决定，无需速度信息，减少了系统所要测量的信息量，增强了算法的实用性。文献[19]采用采样时间间隔内相对位置变化来表示ICD，使其定义得到进一步简化。需指出，文献[17-19]基于ICD最大的选择性信息交互机制中，虽然是选择ICD最大的邻居个体进行信息交互，但在此基础上的控制律设计中，个体信息交互的对象实质上仍为其所有邻居，而最大ICD邻居信息最终被融入分群控制律中，并在采样间隔内与周围特定邻居建立强交互作用实现外部刺激信息的定向流转，从而实现群集的自组织分群行为。

文献[20]提出了基于平均交互和选择交互的速度间歇性交互机制，利用系数调整两种交互的权重，并设计随群体速度状态变化的ICD(由个体和其邻居位置和速度信息来表征)阈值函数，使群体在无序运动状态下阈值较大，很难发生选择交互行为，倾向于融合行为，而当群体处于有序状态时，阈值较小，易发生选择交互行为，进而促进外部刺激信息的传递并诱发分群行为。此交互机制不仅有利于分群的产生，也有利于子群在外界刺激消失时再次融合为一个群体。但由于平均交互和选择交互并存，计算量和复杂度会增加。

文献[21]提出结对交互机制，令个体与其感知范围内运动方向变化最大的个体产生结对行为，实现机器人运动状态的调节，达到分群目的。但这种结对对象的选择标准需要用到邻居前一时刻的运动方向信息，因此，要求个体具有一定的记忆能力。

文献[38]提出一种基于注意力的跟随机制，使个体选择跟随其所感知到的最近目标或感知到目标且距离最近的邻居，并将该机制融入到基于改进拟态物理法的分群控制律中，实现多目标环境下的分群行为。需要指出的是，该机制是根据邻居状态信息实现分群控制，而没有以计算形式来选择跟随对象，减少了计算量与计算过程中的不确定因素，但这要求个体能够识别邻居是否检测到目标。因此，该机制适用于具有识别能力的群集。

3 分群控制的稳定性分析方法

稳定性是分群控制方法的基本特性，是分群控制研究中的重点和难点之一。很多文献均只通过仿真实验验证了所设计的分群控制算法的有效性，并未能从理论上给出相应的稳定性分析。此外，选择性信息交互机制的引入导致拓扑结构图的有向性和不对称性，提高了分群算法稳定性的理论分析难度[3]。文献[5]以图论、矩阵论为基础，利用Lyapunov稳定性定理证明每个虚拟领导者对应的子群都能形成稳定群集，利用Lasalle不变原理证明子群中个体速度一致。文献[6,10,12]利用图论、矩阵论、Lyapunov稳定性定理分析了分群控制算法的稳定性。文献[7,13,18]利用图论、矩阵论、Lasalle不变原理证明了所设计的分群算法的稳定性。文献[19]在定常时滞情况下，利用Lyapunov-Razumikhin定理导出了分群控制算法的充分条件。针对时变时滞情况，采用Lyapunov-Krasovskii泛函方法，利用线性矩阵不等式(LMI)得到了分群控制算法的充分条件。文献[24]基于代数图论和Barbalat引理建立了收敛准则，以保证子群聚集和速度一致，以及整个群集系统中所有智能体之间的避碰。文献[30]利用Lyapunov泛函方法，得到每个子集合形成群集的充分条件。文献[33]中的Lipschitz函数、Barbalat引理证明了二分群集控制算法的有效性。文献[34]利用图论、Lasalle不变原理和Barbalat引理解决了动态双积分器中的二分群集问题。文献[35-36]利用结构平衡图理论、固定时间稳定定理和Lyapunov稳定性定理证明了二分群集策略的有效性。文献[22]基于固定时间稳定定理和结构平衡符号图理论，给出了二分群集的充分条件，利用非光滑分析，可以在有限的时间内产生固定时间的非碰撞二分群集。

从上述研究成果看，目前用于分群控制稳定性分析的方法主要包括图论、矩阵论、Lyapunov稳定性定理、Lasalle不变原理、Barbalat引理、泛函分析等。其中，图论和矩阵论是分群控制设计和分析中不可缺少的理论基础，与其他理论分析方法中的一种或几种进行组合共同实现稳定性的证明。另外，进行固定时间的分群算法的稳定性分析时还要用到固定时间稳定定理。

4 结束语

针对异构和同构群集系统分群问题展开的研究，在一定程度上实现了分群目的，但仍有各自的局限性。所界定的异构属性不同，且实际异构属性也不限于上述文献所列，导致所设计的分群算法基本无法扩展到其他异构群集系统的分群控制中。而同构群集系统分群的子群规模、运动速度等大多仍不可控，还需要进一步研究如何在分群诱因的设计中去体现对分群的性能要求，以实现性能可控、满足实际应用的分群效果。此外，目前所设计的分群控制算法大多只针对单一类型的群集系统，并不具有普适性。因此，同时适用于同构和异构群集系统的分群控制算法将是未来研究的一个重点。并且，与渐近分群相比，固定时间分群更具有工程意义，但目前关于固定时间的分群仍局限于二分群，还需进一步将其拓展至多分群集中。

多智能体群集系统的信息交互机制大多从模拟生物群集的信息交互机制入手，从上述研究成果可知这一思路的有效性。因此，想要使多智能体群集系统更好地显现出生物群集系统所涌现的群体智能，需要结合生物学、统计学等领域在生物群集系统信息交互机制方面最新的研究，进一步深入研究和模拟生物群集系统的信息交互机制。

此外，与基于固定邻居距离的信息交互群集相比，虽然选择性信息交互机制的引入能够使群集系统快速响应外界环境刺激实现分群行为，但却增加了稳定性分析难度；并且随着研究的不断深入，群集系统所处运行环境的复杂性和分群可控性要求也会提高，这将会给稳定性的理论分析带来新的挑战，因此，要继续深化现有的稳定性分析方法，并积极拓展新的理论分析研究思路,探求适合于复杂环境下可控分群行为的稳定性分析理论和方法。