基于改进稀疏A*编队航迹实时规划方法*

程 越，周中良，江建成

（空军工程大学航空航天工程学院，西安 710038）

0 引言

在对地突防任务中，随队支援干扰机在压制敌对空警戒雷达，提升突防效率方面发挥着极其重要的作用。在任务执行中，干扰机编队的任务与航迹应随着战场态势的变化而不断变化，确保突防任务的顺利实施。

在航迹规划与干扰资源分配方面，文献［1］通过ISODATA算法对干扰目标分组，改变干扰样式，实现对干扰资源的优化分配。文献［2］以各航线点精度的平均值为目标函数，对干扰组网雷达提出了资源分配的方法。文献［3-4］提出了基于不同边界条件的分枝定界法来对武器资源分配问题进行求解。文献［5］为简化规划计算量，将空间规划等效为平面规划与高度规划，并运用动态步长提升规划精度，降低威胁度。文献［6］基于任务对多飞行器的航迹进行协同规划，可以较小代价获得较好作战效果。文献［7］设计了混合整数线性规划方法对航迹进行优化。文献［8］提出了利用遗传算法和粒子群算法来降低三维环境下航迹规划问题的复杂度。文献［9］通过构建基于可部分观测的马尔科夫决策过程的行动空间，引导无人机对地面多目标进行跟踪。

本文考虑到突发威胁的情况，重新对编队干扰资源进行分配，并对威胁数据库进行更新。利用改进的稀疏 A*搜索（Sparse A*Search，SAS）算法，以发现威胁时我方随队支援干扰编队的位置为起点进行规划，开展基于动态干扰资源分配的航迹实时规划技术可行性研究。

1 航迹实时规划模型

图1 编队航迹实时规划示意图

图1为编队航迹实时规划的示意图。当编队沿着原始航迹向目标点C飞行时，在节点A处遭遇了一个突发威胁。由于事前规划的航迹是穿过了该威胁区域的，若继续沿着事前规划的航迹飞行，显然会遭遇到敌方拦截。因此，必须实施航迹的实时规划，在突发威胁的局部区域进行寻优，以突破威胁。实时规划的步骤如下：

Step1：确定实时规划航迹的规划起始点。以当前节点A作为航迹实时规划起始点。

Step2：确定实时规划航迹的终点。这里有两种选择：一是把原始航迹穿过突发威胁区域的第1个栅格点作为更新航迹的终点，之后继续按照原始航迹前进，最后到达目标点；二是把原始航迹的目标点作为更新航迹的终点，直接建立从节点A到目标点C的最优航迹，而不需要再使用原始航迹。两种方式各有优劣，第1种的计算量小，实时性比第2种强，但是优化性不如第2种。

Step3：确定航迹实时规划的步长。要求步长大于或等于最小规划步长。

Step4：确立航迹实时规划的目标函数。

Step5：判断威胁类型，如果出现的威胁为障碍物，则只需要在规划的时候绕过这片区域即可，即只用对撞山威胁数据库进行更新。如果是雷达威胁，则需要重新为每架干扰机分配一种干扰样式以及干扰目标，进行干扰资源的调整。在进行了干扰资源重分配后，就可以对航迹段所在空域的威胁数据库进行更新。

Step6：采用优化算法求解航迹段。

Step7：在编队到达下一航迹点之前，以下一航迹点为起点，重新规划下一航迹段直到下一航迹点为目标点。

航迹实时规划流程如图2所示：

图2 航迹实时规划流程图

2 改进稀疏A＊算法

航迹实时规划由于它的实时性，就是一个典型的需要局部寻优的问题。而启发式搜索算法则可以满足这个需求。改进稀疏A*算法可以对领域进行搜索，从起点开始，不断搜索最有希望到达终点的领域节点并依次往下，形成一条代价最小的航迹。因此，本文利用改进稀疏A*算法对航迹进行实时规划。

2.1 稀疏A＊算法

传统的A*算法属于经典启发式算法，具有简单、搜索航迹最优的优点。它的搜索节点分为3种：1）已经被扩展的节点，存入CLOSED表中；2）计算了航迹代价，但是还没有被扩展的节点，存入OPEN表中；3）还未计算航迹代价也未被扩展的节点。OPEN表与CLOSED表中都记录着相同的节点信息，包括节点的坐标、父节点的坐标以及各节点的航迹代价。算法首先计算当前栅格领域的每一个栅格的代价，并对其进行比较。之后将所有领域栅格及其代价存入OPEN表中，作为待扩展节点，而已经被扩展的栅格节点则存入CLOSED表中。这样通过不断搜索当前节点与目标节点之间代价最小的节点，直至目标点，就可以确定出一条航迹代价最小的点迹序列，形成最优航迹。

A*算法中目标函数的表现形式一般为：

由于每次设立仪器站时都没有对仪器进行定向，也没有将仪器站的坐标纳入统一的坐标系中，因此仪器在每个仪器站上获得的目标点坐标之间没有关联，必须统一坐标系。本文采用文献［1］的计算方法进行统一坐标转换。文献［1］给出的计算方法：

其中，n是待扩展节点，f（n）是待扩展节点的评估函数，g（n）是起点到待扩展节点 n 的真实代价，h（n）为启发函数，表示从待扩展节点n到目标节点的代价估值。

但当搜素范围增加后，搜索节点过多，A*算法容易出现搜索时间长难以收敛的缺点，因此，为了提高搜索速度，本文采用了稀疏A*算法。该算法由Szczerba［10］在2000年提出，它通过加入约束条件，可以有效剔除空间中的无效节点，缩小搜索空间。稀疏A*算法在空间中的搜索示意图如图3所示：

图3 稀疏A*算法搜索示意图

2.2 算法改进

本文主要约束条件为前文提到的航迹可飞行性，即用撞山威胁、雷达网探测威胁以及飞行器自身性能对空间中的可飞节点进行筛选。同时，为了解决航迹规划的实时性，本文依据实时规划模型对算法进行改进。

在对航迹点进行搜索的过程中，考虑到搜索角度以及步长的影响，最后不一定能搜索到目标点。因此，这里对算法的结束条件进行更改。当航迹搜索的当前节点与目标点之间的距离小于R0时，搜索结束，即：

其中，（xT，yT，zT）为目标点的坐标，（xc，yc，zc）为当前节点的坐标。

为使航迹能够向目标点方向搜索，这里引入人工势场的思想对算法进行改进。在实时规划起始点与目标点之间构造一个虚拟的引力场与势力场，引力场的中心为目标点，斥力场的中心为起始点。

3 航迹实时规划的目标函数

假设从节点ai开始实时规划，即a1至ai-1的航路节点是已规划好的航路节点，ai到目标点的节点是未规划的航路节点。改进后的目标函数为

其中，P1（li）表示编队在航迹点ai及其航迹段li的航程威胁，P2（li）表示编队在航迹点ai及其航迹段li的撞山威胁，P3（li）表示编队在航迹点ai及其航迹段li的雷达网探测威胁，需要在节点处进行干扰资源优化分配，使探测威胁最小。

γ1、γ2、γ3、γ4、γ5表示 5 个指标的权重系数且和为1，具体的数值根据任务性质由专家打分法获得，一般前3个较大。则目标函数前3个为代价函数，后两个为启发函数。

P4（li）的定义如下：

式（4）中，R0代表以航迹目标点为圆心的一个球体的半径，Ri，z表示待规划航迹点与航迹终点的距离，Ri，q表示待规划航迹点与实时规划航迹起点的距离。为了使目标函数在离航迹终点越近时收敛速度越快，需要目标函数随着距离的减小而减小，因此，加入该指标。

P5（li）的定义如下：

式（5）中，Rm（ai）表示节点ai与目标点的距离，Rq（ai）表示节点ai与起始点的距离，k为人工势场增益。该代价的定义包含了人工势场的思想，可以使节点搜索方向朝着目标点的方向。

4 航迹与干扰资源的实时规划

采用改进的稀疏A*算法来对节点进行扩展，算法步骤如下：

Step1：发现突发威胁时，对航迹实时规划的起始节点进行判断，若为可飞节点，将其插入OPEN表中，同时将上一航迹段的节点从CLOESED表中删除。

Step2：对OPEN表中的节点分别重新进行干扰资源分配，计算节点及其航迹段对应的目标函数。将目标函数值小的节点作为当前航迹点，并放入CLOSED表中。

Step3：如果OPEN表中没有节点，则表示搜索失败，调整算法参数后重新进行搜索。

Step4：如果下一个航迹节点即为目标点，则表示搜索结束。

Step5：重复以上步骤，直到搜索失败或寻找到局部最优航迹。若搜索失败，则回到Step2。

5 仿真实验及结果分析

图4 突发威胁示意图1

图5 突发威胁示意图2

如图4所示，编队在突防过程中发现在山峰上出现了一部之前没有得到任何相关信息的雷达5，且该雷达出现在前方航迹的附近。由于这种雷达一般是战备的时候才使用，也是防止其他雷达失效或损毁而准备的备用雷达，因此，这种雷达与其他4部雷达并没有组网关系。但由于这部雷达较雷达4离航线更近，因此，需要重新优化干扰策略，将雷达对编队自身的探测降到最低。

图6 编队实时规划航迹图1

图7 编队实时规划航迹图2

图6、图7显示了在出现新的突发威胁后，对局部航迹进行实时在线实时规划，得到的最优航迹。与之前没有出现突发威胁时施加干扰的事前规划航迹进行对比，可以看出航迹在雷达5处有一个向左的偏移。此时编队为了降低雷达对编队整体的探测威胁，增加了航程威胁。

图8 实时规划航迹探测威胁

图9 实时规划航迹综合威胁

图8显示了航迹点与雷达探测威胁的关系。在整段航迹上，探测威胁较之前没有出现新的雷达时有了明显提升，尤其是在经过雷达1、5、3时，探测威胁维持在了一个较高的水平，这也与预期估计的效果相符。之后随着离雷达越来越远，探测威胁趋于稳定。图9则是表明了综合威胁在航迹中的变化程度。总的来说，虽然新雷达的出现对我方的航迹规划造成了一定的影响，但是通过局部实时规划技术，将这种影响降到了最低的程度。

6 结论

本文首先对航迹实时规划技术进行了介绍，在事前规划的基础上，考虑了随队支援干扰编队在突防过程中遭遇突发威胁的处理方法。之后建立了编队航迹实时规划的模型以及步骤。然后针对对抗态势的变化，首先重新分配干扰资源，并对局部空间的威胁数据库进行更新，再进行下一步航迹节点的规划。最后利用改进稀疏A*算法，对航迹进行了实时规划。仿真结果验证了算法的有效性。