马 兰，刘佳月

(中国民航大学空中交通管理学院，天津 300300)

1 引言

从宏观层次来讲，主要有三个方面能对飞行安全产生影响，三种因素分别是：人、机、环境。在导致航班延误和改航的各种原因中，强对流天气无疑占据较大比例，其中雷暴云团内的闪电、过冷却水很容易对机身和发动机造成损害，因其生命周期短且突发性为主要特征，飞行计划中很难周全地考虑到。虽然这种天气现象的尺度一般小于两百公里、周期由几分钟至几小时不等，但是对飞行安全来说仍然需要提高警惕。与此同时，在飞行过程中影响飞行安全的因素有很多，许多外在条件的变化都会使飞行路线需要实时的动态规划。

路径规划的目的就是为了使飞机在受各种影响因素的情况下仍然能够圆满地完成飞行任务，国内外对这方面的研究已经有许多[1]。王莉莉、周娟为了应对静态和动态突发天气条件，设计启发式算法将偏航因素考虑进去建立了最短航程模型[2]；王清琦、张兆宁为通过合理划设飞行受限区，利用状态转移矩阵对雷暴轨迹预测，为改航飞行提供参考[3]；陈至坤、郭宝军、王淑香通过栅格法对空间环境建模，以遗传算法对A*算法改进路径进行规划提高了运算效率[4]；Victor Singh和Karen E.Willcox将动态路径规划问题分解为运动规划和轨迹跟踪两部分，考虑了物理性能限制结合大量离线数据，把按约束条件规划表达为马尔科夫决策过程[5]；Egidio D’Amato和Massimiliano Mattei研究了多边形障碍物、禁飞区等情况下的三维飞行路径规划问题，通过降维可见性图(RVG)方法使路径长度最小化[6]。

在实际飞行过程中，出现因操作误差或天气及其它因素导致的未能按既定航线飞行，需要尽快进行路径规划恢复正常，这样才能减小对其它飞机的影响，在繁忙路段更是这样。本文通过改进A*算法的底层结构，提出不同的启发函数，减少算法对环境节点的探索，节约运行时间，针对危险天气在航路上出现的路径规划问题做出主要研究思路如下：1)首先选择全局静态路径规划算法：A*算法作为顶层算法；2)通过Bresenham算法对A*算法底层结构做出优化，达到减少搜索节点的目的；3)二者结合不仅适用与静态路径规划，同时也可以应用于移动障碍或突然出现障碍情况的动态路径规划；4)分析总结在不同的障碍情况下能否继续进行自身查验。

2 Bresenham算法模型

以现代导航的设施设备条件，在进行实际的飞行活动前就能够获取从出发点到目的地的许多相关信息，包括航线、机型性能、预计出发和到达时刻以及预期航空位置等，这相当于已知环境边界以及部分环境做路径规划。传统的路径规划的过程是有层次的，从动态路径规划和静态路径规划来讲主要可以分为A*算法和D*算法，从框架层级上来讲可以分为High Level：Dijkstra、A*算法等；Low Level：VO算法、RVO算法、ORCA算法等。A*算法作为静态路网中路径规划最直接有效的办法被广泛应用和改进。

但是就像引言中提及的，首先，将空域转化为栅格后计算规模较大、时间复杂度高，不能满足动态改航的需求；其次，雷暴云团的生命周期短，A*算法并不具备预知突发情况的能力，使用起来会与实际运行情况存在较大偏差。截至目前为止大部分对A*算法的改进仍停留在针对OPEN表和CLOSED表的方面，以飞行过程中遇到雷暴云团为例，A*算法会从出发点重新规划一条到达目的地的航线，并不能直接对突发天气现象这种动态情况作出及时反映，且运算时间也难以满足需求。因此通过对A*算法的底层框架进行修改，在减少探索节点的同时，通过对探索节点的判别实现动态改航路径规划。

在一次完整的飞行过程中，不考虑备降场的情况下，出发点和目的地是固定的。Breshenham算法的原理就是通过判断起讫点连线的斜率来确定前进的方向。假设以空间环境左下角为坐标原点，将空间转化为栅格元素，坐标原点(0，0)，目标点(x，y)，由起讫点连线得到的一次方程可以表示为

(1)

以轴向右纵轴向上为正向，xi元素每次移动一个栅格。

以d1、d2分别表示当前位置在上下方向距离两个栅格元素的距离。为了方便理解，图1将线的交点视为质点化的栅格元素。则有

(2)

图1 d1和d2

Bresenham算法在选取前进方向时主要有三种情况：

当D1>D2时，前进方向取(xi+1，yi+1)；当D1

其中：D1、D2的大小关系可以通过计算差值确定

D1-D2=2k(xi+1)-2yi+2b-1

(3)

Δx(D1-D2)=2Δy(xi+1)-Δx·2yi+Δx·(2b-1)

(4)

因Δx不存在小于0的情况，令Pi=Δx(D1-D2)，则判断D1和D2的关系如下：Pi≥0时，D1≥D2，取(xi+1，yi+1)为前进方向；Pi<0时，D1

3 改进算法

3.1 无障碍节点模型

对传统的A*算法来说，OPEN表和CLOSED表分别代表了环境空间内还未到达探索过的节点和已经访问探索过的节点，通过不断的减少OPEN表中的节点并将其合适的节点添加到CLOSED表中达到以节点连成路径的目的。

算法公式可以表示为

Fn=gn+h(n)

(5)

F(n)是从出发点到n点的总代价，g(n)是在运行环境中从出发点到n点的实际代价，h(n)是从n点到目标点的最佳路径的估计代价。其主要判断的是当前位置与目标之间的距离D，也就是h(n)的大小。A*算法会在探索当前位置周围全部节点的情况下选择Dmin作为当前位置的最优节点，并重复这一过程，也就是不断更新使

h(n)=h(Dmin)

(6)

F(n)=F(Dmin)

(7)

但是因为这一过程需要对每一个当前节点的周围节点都进行探索，如果不根据改航的实际情况对算法的搜索方向进行限制，可能会出现偏离终点方向的探索，这类探索在航空器的改航中是没有意义的运算，会导致算法运算时间过长、运算效率低下。针对这一点用Bresenham算法对底层结构做出调整，依据是在飞机的实际飞行路线中在当前位置能够探索的节点数是有限的，需要在符合飞机性能的条件下筛选符合条件的节点进行运算，从而减小问题的规模。

Bresenham算法对A*算法的改进可以通过如下举例说明：假设起点在环境空间偏左下的位置，终点在环境空间偏右上的位置，那么为了使从起点到终点走过的总距离尽量短，很明显的是总体移动方向会向右和向上(假设在栅格化的环境空间中不允许直接斜向移动)，也就是起点的前进选择方向是存在限制的，并不是全部的八个方向，而是最多只能从中选择五方向前进，如图2所示。

图2 五方向前进

先定义这五个方向与当前位置的坐标夹角为表示该步长的方向矢量，用SL·cosθ表示，若物体当前位置已经移动到与终点同水平或同垂直边界上，则当前位置的选择方向继续减少。在前进路径上没有障碍阻挡时，各方向步长相同，则当前位置到达周围的栅格可以表示为

(8)

以当前位置正上为0°顺时针计算角度，与空中导航原则保持一致。这样定义的原因是斜向前进每次需要两个步长才能够到达，而直向移动仅需要一个步长就可以到达。与此同时，如果在直向移动一次后发现相对上一步来说斜向移动才是最优路径的话，二者最终在步长上会体现出等同的数量，不会因为方向问题而导致结果不准确。而如果斜向移动两个步长的方向与指向终点的方向相反，则判定该次移动属于冗余移动，需要两个步长回到原位置后再继续。这样带有矢量的方向选择会在一定程度上减少无意义的探索运算，对提升效率、减少运算时间有很大帮助。

在横轴方向上移动的长度表示为dx-nx,在纵轴方向上移动的长度表示为dy-ny，调用Matlab的abs(x)函数，用以表示移动的绝对距离。此时算法函数可以表示为

F(n)=g(SL×cosθ)+h(abs(dx-nx)+abs(dy-ny))

(9)

3.2 有障碍节点模型

本文提出的改进算法核心思路就是在碰到障碍或飞行受限区时，分别从该位置分为左右两支紧贴障碍或受限区边缘前进，直到完全绕过障碍或受限区继续前进或者两条分支分别按既定原则继续前进，最终到达目的地为止，因此称为绕爬算法。

如图3中所示，当前位置在左下角，黑色区域的两个节点是小尺度雷暴云团区域，也就是障碍节点。飞机需要从其两侧绕飞，也就是蓝色箭头1和2代表的路线。当右侧和右上均有障碍节点(黑色区域)阻挡无法探索时，能够继续探索的节点相对当前位置来说只剩三个方向(浅蓝色箭头所指方向)，深蓝色箭头代表了紧贴障碍节点的绕爬节点，1和2分别代表从遇到节点开始向左向右的两个绕爬分支。

图3 有障碍节点的前进

如果两个绕爬分支绕过障碍节点后汇合，定义为完全绕爬的情况。还有一种情况是两个绕爬分支没有任何在一个节点汇合，分别独立继续探索，这种定义为非完全绕爬。针对两种不同的情况，在算法步骤中给出两种解决办法，保证探索过程继续顺利进行。

4 算法设计

在进行算法实际编程前，对一些概念和方式进行梳理和补充：

A)自由节点：在整个路径规划过程中，从当前位置向前探索的、不受障碍覆盖的地图栅格被标记为自由节点，起始探索节点就是最初的自由节点，同时也是原点。

这一概念相当于A*算法中的开放节点。相对而言，不是自由节点的称之为障碍节点或边界节点，也就是本文所讨论的被强对流天气覆盖的需要飞机绕飞的区域(下文将障碍节点和边界节点视为同一种节点不再详细区分)；

B)自由探索：物体一直朝向终点前进的情况下，如果下一步至少存在一个栅格不是障碍节点，也就是可以从当前位置继续向前能够正常进入下一个自由节点探索，这个过程称之为自由探索；该过程等价于基于性能的导航方式下的实际飞行过程。

C)绕爬节点：在物体朝向终点前进的情况下，如果当前位置的前进方向上下一个栅格是障碍节点，则尝试绕过障碍节点，遵循先右后左原则继续探索，绕爬过程中所有自由节点均标记为绕爬节点，直到绕爬过程结束。在实际飞行过程中如果前方航线上存在雷暴云团，分别从左右两侧对路径进行探索再决定绕飞方向。

4.1 算法技术路线图

算法从起点开始，先将起点栅格作为当前节点对下一前进方向的栅格进行判断：如果是障碍节点，选择否。然后以障碍节点为边界，从当前节点位置分出左右分支继续运行，原则为先右后左原则，也就是将向左的分支先挂起到程序后台，首先运行向右分支的判断，用循环语句重复对下一前进方向栅格的判断过程，直到向右分支恢复为自由节点。然后运行向左分支的判断，仍然使用循环语句进行判断，直到向左分支也恢复为自由节点或完成完全绕爬过程。若两个分支汇合，则完全绕爬过程结束，重新重复整个过程，直到到达终点；若两个分支未汇合，则两个分支分别继续探索，重复整个运算过程，直到到达边界或终点结束。

图4 技术路线

算法的具体步骤如下：

1)开始，将起点标记为最初的自由节点，从当前位置出发向终点进行探索；

2)在向终点探索的过程中判断下一格栅格是否为自由节点，

2.1)下一栅格是自由节点，正常前进，步长为一步，将该点标记为自由节点，继续；

2.2)下一栅格不是自由节点，以下一栅格为障碍节点，从该点向左右分出两个绕爬分支，将两个分支的起始探索节点标记为自由节点，再次进行判断，分别尝试绕过障碍节点。

2.2.1)若可以继续探索，将这两个起始探索节点标记为两个绕爬的探索节点；

2.2.2)若不能继续探索，返回上一自由节点；

2.3)若某一绕爬探索节点出现五方向前进均不是自由节点的情况，返回绕爬探索节点的上一个自由节点并暂停，另一绕爬分支继续探索，若该分支也出现同样情况，则继续上一自由节点的探索并将本次探索节点全部标记为障碍节点。

3)两个绕爬分支绕过障碍后可能出现交汇的情况，称为完全绕爬成功，绕过障碍后，选择探索节点更少的分支为合理路径，从汇合点又成为自由节点继续向前；

4)判断两个绕爬分支的长度，当一个分支A先于另一分支B遇到下一个障碍时，A分支分为A1分支和A2分支继续寻路，B分支继续寻路，直到分支汇合或再遇到障碍继续分支，直到某分支到达目标，同时停止所有分支寻路；

5)自由探索的同时也需要判断下一栅格是否为终点，若是，则寻路成功，结束探索过程，选择探索过的节点构成完整路径；若不是，返回步骤2，重复步骤2-5，直到条件“是”达成；

6)到达目标各自后检查路径能否继续优化：在每一次遇到的障碍节点的分支处与下一个分支处重复寻路过程，若移动更短，则用新的路径替代原有路径，若相同，则停止。

4.2 算法仿真

使用Windows10系统的C++语言对绕爬算法按步骤编写语句并进行仿真，如图5所示，算法运行的空间环境边界设置为32×32，其有效空间环境为30×30的正方形区域。选取起点坐标(3，3)，用左下角绿色方块表示；终点坐标(29，22)，用右上角红色方块表示。左侧及下方黑色方块代表空间环境的左下边界，在整个空间环境中设置7处障碍区域，用来代表飞机在飞行过程中可能遇到的雷暴或其它强对流天气障碍。如图5中黑色长条方块区域所示。对算法运行结果计数，分别表示当前分支的路径长度，黄色分支被标记为最优路径作为运算结果。

为体现绕爬算法的有效性，另外使用同一计算机下的Matlab软件对相同条件下的A*算法进行仿真，如图6所示。其中红色点代表空间环境的边界和障碍区域，绿色代表探索过但是并不是最优路径的节点。

对比两种算法所运行的过程和结果如下。

图5 绕爬算法运行结果

图6 A*算法运行结果

两种算法的步长和可探索空间总节点如表1所示。

表1 算法结果对比

5 总结

在给定仿真环境中，绕爬算法和A*算法的仿真结果对比可以很明显的看出：1.A*算法空间环境共900格节点，除去障碍节点71格，完成路径规划共需探索808格节点；2.绕爬算法空间环境及障碍节点数同上，但完成路径规划仅需探索175格节点。3.虽然算法的仿真环境相较于实际情况可能复杂度更高，但算法效率的高下十分清楚，并且从图中可以看出绕爬算法对障碍具有良好的贴边绕障能力，对航路危险天气绕飞有实际意义。4.随着不同运行环境下仿真次数的增加，可以得出的结论为，环境空间越大，绕爬算法相对于A*算法的效率优势就越明显；障碍物越多，虽然A*算法自身效果会越来越好，但是其效率仍然远远不及绕爬算法。

近年来许多对A*算法的改进都停留在减少全向搜索节点数量方面，但是在一个固定的环境空间中，对所有栅格进行独立探索是十分浪费的，随着环境空间的增大，运算次数会较大幅度增加。本文针对这一点先对底层结构中的节点筛选，判断栅格是否可以被选作当前节点的下一步，然后再从这些节点判断有哪些是应该被选择的路径规划节点。这样大大减少了需要进行判别运算的节点，提高算法效率。但是绕爬算法仍然存在一些问题：比如完全绕爬与bresenham算法在优先级上的顺序会影响路径规划的结果，两者的优先级应根据不同情况实际判断，未来深入研究的重点在于如何对运算结果分析并优化。