基于稀疏A*与人工势场算法的EOSID路径规划

2024-05-20杨军利李阿丹李立坤

现代计算机 2024年5期

杨军利，李阿丹，2*，程颖，李立坤

（1. 中国民用航空飞行学院飞行技术学院，广汉 618300；2. 中国东方航空武汉有限责任公司，武汉 430000；3. 中国商用飞机有限责任公司，上海 200000）

0 引言

随着我国民航业的快速发展，行业规模不断扩大，通航机场特别是高原和复杂机场不断增多。截止2022年，我国境内运输机场（不含港澳台）达到了254 个，其中高原机场43 个。从安全与效益的角度，民航业对于制作EOSID 的需求日益增加。

早期的研究侧重于EOSID 设计与性能分析［1-3］，起飞一发失效路径由制作人员根据经验手工完成，工作量很大。为提高EOSID 的制作效率，需结合机场的数字地形实现路径的自动规划。路径规划算法分为数学规划方法、基于图形学的方法如Dijkstra 路径搜索算法、A*算法和随机路标图（PRM）算法等，智能优化算法如蜜獾算法、狮群算法等，以及一些融合算法。刘晓民［4］基于高精度数字地图，利用PRM 和Dijkstra 算法结合飞机性能软件生成了满足起飞性能要求的EOSID 航迹。Masson 等［5］将基于A*算法应用于规划起飞一发失效路径［6-7］；蒋维安等［8］总结了EOSID 总体设计流程，提出了基于A*算法的应急程序路径搜索方法；焦卫东等［9］在考虑了航向角和地形威胁的基础上，利用稀疏A*生成了EOSID 的三维连续航迹。人工势场法［10-13］也是常用于路径规划的方法之一，其局部避障能力较优。文献［14］将稀疏A*搜索算法和改进的人工势场法相结合，应用在不同的障碍物所构成的威胁分布中，规划出了给定威胁指标下的无人机最优路径，结果证明了其具有良好的避障性能。对于地形复杂机场进行一发失效应急程序路径规划，不仅需要着眼于机场附近整体净空条件进行全局规划，还需要关注局部避障能力，尤其在新增障碍物时，才能充分结合民航飞机性能提升业载。

本文旨在采用稀疏A*算法的全局搜索能力融合人工势场法的局部避障能力，结合一发失效规章限制及DEM 数据，快速规划民航飞机一发失效应急程序路径。稀疏A*算法考虑航向角、爬升/下滑角、起始转弯点等约束条件，结合飞机性能的同时缩小搜索空间，缩短算法收敛时间；对于地形复杂的区域融合人工势场法，提升算法的局部避障能力。最后对规划航迹进行平滑处理并在MATLAB 中对规划路径进行验证，实现基于电子地形图的EOSID路径规划。

1 EOSID制作规范

对高原机场及地形复杂机场，在起飞离场和进近复飞中，障碍物是最主要的安全风险。一般飞机的全发性能可满足标准仪表进离场程序的起飞和复飞越障要求。对于一发失效后沿标准离场程序的起飞，由于飞机性能大大降低，可能使得最大起飞重量过小，不能满足航空公司运行经济性要求，这就是制作一发失效应急程序的初衷。2014 年民航局发布了EOSID 制作规范［15］，具体规定了该程序的水平保护区和垂直越障要求。起飞离场保护区如图1所示。

图1 离场保护区

在有航迹引导时，飞机一发失效起飞离场保护区半宽从90 米开始以12.5%梯度扩张至900 米，之后保持900 米直至起飞航迹结束点。与无人机规划仅要求避开障碍物不同，民航飞机需要根据保护区内的障碍物来精确计算飞机起飞性能，对路径规划提出了更高的要求。在总起飞飞行轨迹的基础上，考虑到飞行员的飞行技术误差和飞机性能变化引起上升梯度减小等因素，减去一个梯度后所得到的净起飞垂直飞行轨迹（对于水平加速阶段，加速度要减少当量的数值），起飞减去的梯度值为：0.8%（双发）、0.9%（三发）、1.0%（四发）。净起飞飞行航迹的超障余度为10.7米。

2 路径规划算法

传统A*算法是一种启发式全局路径规划算法，它通过迭代函数进行求解，从起始点向邻节点进行求解，其算法结构直观、易实现、搜索效率较高。稀疏A*算法在计算当前节点到目标点的评估代价时只使用了部分图信息，适用于大规模稀疏图的搜索，这种算法将搜索空间划分为一组子空间。例如，如果在一个大型的室内环境中查找路径，可以将一个房间看作一个子空间，只考虑从一个房间到一个房间的最短路径，而不考虑房间内部的每一个可能的状态，从而大大减少搜索空间的大小，加速查找过程。路径规划所使用的SRTM地形图分辨率为90×90米，属于大规模稀疏图，适用稀疏A*算法。

本文稀疏A*算法结合飞机性能考虑航向角、爬升角、起始转弯点等约束条件缩小搜索空间，缩短算法收敛时间；缺点是当问题规模较大时，时空复杂度很高，易陷入局部最优解或无解。人工势场法是常见的路径规划方法，局部避障能力较优。其基本思想是在障碍物周围构建障碍物斥力势场，在目标点周围构建引力势场，决定斥力势场的因素是飞机与障碍物之间的距离，当飞机未进入障碍物的影响范围时，其受到的势能值为零；当飞机进入障碍物的影响范围后，两者之间的距离越小、障碍物越高，飞机受到的势能值就越大；反之则越小。

2.1 算法流程

采用稀疏A*和人工势场算法进行EOSID路径规划，数据源为SRTM（shuttle radar topography mission）的DEM 数据，算法流程如图2 所示。EOSID路径规划分多个航段进行规划时，应结合起飞性能四个阶段性能参数，每段航迹采取相同路径规划方法完成，本文分两段完成路径规划。

图2 EOSID路径规划流程图

2.2 规划空间处理

根据机场地形情况进行初步分类，受机场周围地形条件的差异影响，选择不同的梯度对地形数据进行筛选处理，构造三维搜索空间。如图3 所示，超过锥形面的区域被视为不可通过，反之则为可通过区域。此外，通过腐蚀算法，将与不可通过区域相邻的区域进行裁剪，缩小可通过区域空间，避免规划的起飞一发失效路径保护区引入地形较高障碍物。

图3 搜索空间

2.3 航迹约束条件

首先，根据各大机场公布的机场信息、标准仪表离场程序（SID），确定航迹规划起始点、起始航迹走向。航迹规划过程中，主要的约束条件为：最大转弯角ϕmax、最大爬升角θmax、最大/小航迹段长度LmaxLmin等。其中转弯角、爬升角最大/最小航迹长度均不能超限。飞机改变飞行姿态前必须保持直飞的最短距离由飞机机动能力和导航要求决定，视为最小航迹段长度；最大航迹段长度可根据需要进行调整，通常最大航迹长度都不是民航飞机起飞一发失效路径规划的限制因素。

2.4 航迹点代价函数

算法航迹点代价函数为

式中：F(n)为起始点经由节点n到目标点的评估代价；G(n)为起始点到节点n的实际代价；H(n)为节点n到目标点最优路径的评估代价。H(n)有各种不同的定义方式，常用的启发距离有欧几里得距离、曼哈顿距离、切比雪夫距离等。综合考虑应用场景后，本式中使用的是欧几里得距离，即直线距离。其中：

式（2）中：N为航迹总段数，w1为航迹长度权重因子，w2为人工势场斥力权重因子，w3为路径地形高度权重因子。li为第i段航迹的长度，ri为估值函数中引入的人工势场法斥力因子，h为规划节点的地形高度。评估函数中引入规划路径地形高度在于规划路径不仅要避开高大障碍物，更要在可运行空间内选择地形相对平坦的区域运行。

式（5）中ρ0为一常数，表示障碍物对飞机产生作用的最大影响范围。ρ(q,qi)为飞机到第i个障碍物的距离。

稀疏A*算法在求解最优路径过程中，依靠启发函数对扩展节点进行选取，受地形复杂、搜索空间削减等影响，容易陷入局部无解。通过加入人工势场斥力因子避开障碍物，提升稀疏A*算法的鲁棒性。此外，评估函数中增加考虑各待扩展节点高度数值项，在不同净空条件的机场调整其在评估函数中的权重，从而不仅仅规避障碍物，还选择最有利的地形来产生最优飞机性能数据。

2.5 稀疏A*与人工势场法搜索

从当前节点，在航向角限制范围内均匀选取M个扇面，由爬升角确定每个扇面的区域范围，根据爬升角限制范围，将扇面均匀分为N个扇区，从而构成结合飞机性能的起飞、爬升转弯的三维搜索方向，共得到M×N个扇区，及M×N个子节点。如M=N= 3，则由传统算法的26 个子节点削减为9 个，有效缩小了搜索空间，提升算法运行效率。将每次代价函数计算得到代价最小的点保存于CLOSED 列表内，直至目标点，进行回溯后即可获得一条完整的EOSID规划航径。

具体步骤如下：

（1）将起始节点插入OPEN 表内，置空CLOSED表；

（2）将OPEN 表中最小代价点存进CLOSED表，同时将其置于当前节点；

（3）如果目标点加入CLOSED 表则搜索结束，得到一条从起始节点到目标节点代价最小的路径；

（4）扩展当前节点。将进入当前节点的航线在水平面上投影方向作为对称轴，水平扩展区是最大转弯角的两倍。待扩展区垂直剖面水平方向对称，亦为最大爬升角的两倍，将可用节点加入到OPEN列表中；

（5）将上一步计算得到的每一个最小代价节点与OPEN表中的节点进行对比，如果代价值更小，则更新该节点代价相关参数值；如果该节点在CLOSED表中则忽略；

（6）输出规划结果。

3 算例与分析

3.1 计算条件

某机场位于西藏东南部，雅鲁藏布江的河谷地带。机场场区较为平坦，但两侧山体较高，净空条件比较复杂。以该机场05 号跑道离场程序为例，采用稀疏A*与人工势场算法进行路径规划，数据源为SRTM 90×90 米数字地形高程模型；离场航迹起始点位于05 跑道末端，经纬度坐标（N29°18'，E094°20'），标高2947 米，终点经纬度（N29°39'，E094°21'），最大拐弯角和最大爬升角分别为45°和30°；最小步长90 米，扇面个数3，扇区个数3。