陈怀民 方泰淙 段晓军

摘 要： 随着低空防御系统的不断完善，飞行器成功突防的安全性越来越低。该文旨在解决动态航迹规划问题。首先根据飞行器自身飞行约束条件和高程数字地图信息，利用地形特征，将相对平坦的山谷地形提取出来，建立骨架，作为航迹规划的参考。然后，根据航迹策略，飞行器在地面起飞前通过寻路算法快速制定一条可飞的航迹，在空中作战遇到突发威胁时，也能够快速重规划出一条可飞航迹。仿真实验结果证明了该算法费时短并且实时性高。

关键词： 飞行器； 数字地图； 骨架提取； 航迹规划； 寻路算法； 可飞航迹

中图分类号： TN967.6?34； V249 文献标识码： A 文章编号： 1004?373X（2018）16?0127?05

Abstract： With the continuous improvement of the low?altitude defense system， the security of successful aircraft penetration is becoming lower and lower. Therefore， the dynamic track planning problem is addressed in this paper. According to the flight constraint condition of the aircraft and the information of the elevation digital map， the relatively flat valley terrain is extracted based on the terrain feature， so as to establish the skeleton as a reference for the flight track planning. According to the track strategy， a flyable track is rapidly determined before the aircraft takes off from the ground by using the pathfinding algorithm， and the flyable track can be quickly replanned when the aircraft encounters an unexpected threat during the air combat. The results of the simulation experiment show that the algorithm has short time?consumption and high real?time performance.

Keywords： aircraft； digital map； skeleton extraction； track planning； pathfinding algorithm； flyable track

0 引 言

随着科技的不断进步，现代化战争的防御系统也日益完善，而飞行器成功从敌方势力范围突防的可能性却不断降低。飞行器作低空和超低空突防时，由于地形遮蔽和地面杂波的干扰使得飞行器不易被地面雷达发现，完成作战任务的可能性更强。因此，低空和超低空突防在现代化战争中的优势很大，并逐渐成为现代战争中完成突防的主要作战方式。地形跟随、地形回避技术根据自身的地形地貌，利用导航系统来寻找最适合的飞行航迹路径。地形跟随、地形回避技术也极大地提高了飞行器的突防能力和生存能力，其中航迹规划是核心技术。航迹规划分为静态航迹和动态航迹。本文首先通过灌水操作将梯度变化较大的山脊进行预处理操作，然后通过二值分法进行骨架化处理，再通过中柱转换提取骨架，最后通过模拟火种燃烧的算法找出可飞的航迹路径。飞行器不仅可以在起飞前制定一条静态航迹，也可以在空中遇到突发威胁时重新规划出一条可飞路径。

1 提取骨架图

1.1 生成骨架图算法

高程地图的梯度信息能够一定程度上反映地形上的差异，遇到山脊的地形，数字高程信息梯度变化较大，而山谷处较为平缓，数字高程信息梯度变化不大。可以先对地图模拟给山谷灌水的预处理操作，通过灌水处理后，谷底平坦，梯度较小，能利用梯度识别出是适合飞行的区域。然后通过设置阈值来分割梯度图，分割处理后，各点值为0或1，得到对应的二值图。再根据地形信息提取相对平台的山谷骨架，提取骨架的方法有很多种，其中中轴变换是一种比较有效的方法，如图1所示。

图中有区域[R]、边界[B]、骨架点[P]。对于每一个骨架点[P]，可在区域[R]中找到和它距离最近的骨架点。如果在[P]中能找到多于一个这样的点，就认为[P]是属于[R]的骨架点。

用一个区域点与两个边界点的最小距离来定义骨架，即：

[DS（P，B）=inf{D（P，Z）Z?B}]

若S是区域R的骨架，则满足：R完全包含S，S处在R里中心位置；S为单个像素宽；S与R具有相同数量的连通组元；R的补集与S的补集具有相同数量的连通组元；根据S重建R。

1.2 骨架的拼接和精简

骨架图上的点可以分为如下三类：

1） A类点。8个邻居中仅有一个邻居是骨架点，称这样的点为端点，或叶子节点。

2） B类点。8个邻居中有两个邻居是骨架点，这种点组成了骨架网络的边。

3） C类点。8个邻居中有大于三个的邻居是骨架点，这种点是骨架网络的关节。

生成的骨架图有的不是联通的，通过将骨架栅格的最后一行和最后一列记录下一个骨架栅格的信息，这样就能保证骨架与骨架之间能够拼接的上。在骨架图上，将A类点通过B类点到C类点的这部分线条称为悬挂边，较短的悬挂边称为短毛。在地形复杂的地区，尤其是山区地形，对应的骨架图上会有大量的长度很小的短毛。通过设定一个阈值来清理这些短毛，这样就会使骨架图精简。

1.3 威胁代价

飞行器在执行任务时所面临的威胁是雷达探测、低空火力、地形威胁和禁飞区。其中禁飞区的威胁是杀伤力最大。飞行器在执行任务遇到禁飞区时，会做规避处理。在现代化战争中，由于战场环境非常复杂，地面防御系统发现敌对目标后，要花一些时间处理消息并通知低空火力才能够有效阻截目标。为了避免这些威胁，尽量选择走山谷的盲雷达区来规避威胁。这些威胁区经研究之后把它们近似作圆域处理，经过圆域处理的威胁区，成为绝对威胁区，飞行器在里面飞行的杀伤力为100%。经过威胁区作圆域处理，这样，初始航迹的规划空间已经形成。

1.4 骨架遇威胁区的处理

飞行器执行飞行任务时会面临各种威胁，规划的航迹路线不能进入威胁区域。威胁区域不能飞行，这样就会使原骨架发生断裂，同时也破坏了保持区域连通性的骨架图。为了解决这个问题，采用如下方法：在拼接完成的骨架图上，将威胁区域设置为背景点，然后检查威胁区域的外边界点，如果外边界点是可飞区域点，将其设置为骨架点。威胁加载后，原来的骨架会被截断，但是将威胁的外边界点加入到骨架中后，依然保持了骨架图的连通性。

2 航迹规划

2.1 航迹代价计算

航迹规划的最终路径是由一段一段的航迹初路径的边组成。在骨架处理完之后的地图上，关键点和关键段都会非常清楚的标出来。航迹段的总目标是综合考虑航迹段的威胁因素和燃料代价使航迹总代价最小，最后形成关键点之间通过代价系数连接而成的网络图，进而转化成网络图中寻路问题。

现采用如下方程来描述：

[Fx，y=（1-z）·Mx，y+zNx，y]

式中：[x，y=0，1，2，…，m，][m]为关键点总数；[Mx，y]代表关键点[x]到[y]的威胁代价；[Nx，y]代表关键点[x]到[y]的燃料代价。

2.2 航迹规划的寻路算法

根据数字地图和骨架图的信息，设计基于骨架提取的快速寻路算法。通过做骨架，将关键点和关键路径提取出来，此算法模拟火种在骨架上的燃烧传播。火种从起点开始匀速向前推进，遇到C类点后分为若干路继续匀速向前，遇到A类端点或已燃烧的点就熄灭，直到火种燃烧到目标点为止。如果起点和终点在骨架图的同一个连通分支上，经过一些时间，火种一定能从起点燃烧到终点，第一个到达终点的火种所走过的路就是最短路。但实际上，会存在起点和终点不在一个连通分支上的情况，如果允许火种从端点处向周围以一定的范围喷发，或者像带电铁丝一样向外放电，使得火种能在距离端点较近的其他分支进行传播，然而跨过背景点且确保不跨越威胁区需要有一定的惩罚系数，这样起点和终点不在一个连通分支上也能很好解决。

寻路整体算法流程图如图2所示。

一次寻路过程的流程如图3所示。

为了更好的描述算法，先定义如下概念：

直线可达：若A，B两点间的直线段都在可飞区域中，称AB直线可达。

探路起点：即首次进行探路操作的骨架点。如果任务起点刚好在骨架上，其本身作为探路起点；否则使用距离任务起点最近的骨架点作为探路起点。为了减少算法的寻路步骤，将任务起点和终点直线连线上的最后一个骨架点作为探路起点。

探路终点：距离任务终点较近的骨架点。当某个探路点距离任务终点较近时，探路结束。将任务终点和任务起点连接在直线上，最后一个任务直线可达的骨架点作为探路终点。

探路先锋：寻路算法执行过程中，在骨架图上能向前推进的B类或C类点。算法中使用一个探路先锋队列保存当前所有的探路先锋。探路起点也是探路先锋，并且探路起点在骨架图上的所有邻居都将成为下一代探路先锋。

放电端点：已经被探路先锋抵达的A类点。算法中将当前所有的放电端点保存到一个放电端点队列中。放电端点进行放电操作时，放电半径R内距离该点最近的、没被探路先锋经过的点会被击中，被击中的点变为新的探路先锋。

能量：探路先锋向前推进的动力，每向前推进一个骨架点，消耗一个能量。

探路树：寻路算法从探路起点开始，所经历的关键点构成一棵树，这棵树称为探路树。

完成一次航迹规划任務的寻路算法描述如下：

1） 初始化探路先锋队列、放电端点队列和探路树，初始值为空，确定探路起点和探路终点；

2） 将探路起点作为树根建立探路树，同时将其放到探路先锋队列中；

3） 给探路先锋队列和放电端点队列中所有点补充能量；

4） 按顺序检查放电端点队列中的每个放电端点，如果放电端点的能量大于某一常量就进行一次放电操作，同时将这个点从队列中删除；

5） 按顺序检查探路先锋队列中的每个探路先锋，如果探路成功，转步骤6）；否则，让探路先锋按照规则向前推进，直到所有的探路先锋把能量耗尽为止，然后转步骤3）；

6） 此时已经得到了从探路起点到探路终点的一条路，从探路树中可得到这条路的关键点序列（[V1，V2，…，Vn]）。

2.3 航迹平滑处理

飞行器在执行任务时不能瞬间改变飞行器飞行的方向和飞行速度，这样飞行器在空中不能瞬间完成转弯，这一因素也影响了飞行器在航路规划中的实际性能。因此，为使现有航迹实时性高，需要对航迹做平滑处理。飞行器的最小转弯半径是影响航迹平滑的主要因素。飞行器的飞行速度和最大法向过载影响和决定了最小转弯半径的大小。

式中：[Vmin]是飞行器的最小飞行速度；[nmin]是飞行器的最大法向过载；[Rmin]代表飞行器的最小转弯半径。

如图4所示。给定飞行器的位置、机头方向、飞行方向、最小转弯半径以及下一个航迹点，其中速度方向和机头方向一致。

M点是以[Rmin]为半径的圆心，[γ]是飞行器沿圆周运动时较初始位置转过的角度，它们之间的关系如下：

航迹经过平滑处理，就可以告诉飞行器在什么时候开始转弯，这样就能得到一条实时性高且可飞的航迹。

3 仿真测试

本文在LabWindows/CVI 8.5的开发平台下对模型和算法进行仿真实验。本实验中设置两个大的威胁区和一个小的威胁区，其中红色的圆形区域为禁飞区。对每块经纬度的地图进行骨架提取后保存，使用时根据任务区域再进行骨架拼接，再通过模拟火种燃烧的算法得到航迹规划关键点，之后通过航迹平滑处理，得到可飞的航迹。

本文分别对离线静态航路和动态实时航路进行仿真实验验证。

3.1 静态航迹规划路径

设定任务起点和任务终点的经纬度分别为（108.80，34.20）和（107.02，33.70），设定禁飞区域为圆形区域，威胁区域有威胁区域1经纬度为（108.80，34.20），威胁半径为10 000 m，威胁区域2经纬度为（108.80，33.80），威胁半径为40 000 m，威胁区域3经纬度为（107.90，33.80），威胁半径为30 000 m。通过加载高程数字地图及威胁区之后通过拼接骨架，然后通过寻路算法规划出的航迹路径界面图如图5所示。

对于规划出的航迹要在地形回避、地形威胁、地形匹配中进行模拟航迹飞行轨迹验证。任务起点和任务终点之间的飞行距离为250 km，飞行速度为200 m/s，如图6所示，飞行器的飞行轨迹验证了静态航迹的可飞性。

3.2 动态航迹规划路径

飞行器在空中作战时，按照起飞前制定的航迹规划路径飞行，当飞行器飞行到经纬度为（108.13，34.12）的点时前方突然遇到了突发性的威胁，威胁区为圆形，圆心经纬度为（108.00，34.12），威胁半径为10 000 m，此时距离任务终点的距离为195 km，导航算法必须重新规划出一条路径。这时飞行器根据航迹策略，通过寻路算法快速实现一条可突围的航迹路径，如图7所示。

对于重规划出的新航迹路径要在地形回避、地形威胁、地形匹配中进行模拟航迹飞行轨迹验证。任务起点和终点之间的飞行距离为250 km，飞行速度为200 m/s，在中途突发遇到威胁时，按照重新规划的航迹能够飞行绕过突发威胁区。如图8所示，飞行器的飞行轨迹验证了动态航迹的可飞性。

3.3 各阶段花费时间

经过多次测试，飞行器在遇到威脅需要重新规划出一条可飞路径时，在相距任务点间的距离有250 km时，设置多个威胁区域。骨架拼接、加载威胁区域及任务起点和任务终点之间寻路所花费的时间如表1所示。

4 结 论

本文通过加载已知威胁区域提取骨架图的方法，将关键点和关键路径标记出来，再通过骨架拼接和修剪，去除短毛，把威胁区域简化为威胁圆，得到了航迹规划的搜索空间，这样航迹规划路径就变成一个网络图。用模拟火种燃烧的广度优先方法快速搜索出一条从起始点到终点的航迹路径。由于加载骨架图之后，就把关键点和关键路径标记出来了，这样在寻路的时候就节省了大量的时间。飞行器在空中遇到突发威胁时，也同样能够规划出一条可飞航迹，这种算法不仅适合静态航迹规划，同样也适应于动态航迹规划。图形仿真证明，整体思路可行，算法实时性高。

参考文献

[1] OH H， SHIN H S， KIM S， et al. Cooperative mission and path planning for a team of UAVs [M]. Springer Netherlands， 2015： 1509?1545.

[2] DING Z， ZHANG J， LI C， et al. A real?time path planning method for emergent threats [C]// Proceedings of IEEE International Conference on Information and Automation. Lijiang： IEEE， 2015： 3014?3019.

[3] LIU Y， ZHANG W， LI G， et al. Path planning of UAV in dynamic environment [J]. Journal of Beijing University of Aeronautics &Astronautics;， 2014， 40（2）： 252?256.

[4] DENG T， XIONG Z M， LIU Y J， et al. Research on 3D route planning for UAV in low?altitude penetration based on improved ant colony algorithm [J]. Applied mechanics & materials， 2014， 442（4）： 556?561.

[5] XU Z J， TANG S. Flight path planning based on improved genetic algorithm [J]. Journal of astronautics， 2008（5）： 80?85.

[6] MENG H， XIN G. UAV route planning based on the genetic simulated annealing algorithm [C]// Proceedings of IEEE International Conference on Mechatronics and Automation. Xian： IEEE， 2010： 788?793.

[7] LAMONT G B. UAV swarm mission planning development using evolutionary algorithms and parallel simulation： Part II SCI?195 [J/OL]. [2008?01?24]. http：//www.ixueshu.com/download/5581d1dc3627cb78318947a18e7f9386.html.

[8] 王维平，刘娟.无人飞行器航迹规划方法综述[J].飞行力学，2010，28（2）：6?10.

WANG Weiping， LIU Juan. Introduction to unmanned air vehicle route planning methods [J]. Flight dynamics， 2010， 28（2）： 6?10.

[9] 李季，孙秀霞.基于改进A?Star算法的无人机航迹规划算法研究[J].兵工学报，2008，29（7）：788?792.

LI Ji， SUN Xiuxia. A route planning′s method for unmanned aerial vehicles based on improved A?Star algorithm [J]. Acta Armamentarii， 2008， 29（7）： 788?792.

[10] 张俊峰，周成平.基于改进稀疏A*算法的三维航迹规划方法[J/OL].[2013?02?01].http：//www.doc88.com/p?789355360238.html.

ZHANG Junfeng， ZHOU Chengping. A 3D route planning based on improved sparse A* algorithm [J/OL]. [2013?02?01]. http：//www.doc88.com/p?789355360238.html.