基于SAS算法的直升机应召搜潜航路规划研究∗

李 林 韩 强 黎子芬

（海军航空大学青岛校区 青岛 266041）

1 引言

直升机搜潜方式主要包括应召、巡逻等搜潜方式。相比较而言，应召搜潜是反潜作战、训练中使用最多而且十分重要的战术方式。应召搜潜是指在已经获取了目标潜艇在某一时刻的概略位置或航向、航速等信息的前提下，反潜直升机领受任务后飞抵目标海域，再次对目标进行搜索定位的过程［1］。如何克服应召搜潜飞行航路存在的随机性和盲目性，提高搜索效率是各方关心的问题。本文基于SAS算法对直升机搜潜航路进行仿真计算和规划效率评估，可以为部队反潜训练中制定应召搜潜航路提供参考，在提高搜潜效率方面发挥积极作用。

2 算法分析

应用于飞行器航路规划的算法主要有简单航路规划、A*搜索算法、遗传算法、蚁群算法、电视规划算法以及一些新型的规划算法［2］，但并非所有算法都适用于直升机应召反潜航路规划。经初步筛选，可用于直升机航路规划的算法主要有简单航路规划、遗传算法、蚁群算法、A*搜索算法等。其中，蚁群算法应用于直升机搜潜航路规划本文作者已经进行了研究，这里也不再赘述。

简单航路规划算法适用于飞行航线上障碍物少、威胁程度低、威胁源移动速度慢等简单情况，具有航路简单、速度快的优点，通常用于近海反潜作战，这里不作为主要研究对象。

遗传算法作为一种仿生学技术，因其独特的组织学习适应能力，在许多领域都有出色的表现。但是，在航路规划方面并没有其他启发式路径寻优算法表现的效果好。综合考虑该算法的特性和应用实际，也不作为本文的主要研究对象。

A*搜索算法是启发式搜索算法的一种，是非常优秀的最短路径搜索算法之一［3］。由于A*算法的复杂性以及其搜索的可能种类为无穷，导致解算过程需占用大量的时间和空间。为便于实际应用，将其进行压缩和优化处理，改进为SAS算法，即稀疏A*搜索算法（Sparse A*search，SAS）［4］，适用于直升机搜潜航路规划。

3 SAS算法

3.1 算法描述

SAS算法是Robert J.Barbarize等为了加快A*算法的收敛速度、节省运算空间改进的一种新算法［5］。 A*算 法 的 函 数 表 达 式 为f*(x)=p*g*(x)+q*h*(x)，SAS算法则是将该函数中的系数设置为常数，简化为 f*(x)=g*(x)+h*(x)。该算法的核心是评估函数的设计，在选择当前节点的下一个考察接点i时引入了估价函数，f*(x)表示从节点S0到节点x的一条最佳路径的实际代价加上从节点x到目标节点的一条最佳路径的代价之和，g*(x)就是从节点S0到节点x之间最小代价路径的实际代价，h*(x)则是从x节点到目标节点的最小代价路径上的代价［6］。

SAS算法具有两种优秀的特性，即可采纳性（在可解状态空间里能在有限的时间内终止并找到解）和单调性（通过对h*(x)启发函数以适当单调性限制，可使一系列节点的评估值成一定的单调增或非减特性）［7～8］，可以保证对直升机应召搜潜航路进行高效、最优规划。

3.2 算法流程

路径规划求解是要求全局最优的优先搜索问题，SAS算法流程如图1所示，其搜索算法如下：

1）初始化，把初始节点S0放入OPEN表；

2）寻找该节点周围可到达的点，该点作为这些点的上辈节点；

3）从OPEN列表删除该点，加入CLOSE列表；

4）计算该点 F=G+H（F=f*(x)；G=g*(x)；H=h*(x)）；

5）判断F是否最小，最小则寻找节点成功，把它从OPEN列表删除，加入CLOSE列表；否则，该点不加入CLOSE列表；

6）该点是否为目标点，是则结束；否则跳转到第2）步。

图1 SAS算法流程图

4 约束条件

在对应召搜潜航路进行评价时，首先要构建评价指标，通常要考虑直升机的航程指标、安全指标、飞行时间指标以及综合权重指标等。除此之外，还须考虑到直升机自身的性能特点和所处的战场环境，包括机动性能、最大航程和威胁、战术等方面的约束条件［9］。

4.1 机动性能约束

机动性能约束主要是指由于威胁区的存在，直升机在航路转弯时对飞行方向和高度进行调整时需考虑的最小转弯半径以及最大爬升速度等限制。

1）最小转弯半径

反映了直升机在水平面上转变航向的机动能力，主要考虑的是威胁区影响和目标大角度规避时为及时跟踪搜索而进行的机动。关键航路点的设置应满足：

式中： ||KAKB是两个关键航路点间的距离；θ是转弯角；rmin是最小转弯半径。

2）最大爬升速度

反映了直升机在一定的水平初速情况下在垂直方向上的机动能力。在一定的速度下，在飞跃军舰、海岛等一定高度的障碍时，需对其考虑，以免其发生碰撞。

4.2 最大航程约束

直升机执行应召搜潜任务时需携带一种甚至多种搜潜器材，必要时还要携带攻潜武器，这就限制了所能携带的燃油数量，而且直升机通常还要在目标海域滞留一段时间，上述因素决定了规划的航路必须考虑最大航程的约束，即各航段的总路程之和不能大于最大航程。

对于一条有n个航路点的航路，其最大航程约束可表示为

式中，JC为某条航路的航程指标；Li-1为两个相邻航路点之间的航程；Lmax为燃料消耗指标所允许的最大值。

4.3 威胁约束

威胁约束是动态变化的，是重要的约束条件。常见的威胁源主要包括敌方的防空雷达、防空武器以及战机等［10］。由于在进行航路规划时威胁是必须规避的，可将其归结为不可穿越障碍区，并在仿真中适当予以扩大，防止直升飞机执行搜潜任务时因累积偏差误入威胁区。

假设直升机领受搜潜任务后飞向目标海域过程中的威胁区和禁飞区的集合为RT，航路函数为f(x ，y，t)=0（x，y，t分别表示航路上任意点的经纬度坐标和直升机飞行时间），则威胁约束可以用下式进行描述：

4.4 战术约束

在反潜作战中，目标从被发现到消失的时间通常十分有限，因此要求直升机必须在最短的时间内到达目标海域，这就涉及到战术约束条件［11］。

1）进入搜索区的方位约束

由于目标散布概率模型不同，直升机进入搜索区的方位不同，搜索概率也不同。理想的进入方位是沿着潜艇运动方向进入，即对直升机进入搜索区的方位进行约束。

式中，HS为进入搜索区的预定方向；(Xf，Yf)为直升机最后一个航路点坐标；(Xt，Yt) 为目标被发现的坐标；DH为允许进入方位最大偏差。

2）时间约束

直升机从领受任务至到达搜索区的时间受天气、环境、速度、航路轨迹等诸多因素的约束，在多机、舰机协同作战中的要求更高。为避免给目标更多的逃逸时间，这就要求规划的航路必须合理、高效。

4.5 其它约束

除了上述约束外，还有诸如航空管制区、禁飞区、飞行限制区等需要考虑［12］。为方便仿真计算，可将其简化为威胁区性质的障碍模型处理。

5 仿真验证

直升机在执行应召搜潜任务时，首先要获取目标的概略位置，然后获取战场地图信息、敌我态势信息以及禁飞区等障碍区域信息，最后选择合适的航路规划算法计算出最优航路。

为了适应SAS算法寻找最优路径，可将相关地图信息用方格图的形式进行显示，并适当放大禁飞区范围。战场环境可通过通过加载txt文件矩阵数据来生成，在具体使用过程中同样可以加载获取的实时战场态势信息来进行实时航路规划。

在航路规划时，首先加载禁飞区域信息和相关数据，由飞行员手动选取开始点和目标点（如图2所示）后便可动画显示搜索路径（如图3所示），当搜索到最短路径后自动显示在屏幕上（如图4所示）。

为便于使用，采用北东坐标系进行显示，可以以开始点为参考点，以目标相对我方位置进行显示。飞行员根据图中最短路径（由于已经把其他因素给排除掉了，所以这里所说的最短路径，即最优路径）操纵飞行到达目标点，也可根据战场态势变化，实时规划出最优路径，辅助飞行员进行决策。

采用SAS算法对直升机应召搜潜航路规划进行仿真分析，可以得出如下结果：

图3 输入开始点、目标点后动画显示的搜索路径

1）在地图信息信息不是很大的情况下，运行32*32大的矩阵图进行寻找最优路径，SAS约为46.6个方格距离（如图5所示）。在规划速度方面，整个仿真程序耗时大概在8s左右，其中SAS算法路径规划耗时0.2s左右。

图4 搜索到的最短路径

图5 SAS算法仿真图

2）在地图信息信息进行适当放大以后，运行84*84大的矩阵图进行寻找最优路径，规划出的最优路径约为118.6个方格距离（如图6所示）。在规划速度方面，整个仿真程序耗时24s，其中SAS算法路径规划耗时约2.8s。

图6 SAS算法仿真图

3）为了进一步验证该算法是否符合实际要求，用168*168的地理信息矩阵进行仿真，规划出的最短路径约为233.7个方格距离（如图7所示），最短路径效果指标也比较理想。而且，规划速度也很快，整个仿真程序耗时约88.3s，其中SAS算法路径规划耗时约21.7s。

图7 SAS算法仿真图

6 结语

通过利用SAS算法对直升机应召搜潜航路规划进行仿真计算，结果表明：

1）地图信息量不大时，在获取的最优路径效果相当的情况下，SAS算法与其他算法（如蚁群算法、遗传算法等）相比在运算速度方面基本相当，都能够较好的满足要求。也就是说，在非交战环境下执行搜潜任务或者在交战环境下敌方海上军力一般的情况下，采用SAS算法对直升机应召搜潜航路进行规划是适用的。

2）地图信息量较大时，也就是说执行应召搜潜区域的海况比较复杂或者敌方海上力量比较强大时，SAS算法与其他算法（如蚁群算法、遗传算法等）相比在运算速度和航路规划效果上表现出明显优势，能够较好地满足作战、训练的需求。

因此，直升机在执行应召搜潜航路规划时，无论地图信息量大小选择SAS算法都能比其他算法更好满足实际需求，但考虑到地图信息量大时运算速度会下降，有必要对战场信息进行过滤和简化来提高规划效率。