第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992/tis.201904052 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20191205.1011.004html 鸽群交互模式切换模型及其同步性分析 邱华鑫2，段海滨3，范彦铭4，邓亦敏'，魏晨1 (1.北京航室航天大学自动化科学与电气工程学院，北京100083：2.中国空问技术研究院钱学森空间技术实 验室，北京100094：3.鹏城实验室，深圳518000：4.中国航空工业集团公司沈阳飞机设计研究所，辽宁沈阳 110035) 摘要：以原鸽为研究对象，归纳出其群体归巢机制中的双模式决策原则、模式切换原则与优势个体原则。模 拟双模式决策原则设定双模式邻居集合与对齐权重，模拟模式切换原则设定基于群体轨迹曲率的切换规则，模 拟优势个体原则设定高层级个体集合，进而建立鸽群交互模式切换模型。基于LaSalle不变集理论给出鸽群系 统以无碰撞、同步编队抵近目标的条件。采用蒙特卡罗仿真分析不同参数对模型特性的影响，即不同个体数 目、高层级个体数目以及最大速率均可保证模型的同步性。 关键词：鸽群；群体智能；群集运动：异构群体；层级交互模式；平等交互模式；交互模式切换；同步性 中图分类号：TP13:V249.122文献标志码：A文章编号：1673-4785(2020)020334-10 中文引用格式：邱华鑫，段海滨，范彦铭，等.鸽群交互模式切换模型及其同步性分析IJ.智能系统学报，2020,15(2)： 334-343. 英文引用格式：QIU Huaxin,,DUAN Haibin,.FAN Yanming,.etal.Pigeon flock interaction pattern switching model and its syn- chronization analysis[Jl.CAAI transactions on intelligent systems,2020,15(2):334-343. Pigeon flock interaction pattern switching model and its synchronization analysis QIU Huaxin'2,DUAN Haibin,FAN Yanming',DENG Yimin',WEI Chen' (1.School of Automation Science and Electrical Engineering,Beihang University,Beijing 100083,China;2.QIAN Xuesen Laborat- ory of Space Technology,China Academy of Space Technology,Beijing 100094,China;3.Peng Cheng Laboratory,Shenzhen 518000,China;4.Shenyang Aircraft Design and Research Institute,Aviation Industry Corporation of China,Shenyang 110035, China) Abstract:Taking Columba livia as the research object,we summarized the dual-mode decision-making,mode-switch- ing,and dominant individual principles in the homing mechanism of pigeons to establish a pigeon flock interaction pat- tern switching model.In the model,the neighbor set and alignment weight in dual mode were set by mimicking the dual- mode decision-making principle,the switching rule based on the curvature of the group trajectory was set by mimicking the mode-switching principle,and the collection of higher-rank individuals was set by mimicking the dominant individu- al principle.On the basis of LaSalle's invariant set theory,the conditions under which the pigeon flock can approach the target with collision-free and synchronous formations are given.Monte Carlo simulation was used to analyze the influ- ence of different parameters on the model characteristics.Results show that the synchronization of the model can be en- sured by setting the appropriate number of individuals,number of higher-rank individuals,and maximum velocity. Keywords:pigeon flock;swarm intelligence;collective motion;heterogeneous group;hierarchical interaction pattern; egalitarian interaction pattern;interaction pattern switching;synchronization 收稿日期：2019-04-22.网络出版日期：2019-12-05 鸟类群体的有组织飞行(organized flight)大致 基金项目：国家自然科学基金项目(61803011,91948204)：中国 可分为两种方式"：线性编队(line formation)和群 博士后科学基金资助项目. 通信作者：段海滨.E-mail:hbduan@buaa.edu.cn 集编队(cluster formation)。水禽等大型鸟类主要
DOI: 10.11992/tis.201904052 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20191205.1011.004.html 鸽群交互模式切换模型及其同步性分析 邱华鑫1,2，段海滨1,3，范彦铭4 ，邓亦敏1 ，魏晨1 （1. 北京航空航天大学 自动化科学与电气工程学院，北京 100083; 2. 中国空间技术研究院 钱学森空间技术实 验室，北京 100094; 3. 鹏城实验室，深圳 518000; 4. 中国航空工业集团公司 沈阳飞机设计研究所，辽宁 沈阳 110035） 摘 要：以原鸽为研究对象，归纳出其群体归巢机制中的双模式决策原则、模式切换原则与优势个体原则。模 拟双模式决策原则设定双模式邻居集合与对齐权重，模拟模式切换原则设定基于群体轨迹曲率的切换规则，模 拟优势个体原则设定高层级个体集合，进而建立鸽群交互模式切换模型。基于 LaSalle 不变集理论给出鸽群系 统以无碰撞、同步编队抵近目标的条件。采用蒙特卡罗仿真分析不同参数对模型特性的影响，即不同个体数 目、高层级个体数目以及最大速率均可保证模型的同步性。 关键词：鸽群；群体智能；群集运动；异构群体；层级交互模式；平等交互模式；交互模式切换；同步性 中图分类号：TP13; V249.122 文献标志码：A 文章编号：1673−4785(2020)02−0334−10 中文引用格式：邱华鑫, 段海滨, 范彦铭, 等. 鸽群交互模式切换模型及其同步性分析 [J]. 智能系统学报, 2020, 15(2): 334–343. 英文引用格式：QIU Huaxin, DUAN Haibin, FAN Yanming, et al. Pigeon flock interaction pattern switching model and its synchronization analysis[J]. CAAI transactions on intelligent systems, 2020, 15(2): 334–343. Pigeon flock interaction pattern switching model and its synchronization analysis QIU Huaxin1,2 ，DUAN Haibin1,3 ，FAN Yanming4 ，DENG Yimin1 ，WEI Chen1 (1. School of Automation Science and Electrical Engineering, Beihang University, Beijing 100083, China; 2. QIAN Xuesen Laboratory of Space Technology, China Academy of Space Technology, Beijing 100094, China; 3. Peng Cheng Laboratory, Shenzhen 518000, China; 4. Shenyang Aircraft Design and Research Institute, Aviation Industry Corporation of China, Shenyang 110035, China) Abstract: Taking Columba livia as the research object, we summarized the dual-mode decision-making, mode-switching, and dominant individual principles in the homing mechanism of pigeons to establish a pigeon flock interaction pattern switching model. In the model, the neighbor set and alignment weight in dual mode were set by mimicking the dualmode decision-making principle, the switching rule based on the curvature of the group trajectory was set by mimicking the mode-switching principle, and the collection of higher-rank individuals was set by mimicking the dominant individual principle. On the basis of LaSalle’s invariant set theory, the conditions under which the pigeon flock can approach the target with collision-free and synchronous formations are given. Monte Carlo simulation was used to analyze the influence of different parameters on the model characteristics. Results show that the synchronization of the model can be ensured by setting the appropriate number of individuals, number of higher-rank individuals, and maximum velocity. Keywords: pigeon flock; swarm intelligence; collective motion; heterogeneous group; hierarchical interaction pattern; egalitarian interaction pattern; interaction pattern switching; synchronization 鸟类群体的有组织飞行 (organized flight) 大致 可分为两种方式[1] ：线性编队 (line formation) 和群 集编队 (cluster formation)。水禽等大型鸟类主要 收稿日期：2019−04−22. 网络出版日期：2019−12−05. 基金项目：国家自然科学基金项目 (61803011,91948204)； 中国 博士后科学基金资助项目. 通信作者：段海滨. E-mail：hbduan@buaa.edu.cn. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
第2期 邱华鑫，等：鸽群交互模式切换模型及其同步性分析 ·335· 采用线性编队方式飞行，研究此种方式的研究者 体，或为最近固定数量的邻居个体，即服从固定 主要关注线性编队的成因。鸽子、乌鹩等小型鸟 邻居范围(fixed neighborhood region,FNR)模型或 类主要采用群集编队方式飞行，研究此种方式的 固定邻居数量(fixed number of neighbors,.FNN)模 研究者主要关注群集同步的机理。 型。层级交互模式下，鸟类个体跟随具有较高飞 采用群集编队方式飞行的鸟类其单体智能水 行领导层级的其他个体进行飞行。为深入研究自 平并不高，但无论群集规模大小，可实现群体同 由飞行中鸽群两种交互模式的切换关系，Zhang 步且迅速的飞行转向。在大型群集编队方面， 等u8-11基于Nagy等m记录的鸽群自由飞行实验 Ballerini等通过立体测量和计算机视觉技术重 数据，发现鸽群实际上切换采用上述两种交互模 建同一群体中2600只欧椋鸟(European starlings/, 式，即当原鸽个体沿平滑轨迹运动时，其飞行方 Sturnus Vulgaris)的三维位置后发现鸟群个体间交 向趋向跟随邻居平均，而当突然转弯或轨迹曲折 互依赖于拓扑距离(topological distance),而并非大 时，趋向跟随领导者。 多数理论模型所假设的模式距离(metric distance)), 至此，可归纳原鸽归巢机制如下。1)双模式 即个体与固定数量(6~7只)的邻居进行交互，而 决策原则：鸽群在迁徙过程中，群体飞行决策采 非与固定模式距离内的邻居进行交互。在小型群 用平等交互模式或层级交互模式，平等交互模式 集编队方面，Nagy等忉通过高精度微型全球定位 下，原鸽个体的飞行决策彼此间相互影响，层级 系统(global positioning system,GPS)跟踪记录 交互模式下，存在至少一个原鸽个体，会对其交 l0只原鸽(Columba Livia/homing pigeon/domestic 互范围内的其他原鸽个体的飞行决策产生较大影 pigeon)的飞行，采用统计物理学方法以系列相关 响。2)模式切换原则：异构原鸽群体的模式切换 函数定义成对交互中的领导关系，进而发现一个 与鸽群轨迹曲率呈现一定的关联，当鸽群飞行状 清晰的层级制度：鸽群内个体的平均空间位置与 态不够平稳时，原鸽个体采用层级交互模式，反 其在层级网络中的飞行领导等级(flight leadership 之采用平等交互模式。3)优势个体原则：异构原 rank)密切相关。从进化角度来说，层级交互模式 鸽群体内存在可能因某些因素导致的某个或某几 (hierarchical interaction pattern)比之于平等交互模 个优势原鸽个体，当鸽群处于层级交互模式时， 式(egalitarian interaction pattern)信息传递更快，效 非优势原鸽个体会偏重依赖该类优势个体进行飞 率更高⑧：此外，具有特定社会结构的层级交互模 行决策。 式可补偿个体导航误差，提高群体导航精度例：需 本文在上述原鸽归巢机制分析基础上，建立 要说明的是，在不考虑领导者切换的条件下，层 鸽群交互模式切换模型，模型对应原鸽归巢机制 级网络可简化为双层领导跟随结构，即仅存在唯 中的双模式决策原则定义了平等交互模式与层级 一领导者，其余跟随者均以特定时延复制领导者 交互模式下的邻居集合与对齐权重，对应模式切 运动，该结构可节约个体运动和通信消耗。与 换原则定义了由群体轨迹曲率触发的交互模式切 仅由攻击和觅食等个体体能特征决定的啄序等 换规则，对应优势个体原则将可获知目标位置和 级(pecking order rank)不同，飞行领导等级是个 速度信息的原鸽个体视为高层级个体。基于LaS- 体不断优化自身利益的结果，亦是领导、学习以 alle不变集理论2o给出鸽群系统可避免碰撞、实 及个人能力综合作用的结果2。个体速度31 现速度渐近同步、相对位置趋于期望并抵达目标 路径保真度(route fidelity)以及飞行经验is-1m均 的条件。以序参量衡量鸽群同步性，以序参量衡 可能决定成对领导关系，进而影响个体飞行领导 量鸽群同步性，采用蒙特卡罗仿真测试个体数 层级：个体受前方邻居的影响往往高于后方邻 目、高层级个体数目、个体最大速率对鸽群抵达 居，即飞行速度慢的个体需要牺牲方向决策权来 目标时间以及序参量的影响。 跟随快速个体；路径差异越小表示路径保真度越 1鸽群交互模式切换模型 高，单飞时保真度高的个体在成对飞行时较易成 为领导者；具有更多飞行经验的鸽子以较大概率 考虑N只原鸽在三维欧式空间中飞行，每 可处于在飞行领导层级中较高的层级。 个原鸽个体可视作一个质点，其动力学模型如 综上所述，以群集编队飞行时，鸟群内部存在 式(1)所示： 平等交互和层级交互两种模式。平等交互模式 (1) 下，鸟类个体交互范围或为固定半径内的邻居个 =y,i=1,2…N mvi=ui
采用线性编队方式飞行，研究此种方式的研究者 主要关注线性编队的成因。鸽子、乌鸫等小型鸟 类主要采用群集编队方式飞行，研究此种方式的 研究者主要关注群集同步的机理[2-5]。 采用群集编队方式飞行的鸟类其单体智能水 平并不高，但无论群集规模大小，可实现群体同 步且迅速的飞行转向。在大型群集编队方面， Ballerini 等 [6] 通过立体测量和计算机视觉技术重 建同一群体中 2 600 只欧椋鸟 (European starlings/ Sturnus Vulgaris) 的三维位置后发现鸟群个体间交 互依赖于拓扑距离 (topological distance)，而并非大 多数理论模型所假设的模式距离 (metric distance)， 即个体与固定数量 (6~7 只) 的邻居进行交互，而 非与固定模式距离内的邻居进行交互。在小型群 集编队方面，Nagy 等 [7] 通过高精度微型全球定位 系统 (global positioning system，GPS) 跟踪记录 10 只原鸽 (Columba Livia/homing pigeon/domestic pigeon) 的飞行，采用统计物理学方法以系列相关 函数定义成对交互中的领导关系，进而发现一个 清晰的层级制度：鸽群内个体的平均空间位置与 其在层级网络中的飞行领导等级 (flight leadership rank) 密切相关。从进化角度来说，层级交互模式 (hierarchical interaction pattern) 比之于平等交互模 式 (egalitarian interaction pattern) 信息传递更快，效 率更高[8] ；此外，具有特定社会结构的层级交互模 式可补偿个体导航误差，提高群体导航精度[9] ；需 要说明的是，在不考虑领导者切换的条件下，层 级网络可简化为双层领导跟随结构，即仅存在唯 一领导者，其余跟随者均以特定时延复制领导者 运动，该结构可节约个体运动和通信消耗[10]。与 仅由攻击和觅食等个体体能特征决定的啄序等 级 (pecking order rank) 不同[11] ，飞行领导等级是个 体不断优化自身利益的结果，亦是领导、学习以 及个人能力综合作用的结果[12]。个体速度[13-14] 、 路径保真度 (route fidelity)[15] 以及飞行经验[16-17] 均 可能决定成对领导关系，进而影响个体飞行领导 层级：个体受前方邻居的影响往往高于后方邻 居，即飞行速度慢的个体需要牺牲方向决策权来 跟随快速个体；路径差异越小表示路径保真度越 高，单飞时保真度高的个体在成对飞行时较易成 为领导者；具有更多飞行经验的鸽子以较大概率 可处于在飞行领导层级中较高的层级。 综上所述，以群集编队飞行时，鸟群内部存在 平等交互和层级交互两种模式。平等交互模式 下，鸟类个体交互范围或为固定半径内的邻居个 体，或为最近固定数量的邻居个体，即服从固定 邻居范围 (fixed neighborhood region，FNR) 模型或 固定邻居数量 (fixed number of neighbors，FNN) 模 型。层级交互模式下，鸟类个体跟随具有较高飞 行领导层级的其他个体进行飞行。为深入研究自 由飞行中鸽群两种交互模式的切换关系，Zhang 等 [18-19] 基于 Nagy 等 [7] 记录的鸽群自由飞行实验 数据，发现鸽群实际上切换采用上述两种交互模 式，即当原鸽个体沿平滑轨迹运动时，其飞行方 向趋向跟随邻居平均，而当突然转弯或轨迹曲折 时，趋向跟随领导者。 至此，可归纳原鸽归巢机制如下。1) 双模式 决策原则：鸽群在迁徙过程中，群体飞行决策采 用平等交互模式或层级交互模式，平等交互模式 下，原鸽个体的飞行决策彼此间相互影响，层级 交互模式下，存在至少一个原鸽个体，会对其交 互范围内的其他原鸽个体的飞行决策产生较大影 响。2) 模式切换原则：异构原鸽群体的模式切换 与鸽群轨迹曲率呈现一定的关联，当鸽群飞行状 态不够平稳时，原鸽个体采用层级交互模式，反 之采用平等交互模式。3) 优势个体原则：异构原 鸽群体内存在可能因某些因素导致的某个或某几 个优势原鸽个体，当鸽群处于层级交互模式时， 非优势原鸽个体会偏重依赖该类优势个体进行飞 行决策。 本文在上述原鸽归巢机制分析基础上，建立 鸽群交互模式切换模型，模型对应原鸽归巢机制 中的双模式决策原则定义了平等交互模式与层级 交互模式下的邻居集合与对齐权重，对应模式切 换原则定义了由群体轨迹曲率触发的交互模式切 换规则，对应优势个体原则将可获知目标位置和 速度信息的原鸽个体视为高层级个体。基于 LaSalle 不变集理论[20] 给出鸽群系统可避免碰撞、实 现速度渐近同步、相对位置趋于期望并抵达目标 的条件。以序参量衡量鸽群同步性,以序参量衡 量鸽群同步性，采用蒙特卡罗仿真测试个体数 目、高层级个体数目、个体最大速率对鸽群抵达 目标时间以及序参量的影响。 1 鸽群交互模式切换模型 N i 考虑 只原鸽在三维欧式空间中飞行，每 个原鸽个体 可视作一个质点，其动力学模型如 式（1）所示： { x˙i = vi miv˙i = ui ,i = 1,2,··· ,N (1) 第 2 期 邱华鑫，等：鸽群交互模式切换模型及其同步性分析 ·335·
·336· 智能系统学报 第15卷 式中：x,,,∈RD1分别为原鸽个体i的位置向 -K∑.9D 量、速度向量以及控制输入，D为上述3个向量 jEN 的维数；w,2≤Vax,Vx>0为原鸽个体最大速率； -KTVx VT (x;-xTll) iEUpper m,为原鸽个体i的质量。 -K心w∑ 定义鸽群中可获知目标T位置和速度信息的 -k∑.D (6) 原鸽个体为高层级个体（即优势个体），即原鸽个 jeN 体iEUpper,.其中Upper为高层级原鸽个体集合， i座Jpper 其可观测目标标识符infor,=l;余下原鸽个体为低 -K EN\Upper +w 层级个体，可观测目标标识符infora=0,其中原鸽 jENnUpper 个体i=l,2,…,N且iUpper.。原鸽个体依据鸽 式中：>0、KT>0、Kw>0分别为编队控制增 群飞行状态选用不同交互模式：交互模式标识符 益、目标控制增益以及对齐控制增益，=-y,为 mode,=0,表示原鸽个体处于平等交互模式；交互 原鸽个体i相对于原鸽个体j的速度向量。定义 模式标识符mode,=l,表示原鸽个体处于层级交互 对齐权重w如式(7)所示： 模式。当群体轨迹曲率较小时，原鸽个体处于 1,mode;=0 平等交互模式，当群体轨迹曲率较大时，原鸽 w= w',mode;=1 (7) 个体处于层级交互模式，交互模式标识符mode, 式中w≥1为层级交互模式下对齐权重。编队势 与群体轨迹曲率间的关系如式(2)所示： 场函数定义为 0 R<Kswitch mode,=1,≥K (2) (Raca)Ln0Rae 式中Kwh为轨迹曲率模式切换阈值。由式(2) 1 可知，当Kwh=0,个体始终处于层级交互模式； -ll /R-R） 当K=o,个体始终处于平等交互模式。 好(eD R.comm 原鸽个体在不同交互模式下，其交互范围并 Rdesire - 不相同。首先，定义平等交互模式下原鸽个体 (Rdesire)In- Rcomm.-Rdesire 的邻居集合N如式(3)所示： Resire≤kl≤Rcomm {jlxl≤Rom-Rmj≠i,k=0 (8) l≤Romm, 式中Ree为个体间期望距离。定义目标势场函 N(t)= jeN(-i),j≠i 数如式(9)所示： or ull≤Rcomm.-Rn k=1,2,…N :-xTl j年N(t-),j≠i 2 lx-xl≥Ra (3) 0 0≤lx,-xl<R 式中：t为采样时间点，即满足t+1=+ts:j=1,2,…, (9) N,x=x-x为原鸽个体i相对于原鸽个体j的位 式中：x灯为目标位置向量；为个体抵达目标的 置向量；Rmm为平等交互模式下最大通信距离， 最大容许误差。 Rn∈(O,Rmm)为添加个体连接延迟距离。并定义 层级交互模式下原鸽个体ⅰ的邻居集合W如式 2模型同步性理论分析 (4)所示： 本节旨在从理论分析角度对鸽群交互模式切 N={l≤Rmj≠ij=1,2,…,N}(4) 换模型同步性展开研究。首先定义鸽群平等交互 式中Rm≥R.m为层级交互模式下最大通信距 模式下的有向图g=(V,8),若原鸽个体jeN, 离。则原鸽个体i的当前邻居集合N可表示为 则有序点对(，)属于边集8。定义鸽群拉普拉斯 N,mode:=0 矩阵Lw=[∈Rxw如式(I0)所示： N= (5) N,mode;=1 -1,jEN 原鸽个体i依赖邻居交互信息以及目标信息 l={0,j年N,j≠i (10) (仅高层级个体可获知)，求取控制输入，具体如 IN,j=i 式(6)： 式中4为集合A中元素数目
xi , vi ,ui ∈ R D×1 i D ∥vi∥2 ⩽ Vmax Vmax > 0 mi i 式中： 分别为原鸽个体 的位置向 量、速度向量以及控制输入， 为上述 3 个向量 的维数； ， 为原鸽个体最大速率； 为原鸽个体 的质量。 T i ∈ Upper Upperinfori=1 infori=0 i = 1,2,··· ,N i < Upper modei=0 modei=1 K¯t K¯t modei K¯t 定义鸽群中可获知目标 位置和速度信息的 原鸽个体为高层级个体 (即优势个体)，即原鸽个 体 ，其中 为高层级原鸽个体集合， 其可观测目标标识符 ；余下原鸽个体为低 层级个体，可观测目标标识符 ，其中原鸽 个体 且 。原鸽个体依据鸽 群飞行状态选用不同交互模式：交互模式标识符 ，表示原鸽个体处于平等交互模式；交互 模式标识符 ，表示原鸽个体处于层级交互 模式。当群体轨迹曲率 较小时，原鸽个体处于 平等交互模式，当群体轨迹曲率 较大时，原鸽 个体处于层级交互模式，交互模式标识符 与群体轨迹曲率 间的关系如式（2）所示： modei = { 0, K¯t < Kswitch 1, K¯t ⩾ Kswitch (2) KswitchKswitch=0 Kswitch=∞ 式中 为轨迹曲率模式切换阈值。由式（2） 可知，当 ，个体始终处于层级交互模式； 当 ，个体始终处于平等交互模式。 i N1 i 原鸽个体在不同交互模式下，其交互范围并 不相同。首先，定义平等交互模式下原鸽个体 的邻居集合 如式（3）所示： N 1 i (tk)= { j xi j ⩽ R 1 comm. −R 1 lim, j , i } , k = 0 j xi j ⩽ R 1 comm. , j ∈ N1 i (tk−1), j , i or xi j ⩽ R 1 comm. −R 1 lim, j < N1 i (tk−1), j , i , k = 1,2,···N (3) tk tk+1=tk+ts j = 1,2,··· , xi j=xi − xj i j R 1 comm. R 1 lim ∈ ( 0,R 1 comm. ) i N2 i 式中： 为采样时间点，即满足 ； N， 为原鸽个体 相对于原鸽个体 的位 置向量； 为平等交互模式下最大通信距离， 为添加个体连接延迟距离。并定义 层级交互模式下原鸽个体 的邻居集合 如式 （4）所示： N 2 i = { j xi j ⩽ R 2 comm. , j , i, j = 1,2,··· ,N } (4) R 2 comm. ⩾ R 1 comm. i Ni 式中 为层级交互模式下最大通信距 离。则原鸽个体 的当前邻居集合 可表示为 Ni= N1 i , modei=0 N2 i , modei=1 (5) 原鸽个体 i 依赖邻居交互信息以及目标信息 (仅高层级个体可获知)，求取控制输入，具体如 式 (6)： ui= mi −K f∑ j∈N1 i ∇xiV f i j( xi j ) −K T∇xiV T i (∥xi − xT∥) −K Vw ∑ j∈Ni vi j , i ∈ Upper mi −K f∑ j∈N1 i ∇xiV f i j( xi j ) −K V ∑ j∈Ni\Upper vi j +w ∑ j∈Ni∩Upper vi j , i < Upper (6) K f > 0 K T > 0 K V > 0 vi j=vi −vj i j w 式中： 、 、 分别为编队控制增 益、目标控制增益以及对齐控制增益， 为 原鸽个体 相对于原鸽个体 的速度向量。定义 对齐权重 如式（7）所示： w= { 1, modei=0 w ′ , modei= 1 (7) w ′ ⩾ 1 V f i j 式中 为层级交互模式下对齐权重。编队势 场函数 定义为 V f i j( xi j ) = 1 2 xi j 2 −(Rdesire) 2Ln xi j ,0 ⩽ xi j ⩽ Rdesire 1 2 Rdesire R 1 comm. − xi j / ( R 1 comm. −Rdesire) 2 − (Rdesire) 2 ln Rdesire R 1 comm. − xi j R1 comm. −Rdesire , Rdesire ⩽ xi j ⩽ R 1 comm. (8) Rdesire V T i 式中 为个体间期望距离。定义目标势场函 数 如式（9）所示： V T i (∥xi − xT∥)= ( ∥xi − xT∥ −R 2 lim )2 2 , ∥xi − xT∥ ⩾ R 2 lim 0, 0 ⩽ ∥xi − xT∥ < R 2 lim (9) xT R 2 式中： 为目标位置向量； lim 为个体抵达目标的 最大容许误差。 2 模型同步性理论分析 G ′ = (V,E ′ ) j ∈ N1 i (j,i) E ′ LN = [ li j] ∈ R N×N 本节旨在从理论分析角度对鸽群交互模式切 换模型同步性展开研究。首先定义鸽群平等交互 模式下的有向图 ，若原鸽个体 ， 则有序点对 属于边集 。定义鸽群拉普拉斯 矩阵 如式（10）所示： li j = −1, j ∈ Ni 0, j < Ni , j , i |Ni |, j=i (10) 式中 |A| 为集合 A 中元素数目。 ·336· 智 能 系 统 学 报 第 15 卷
第2期 邱华鑫，等：鸽群交互模式切换模型及其同步性分析 ·337· 定义仅保留高层级个体间连接以及高层级个 体与低层级个体间连接的鸽群伪拉普拉斯矩阵 =xzeo,0+,. Lw=eRw如式(I1)所示： -1 if je N,ie Upper K∑.-x+∑) or jENnUpper,iUpper 0 if j N.iE Upper or jNnUpper,i Upper 22,0叶 NnUpper. j=i (11) K".W-s+卫 定义鸽群Lyapunov函数H如式(12)所示： (15) H=H+H2 (12) 将式(1)和式(6)代入式(15)有： 其中势能函数H如式(13)所示： ax.0叶 EN (13) K∑(qx-x .9ax-+2} 动能函数H2如式(14)所示： 叶 - (14) K∑(Tx-xDH 假设1鸽群初始拓扑g(to)为连通图。 假设2Vax Rm-R-R,其中R∈O, .vallz,) 2t. Rm一R)为添加个体联结时原鸽个体间的最小 -..-xD-K (16 距离。 假设3鸽群初始能量H(o)为有限值，g() -g. 在时刻g发生切换，其中q=1,2,…,鸽群拓扑相 -KV 邻两次切换的驻留时间tg-g-1≥1，>0。 假设4鸽群高层级个体集合Upper≠O且高 层级原鸽个体数目Upper<N。 引理1对于一个动态系统=fx),其中 1∑∑ f(x)为连续函数，若存在一个具有一阶连续偏导 ieUpper jeN, +(w-1) 数的连续函数V(x),且满足如下条件。 +∑∑ 1)存在正常数C,使得集合2={x∈RDIV(x)≤C} -KYyT((Lw+(w-1)Lv)8Ip)v 有界； 由式(7)可知w≥1，且由Lw、Lw均为对称半 2)对于任意的x∈2，有(x)≤0： 正定矩阵，故有： 则对于x∈2，当t→o时，x()趋向于S= H≤0，te[tg-1,tg) (17) x∈RP|(x)=0}中的最大不变集。 由式（③）可知，若jeN6-i,则有lxe0,Rmm 定理1考虑由N个原鸽个体组成的鸽群系 并由式(8)可知，当xl→Rm,有写(x0→o。 统，每个原鸽个体动力学模型满足式(1)，若系统 而由式(17)可知： 满足假设1~4，则在如式(6)所示的分布式控制律 H)≤H(tg-i),t∈[tg-1,tg) (18) 作用下，所有原鸽个体间可避免碰撞，实现速度 即若H(t,-)<o,H(①<o。则由H在时域上 渐近同步，相对位置趋于期望，整个鸽群可实现 的连续性，可知：jeN(t,-i),均有cl<Rm,并 稳定的编队并抵近目标。 由式(3)可知，jeN,)。故鸽群系统g内已存 证明当te[tg-,,对式(12)关于时间t求 在的原鸽个体间拓扑连接在下一切换时刻t,时仍 导，有： 然保持，即若假设1成立，鸽群系统内部始终保持
L ′ N = [ l ′ i j] ∈ R N×N 定义仅保留高层级个体间连接以及高层级个 体与低层级个体间连接的鸽群伪拉普拉斯矩阵 如式 (11) 所示： l ′ i j = −1, if j ∈ Ni ,i ∈ Upper or j ∈ Ni ∩Upper,i < Upper 0, if j < Ni ,i ∈ Upper or j < Ni ∩Upper,i < Upper Ni ∩Upper , j=i (11) 定义鸽群 Lyapunov 函数 H 如式 (12) 所示： H=H1 + H2 (12) 其中势能函数 H1 如式 (13) 所示： H1=K f∑N i=1 1 2 ∑ j∈N1 i V f i j( xi j ) + K T ∑ i∈Upper ( V T i (∥xi − xT ∥) ) (13) 动能函数 H2 如式 (14) 所示： H2= ∑N i=1 ( 1 2 v T i vi ) (14) G ′ 假设 1 鸽群初始拓扑 (t0) 为连通图。 Vmax ⩽ R 1 comm. −R 1 lim −R 3 lim 2ts R 3 lim ∈ (0, R 1 comm. −R 1 lim) 假设 2 ，其中 为添加个体联结时原鸽个体间的最小 距离。 H (t0) G ′ (t) tq q = 1,2,··· tq −tq−1 ⩾ ts > 0 假设 3 鸽群初始能量 为有限值， 在时刻 发生切换，其中 ，鸽群拓扑相 邻两次切换的驻留时间 。 Upper , Ø Upper < N 假设 4 鸽群高层级个体集合 且高 层级原鸽个体数目 。 x˙ = f (x) f (x) V (x) 引理 1 [21] 对于一个动态系统 ，其中 为连续函数，若存在一个具有一阶连续偏导 数的连续函数 ，且满足如下条件。 C Ω = { x ∈ R D |V(x) ⩽ C } 1) 存在正常数 ，使得集合 有界； x ∈ Ω V˙ 2) 对于任意的 ，有 (x) ⩽ 0 ； ∀x0 ∈ Ω t → ∞ x(t) S= { x ∈ R D V˙ (x) = 0 } 则对于 ，当 时 ， 趋向于 中的最大不变集。 定理 1 考虑由 N 个原鸽个体组成的鸽群系 统，每个原鸽个体动力学模型满足式 (1)，若系统 满足假设 1~4，则在如式 (6) 所示的分布式控制律 作用下，所有原鸽个体间可避免碰撞，实现速度 渐近同步，相对位置趋于期望，整个鸽群可实现 稳定的编队并抵近目标。 证明 当 t ∈ [tq−1,tq) ，对式 (12) 关于时间 t 求 导，有： H˙=K f∑N i=1 1 2 ∑ j∈N1 i ( v T i ∇xiV f i j( xi j ) +v T j∇xjV f i j( xi j )) + K T ∑ i∈Upper ( v T i ∇xiV T i (∥xi − xT ∥) ) + ∑N i=1 ( v T i v˙i ) = K f∑N i=1 v T i ∑ j∈N1 i ∇xiV f i j( xi j ) + K T ∑ i∈Upper ( v T i ∇xiV T i (∥xi − xT ∥) ) + ∑N i=1 ( v T i v˙i ) (15) 将式 (1) 和式 (6) 代入式 (15)，有： H˙=K f∑N i=1 v T i ∑ j∈N1 i ∇xiV f i j( xi j ) + K T ∑ i∈Upper ( v T i ∇xiV T i (∥xi − xT ∥) ) + ∑N i=1 ( v T i ui mi ) = K f∑N i=1 v T i ∑ j∈N1 i ∇xiV f i j( xi j ) + K T ∑ i∈Upper ( v T i ∇xiV T i (∥xi − xT ∥) ) + ∑ i∈Upper v T i −K f∑ j∈N1 i ∇xiV f i j( xi j ) −K T∇xiV T i (∥xi − xT∥)−K Vw ∑ j∈Ni vi j + ∑ i<Upper v T i −K f∑ j∈N1 i ∇xiV f i j( xi j ) −K V ∑ j∈Ni\Upper vi j+w ∑ j∈Ni∩Upper vi j = −K V ∑N i=1 v T i ∑ j∈Ni vi j +(w−1) l ∑ i∈Upper v T i ∑ j∈Ni vi j + ∑ i<Upper v T i ∑ j∈Ni∩Upperi vi j = −K V v T ((LN +(w−1) L ′ N ) ⊗ ID ) v (16) w ⩾ 1 LN L ′ 由式 N (7) 可知 ，且由 、 均为对称半 正定矩阵，故有： H˙ ⩽ 0,∀t ∈ [tq−1,tq) (17) j ∈ N1 i ( tq−1 ) xi j ∈ [ 0,R 1 comm. ] xi j → R 1 comm. V f i j( xi j ) → ∞ 由式(3)可知，若 ，则有 ， 并由式 (8) 可知，当 ，有 。 而由式 (17) 可知： H (t) ⩽ H ( tq−1 ) ,∀t ∈ [tq−1,tq) (18) H ( tq−1 ) < ∞ H (t) < ∞ H j ∈ N1 i ( tq−1 ) xi j < R 1 comm. j ∈ N1 i ( tq ) G ′ tq 即若 ， 。则由 在时域上 的连续性，可知： ，均有 ，并 由式 (3) 可知， 。故鸽群系统 内已存 在的原鸽个体间拓扑连接在下一切换时刻 时仍 然保持，即若假设 1 成立，鸽群系统内部始终保持 第 2 期 邱华鑫，等：鸽群交互模式切换模型及其同步性分析 ·337·
·338· 智能系统学报 第15卷 连通。由式(I3)可知，鸽群Lyapunov函数H在 由假设4可知，存在i使Upper.。由式(6)可知，当 切换时刻1，只可能由于g内添加的原鸽个体间 ig Upper时，4：=0。由式(25)可知1=2=…=w=0, 拓扑连接而产生能量变化。 故有 由式(3)和假设2可知，在切换时刻tg,j∈ -K∑(D N(g)/N(g-i),有Rn≤≤Rmm-Rm,并由式 jEN好 (8)可知： -infor KTVs,VI (1-xTll) (x)≤V (19) -K∑V.(x0 jeM; 式中Vix=maxV(Rm),(Ram-Rm)}<o为添 -infor2KV:V2 (x2-xTll)) (25) 加单条个体间拓扑连接所增加的最大势能。 假设在切换时刻g,有n。条个体间拓扑连接 -K∑以(xw0 添加至N,)。由假设1可知之≤W-1)。故 jEN 由假设3、式(18)及式(19)可知： -inforN KV Vy(lN-xl) H(t)<Hmax=H(to)+Vi (N-1)2<oo 即鸽群内所有原鸽个体将会收敛至固定的几 (20) 何构型。且由假设4可知，鸽群中的高层领导者 式中H,max为鸽群Lyapunov函数上界。 由式(18)和式(20)可知，H≤∞，故所有原 可抵达至距目标点xr距离为R的区域内。表 鸽个体间可避免碰撞。否则由式(8)可知，当 明所有原鸽个体间相对位置趋于期望，整个鸽群 r→0，均有(xD→oo。 可实现稳定的编队并抵近目标。 由假设3可知，0<ng≤N(W-1)-(W-1)=(W-1)2, 3模型同步性仿真分析 则切换数目q≤qma<o,其中qx为最大切换次 数。即，鸽群G最终为固定拓扑。当te[,o), 本节通过仿真实验进一步研究鸽群交互模式 H为连续函数。由式(8)和式(9)可知，Ⅱ亦连 切换模型中不同参数（包括原鸽个体数目N、高 续。定义集合 层级原鸽个体数目Upper以及个体最大速率 Q=E RDN,vERON H<Hmx H>0 (21) Vx)对鸽群系统同步性的影响。设定N个原鸽 式中=[xi,x2,…,x,…,xW,xW2…,xWw。 个体的初始位置向量随机分布在满足0≤x≤20m 由于g()对于t≥0为连通图，故鸽群中任意 且-10m≤x≤10m的方形区域内，初始位置向量 两个原鸽个体i和j可通过至少一条路径彼此连 =[10m/s,0],目标位置向量xr=[50m,-50m,随 通，且路径长度≤(W-1)R。此外，由于H<Ha 机指定Upper个原鸽个体作为高层级个体。设 则有l,l<V2H,故2为有界闭集。由于控制 定采样时间t,=0.05s,最大仿真时间Tx=50s,当 输入如式(6)所示的鸽群系统(1)在t∈[t,∞)为 鸽群抵达目标点时，即当原鸽个体与目标点平均 一个自治系统，故可由引理1证明鸽群的稳定性， 距离之k-小于或等于群体辑达目标的银 即对于任意起始于2的状态轨迹最终将收敛至 大容许误差R时，仿真停止，停止时间为T,可 如式(22)定义的集合的最大不变子集： 将T,认定为鸽群抵达目标点所用时间。 S={EE RDN,v∈RON H=O (22) 依照所建模型进行仿真，设定层级交互模式 此时有 下最大通信距离R?mm=Rmm,平等交互模式下最 H=-KVyT((Lw+(w-1)Lv)8ID)v=- 大通信距离Rm=rRm,其中。为平等交互距 K∑∑- 离占比，余下仿真参数设置如表1所示。图1给 (23) i=1 jEN 出了鸽群抵近目标点的仿真运动轨迹，图中五角 K(w-1)∑∑w-P=0 星表示目标，圆形表示鸽群初始位置，三角形表 ieUpper jeN 示鸽群终了位置，实线表示高层级原鸽个体的运 则式(23)成立当且仅当1=2=…=yw=v,其中 动轨迹，虚线表示非高层级原鸽个体的运动轨 ”为鸽群同步速度，即鸽群内所有原鸽个体实现 迹，由图可见，鸽群可在高层级原鸽个体引领下 速度同步。进而可得x=C,且有 抵达目标点。图2给出了鸽群内原鸽个体与目标 1=l2=…=UN (24) 点的平均距离随时间t的变化曲线，由图可见鸽 由式(8)可知，(r=C,故70=0。 群在高层级原鸽个体引领下逐渐趋近目标点，并
H tq G ′ 连通。由式 (13) 可知，鸽群 Lyapunov 函数 在 切换时刻 只可能由于 内添加的原鸽个体间 拓扑连接而产生能量变化。 tq ∀ j ∈ N1 i ( tq ) /N1 i ( tq−1 ) R 3 lim ⩽ xi j ⩽ R 1 comm. −R 1 lim 由式 (3) 和假设 2 可知，在切换时刻 ， ，有 ，并由式 (8) 可知： V f i j( xi j ) ⩽ V f max (19) V f max = max{ V f i j ( R 3 lim ) ,V f i j ( R 1 comm. −R 1 lim ) } 式中 < ∞ 为添 加单条个体间拓扑连接所增加的最大势能。 tq n 1 q N1 i ( tq ) ∑q k=1 n 1 k ⩽ (N −1) 2 假设在切换时刻 ，有 条个体间拓扑连接 添加至 。由假设 1 可知 。故 由假设 3、式 (18) 及式 (19) 可知： H ( tq ) < Hmax=H (t0)+V f max(N −1) 2 < ∞ (20) 式中 Hmax 为鸽群 Lyapunov 函数上界。 H ≪ ∞ xi j → 0 V f i j( xi j ) → ∞ 由式 (18) 和式 (20) 可知， ，故所有原 鸽个体间可避免碰撞。否则由式 (8) 可知，当 ，均有 。 0 < n 1 q ⩽ N (N−1)−(N −1)=(N−1) 2 q ⩽ qmax ≪ ∞ qmax G ′ t ∈ [ tqmax ,∞ ) H H˙ 由假设 3 可知， ， 则切换数目 ，其中 为最大切换次 数。即，鸽群 最终为固定拓扑。当 ， 为连续函数。由式 (8) 和式 (9) 可知， 亦连 续。定义集合 Ω= { x¯ ∈ R DN2 , v ∈ R DN |H < Hmax,Hmax > 0 } (21) x¯ = [x T 11, x T 12,··· , x T 1N ,··· , x T N1 , x T N2 ,··· , x T NN] 式中 T。 G ′ (t) t ⩾ 0 i j xi j ⩽ (N −1)R H < Hmax ∥vi∥ < √ 2Hmax Ω t ∈ [ tqmax ,∞ ) Ω 由于 对于 为连通图，故鸽群中任意 两个原鸽个体 和 可通过至少一条路径彼此连 通，且路径长度 。此外，由于 ， 则有 ，故 为有界闭集。由于控制 输入如式 (6) 所示的鸽群系统 (1) 在 为 一个自治系统，故可由引理 1 证明鸽群的稳定性， 即对于任意起始于 的状态轨迹最终将收敛至 如式 (22) 定义的集合的最大不变子集： S= { x¯ ∈ R DN2 , v ∈ R DN H˙=0 } (22) 此时有 H˙=−K V v T ((LN +(w−1) L ′ N ) ⊗ ID ) v=− K V∑N i=1 ∑ j∈Ni (vi −vj) 2− K V (w−1) ∑ i∈Upper ∑ j∈Ni (vi −vj) 2 = 0 (23) v1=v2=···=vN=v ′ v ′ xi j =C 则式 (23) 成立当且仅当 ，其中 为鸽群同步速度，即鸽群内所有原鸽个体实现 速度同步。进而可得 ，且有 u1=u2=···=uN (24) V f i j( xi j ) =C ∇xiV f i j( xi j ) 由式 (8) 可知， ，故 =0。 i < Upper i < Upper ui=0 u1=u2=···=uN=0 由假设 4 可知，存在 。由式 (6) 可知，当 时， 。由式 (25) 可知 ， 故有 u= −K f∑ j∈N1 1 ∇x1V f 1 j ( x1 j ) −infor1K T∇x1V T 1 (∥x1 − xT∥) −K f∑ j∈N1 2 ∇x2V f 2 j ( x2 j ) −infor2K T∇x2V T 2 (∥x2 − xT∥) . . . −K f ∑ j∈N1 N ∇xN V f N j( xN j ) −inforN K T∇xN V T N (∥xN − xT∥) =0 (25) xT R 2 lim 即鸽群内所有原鸽个体将会收敛至固定的几 何构型。且由假设 4 可知，鸽群中的高层领导者 可抵达至距目标点 距离为 的区域内。表 明所有原鸽个体间相对位置趋于期望，整个鸽群 可实现稳定的编队并抵近目标。 3 模型同步性仿真分析 N Upper Vmax N 0 ⩽ x 1 i ⩽ 20 m −10 m ⩽ x 2 i ⩽ 10 m vi=[10 m/s,0] xT=[50 m,−50 m] Upper ts=0.05 s Tmax=50 s 1 N ∑N i=1 ∥xi − xT∥ R 5 lim Ta Ta 本节通过仿真实验进一步研究鸽群交互模式 切换模型中不同参数 (包括原鸽个体数目 、高 层级原鸽个体数目 以及个体最大速率 ) 对鸽群系统同步性的影响。设定 个原鸽 个体的初始位置向量随机分布在满足 且 的方形区域内，初始位置向量 ，目标位置向量 ，随 机指定 个原鸽个体作为高层级个体。设 定采样时间 ，最大仿真时间 ，当 鸽群抵达目标点时，即当原鸽个体与目标点平均 距离 小于或等于群体抵达目标的最 大容许误差 时，仿真停止，停止时间为 ，可 将 认定为鸽群抵达目标点所用时间。 R 2 comm.=Rcomm. R 1 comm.=rcR 2 comm. rc t 依照所建模型进行仿真，设定层级交互模式 下最大通信距离 ，平等交互模式下最 大通信距离 ，其中 为平等交互距 离占比，余下仿真参数设置如表 1 所示。图 1 给 出了鸽群抵近目标点的仿真运动轨迹，图中五角 星表示目标，圆形表示鸽群初始位置，三角形表 示鸽群终了位置，实线表示高层级原鸽个体的运 动轨迹，虚线表示非高层级原鸽个体的运动轨 迹，由图可见，鸽群可在高层级原鸽个体引领下 抵达目标点。图 2 给出了鸽群内原鸽个体与目标 点的平均距离随时间 的变化曲线，由图可见鸽 群在高层级原鸽个体引领下逐渐趋近目标点，并 ·338· 智 能 系 统 学 报 第 15 卷