2018, Vol. 33
群集行为是大量个体通过相对简单的局部自组织交互在集体层面上涌现出的一种有序运动现象[1], 而其分裂(fission)与融合(fusion)运动是各种群集现象(如聚集、编队、迁徙、分裂等)得以形成的基础[2].通常, 群集利用融合行为可实现个体的自发聚集、编队等协同运动, 而通过部分个体从母群中分离而出的分裂行为可执行诸如多目标跟踪[3]、多点监控以及危险自主规避[4]等任务.群集的分裂/融合行为是其对环境适应能力的典型体现, 对群集的生存、演化与繁衍起着至关重要的作用[2].
目前, 关于群集运动的研究主要集中在其融合行为方面(如聚集、编队、信息一致性等). Reynolds[5]于1987年提出了包含“分离/对齐/聚集”规则的“Boids”模型, 奠定了自组织群集运动研究的基础; Vicsek等[6]仅利用“对齐”规则, 建立了自由空间自驱动粒子(Self-propelled particles, SPP)群集运动的离散模型; Jadbabaie等[7]从拓扑图论角度出发, 对该模型进行了严格的理论分析; Ren等[8]研究了切换拓扑下的群集信息一致性问题, 指出其实现一致性的必要条件是拓扑图的并集中包含最小生成树; Olfati-Saber[9]针对群集系统的蜂拥控制问题, 提出了一系列群集编队运动控制算法.
大量研究表明, 生物群集在无任何高等级中央控制或沟通协调下, 仅依靠个体间的自组织交互便可聚集成有序运动的群集, 亦可根据外部环境刺激自发分裂成若干个子群[4, 10].因而, 从仿生学角度, 一个完备的群集协同方法应同时具备对其分裂与融合行为进行表征的能力[2, 11].但是, 受限于对群集运动认知的偏颇, 早期研究很少将群集的分裂/融合行为纳入统一的协同框架下进行讨论, 导致目前所提出的群集协同方法在功能完备性和环境适应性上尚存在诸多不足[1-2].
近年来, 随着人们对群集运作机制认知的加深, 研究人员开始尝试采用同一套协同规则对群集的分裂/融合现象进行表征与控制. Morgan等[12]通过在“leader-follower”协同策略中引入同伦参数控制跟随作用强度, 实现了群体的分裂与融合运动. Chen等[13]在“远距吸引-近距排斥”规则中引入“中距排斥力”, 再现了群集的自组织分裂/融合行为; Navarro[14]在群集机器人协同框架中加入分群控制模块将机器人分成不同团簇, 并结合避障模块达到机器人群集自发分群/组合的目的. Liu等[11, 15]从个体间关联强度出发, 提出了一种基于信息耦合度的群集协同控制方法, 使其具备了自发融合与应激分裂能力.
然而, 以上研究均假设个体仅能根据自身及周围邻居的当前运动信息(如位置、速度等)对其行为进行调节, 缺乏对未来信息的预见性.事实上, 生物体普遍具备一定的“预测智能”[16], 可根据过去的运动信息对未来状态进行预测.早在1959年, Woods[17]便通过实验证实了蜂群编队中预测机制的存在; 在此基础上, Montague等[18]提出了一种基于赫布学习的预测规则来刻画蜜蜂在未知环境中的觅食行为; David[19]通过对视觉感知机制的研究, 发现其视觉适应行为可以使眼睛对所注视物体的未来位置进行有效预测.上述研究表明, 预测机制在个体的行为决策中发挥了重要作用.
受此启发, 本文在文献[11, 15]的基础上, 针对群集系统的自组织分裂/融合问题, 考虑将预测智能融入其协同控制律的研究中.首先, 设计一种基于最小二乘估计的预测机制, 实现对邻居行为的预测.然后, 从群内信息传播的角度出发, 提出一种融入预测信息的群集协同控制算法, 实现群集的自发组群和外部刺激下的应激分裂运动.仿真结果表明, 引入预测机制可显著提升群集的自组织分裂/融合性能, 对增强群集的运动灵活性和环境适应能力均具有重要意义.
1 问题描述考虑在n维空间运行的N个无差别个体组成的群集系统, 其个体动力学方程如下:
|
(1) |
其中: pi∈Rn和vi∈Rn分别为个体i的位置和速度向量, ui∈Rn为加速度向量(作为控制输入).
对于群集系统而言, 其个体感知能力有限, 只有位于群集边缘的个体才能直接与外部环境发生交互, 而群内大多数个体的行为只能由周边有限范围内的邻居决定[11].因此, 一个典型的群集协同控制律可写成如下形式:
|
(2) |
其中: uiin为周围邻居施加在个体i上的内部作用力之和; f(·)为作用力函数; 
在目前的群集分裂/融合行为研究中, 个体大多根据当前所获取的邻居信息对自身的运动进行调节[11, 13, 15].该方法虽然能够实现群集的自组织分裂/融合运动, 但却未能有效发掘个体的预测能力, 无法对未来一段时间内邻居的行为进行有效的预测和判断, 在一定程度上造成个体决策的“短视性”, 降低了群体运动的效率.
鉴于此, 本文的研究目的是将预测机制引入群集的自组织分裂/融合行为中, 通过赋予个体一定的“预测智能”, 使其具备对邻居行为进行预测的能力, 从而显著提升群集的“预见性”, 以增强群集的运动灵活性和环境应激能力.
2 基于预测机制的群集分裂/融合算法生物普遍具备一定的“预测智能”, 可以根据历史信息对未来状态进行预测[16-19].受此启发, 本节采用最小二乘估计的方法对邻居的运动行为进行预测, 并据此提出一种基于预测机制的群集自组织分裂/融合算法.
2.1 基于最小二乘估计的邻居状态预测对于生物群集而言, 其个体运动状态连续且通常不会发生突变, 具有很强的可预测性[16].在此, 采用最小二乘法对其预测行为进行模拟.
定义xj(k)=[pj(k), vj(k)]为k时刻邻居j的运动状态, 并令Xj(k, H)=[xj(k-1), xj(k-2), …, xj(k-H)]T为邻居j在k时刻之前的H个状态序列, 则邻居j的预测状态可表示为
|
(3) |
其中W=[ω1, ω2, …, ωH]为预测权值系数向量.
从式(3)可以看出, 邻居j在k时刻的预测状态xjP(k)为其之前H个状态序列的加权求和, 其核心在于确定预测权值系数向量W.
为推导出W的具体形式, 在此采用如下线性模型对邻居j的预测状态进行逼近:
|
(4) |
其中a=[ap, av]和b=[bp, bv]为线性模型参数.
将式(4)写成如下矩阵形式:
|
(5) |
其中
|
(6) |
则预测误差可以写成
|
(7) |
采用最小二乘法, 将代价函数设计为
|
(8) |
寻找最优近似线性模型
|
(9) |
在ψ=0处沿式(8)对ψ求导, 可得
|
(10) |
结合式(3)和(5), 可得τ步之后邻居j的预测状态为
|
(11) |
由式(6)可知
|
(12) |
其中
|
由于H>1, HΩ1(k)-[Ω2(k)]2=H2(H2-1)/12, 有
|
(13) |
由式(11) ~ (13)可知预测权值系数向量为
|
(14) |
最后, 将式(14)代入(3)中, 即可得到邻居j在k时刻的预测状态xjP(k).
2.2 基于邻居状态预测的群集自组织分裂/融合方法群集的自组织分裂/融合行为均是群集与外部环境作用下的自发反应, 是“同一套机制”在不同条件下所产生的“迥异结果”[1].基于该认识, 提出如下群集自组织分裂/融合控制律:
|
(15) |
其中:
1) uifus为群集融合项, 实现个体的空间聚集和运动有序性, 主要包含两部分:
ⅰ) uipos是位置协同项, 用于调节个体与其周围邻居间的距离, 起到了远距排斥/近距吸引的作用, 有
|
(16) |
A, B>0为调节参数, C>0为个体间平衡距离, dij =pj-pi为个体i与j之间的距离.
ⅱ) uivel是速度协调项, 保证群集运动的有序性.在此采用基于“平均规则”的速度一致性方法实现, 即
|
(17) |
Ni为个体i的周围邻居数量.
2) uifis为群集分裂控制项, 是外部环境刺激和个体间内部交互两者共同作用的结果[11, 15]:
ⅰ) uicoord是个体间的内部交互作用项, 用于对群集的分裂/融合行为进行自组织协调.在此, 引入对邻居行为的预测机制, 将其设计成
|
(18) |
uicur为基于当前邻居状态的运动协调项, uipre为利用预测的邻居信息的运动控制项. α∈[0, 1]为调节两项作用强度的参数, 当α→1时, 个体仅依靠当前邻居信息进行决策; 当α→0时, 个体则更倾向于根据预测的邻居信息对自身行为进行调节.
基于文献[15]所提出的“成对交互”方法和“最大信息耦合度(maximum-ICD)”分群控制策略, 从促进群内信息传播的角度, 选择个体交互作用强度最大邻居li为
|
(19) |
其中
|
(20) |
其中ζij, κij>0为交互强度系数.
为了增强算法鲁棒性, 防止无序随机分裂现象发生, 引入参数
|
(21) |
其中: β>0为阈值调节参数; ϕi为表示个体周围邻居运动有序程度的参数(序参量), 有
|
(22) |
Ni为个体i周围的邻居数.
在此基础上, 将邻居li的运动信息作为个体i运动行为的临时引导项, 并将其融入群集协同控制律中, 有
|
(23) |
其中: pli和vli分别为邻居li当前的位置和速度信息, pliP和vliP分别为个体i依据式(3)所预测的邻居li的位置和速度信息.
ⅱ) uiout为外部刺激项, 通常为一个已知的吸引力(如食物源位置或迁徙方向)或排斥力(如危险的距离、方位), 其具体形式将在仿真验证部分给出.
注1 从式(19) ~ (22)可以看出, 个体会根据序参量ϕi自发调节与邻居的成对交互作用.当序参量很小时(ϕi≈0), 个体运动无序, 阈值
注2 对于群集的自组织分裂/融合控制律(15)而言, 其融合项uifus和分裂项uifis是相辅相成、缺一不可的.若仅有融合项而无分裂项, 群集将处于“凝聚不散”的聚合状态, 失去了对外部刺激的有效应对能力; 而倘若仅有分裂项而无融合项, 群集则可能陷入“无序分裂”的混乱状态, 丧失群集运动得以形成的基础.正是由于分裂和融合作用的有机结合, 才使得群集具备了良好的运动有序性和环境应激能力.
3 仿真验证 3.1 仿真设置为了验证本文所提的基于预测机制的群集自组织分裂/融合方法的可行性和有效性, 选取30个个体在Matlab下展开仿真研究, 其初始位置随机分布在15×15 m2的二维平面内, 初始速度均为0 m/s.其他仿真参数为: R=15 m, ζij=0.3, κij=2, β=0.25, A=0.2, B=0.01, C=3, τ=1, H=5, α=0.5.
假设群集运行在无障碍的自由空间, 在控制律(15)的作用下首先开始群集的编队融合运动.待编队稳定后(t≥6 s), 在群集边缘选择两个个体(设为个体1和个体2)从群内分离而出(模拟部分个体感受到外部刺激的情形), 其所受的作用力分别为
|
(24) |
其中: γ1=γ2=10为反馈系数, v1stimu=[0 -8]T m/s和v2stimu=[-8 0]T m/s分别为个体1和个体2的期望速度.
3.2 仿真结果图 1为群集在融合/分裂过程中的运动曲线.其中:空心圆圈表示个体的初始位置, 实心圆点为其终止位置, 实线代表其运动轨迹.此外, 用菱形表示感受外部刺激个体的终止位置, 并用加粗的实线表示其在感受外部刺激后的运动轨迹.
|
图 1 群集融合/分裂运动轨迹曲线 |
从图 1可以看出, 个体在群集融合/分裂控制律(15)的作用下, 首先从初始随机分布状态聚集成群, 并以编队的形式有序运动.在部分个体感受到外部刺激从群内分离而出时, 其余个体能够自发实施分裂运动, 从一个紧致的母群分裂成两个独立运行的子群.
图 2给出了群集融合/分裂过程中的个体速度曲线.其中: 0~6 s为个体从初始状态聚集并开始编队运行的阶段, 个体会从初始速度0逐渐趋近于期望的编队速度; 6~10 s为群集在外部刺激下的分裂运动阶段, 曲线代表感知外部刺激信息个体的速度.从图 2可以看出:在群集融合阶段, 个体速度会渐近趋于一致, 实现了群集的有序编队; 在群集分裂阶段, 子群中个体速度会分别趋近于从群集中分离而出的两个个体的速度, 从而保证了分裂后子群运动的有序性.
|
图 2 群集融合/分裂运动速度曲线 |
由此可见, 群集在控制律(15)的作用下能够实现自发的聚集与编队运动, 在部分个体感受到外部刺激从群内“挣脱”而出时, 能够实现有序的分裂运动, 且分出的子群能够以编队形式稳定运行.群集这种优良融合/分裂能力的获得, 得益于本文所提出的群集自组织分裂/融合控制律(15), 使其能够同时保持群集运动的有序性和对外部刺激的敏感性, 从而显著增强群集的运动灵活性和环境适应能力.
3.3 对比分析为便于更客观地将本文所提算法的性能与现有的群集分裂/融合控制方法(参见文献[11, 15])进行比较, 下面分群集融合与分裂两种运动模式, 对其进行定量分析.
1) 群集融合运动.定义群集融合耗时Tfus和速度一致方差Cvel两项指标, 对引入预测机制前后群集融合运动的性能进行评价.其中:群集融合耗时表示个体从无序随机运动到速度一致所消耗的时间; 速度一致方差表征个体在融合运动过程中与邻居平均速度的偏差程度, 有
|
(25) |
表 1给出了引入预测机制前后群集的融合耗时对比, 可见引入预测机制之后, 借助于对邻居未来状态的提前“感知”, 能够有效降低群集融合行为的耗时, 从而有助于提升群集的编队快速性, 并且随着群集规模的增大, 其优势更为明显.
|
表 1 引入预测机制前后的群集融合耗时对比 |
另外, 从表 2对引入预测机制前后群集速度一致方差的对比也可以看出, 引入预测行为后, 在同一时刻, 个体与周围邻居的运动偏差会显著降低, 表明个体与邻居的运动行为更为一致, 从而有助于促使群集运动的有序性快速达成.
|
|
表 2 引入预测前后的群集融合运动速度一致方差对比 |
2) 群集分裂运动.定义分裂耗时Tfis对引入预测机制前后群集分裂运动的性能进行评价.在此, 分裂耗时表示群集从开始分裂到分裂出的子群独立稳定运行所消耗的时间.
从表 3可以看出, 引入预测后, 群集分裂耗时会大幅下降, 且随着群集规模的增大, 这种优势更为明显.究其原因, 是由于预测的引入有助于个体利用邻居的未来信息对自身行为进行决策, 从而促进了刺激信息在群内的定向流转, 使得群集的分裂耗时显著降低, 进而快速实施分群机动, 提高了其运动灵活性.
|
|
表 3 引入预测机制前后的群集分裂耗时对比 |
综上可知, 引入预测信息可以显著提升群集的运动性能, 使群集能够快速、高效、有序地执行分裂/融合运动.该优良特性的获得, 在于预测机制的引入能够使个体增强其信息获取的“提前性”, 可依据邻居的预测状态提前对其运动进行调节, 从而提升了个体行为决策的“前瞻能力”.
3.4 讨论为进一步明确群集分裂/融合控制律(15)中的相关参数对群集运动的影响规律, 下面分别就预测步数τ和预测信息在群集协同控制中所占比例α两个参数, 对群集融合/分裂运动耗时的影响展开讨论.
1) τ对群集融合/分裂耗时的影响.预测步数τ反映了个体对邻居未来运动状态探索的程度. τ越大, 表明个体获取的邻居信息越超前.在此, 分别在α取0.3、0.5和0.8时, 研究τ(τ∈[0 15])对群集融合/分裂耗时的影响, 仿真结果如图 3所示.
|
图 3 τ对群集行为的影响 |
从图 3可以看出:预测机制的引入可有效提升群集融合/分裂运动的快速性.随着预测步数τ的增加, 群集的融合/分裂耗时均呈下降趋势, 并在τ≈5时, 耗时达到最小; 但随着τ的进一步增大, 群集的融合/分裂耗时均又开始上升.上述结果表明, 适度的预测有利于提升群集运动的性能, 但过度的预测反而无助于群集运动快速性的达成, 甚至会导致群集性能的下降.这种现象的产生, 一方面是由于过多的预测步数会增加预测算法(11)的计算复杂度, 使得预测输出的实时性降低, 导致群集分裂/融合耗时的上升; 另一方面, 本文所采用的基于最小二乘估计的预测机制是一种典型的线性预测方法, 对个体运动轨迹呈线性或者短时呈线性的情形较为有效, 但尚不具备对个体非线性运动轨迹进行精确预测的能力.随着预测步数的增加, 预测结果准确性可能会降低, 从而导致群集运动性能下降.
2) α对群集融合/分裂耗时的影响. α表征了个体在运动协同中对所预测信息的利用程度.在此, 分别在τ取3、5和8时, 研究α对群集融合/分裂耗时的影响, 仿真结果如图 4所示.
|
图 4 α对群集行为的影响 |
从图 4可以看出:在群集融合/分裂控制律中融入预测信息后, 其融合/分裂耗时均呈下降趋势, 且在α≈0.25~0.3时, 耗时达到最小; 但随着α的继续增大, 耗时又开始呈现上升趋势.由此可见, 适度的预测有助于提升群集运动的快速性, 但过多地依赖于预测信息反而会使群集性能下降.在此过程中, α体现了个体行为决策“探索-开发”的两相权衡, 起着对当前信息的“开发”以及对未来预测信息“探索”的平衡作用.在自然界中, 生物行为大都遵循“有效开发现有资源”与“高效探索未知资源”这一准则, “探索-开发”相权衡产生的功能互补效应, 使得群集的灵活性(探索)与稳定性(开发)得以兼顾, 从而有效提升群集的环境适应能力.
4 结论生物个体普遍具有一定的预测能力, 受此启发, 本文将预测机制引入群集的自组织分裂/融合协同控制律中, 采用最小二乘法对邻居的运动状态进行预测, 并基于个体当前信息和对邻居的预测信息设计了分布式群集分裂/融合控制算法, 实现了群集的自组织分裂/融合运动.仿真结果表明, 所提方法可显著提升群集分裂与融合行为的效率, 有助于增强群集的运动灵活性和环境适应性.关于该方法的详细理论分析将是后续研究工作的重点.
| [1] |
刘明雍, 雷小康, 杨盼盼, 等. 群集运动的理论建模与实证分析[J]. 科学通报, 2014, 59(25): 2464-2483. (Liu M Y, Lei X K, Yang P P, et al. Progress of theoretical modelling and empirical studies on collective motion[J]. Chinese Science Bulletin, 2014, 59(25): 2464-2483.) |
| [2] |
杨盼盼, 刘明雍, 雷小康, 等. 群集系统分群行为建模与控制研究进展[J]. 控制与决策, 2016, 31(2): 193-206. (Yang P P, Liu M Y, Lei X K, et al. Progress in modeling and control of fission behavior for flocking system[J]. Control and Decision, 2016, 31(2): 193-206.) |
| [3] |
La H M, Sheng W. Dynamic target tracking and observing in a mobile sensor network[J]. Robotics & Autonomous Systems, 2012, 60(7): 996-1009. |
| [4] |
Bajec I L, Heppner F H. Organized flight in birds[J]. Animal Behaviour, 2009, 78(4): 777-789. DOI:10.1016/j.anbehav.2009.07.007 |
| [5] |
Reynolds C W. Flocks, herds, and schools:A distributed behavioral model[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 25-34. DOI:10.1145/37402 |
| [6] |
Vicsek T, Czirók A, Ben-Jacob E, et al. Novel type of phase transition in a system of self-driven particles[J]. Physical Review Letters, 1995, 75(6): 1226-1229. DOI:10.1103/PhysRevLett.75.1226 |
| [7] |
Jadbabaie A, Lin J, Morse A S. Coordination of groups of mobile autonomous agents using nearest neighbor[J]. IEEE Trans on Automatic Control, 2003, 48(6): 988-1001. DOI:10.1109/TAC.2003.812781 |
| [8] |
Ren W, Beard R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies[J]. IEEE Trans on Automatic Control, 2005, 50(5): 655-661. DOI:10.1109/TAC.2005.846556 |
| [9] |
Olfati-Saber R. Flocking for multi-agent dynamic systems:Algorithms and theory[J]. IEEE Trans on Automatic Control, 2006, 51(3): 401-420. DOI:10.1109/TAC.2005.864190 |
| [10] |
Lukeman R, Li Y X, Edelstein-Keshet L. Inferring individual rules from collective behavior[J]. Proc of the National Academy of Sciences, 2010, 107(28): 12576-12580. DOI:10.1073/pnas.1001763107 |
| [11] |
刘明雍, 雷小康, 杨盼盼, 等. 基于信息耦合度的群集系统自组织分群方法[J]. 控制与决策, 2015, 30(2): 271-276. (Liu M Y, Lei X K, Yang P P, et al. Information coupling degree based approach for self-organized fission behavior in flocking system[J]. Control and Decision, 2015, 30(2): 271-276.) |
| [12] |
Morgan D S, Schwartz I B. Dynamic coordinated control laws in multiple agent models[J]. Physics Letters A, 2005, 340: 121-131. DOI:10.1016/j.physleta.2005.03.074 |
| [13] |
Chen Z, Liao H, Chu T. Aggregation and splitting in self-driven swarms[J]. Physica A, 2012, 391(15): 3988-3994. DOI:10.1016/j.physa.2012.03.015 |
| [14] |
Navarro I. Exploring the split and join capabilities of a robotic collective movement framework[J]. Int J of Advanced Robotic Systems, 2013, 10(224): 1-12. |
| [15] |
Liu M Y, Yang P P, Lei X K, et al. Self-organized fission control for flocking system[J]. J of Robotics, 2015, 321781(10). |
| [16] |
Zhang H T, Cheng Z, Fan M C, et al. Collective behavior coordination with predictive mechanisms[J]. IEEE Circuits & Systems Magazine, 2008, 8(3): 67-85. |
| [17] |
Woods E F. Electronic prediction of swarming in bees[J]. Nature, 1959, 184(4690): 842-844. DOI:10.1038/184842a0 |
| [18] |
Montague P R, Dayan P, Person C, et al. Bee foraging in uncertain environments using predictive hebbian learning[J]. Nature, 1995, 377(6551): 725-728. DOI:10.1038/377725a0 |
| [19] |
David M. Predictive remapping of visual features precedes saccadic eye movements[J]. Nature Neuroscience, 2007, 10(7): 903-907. DOI:10.1038/nn1917 |
| [20] |
Zhang H T, Chen Z, Vicsek T, et al. Route-dependent switch between hierarchical and egalitarian strategies in pigeon flocks[J]. Scientific Reports, 2014, 4(5805): 1-7. |