基于概略图的航迹优化的改进A*算法研究*

陈韶千，董国才，唐同斌，张健楠，章 校，王 姣，刘士勋，喻 戈，张 翔

(西安现代控制技术研究所， 西安 710065)

0 引言

A*算法作为一种航迹优化的有效手段，可在数字地图中规划出合适的航迹[1]，但是由于A*算法是启发式的，因此无论怎么改进，都无法改变启发式算法遍历节点随搜索范围和距离的增加而大幅度增加的事实[2-3]。离线优化阶段，为从根本上减少搜索点的个数，提出了概略图法——先使用概略图技术对数字地图进行预处理，然后再在狭窄通道等小范围使用A*算法。

概略图(Skeleton)也称为路标图(Roadmap)[4-5]。地形的概略图是将地形中的山谷、通路，进行概略抽象，表示成一个由一维线段构成的网络图，然后采用搜索算法在该网络图上进行搜索。这样，路径优化问题被转化为一个网络图的搜索问题。概略图必须表示出地形控件中的所有可能的路径，否则就是不完全的，即可能丢失最优解。

最终生成的地形概略图是一个带有加权系数和经纬度信息的路标图，在图中每个节点都是带有经纬度信息的可能航路点，点与点之间是具有加权系数的连线，连线的加权系数反映了这条通路的代价(包括：威胁代价、高度代价、航程代价、燃油代价、飞机纵向机动性能等因素)，连线之间的夹角考虑了飞机的横侧向机动约束。

1 立体联通概略图

要利用概略图法进行航迹优化，先必须得到概略图。下面简略介绍得到概略图的过程。

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

现在先选取秦岭俯视地图的一部分作为例子，该地图显示的是西安市附近秦岭的俯视图。该图是一个黑白的地形俯视图，将要对该地图进行分析操作。在地图上选了两个点，一个作为出发点，另一个作为目标点。从出发点飞机要飞过很多山地障碍才能到达目的地。先选取80 m高度，得到地图80 m高度的横切面,如图1所示。白色的部分是山体，是不可穿过的，黑色的部分是空旷可以穿过的，两个红点分别为起点和终点。从地图上可以看出，在相对地面高度为80 m的时候，无论飞机从哪里飞，都不能够穿越障碍区域到达目的地，所以这个高度就是无法通过的，必须要提升飞行高度，继续寻找可能的路径。

图1 高度为80 m处的横切面

图2 高度为100 m处的横切面

将飞机的飞行高度提升到相对地面100 m，现在得到100 m高度的横切面如图2所示。可以看出随着高度的增加，白色区域有所减少，有的地方出现了黑色的缺口和通道。缺口的宽度假定为100 m，在缺口或通道宽度大于这个值的时候我们就可以认为这个地方是飞机可以通过的。从地图上可以看到这样的缺口出现了，并且还不止一处。所以，飞机在100 m高的空域飞行，可以穿越障碍达到目的地。

现在对图像进行处理，作出腐蚀与膨胀操作，操作的目的是去除地图上的毛刺，得出图3。

图3 膨胀处理之后的100 m高度横切面

图4 120 m高度横切面

从图3上看出，白色的山体“变胖”了，这个膨胀的多少可以假定为我们上面选定的那个宽度值10 m。从这里看到，有一些通道被堵死了，有一条却被压缩得很细。很细的通道表明飞机可以从这里飞过去。被堵死的通道因为不能满足飞机安全通过的需求，被排除在外，仍然存在的这条通路就是飞机可以选择的航路。将这条航路用线段连接，也就是将地图骨骼化，标记出它的起点和终点。对每一条被找出的这种通道都做这样的处理，于是就得到了上面提出的概略图，即表示成一个由一维线段构成的网络图。每一个通道的起点和终点都被称作关键点，这些点有经纬度信息。

继续改变高度，达到了120 m，这样得到120 m的横切面，如图4所示。如图可见，现在地图上只有零星的障碍了，再用上述办法得出高度为120 m时的最优航路。直到高度提升到150 m以上，白色的障碍物消失，全部都是自由空域。

综上所述，整个方案的关键就在如何寻找关键点并画出概略图。这样做的目的是为了大大减小需要使用航迹搜索算法进行航路优化的地区的范围，从整个地图都需要使用航迹优化算法变成了只要在几个狭窄通道或者是缺口处才要使用。而这需要用到地理信息系统(GIS)知识中的地图自动抽象技术。该技术将一定高度所截得的地图进行处理，将障碍物进行膨胀得到飞机实际能够通过的通道和缺口的位置。

概略图法的思路总结如下：将在海拔60 m到该处地图最高山峰的高度范围内的数字地图进行间隔为10 m的等高切割，每层都得到一个固定在该高度下的数字地形的横截面。规定在山体缺口最窄处的中点为圆心距离两侧山体都为100 m处为一处狭窄通道，从缺口向两侧开阔地带延伸。随着地形越来越开阔，跟山体两侧都相切的圆的半径也在增大。取半径为200 m的圆的圆心为关键点。因为在开阔地带基本不需要避障和算法，所以概略图法的最主要的目的就是找出狭窄通道。

由于算法的主要目的就是找出关键点和狭窄通道，仅在该处使用航迹优化搜索算法进行优化，从而缩短离线优化所需要的时间。这里的关键点其实都可以称做狭窄通道。下面来说明如何判断某处是否可以被称为狭窄通道。

图5 典型狭窄通道示意图

假设飞行器允许通过的通道最窄处圆的半径为100 m。为减少满足这个条件的点的数量，需要过滤掉无效关键点，所以同时规定，狭窄通道的最宽的地方圆的半径为200 m。图5展示的是一种典型的狭窄通道寻找关键点的情况。下面两个以点A为圆心的同心圆一个是100 m半径，另一个是200 m半径，上面那个圆半径是100 m。两侧的阴影部分圆弧表示山体部分，虚线圆弧是虚拟的向外扩张了100 m的山体。从图5可见，因为A点到C点之间这个狭窄通道中最窄处的B点处宽度为半径100 m，所以从点A到点C之间总有点满足到山体的距离大于100 m小于200 m的条件，可以取两个端点A和C为此处狭窄通道内关键点。因为届时要在此处进行A*的优化，在A和C点之间使用算法，在该处狭窄通道之外就可以直接与其他狭窄通道的关键点或者起始点/目标点链接。若是最窄处的圆半径大于等于100 m，则该高度处满足飞机安全通过的要求，若小于100 m，则该高度处不能满足要求。从图上可以清楚的知道，既然最窄处都满足要求，那其至少还存在分布于两侧的同心圆，如上图中的A和C。这样，搜索算法到这里需要遍历的点就从一堆变成了两个。

因为在地形平坦的平原地区上空飞行，一般可以直接采用尽量贴地的直线飞行，无需使用航迹优化软件来提前优化路径，所以在常用的低空突防航迹优化的环境中，飞机都是在山区的环境中执行任务。山体一般来说都是上小下大，同样的地区，空域的海拔越高，障碍物就越稀少。基于山体的这个特征，只要在某山谷的较低海拔处飞机可以安全通过，在同一个经纬度的较高海拔处也一定可以让飞机安全通过。所以，在立体地形中选取关键点，还是像上面一样在不同的高度对数字地形进行横切，在这些横切的图形中寻找关键点，并把所有高度层找到的所有关键点放在一起跟起始点和终点相连，比较代价，选择代价最小的路线。为了确保能够尽量降低飞行器的飞行高度，只选取最窄处圆半径恰好为100 m的通道，这个高度的狭窄通道的关键点就作为整个立体地形的一处关键点。这样选出来的关键点是同一处狭窄通道的海拔最低的关键点，在满足飞机安全通过需要的前提下同时又能满足低空突防尽量降低飞行高度的要求。

2 基于概略图的航迹优化算法

文中基于概略图的航迹优化的具体做法是：

第一步:读取数字地图，将其以10 m为高度间隔，从海拔60 m到海拔4 500 m分割成不同高度的地图横切面；

第二步:在这些横切面里面分别寻找关键点，并将这些关键点放在同一张数字地形地图里形成立体概略图；

第三步:连接起始点、目标点和这些关键点，形成多条航路，计算这些航路的代价，选择其中代价最低的那一条作为大概航路；

第四步:对这条航路中的狭窄通道部分使用改进型稀疏A*算法得到最终的优化航迹。

3 离线仿真结果对比

为了验证立体联通概略图的实际作用效能，将在同一数字地图的同一部位，在起始点和预设各目标点坐标相同，约束条件也相同的情况下，分别运用未经修改的启发式A*算法、改进的稀疏A*算法和立体联通概略图法进行航迹优化，将得到的路线和搜索时间进行一个对比。由于距离远，为更清楚的对比各情况的结果，选取含有起始点、大量威胁点和复杂地形的这部分的航迹优化结果。图中红色的线是航迹的一些预先设定的必经节点之间的连线。这里显示出的5个节点纬度和经度坐标分别为(34.20°，108.80°)、(34.20°，108.38°)、(34.08°，108.20°)、(33.70°，107.02°)、(33.20°，106.90°)。3个大小不一的红褐色圆为威胁区域，其坐标、高度和作用范围为(34.21°, 108.60°, -1 000 m, 10 000 m)、(33.80°, 108.80°, -1 000 m, 40 000 m)、(33.80°, 107.90°, -1 000 m, 30 000 m)。此时视威胁为无限高山峰，所以威胁中心高度没有意义。因此，高度选取-1 000 m以代表这是一个没有实际意义的高度。

1)未经修改的启发式A*算法

使用未经修改的启发式A*算法，整个算法完成优化用时27 min 19 s，得到的优化结果如图6所示。

图6 未加修改的启发式A*算法优化

2)立体联通概略图法

采用立体连通概略图和改进的稀疏A*算法相结合的方式，选用的参数和改进的稀疏A*算法相同时，搜索时间为7 min 26 s，得到的优化结果如图7所示。

图7 改进的A*算法相结合的优化

4 结论

综上所述，随着算法的改进和概略图技术的应用，离线优化所需的时间被有效缩短，优化时间从27 min多钟缩减到7 min左右。虽然每次的路径结果不尽相同，但是优化的路径都能满足飞行器各项物理约束限制、飞行安全和执行任务的需要。由此可见，概略图技术和改进的稀疏A*算法相结合之后相比于一般的航迹优化算法搜索的效率大大提高。