采用威胁启发鸽群优化的武装直升机航路规划

蒋飘蓬， 周 凯， 朱乾坤， 姜文志

(海军航空工程学院，山东 烟台 264001)

采用威胁启发鸽群优化的武装直升机航路规划

蒋飘蓬， 周 凯， 朱乾坤， 姜文志

(海军航空工程学院，山东 烟台 264001)

针对复杂地形和威胁环境下武装直升机对地攻击航路规划问题，对鸽群优化进行了改进，提出了融入威胁启发机制的改进鸽群优化。充分利用作战区域中已知的威胁信息，将其作为启发信息反馈到鸽群中指导信鸽飞行，增强个体在搜索过程中的方向性。此外，采用航路点允许列表构成鸽群优化的寻优空间，缩小搜索空间，并保证了生成航路的可行性。仿真结果表明，所提出的方法能够有效地规划出直升机的最优航路，且规划航路具备避开地形障碍和敌方威胁的能力。

武装直升机； 航路规划； 威胁启发； 鸽群优化； 航路点允许列表

0 引言

直升机作为现代立体化战争中一种重要武器平台，具备较强的攻击能力和快速的机动能力，主要在低空或超低空遂行对地攻击作战任务，而航路规划是低空安全飞行、提升作战效能的重要保障。航路规划是指在特定约束下，为直升机寻找一条从当前位置到期望目标位置的最佳可飞航迹，并且该路径能够避开可能导致飞行安全的不利因素，有效完成作战任务[1]。从本质上讲，航路规划是一个复杂多约束的优化问题，

1 环境建模与航路代价模型

1.1 构造搜索空间

直升机三维空间的全局航路规划，就是在一个威胁和障碍分布已知的环境空间中，寻找一条从起点S飞向目标点D的最优航路。如图1所示，该问题可转化为寻找飞行时所必须经过的一个点集{S,P1,P2,…,Pn,D}，同时每个航路点Pj要满足：Pj为非障碍点，且相邻点的连线上不存在障碍[9]。

图1 环境建模O-XYZ坐标系Fig.1 Modeling in coordinate system O-XYZ

为了便于处理，将直升机作为一个质点来研究，设雷达威胁为半球，并将其边界向外扩张半个直升机最大直径，分别用{(oi,ri)|i=1,2,…,k}表示，其中,oi,ri分别表示第i个雷达的中心位置和作用半径。

图2 圆与正多边形的交点点阵集合Fig.2 Intersection point set of circle and polygon

由于S到D之间存在障碍物，某些路径是无效的，就要消除平面上障碍点，因此为平面Mi(i=1,2,…,n)上的点Pi(ki,ji)引入一个允许列表[10]allowi(u,v)。allowi(u,v)为平面Mi+1上点集的子集，且连接Pi(ki,ji)与allowi(u,v)中任何一点都不会穿过障碍物,该方法能有效减小规划空间，从而提高规划航路的可行性。

1.2 航路代价模型

代价函数作为算法与实际物理问题联系的纽带，设计合理的代价函数是利用优化算法进行航路规划的一个重要环节。对于直升机航路规划这个特殊应用背景，其核心就是建立满足对地攻击问题实际需求的代价函数，作为评价航路优劣的唯一评价标准。

在战场上，为了避开敌方的威胁，直升机借助超低空机动性能利用地形隐蔽飞行，降低威胁代价的同时增加了航路长度；反之，若单纯追求航路长度最小化将导致威胁代价增加，甚至可能穿过威胁区。另一方面，根据武装直升机自身机动性能的限制和使用要求，所规划出的航路要平缓，依照规划航路到达敌区域时，应能满足机载武器系统的发射条件(如攻击时的飞行高度)。为此，本文在计算航路代价时，除了考虑航路代价与威胁代价外，还把直升机必须满足的约束条件(航迹角、爬升/俯冲角、飞行高度等)集成到代价函数中，即在代价函数中还考虑航迹角代价、爬升/俯冲角代价和飞行高度代价。综合考虑这些代价，对给定航路X{i}，其总代价可表示为这些代价的加权和，即

(1)

式中:J1～J5分别为航路的长度代价、威胁代价、航迹角代价、爬升/俯冲角代价和飞行高度代价;ωk为它们相应的权系数(k=1,…,5)。

航路的长度代价、威胁代价、航迹角代价、爬升/俯冲角代价和飞行高度代价的具体计算方法可参见文献[11-13]。

2 基于PIO的直升机航路规划

2.1 基本鸽群优化

2014年，段海滨等人根据生物界信鸽的自动导航能力，提出了一种仿生智能优化算法——鸽群优化(PIO)。PIO中每个鸽子都对应一个可行解，具有位置和速度两个属性，并通过适应度函数来评价鸽子的品质。PIO采用指南针算子和地标算子来模仿飞行导航工具的不同阶段，并通过导航过渡因子tr[14]，将两个独立的进化和筛选操作融合为一个迭代循环寻优过程。具体更新方式如下

Vi(t)=Vi(t-1)·e-R×t+rand·tr·
(1-logtmaxt)(Xgbest-Xi(t-1))+rand·tr·
logtmaxt(Xc(t-1)-Xi(t-1))

(2)

Xi(t)=Xi(t-1)+Vi(t)

。

(3)

式(2)中：第一部分为原有速度的继承；第二部分为地图和指南针算子[8]，用于模仿太阳和地球磁场对鸽子飞行的导向作用，R表示地图和指南针因数，并且可以设定成0到1之间的数，t表示当前的迭代次数，Xi(t)和Vi(t)分别表示鸽子i在t代的位置和速度，Xgbest表示在t-1次迭代循环后通过比较所有鸽子的位置而获得的全局最好位置，rand是[0,1]上的随机数；第三部分为地标算子[8]，用来模仿鸽子靠近目的地飞行时，地标在路线评估和修正中起到的作用。熟悉地标的鸽子可径直飞向目的地，不熟悉地标并且远离目的地的鸽子(即品质差)可跟随熟悉地标的鸽子飞行从而到达目的地。在每次的迭代循环中，地标算子会将当前个体的适应值进行排序，将品质差的个体舍弃，Ndec表示每次迭代循环中舍弃的鸽子数，把余下鸽子的中心位置Xc(t)当成地标作为飞行的参考方向。具体计算方法如下

Np(t)=Np(t-1)-Ndec

(4)

。

(5)

最后，依据式(3)对鸽子的位置Xi(t)进行更新。

2.2 威胁启发

标准的鸽群优化只利用全局最好位置和群体中心位置的已知信息来指导飞行，没有体现出鸽群飞行要远离环境中威胁点的特性。在已知任务区域威胁分布的情况下，如果能够充分利用这些威胁信息，为鸽子的飞行提供指导，则有助于增强鸽子更新的针对性，具体实现方法是鸽子在速度更新时，增加威胁启发项，以表征威胁信息对速度更新的影响，效果如图3所示。新的速度更新表达式为

Vi(t)=Vi(t-1)·e-R×t+r1·tr·(1-logtmaxt)·
(Xgbest-Xi(t-1))+r2·tr·logtmaxt(Xc(t-1)-
Xi(t-1))+r3·T(Xi(t-1))·
(Xi(t-1)-Qh)/‖Xi(t-1)-Qh‖

(6)

式中:等式右边前三项与鸽群优化相同;第四项表示环境认知操作，把威胁启发信息对个体影响融入到速度的更新公式中。T(Xi(t-1))表示受到的威胁代价；Qh为个体每一维受到最大威胁源的位置所组成的向量；(Xi(t-1)-Qh)/‖Xi(t-1)-Qh‖为背离其最大威胁源的单位方向的向量，是威胁启发项中的方向信息。当T(Xi(t-1))越大时，相当于对个体施加一个较大概率的扰动，再结合威胁方向信息，从而可以使节点离开目前存在较大威胁的区域。

图3 速度更新示意图Fig.3 Diagram of velocity updating

2.3 算法实现

,

。

其中,n,kn,jn取值范围与构造规划空间时定义的一致。

2.4 算法流程

1) 初始化。

① 通过转换矩阵确定威胁和障碍在新坐标系O′-X′Y′Z′中的位置。

② 环境建模，构造搜索空间，计算出规划空间中每个点的航路点允许列表allowi(k,j)。

③ 鸽群初始化，随机为每个个体配置初始位置和速度，个体的维数为n+2，第1维和第n维分别为点S和点D，它们在更新时保持不变，其他n维分别在其允许列表allowi(k,j)中选取,以此保证随机产生的个体所代表的航路不会碰到障碍物。

2) 每代种群中的个体可更新。

Vdkdjdi(t)=Vdkdjdi(t-1)·e-R×t+r1·tr·(1-logtmaxt)·

(7)

Xdkdjdi(t)=Xdkdjdi(t-1)+Vdkdjdi(t)

(8)

3) 对个体的速度和位置进行更新后，判断其是否满足相应的允许列表allowi(k,j)，如果个体代表的航路穿越障碍物，则该个体失效；再补充新的个体添加到鸽群中，进行优化。

4) 通过直升机航路代价确定的适应度函数来计算个体适应度，更新Xgbest与Xc(t-1)。

5) 如果满足迭代结束要求，输出最优航路；否则转至步骤2)。

3 仿真验证

为了验证改进算法的有效性，进行了相应的仿真实验。本文实验采用以下参数值：直升机飞行离地间隙一般为10～100 m；最大航迹角和最大爬升/下滑角分别为60°和30°；权系数ω1～ω5分别为0.1，0.4，0.2，0.2，0.1；种群规模为40，最大迭代次数200，地图和指南因数R为0.3，导航过渡因子tr为2。

坐标系采用三维直角坐标，规划区域为190 km×210 km的区域，地形采用函数模拟。图6中，直升机起始点“◇”坐标为(10 km，20 km,20 m)，目标点“☆”坐标为(200 km,170 km,40 m)，任务区域有9座山峰表示地形障碍，已知4个地面威胁区域中心“*”坐标分别为(85 km,115 km,20 m)，(145 km,80 km,18 m)，(150 km,150 km,20 m)，(70 km,30 km,20 m)。

分别使用蚁群算法(ACO)、鸽群优化(PIO)和威胁启发鸽群优化(改进PIO)在相同参数设置下进行航路规划。如图4所示，黑色曲线表明威胁启发鸽群优化能够迅速找到最优航路，平均在第78次迭代时收敛到最优；而从红色表示的ACO和蓝色表示的标准PIO的适应度变化曲线，可以看出收敛速度偏慢，且易陷入局部最优;实验结果表明，本文提出的算法与蚁群算法、标准鸽群优化相比能够更快地收敛而且稳定性好，同时改进PIO在收敛精度上也体现了优势，这说明威胁启发项的加入使得个体飞行具有方向性，提高算法的规划能力。

图4 航路代价变化图Fig.4 Chart of flight routes costs

图5 三维航路规划图Fig.5 Chart of three dimensional path planning

图6 航路水平投影图Fig.6 Horizontal projection of aerial path

从图5～图6可以明显看出，本文提出的威胁启发鸽群优化与蚁群算法相比，所规划出的最优航路更加平滑和安全，能够有效对任务区域中的威胁进行回避，更好地解决了直升机贴地隐蔽飞行的安全问题。

4 结束语

在本文中，威胁是任务区域中的已知信息，直升机航路规划将其作为威胁启发项，集成到鸽群优化速度更新公式中，有效地拓展了鸽群优化的飞行方向，增强个体在搜索过程中的方向性和指导性。仿真结果验证该算法的合理性和有效性，能够在沿着最短路径方向的情况下，有效避开威胁阵地，并尽可能利用地形环境作掩护进行低空作战。

[1] 武晶杰，潘丽君，张峰刚．虚拟战场环境中武装直升机航路规划算法研究[J].系统仿真学报，2006，18(2)：721-730．

[2] 郝霞，张健，蔡满意.自适应遗传算法在飞行器离线航迹规划中的应用[J].电光与控制，2010，17(1)：65-68.

[3] 刘科，周继强，郭小和.基于改进粒子群算法的无人机路径规划研究[J].中北大学学报：自然科学版，2013，34(4)：441-446.

[4] DUAN H B,ZHANG X Y,WU J. Max-min adaptive ant colony optimization approach to multi-UAV coordinated trajectory replanning in dynamic and uncertain environment[J].Journal of Bionic Engineering,2009,6(2):161-173.

[5] 刘敏，邹杰，冯星，等．人工蜂群算法的无人机航路规划与平滑[J]．智能系统学报，2011，6(4)：344-349．

[6] DUAN H,YU Y,ZHANG X,et al.Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm[J].Simulation Modelling Practice & Theory, 2010,18(8):1104-1115.

[7] 李猛，王道波，柏婷婷，等．采用威胁启发粒子群算法的无人机航路规划[J]．电光与控制，2011，18(12)：1-4．

[8] DUAN H B,QIAO P X.Pigeon-inspired optimization:a new swarm intelligence optimizer for air robot path planning[J].International Journal of Intelligent Computing and Cybernetics,2014,7(1):24-37.

[9] 陈世明，谢竟，陈文栋，等．基于HPSO算法的三维空间路径规划[J]．华中科技大学学报:自然科学版，2013，41(2)：109-113．

[10] 魏代俊，向长城．粒子群算法在三维空间机器人路径规划中的应用[J]．南京师范大学学报,2008，8(3)：77-81．

[11] 肖剑，单超，王萍，等．武装直升机对地攻击路径规划遗传算法适配函数设计[J]．直升机技术，2008(1):35-40.

[12] FU Y G,DING M Y,ZHOU C P,et al.Path planning for UAV based on quantum-behaved particle swarm optimization[C]//SPIE Intemational Symposium on Multispectral Image Processing and Pattern Recognition, Yichang,2009:74970B-1-74970B-7.

[13] 陈琳，白振兴．应用PSO算法的无人机三维航迹规划[J]．电光与控制，2008，15(4)：50-53．

[14] 段海滨，邱华鑫，范彦铭．基于捕食逃逸鸽群优化的无人机紧密编队协同控制[J]．中国科学：科学技术，2015,45(6):559-572．

RoutePlanningofArmedHelicopterBasedonPigeon-InspiredOptimizationwithThreatHeuristic

JIANG Piao-peng, ZHOU Kai, ZHU Qian-kun, JIANG Wen-zhi

(Naval Aeronautical and Astronautical University,Yantai 264001,China)

In order to solve the problem of helicopter’s route planning under the environment with complex terrain and threats,an improved pigeon-inspired optimization is proposed,in which the threat heuristic mechanism is integrated. The new algorithm makes full use of the known threat information in combat zone and takes it as the feedback information for guiding the flight,which can enhance the directivity of an individual during searching. The searching space constructed by allowed lists of way points can compress the searching space and ensure feasibility of the planned route. The simulation results show that the proposed method can effectively obtain the optimum route for the helicopter,which has the capability of terrain avoidance and threat avoidance.

armed helicopter; route planning; threat heuristic; pigeon-inspired optimization; allowed list of way point

蒋飘蓬,周凯,朱乾坤,等.采用威胁启发鸽群优化的武装直升机航路规划[J].电光与控制，2017，24(7)：57-61.JIANG P P,ZHOU K,ZHU Q K,et al.Route planning of armed helicopter based on pigeon-inspired optimization with threat heuristic[J].Electronics Optics & Control,2017,24(7):57-61.

V271.4; TP391

A

10.3969/j.issn.1671-637X.2017.07.012

2016-07-26

2016-08-16

蒋飘蓬(1984 —),男，湖南江永人，硕士，工程师，研究方向计算机应用教学。遗传算法[2]、粒子群算法[3]、蚁群算法[4]和人工蜂群[5]等智能算法在航路规划问题中已有很多应用，均展现良好的搜索能力，取得了预期效果。但是当作战区域较大时，直接进行三维路径规划会导致搜索空间过大，算法收敛速度变缓。基于此，本文根据直升机三维航路规划的具体特征，首先构建了满足对地攻击问题实际需求的航路代价模型；其次借鉴文献[6-8]提出了用于三维航路规划的启发式鸽群优化；再次引入航路点允许列表重构航路的寻优空间；最后通过仿真实验对所提方法进行验证。