王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·1343· simulated annealing(SA)mechanism was exploited to reserve the worse individual,which effectively reduced the problem that PIO was easy to fall into local optimum.Finally,the algorithm was compared with other swarm intelligence algorithms through simulation experi- ments.The results show that the new method is effective and available. KEY WORDS multi-UAVs;cooperative search;honeycomb model;Markov chain;Cauchy mutation;Gaussian mutation;pigeon- inspired optimization 军事领域的智能无人化发展，是“加快军事智 响其性能的主要因素有搜索环境、无人机自身特性、 能化发展”的重要内容，也是军事智能“由人向物” 目标运动等 迁移的关键领域.无人机具有持续工作能力强、全 1.1环境信息图 寿命周期成本低等特点，在尺寸、速度和机动性等方 环境信息图，是无人机在搜索过程中对环境不 面具有独特的优势口，成为影响未来信息化战争的 确定性的反应.文献[4]和[9]均采用矩形栅格离 时代力量.由于单架无人机所能携带的任务载荷相 散化搜索区域，但是传感器对周围环境的探测更接 对单一，执行任务能力有限，而通过多无人机的能力 近于圆形域，所以本文采用六边形构建蜂窝状的搜 互补和行动协调，可实现整个系统效能的提升.因 索环境，这样可以减少重复区域的搜索，进而提高搜 此，无人机的应用样式逐步从单平台向群体智能的 索效率.将搜索区域L离散化为L×L,的栅格，每 多平台发展 架无人机看作栅格中的一个质点，这样多无人机协 多无人机协同搜索，即多架无人机按照一定的 同搜索问题就可以转化成无人机之间栅格位置的协 搜索规则，在未知区域中最大限度地降低环境的不 同.构建环境信息模型如图1所示. 确定性，且尽可能地发现目标的过程.Peng等对 几种典型协同目标搜索策略进行仿真分析.如，随 机搜索、贪婪搜索、滚动时域控制(receding horizon control,RHC)搜索等.由于群体智能个体行为的去 中心化、交互合作分布式、整体自组织等特点与无人 机协同搜索的局部性、分布式和鲁棒性等要求存在 契合之处[).因此，研究群体智能的多无人机协同 图1环境信息模型 Fig.I Environmental information model 搜索成为热点话题.文献[4]基于搜索图建立环境 模型，采用局部粒子群实时构建无人机子群，实现分 图1中，灰色阴影部分为搜索区域.假设该区 布式搜索多个静态目标.Yang等]提出基于不确 域用二维坐标(x,y)表示，传感器的探测半径为「， 定环境的改进蚁群多无人机协同搜索方法，该方法 横坐标x的增幅△x为V5r,纵坐标y的增幅△y为 使用改进蚁群算法的行为规则决定航路点的转移， 3r/2. 并基于信息素图进行更新.但是基于群体智能的蚁 假设p(x,y,t)是t时刻目标在栅格(x,y)内存 群优化算法、粒子群优化算法、人工蜂群优化算法存 在的概率，p(x,y,t)∈[0,1].ud(x,y,t)是环境信 在搜索效率低、收敛速度慢等问题，段海滨等6)提 息的不确定度，可用目标存在概率p(x,y,t)的嫡描 出的鸽群优化(pigeon-inspired optimization,PIO)算 述，定义为： 法能够有效克服以上问题，并已在很多方面取得研 (0 p(x,y,t)=0或者1 究成果).Li等[8】提出边缘势函数和改进鸽群优化 ud(x,y,t)= (H[p(x,y,)]其他 的图像目标检测方法.但以上算法在两方面存在局 (1) 限性：(1)针对静态目标完成协同搜索：(2)群体智 H[p(x,y,t)]=-p(x,y,t)logzp(x,y,t)- 能算法容易陷入局部最优.因此，本文提出运动目 (1-p(x,y,t))log2(1-p(x,y,t))(2) 标模型和扰动模拟退火鸽群优化(mutations simula- 1.2无人机运动模型 ted annealing pigeon-inspired optimization,MSAPIO) 假设所有无人机处于相同飞行高度.UAV,在t 算法完成多无人机协同搜索 时刻的状态信息x:(t)为： 系统建模 x:(t)=[pos:(t)且0：(t)] (3) 式中，pos(t)=(x:(t),y:(t))∈{1,2，，L}× 多无人机协同搜索是一个复杂的动态过程，影 {1,2,…,L,}为UAV的空间位置；方向O,(t)∈{0，王 瑞等: 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 simulated annealing (SA) mechanism was exploited to reserve the worse individual, which effectively reduced the problem that PIO was easy to fall into local optimum. Finally, the algorithm was compared with other swarm intelligence algorithms through simulation experi鄄 ments. The results show that the new method is effective and available. KEY WORDS multi鄄UAVs; cooperative search; honeycomb model; Markov chain; Cauchy mutation; Gaussian mutation; pigeon鄄 inspired optimization 军事领域的智能无人化发展,是“加快军事智 能化发展冶的重要内容,也是军事智能“由人向物冶 迁移的关键领域. 无人机具有持续工作能力强、全 寿命周期成本低等特点,在尺寸、速度和机动性等方 面具有独特的优势[1] ,成为影响未来信息化战争的 时代力量. 由于单架无人机所能携带的任务载荷相 对单一,执行任务能力有限,而通过多无人机的能力 互补和行动协调,可实现整个系统效能的提升. 因 此,无人机的应用样式逐步从单平台向群体智能的 多平台发展. 多无人机协同搜索,即多架无人机按照一定的 搜索规则,在未知区域中最大限度地降低环境的不 确定性,且尽可能地发现目标的过程. Peng 等[2] 对 几种典型协同目标搜索策略进行仿真分析. 如,随 机搜索、贪婪搜索、滚动时域控制( receding horizon control,RHC)搜索等. 由于群体智能个体行为的去 中心化、交互合作分布式、整体自组织等特点与无人 机协同搜索的局部性、分布式和鲁棒性等要求存在 契合之处[3] . 因此,研究群体智能的多无人机协同 搜索成为热点话题. 文献[4]基于搜索图建立环境 模型,采用局部粒子群实时构建无人机子群,实现分 布式搜索多个静态目标. Yang 等[5] 提出基于不确 定环境的改进蚁群多无人机协同搜索方法,该方法 使用改进蚁群算法的行为规则决定航路点的转移, 并基于信息素图进行更新. 但是基于群体智能的蚁 群优化算法、粒子群优化算法、人工蜂群优化算法存 在搜索效率低、收敛速度慢等问题,段海滨等[6] 提 出的鸽群优化( pigeon鄄inspired optimization,PIO) 算 法能够有效克服以上问题,并已在很多方面取得研 究成果[7] . Li 等[8]提出边缘势函数和改进鸽群优化 的图像目标检测方法. 但以上算法在两方面存在局 限性:(1)针对静态目标完成协同搜索;(2)群体智 能算法容易陷入局部最优. 因此,本文提出运动目 标模型和扰动模拟退火鸽群优化(mutations simula鄄 ted annealing pigeon鄄inspired optimization, MSAPIO) 算法完成多无人机协同搜索. 1 系统建模 多无人机协同搜索是一个复杂的动态过程,影 响其性能的主要因素有搜索环境、无人机自身特性、 目标运动等. 1郾 1 环境信息图 环境信息图,是无人机在搜索过程中对环境不 确定性的反应. 文献[4]和[9]均采用矩形栅格离 散化搜索区域,但是传感器对周围环境的探测更接 近于圆形域,所以本文采用六边形构建蜂窝状的搜 索环境,这样可以减少重复区域的搜索,进而提高搜 索效率. 将搜索区域 L 离散化为 Lx 伊 Ly的栅格,每 架无人机看作栅格中的一个质点,这样多无人机协 同搜索问题就可以转化成无人机之间栅格位置的协 同. 构建环境信息模型如图 1 所示. 图 1 环境信息模型 Fig. 1 Environmental information model 图 1 中,灰色阴影部分为搜索区域. 假设该区 域用二维坐标(x, y)表示,传感器的探测半径为 r, 横坐标 x 的增幅 驻x 为 3 r,纵坐标 y 的增幅 驻y 为 3r/ 2. 假设 p(x,y,t)是 t 时刻目标在栅格( x,y)内存 在的概率,p(x,y,t)沂[0,1]. ud(x,y,t)是环境信 息的不确定度,可用目标存在概率 p( x,y,t)的熵描 述,定义为: ud(x,y,t) = 0 p(x,y,t) = 0 或者 1 H[p(x,y,t)] { 其他 (1) H[p(x,y,t)] = - p(x,y,t)log2 p(x,y,t) - (1 - p(x,y,t))log2 (1 - p(x,y,t)) (2) 1郾 2 无人机运动模型 假设所有无人机处于相同飞行高度. UAVi在 t 时刻的状态信息 xi(t)为: xi(t) = [posi(t)且 Oi(t)] (3) 式中,posi( t) = ( xi ( t),yi ( t)) 沂{1,2, …,Lx } 伊 {1,2, …,Ly}为 UAVi的空间位置;方向 Oi(t)沂{0, ·1343·