RF航段自动路径规划研究

任思潜，吴娟

（中国民用航空飞行学院飞行技术学院，广汉618307）

0 引言

现国内一些机场地形复杂且障碍物分布较为特殊，例如林芝、深圳等机场。在进行飞行程序设计时较为困难，为了满足规章规定的越障需求，躲避障碍物，提高航空器的运行能力及飞行安全，往往会尝试采用RF航段。RF航段是以某一个定位点（Fix）作为圆心，以固定转弯半径从一个定位点沿弧径飞至另一个定位点。

目前，在飞行程序设计中，RF航段的设计均是通过人工筛选完成，但对于复杂地形机场，需要考虑地形和障碍物限制、航段保护区限制及航空器性能限制等众多条件才能够完成。这些诸多的限制条件给程序设计人员带来了非常大地工作量。随着路径规划算法的广泛应用，将其应用于RF航段自动路径规划的研究中，用计算机代替人工筛选与设计，可以在更大地、更复杂地搜索空间内，使用更加多地约束条件，快速地确定一条最优的RF航段。迄今为止，在我国，有关路径规划的研究较为丰富，但均是针对于无人机避障路径规划、无人机航迹规划以及机器人路径规划等相关文章。李燕、季建楠等[1]提出一种自适应变化信息素总量的方式，对蚁群算法进行改进，在复杂环境下研究了移动机器人的路径规划问题。岳高峰、昱衡等[2-3]在综合考虑路程与时间开销花费情形下，经过改进A*算法的代价函数，提出了一种基于改进A*的全局路径规划算法，分别对机器人移动和采矿车的最优路线规划进行了分析、讨论。李晓辉等[4]在传统A*算法的基础上，考虑了多种类型的禁飞区，对原有的A*算法进行改进，研究了在任意两个客户点之间如何规划搜索出一条最优的无人机避障飞行路径。赵睿、楼佩煌等[5]针对现有的遗传算法收敛速度较慢等缺点，通过加入基于时间窗的调整策略方法，对AGV集结路径进行了研究。然而，关于RF航段自动路径规划研究几乎没有。

本文采用一种余弦相似度法，结合点云图像处理算法对地形障碍物特征信息进行提取，通过三次样条插值方法对地形进行拟合。其次，根据RF航段特征，建立RF航段飞行曲线模型。考虑RF航段的保护区限制及规章规定越障标准等限制要求，采用改进的A*算法寻找从一个定位点到另一个定位点之间搜寻出一条飞行路径最短的RF航段。最后，为进一步验证改进A*算法的性能，选取A*算法和遗传算法，进行对比分析。结果表明，在搜寻时间与航段路径长度两方面，改进A*算法在性能上都优于A*算法和遗传算法；在内存占用率方面，改进A*算法明显优于A*算法。

1 RF航段自动规划建模

1.1 障碍物特征提取

为了能够在复杂地形条件下找出一条符合实际的RF航段，需要从被搜索空间的地形中获取地形信息及障碍物信息，如图1所示。研究考虑采用余弦相似度法进行障碍物特征信息提取[6-7]，提取的障碍物信息如下：

式中，(Xi,Yi)则为第i个障碍物的中心坐标；Zi是障碍物参数，表示其高度；i表示障碍物的数量。

图1障碍物特征信息提取

1.2 路径规划约束条件

根据飞行设计要求规定[8]，进行RF航段自动路径规划需考虑最短航段长度、航迹角改变大小、航段保护区宽度、被搜索空间地形高及转弯半径等约束条件。

式（2）中，dmin为最短RF航段长度；θ2和θ1分别为航段起始、终点的航迹角；α为预定航迹所需要的最大坡度；V1为航空器在转弯最高点的最大转弯空速；V2为在转弯最高点中的最大风速；L为保护区半宽距离，Q+Rmin在保护区内满足最低的越障碍要求；H为障碍物标高，其值加上0.75海里不能大于航路点之前航段的超障高hOCA与航路点之前航段的主区超障余度hMOC之间的差值。

1.3 建立RF航段数学模型

根据RF航段的特征，列出RF航段飞行曲线模型的参数方程：

2 自动路径规划算法

2.1 传统A＊算法

A*算法，全称A-Star，一种启发式搜索算法，是求解静态路网中最短路径的一种最直接有效的搜索方法。它在搜索过程中，其搜索方向是通过一个评价函数来确定的，向着终点开始搜寻。它是将已知的迭代步数及从初始状态或者当前状态到目标状态的费用信息作为评价量度，计算每一个节点的开销值，并将其添加到一个open_set集合中，选取开销最小的相邻节点作为下一个延伸节点，直至目标节点添加到该open_set集合中。然后通过回溯关系找到满足约束条件的最优解。利用A*算法进行RF航段自动路径规划时，在考虑地形障碍物限制条件和最少迭代步数条件下，尽可能地找出每一个最佳状态，根据每个最佳状态确定最终规划得到的最优RF航段。

航空器在复杂地形区域进行路径规划时，除障碍物与障碍物边缘以外的区域都可看作是可行搜索空间。

航空器从航段起始点start搜寻至航段的终点end的过程中，引入当前节点i的评价函数f*(i)=g(i)+h*(i)，这里g(i)表示从起始点至当前节点i所消耗的实际费用，h*(i)则表示从节点i至终点所消耗的实际费用大小的估计，且其必须小于节点i到终点的实际最小费用，其中g(i)和h*(i)选取曼哈顿距离来度量消耗的费用大小。规划算法主要步骤：

（1）定义两个列表集合open_set=set（）、closed_set=set（），其中open_set集合用于存储已经遍历过的节点，未被尚未遍历的节点则存储进closed_set集合。

（2）从open_set集合中选取出开销费用最小的节点，并将其添加进closed_set集合，同时再将与该添加节点周围相邻的节点也一起加入至closed_set集合中。

（3）在步骤（2）完成后，更新open_set集合中起始节点至每一个节点之间的开销花费，以及每一个节点至目标点的开销花费。

（4）判断目标点是否被添加至open_set集合，如果被添加，则完成搜寻。反之，则重复步骤（2）和步骤（3），直至目标点被添加进open_set集合，算法结束。

2.2 算法改进

针对传统A*算法在搜寻过程中存在计算量大、效率低、内存空间耗费严重以及搜索路径不唯一等缺陷，考虑通过改进评价函数计算方式并结合动态多路径规划算法对传统的A*算法进行改进。

（1）评价函数的改进方式。评价函数作为A*搜索算法中很重要的一个函数，其对算法的效率优化起着重大作用。针对原有算法计算量大、效率低的情况，通过改进评价函数优化程序运行效率。传统的A*算法通常采用的是曼哈顿距离或者欧氏距离作为度量标准，然而由于事先定义航空器的运动方向为8个方向，从而导致规划得到的路径不满足曼哈顿距离或欧氏距离计算结果。考虑通过引入一个协方差矩阵S，将原有的欧氏距离进行变换：

式中，i、j均是属于1至n的正整数；向量xi为向量xj对应的均值。

因此，改进后的评价函数为：

式（7）中，C表示在搜寻过程中每移动一小方格的路径开销。

（2）动态多路径规划策略下的改进。针对传统A*算法在搜寻过程中存在搜寻路径不唯一的情形，考虑在A*算法中融合动态多路径规划策略，它是在算法中通过引入重复路径惩罚因子，然后对在搜寻到的航段起点start和目标点end之后得到多条路径通行代价与目标路径相似度之间取得相对最优的动态优化路径。其算法的主要思想为：首先利用上一节的自动路径规划算法搜索出n条可行路径，再将n条路径上每一个节点的通行代价都乘以一个惩罚因子，然后分别将n条路径相似度与目标路径的相似度进行对比，取相似比最接近于1的那条路径即为最优动态路径。相似度计算公式如下：

图2动态多路径规划策略下改进流程

2.3 路径平滑处理

利用Python根据改进后A*算法搜寻得到路径，由于在某些点处出现了较大的曲折，考虑利用佛洛依德法[9]对拟合得到的航段路径进行平滑处理，使得处理后的航段路径满足要求。

3 仿真验证及结果分析

以深圳机场RWY34的一条进场程序为例，RF航段起始点为SZ951，终点为SZ950，圆心为RSZ45，圆心角取30°，转弯半径为2.1 NM，航空器垂直下降率通常取300 ft/min，在地形障碍物约束下进行路径自动搜寻。图3为考虑地形障碍物后，按限制要求搜索产生的一条RF航段。

图3改进A*算法规划得到RF航段

为进一步验证改进后算法的可行性，分别对A*算法、改进A*算法和遗传算法进行仿真分析。结果如表1所示。

表1改进的A*算法性能对比分析

结果表明，在搜寻花费时间方面，改进的A*算法相对于遗传算法减少了20.54 s，相对A*算法减少了6.17 s；在航段长度方面，改进的A*算法与遗传算法搜寻获得结果相比遗传算法减少了0.06 NM，相比A*算法更是减少了0.25 NM；在最优开销代价方面，改进A*算法虽然明显优于A*算法，但是相比遗传算法增加了6%的开销。

4 结语

以深圳机场为研究对象，其仿真结果表明，在满足RF航段限制条件及规章规定的越障要求的情况下，改进A*算法实现了从起始定位点至目标定位点之间RF航段路径自动规划，将其与现有的RF航段作对比，结果大致相同，验证所设计RF航段飞行曲线模型及自动路径规划算法的可行性与合理性。

在实际RF航段的设计与规划过程中，应用改进的自动路径规划算法，在满足航段设计约束情形下，能够快速地规划出一条RF航段，减小了设计人员的工作量，提高了设计效率。