融合动态风险图和改进A*算法的动态改航规划

李海 郭水林 周晔

摘要：结合机载气象雷达探测信息，本文提出了一种融合动态风险图和改进A^*算法的动态改航规划方法。该方法首先利用机载气象雷达的探测结果，将其进行离散化处理，建立一个定期更新的动态风险图，以此作为算法的仿真环境；然后，综合考虑了航迹长度、航迹偏离度和管制约束等因素来构造算法的代价函数，基于该代价函数进行航迹规划。同时，对A^*算法的搜索方式进行了改进，并对规划后的航迹进行了平滑优化处理；最后，提出两种不同策略进行了仿真分析试验，试验结果验证了所提方法的有效性，并且适用于动态改航规划。

关键词：机载气象雷达；风险图；A^*算法；航迹平滑；动态改航

中图分类号：V355文献标识码：ADOI：10.19452/j.issn1007-5453.2021.05.009

目前，國内外在航迹规划方面的研究主要分为飞行前航迹规划和实时航迹规划[1]。参考文献[2]、参考文献[3]运用传统规划算法对飞行航迹进行规划，为解决传统算法易陷入局部最优的问题，对算法进行了改进，但是规划后的航迹不够平滑。参考文献[4]～参考文献[6]采用智能仿生学算法进行航迹规划，此类算法具有容易实现、鲁棒性强等优势，但算法的计算量大，而且无法保证所规划的航迹是全局最优的航迹。参考文献[7]、参考文献[8]结合了图形学的规划方法，规划过程直观，而且能够兼顾规划时间和航迹质量，但算法复杂度随着危险区域增多时提升，因此不适用于复杂的危险气象场景。A^*算法[9-10]作为一种启发式搜索算法，在应用于复杂的气象环境场景下时，可能会出现搜索陷入死循环无法跳出，以及规划后的航迹不够平滑。

综上所述，目前关于航迹规划的研究大多数都没有利用机载气象雷达的探测信息，在这种情况下，规划的航迹就容易产生冗余的绕飞距离，导致无谓的航油消耗。机载气象雷达作为民航飞机的“双眼”，能够实时探测飞行航路前方的危险气象，为飞行员绕飞策略的制定提供了最直接的先验信息。现行的机载气象雷达采用的是单极化雷达，单极化雷达发射时发射垂直或水平单一极化信号，接收时接收同一单一极化的雷达回波信号，目标在单极化雷达照射下只受垂直或水平单一极化电磁波激励。因此，单极化雷达仅能通过雷达反射率对降水目标的含水量予以检测，并用不同的颜色来表示不同的降水等级，并不具备降水粒子区分的功能[11]。而作为下一代的机载气象雷达——双极化雷达，能够同时接收目标雷达回波信号的同极化和交叉极化分量。因此，双极化雷达能够对降雨粒子进行精确的分类[12]，揭示各种降水系统中小雨滴、大雨滴、霰、冰雹、雪花、冰晶等多种水凝物粒子的分布，为飞行员绕飞策略的制定提供了更加精确的先验信息。

本文利用机载气象雷达的探测结果，并结合改进A^*算法，提出了一种融合动态风险图和改进A^*算法的动态改航规划方法。首先，在改航约束条件下，根据机载气象雷达的探测结果对空域进行离散化处理，建立一个飞行区域初始化风险图，并利用实时得到的机载气象雷达的探测结果对初始化风险图进行定期更新，得到一个动态风险图，以此作为改进A^*算法的搜索环境。然后，对传统A^*算法的代价函数和搜索方式（即航迹规划）进行了改进，并增加了航迹平滑优化处理。最后，从航油消耗、经济环保、空域利用率等角度考虑，对雷达回波强度小于41dBZ的危险区域提出了保守策略和非保守策略[13]的两种不同规避策略，并设计了本文方法与A^*算法、蚁群算法、遗传算法和人工势场算法[14]，以及与基于改进人工势场法的动态改航规划[2]、基于改进多目标粒子群算法的航空器改航研究[4]、利用自适应扩展节点的A^*算法对改航路径规划进行求解[15]的对比仿真试验。试验结果表明，本文方法规划的航迹能够安全有效地规避危险气象，并且优于A^*算法、蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进对目标粒子群算法和自适应扩展节点的A^*算法。

1整体框架

融合动态风险图和改进A^*算法的动态改航规划方法主要由两部分组成：动态风险图和改进A^*算法。首先，根据机载气象雷达的探测结果对空域进行离散化处理得到一个风险矩阵，根据风险矩阵建立一个飞行区域初始化风险图，并利用实时得到的机载气象雷达探测结果对初始化风险图进行定期更新，得到一个动态风险图，以此作为改进A^*算法的搜索环境。然后，对传统A^*算法的代价函数和搜索方式进行改进，并对规划后的航迹进行了平滑优化处理。改进A^*算法分为代价函数设计、航迹规划和航迹平滑优化三部分。所提方法的整体框架如图1所示。

在图1中，本文中设定风险图的定期更新时间为5min[16]，每隔5min利用改进A^*算法对动态风险图进行航迹规划。

2动态风险图

机载气象雷达的最大探测距离是600km，运输航空完成一次转弯至少需要7.4km[1]。因此，将机载气象雷达的探测结果进行离散化处理，针对不同的危险气象类型进行数字化风险评估[17]，数字化风险评估表见表1。为简化模型，并保证航空器能在一个单元格内顺利执行一次转弯，选取距离为15km作为一个单元格的边长，则可以得到一个M×N的探测结果矩阵，其中M=40，N=40。为简单起见，本文只考虑航空器的巡航阶段，因为对于起飞和进近阶段也可以进行类似的考虑。

假设某一时刻得到的机载气象雷达的探测结果经过离散化处理后得到的探测结果矩阵见表2。

利用表1的数字化风险评估表并结合雷达探测的回波强度，对表2的机载气象雷达探测结果矩阵进行数字化风险评估，并进行归一化处理，得到一个M×N的风险矩阵，见表3，表中的不同数值表示不同危险气象类型的数字化评估结果。

（3）危险区域限制

通常情况对于航空器来说，当雷达回波强度大于等于41dBZ的危险区域，不允许航空器穿越飞行，必须采取规避策略。

（4）改航點数量限制

为减少导航误差，避免过度增加飞行员和管制员在实施改航过程中的工作负荷，航空器在远距离飞行时一般不希望迂回行进和频繁的转弯，改航点数量每100km应不多于1个。

（5）危险系数设置

在规避危险气象的过程中，根据选择策略[20]的不同可设置相应的规避危险系数T（0≤T≤1）。在保守策略下，设置的危险系数T=0；在非保守策略下可设置不同的危险系数T，需要注意的是设置的T越大，则规避的危险系数越高。

3.2.2正向扩展式搜索

首先，初始化截距d=3，并将飞行区域I内风险系数Fx，y> T的单元格点设置为非可行单元格点（路障点）。其次，通过代价函数在A（3）内进行搜索，当搜索陷入死区（被路障点包围，算法无法自动跳出的区域）时，则基于当前单元格点，在其相邻单元格点中随机选取未被遍历的可行单元格点继续搜索。此时，当搜索到达改航终点时，则停止搜索，输出搜索得到的单元格点集合；否则，判定A（3）内无法通行。然后，增大d值，基于A（3）约束边界上被遍历过的单元格点，随机选择其在A（6）内的相邻可行单元格点继续搜索（搜索区域包含A（6）和A（3））。此时，如果没有搜索到达改航终点，则继续增大d值，基于A（6）约束边界上被遍历过的单元格点，随机选择其在A（9）内的相邻可行单元格点继续搜索，并依此类推，直到A（3n）搜索到达改航终点为止。在增大d值进行搜索的过程中，如果d > N时还没有搜索到达改航终点，则判定该飞行区域在当前危险系数T值下，航空器无法穿越飞行，搜索结束。对于飞行区域II的搜索操作同飞行区域I一样，在此就不再赘述。正向扩展式搜索的具体流程图如图5所示。

正式扩展式搜索结果存在以下三种可能。

情况1：飞行区域I和飞行区域II仅有一个区域能够搜索到达改航终点。此时，选择能够搜索到达改航终点的飞行区域，并获得该区域内搜索得到的单元格点集合。

情况2：飞行区域I和飞行区域II都搜索到达改航终点。此时，根据机载气象雷达的探测结果选择危险气象分布比较稀疏且危险气象的风险系数比较小的飞行区域，并获得该区域内搜索得到的单元格点集合。

情况3：飞行区域I和飞行区域II都没有搜索到达改航终点，则判定当前危险系数T值下航空器无法穿越飞行。此时，飞行员可以考虑在保证飞行安全的情况下，适当增大T值重新进行航迹规划，或者采取其他策略（如就地备降、上升飞行高度、降低飞行高度等）。

3.4算法流程

改进A^*算法的主要步骤如下：（1）利用机载气象雷达的探测结果建立当前飞行区域风险图；（2）根据选择的规避策略，设置不同的危险系数T；（3）将风险图中大于危险系数T的单元格点设置为路障点；（4）在计划航迹两侧进行正向扩展式搜索；（5）利用最小二乘法对正向扩展式搜索得到的单元格点集合进行优化筛选；（6）对优化筛选出来的单元格点进行逆序搜索；（7）航迹平滑优化处理；（8）输出最优的航迹。改进A^*算法的流程图如图7所示。

4仿真分析

对本文方法进行仿真分析。试验1在简单气象环境下，本文方法和A^*算法进行对比仿真分析；试验2在复杂气象环境下，本文方法与蚁群算法、遗传算法、人工势场算法[14]、改进人工势场算法[2]、改进多目标粒子群算法[4]和自适应扩展节点的A^*算法[15]进行对比仿真分析。

试验1：简单气象环境下，模拟仿真试验数据采用本文中建立动态风险图的方法构建模拟仿真环境，利用本文方法进行仿真试验，并与A^*算法进行了对比。图8是在保守策略下，危险系数T=0，两种方法的对比仿真结果图。图9和图10是在非保守策略下，危险系数T=0.2和T=0.4，两种方法的对比仿真结果图。

航程指航空器从改航起点到改航终点所飞行经过的航迹长度，其公式定义如式（12）所示：

表5为非保守策略下，危险系数T=0.2，本文方法与A^*算法关于上述三个评估指标以及算法运行时间的仿真结果对比数据。

表6为非保守策略下，危险系数T=0.4，本文方法与A^*算法关于上述三个评估指标以及算法运行时间的仿真结果对比数据。

通过表4～表6的试验对比数据可知，在保守策略下，本文方法在航程上和算法运行时间上都要优于A^*算法，虽然A^*算法在侧向偏离度上小于本文方法，但是综合比较本文方法还是要优于A^*算法；在非保守策略下，当规避策略采取T=0.2和T=0.4时，本文方法算法在航程、侧向偏离度、风险值和算法运算时间都要小于A^*算法。综上所述，本文方法优于A^*算法。

试验2：复杂气象环境下，模拟仿真试验数据采用图2中的飞行区域风险图，利用本文方法进行仿真试验，但由于A^*搜索陷入“死区”而无法得到搜索航迹。在此，采用了蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进多目标粒子群算法和自适应扩展节点的A^*算法进行了对比仿真试验。图11是在保守策略下，当危险系数T=0的对比仿真结果；图12是在非保守策略下，当危险系数T=0.2的对比仿真结果；图13是在非保守策略下，当危险系数T=0.4的对比仿真结果。

为定量评估本文方法规划的航迹与蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进多目标粒子群算法和自适应扩展节点的A^*算法所规划的航迹的优劣性，同样采用试验1中建立的三个评估参数：航程、侧向偏离度、风险值，以及算法的运行时间进行对比分析。

表7为保守策略下，危险系数T=0，本文方法、蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进多目标粒子群算法和自适应扩展节点的A^*算法关于上述三个评估指标以及算法运行时间的仿真结果对比数据。

表8为非保守策略下，危险系数T=0.2，本文方法、蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进多目标粒子群算法和自适应扩展节点的A^*算法关于上述三个评估指标以及算法运行时间的仿真结果对比数据。

表9为非保守策略下，危险系数T=0.4，本文方法、蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进多目标粒子群算法和自適应扩展节点的A^*算法关于上述三个评估指标以及算法运行时间的仿真结果对比数据。

从表7可知，在保守策略下，本文方法在航程上除了比改进多目标粒子群算法的要大，比其他方法都小。虽然改进多目标粒子群算法的航程要比本文方法的小，但是这不足以弥补本文方法在侧向偏离度和算法运行时间上相对于改进多目标粒子群算法的优势；从表8可知，在非保守策略T=0.2下，本文方法在航程上除了比改进多目标粒子群算法和自适应扩展节点的A^*算法的要大，比其他方法都小。虽然在航程上改进多目标粒子群算法和自适应扩展A^*算法要比本文方法的更好，但是这不足弥补本文方法在侧向偏离度、风险值和算法运行时间上相对于这两种方法的优势；从表9可知，在非保守策略T=0.4下，本文方法在航程上除了比人工势场算法和改进人工势场算法的要大，比其他方法都小。虽然在航程上人工势场算法和改进人工势场算法要比本文方法的小，但是这不足弥补本文方法在侧向偏离度、风险值和算法运行时间上相对于这两种方法的优势。综上所述，本文方法优于蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进多目标粒子群算法和自适应扩展节点的A^*算法。

5结论

本文提出了一种融合风险图和改进A^*算法的动态改航规划方法。首先，利用机载气象雷达的探测结果建立一个飞行区域初始化风险图，并利用实时得到的机载气象雷达的探测结果对初始化风险图进行定期更新得到一个动态风险图，以此作为算法的搜索环境。然后，对传统A^*算法的代价函数和搜索方式进行了改进，并且增加了航迹平滑优化。最后，对改进A^*算法进行仿真试验，并且还采取了保守策略和非保守策略的两种规避策略进行飞行航迹规划，为飞行员安全规避危险气象提供可选择的绕飞策略。同时，在简单气象环境下，设计了本文方法与A^*算法的对比试验；在复杂气象环境下，设计了本文方法与蚁群算法、遗传算法、人工势场算法、改进人工势场算法、改进对目标粒子群算法和自适应扩展节点的A^*算法的对比仿真试验。并设定了三个定量评估指标和算法运行时间来分析试验的仿真结果。研究结果表明，本文方法能够在两种规避策略下安全有效地规避危险气象，并且优于A^*算法、蚁群算法、遗传算法和人工势场算法、改进人工势场算法、改进多目标粒子群算法和自适应扩展节点的A^*算法。

参考文献

[1]李雄.飞行危险天气下的航班改航路径规划研究[D].南京：南京航空航天大学，2009. Li Xiong. Research on flight diversion route planning in dangerous weather[D]. Nanjing ： Nanjing University of Aeronautics andAstronautics， 2009. （in Chinese）

[2]陈可嘉，陈琳琳.基于改进人工势场法的动态改航规划[J].飞行力学，2020，38（5）：84-89. Chen Kejia， Chen Linlin. Dynamic course modification planning based on improved artificial potential field method[J]. Flight Dynamics， 2020，38（5）：84-89.（in Chinese）

[3]李宪强，马戎，张伸，等.蚁群算法的改进设计及在航迹规划中的应用[J].航空学报，2020，41（S2）：213-219. Li Xianqiang， Ma Rong， Zhang Shen， et al. Improved design of ant colony algorithm and its application in route planning[J]. Acta Aeronautica et Astronautica Sinica，2020，41（S2）：213-219.（in Chinese）

[4]杜实，王俊凯，任景瑞.基于改进多目标粒子群算法的航空器改航研究[J].安全与环境学报，2020，20（1）：177-185. Du Shi， Wang Junkai， Ren Jingrui. Research on aircraft diversion based on improved multi-objective particleswarm optimization [J]. Journal of Safety and Environment， 2020，20（1）： 177-185. （in Chinese）

[5]李根，李航，张帅阳，等.基于蚁群算法的最优路径规划及参数研究[J].中国科技论文，2018，13（16）：1909-1914. Li Gen， Li Hang， Zhang Shuaiyang， et al. Research on optimal path planning and parameters based on ant colony algorithm[J]. China Science Paper， 2018， 13 （16）： 1909-1914. （in Chinese）

[6]Norouzi A，Kazemi R，Abbasi O R. Path planning and replanning of lane change maneuvers in dynamic traffic environments[J]. International Journal of Vehicle Autonomous Systems，2019，14（3）：239-264.

[7]徐琳，宋萬强，严冲，等.基于威胁评估和扩展Voronoi图的战术飞行轨迹规划方法[J].航空科学技术，2019，30（1）：35-43. Xu Lin， Song Wanqiang，Yan Chong， et al. Tactical flight path planning method based on threat assessment and extended Voronoi diagram[J]. Aeronautical Science & Technology， 2019， 30（1）：35-43. （in Chinese）

[8]陈雨童，胡明华，杨磊，等.受限航路空域自主航迹规划与冲突管理技术[J].航空学报，2020，41（9）：253-270. Chen Yutong， Hu Minghua，Yang Lei， et al. Autonomous track planning and conflict management technology in restricted air route airspac[J]. Acta Aeronautica et Astronautica Sinica， 2020， 41（9）：253-270. （in Chinese）

[9]Xie L，Xue S，Zhang J，et al. A path planning approach based on multi-direction A^*algorithm for ships navigating within wind farm waters[J]. Ocean Engineering，2019，184（15）：311-322.

[10]刘永琦，徐丹，程归，等.基于改进A～*算法的无人机快速轨迹规划方法[J].飞行力学，2020，38（2）：40-46. Liu Yongqi， Xu Dan， Cheng Gui， et al. Fast trajectory planning method of UAV based on improved A～* algorithm[J]. Flight Dynamics， 2020，38（2）：40-46.（in Chinese）

[11]Zhao C，Zhang Y，Zheng D，et al. An improved hydrometeor identification method for X-band dual-polarization radar and its application for one summer Hailstorm over Northern China[J]. Atmospheric Research，2020，245：105075.

[12]Ma Jianli. Improvement of X-Band polarization radar melting layerrecognition by the bayesian method and its impact on hydrometeorclassification[J].AdvancesinAtmospheric Sciences，2020，37（1）：105-116.

[13]Marconnet D，Norden C，Vidal L.Optimum use of weather radar[J]. Safety First，2016，22：22-43.

[14]徐肖豪，李成功，赵嶷飞，等.基于人工势场算法的改航路径规划[J].交通运输工程学报，2009，9（6）：64-68. Xu Xiaohao， Li Chenggong， Zhao Yifei， et al. Path planning for course change based on artificial potential field algorithm[J]. Journal of Traffic and Transportation Engineering， 2009，9（6）：64-68.（in Chinese）

[15]赵元棣，李瑞东，吴佳馨.动态危险天气下改航路径快速规划方法[J].中国科技论文，2020，15（6）：678-681. Zhao Yuandi， Li Ruidong，Wu Jiaxin. A fast planning method for course change under dynamic dangerous weather[J]. China Science Paper， 2020，15（6）：678-681.（in Chinese）

[16]Chernokulsky A，Shikhov A，Bykov A，et al. Satellite-based study and numerical forecasting of two tornado outbreaks in the Ural Region in June 2017[J]. Atmosphere，2020，11（11）：1146.

[17]Sermi F，Cuccoli F，Mugnai C，et al. Aircraft hazard evaluation for critical weather avoidance[C]// 2015 IEEE Metrology for Aerospace Conference. Benevento，Italy：IEEE，2015：454 - 459.

[18]赵元棣，付云峰，吴佳馨.航空器飞行轨迹表示方法及其应用[J].科学技术与工程，2020，20（12）：5000-5004. Zhao Yuandi， Fu Yunfeng， Wu Jiaxin. Representation of aircraft flight path and its application[J]. Science Technology and Engineering， 2020，20（12）：5000-5004.（in Chinese）

[19]占伟伟，王伟，陈能成，等.一种利用改进A^*算法的无人机航迹规划[J].武汉大学学报（信息科学版），2015，40（3）：315-320. Zhan Weiwei， Wang Wei， Chen Nengcheng， et al. An unmanned aerial vehicle （UAV） path planning using improved A^*algorithm[J]. Geomatics and Information Science of Wuhan University， 2015，40（3）：315-320.（in Chinese）

[20]胡中华，许昕，陈中.无人机三维航迹非均匀三次B样条平滑算法[J].控制工程，2020，27（7）：1259-1266. Hu Zhonghua， Xu Xin， Chen Zhong. Three-dimensional nonuniform B-spline smoothing algorithm for unmanned aerial vehicle[J]. Control Engineering of China， 2020， 27（7）： 1259- 1266.（in Chinese）

（责任编辑皮卫东）

作者简介

李海（1976-）男，博士，教授。主要研究方向：机载气象雷达信号处理、分布式目标检测与参数估计、自适应信号处理、阵列信号处理、动目标检测与参数估计。

Tel：13602155208

E-mail：haili@cauc.edu.cn

郭水林（1996-）男，碩士研究生。主要研究方向：飞行航迹规划。

Tel：16622986909

E-mail：ShuilinGuo@163.com

周晔（1982-）女，硕士，高级工程师。主要研究方向：机载气象雷达系统技术、雷达信号检测及识别等。

Tel：15951585397E-mail：zhouye@chinaleihua.com

Dynamic Diversion Planning Combining Dynamic Risk Map and Improved A^*Algorithm

Li Hai1，*，Guo Shuilin1，Zhou Ye2

1. Tianjin Key Lab for Advanced Signal Processing，Civil Aviation University of China，Tianjin 300300，China 2. AVIC Leihua Electronic Technology Research Institute，Wuxi 214063，China

Abstract： Combining with airborne weather radar detection information， this paper proposes a dynamic diversion planning method which combines dynamic risk map and improved A^*algorithm. Firstly， the detection results of airborne weather radar are discretized to establish a dynamic risk map which is updated regularly， which is used as the simulation environment of the algorithm. Secondly， the cost function of the algorithm is constructed by considering the track length， track deviation and control constraints etc.， the cost function is used for route planning. At the same time， the search method of A^*algorithm is improved， and the planned track is smoothed and optimized. Finally， two different strategies are proposed to carry out simulation analysis experiments. The experimental results verify the effectiveness of the proposed method which is suitable for dynamic diversion planning.

Key Words： airborne weather radar； risk map； A^*algorithm； track smoothing； dynamic diversion