基于战术意图欺骗的无人舰艇航路规划算法*

安 彧，张抒尘，刘 颢，耿 亮，巩庆涛

（1.湖北工业大学理学院，武汉 430068；2.上海交通大学电子信息与电气工程学院，上海 200240；3.武汉数字工程研究所，武汉 430074；4.鲁东大学山东省海上航天装备技术创新中心，山东 烟台 264025）

0 引言

随着智能化技术在船舶领域的升级和发展，无人舰艇已经成为海战场中越来越重要的元素，其具有不同于传统舰艇的优势，如较小的体积重量、灵活的机动性、优秀的自主导航能力［1］等。而航路规划作为无人舰艇控制系统中的重要组成部分，对于保证无人舰艇的安全性、减少控制成本、提高任务执行效率和自动巡航都具有重要意义，是当前研究的热点。

目前无人舰艇的航路规划算法主要可分为两类：基于仿生的智能算法和基于图论的搜索算法。其中，基于仿生的智能算法包括蚁群算法、细菌觅食法、人工鱼群法等。王成等通过使蚁群信息素的分配不均匀和加入惩罚机制，解决了陷入死锁航路的问题。但由于蚁群算法对初始解依赖性较强，参数量大且难以设置，导致算法的易用性上受到了局限［2］。YANG L 等提出了一种细菌觅食算法用于无人舰艇的航路规划，可以加快路径搜索性能，提高收敛速度。但在理论上尚存在不足，难以给出具体数学模型［3］。LIAO Y 等提出了一种改进的人工鱼群算法用于提高航路求解精度，并采用最小消耗误差进行优化，使规划出的航路更加符合任务期望［4］。但由于鱼群的行为是随机的，不同的初始值仍会使结果出现差异。总的来说，仿生智能算法主要源自于大自然规律和生物行为，具有处理动态环境能力强、处理复杂规划问题能力好的优点；但也普遍存在参数设置复杂、时间复杂度高以及较为依赖人工设置特征函数等缺点，在易用性和适用泛性上存在较大局限。

基于图论的搜索算法具有搜索范围广、效率高、理论基础充分和易于实现等优点，包括RRT 算法、Dijkstra 算法和A*算法等，这类算法相比仿生智能算法，有更强的可解释性和易用性。LI J 等提出了一种基于角度距离的RRT 算法，提高了相邻节点间的搜索速度［5］；但由于搜索是随机的，该方法难以找出精确最短航路。吕成采用Dijkstra 算法建立了极区环境的航路规划方法，将环境阻力纳入考虑范围，增加了算法可拓性［6］，但由于该算法仅根据广度搜索策略进行节点搜索，在效率上不够优秀。A*算法是一种效率高、灵活性强、工程实现容易的最短路径搜索算法，其引入了启发函数用于引导搜索，可快速地完成规划任务［7］。且由于启发函数的存在，A*算法还具有极强的可适性和拓展性，可根据实际需求灵活调整搜索范围，以适应规划需求。TANG R X 等通过提出双向搜索和引导线的概念改进了A*算法，优化了算法效率及空间复杂度［8］。郑煜坤等提出了一种基于追踪模型方程改进的A*算法，使其能够进一步缩短弯折处的路径长度，并提高了避障能力［9］。

可见，目前研究中对于A* 算法的主要改进方向仍是优化其算法效率和路径长度，这种改进难以满足实际海上作战中航路规划问题的需求。对于海战场而言，意图欺骗是一种非常重要的作战手段；通过意图欺骗，可以让敌方产生偏差，对方真实战术意图产生误判，从而提高我方的作战胜算概率。因此，为在实际作战中规划出一条带有意图欺骗性的最优无人舰艇航路，联系A* 算法较强的拓展性与可适性，本文尝试对A* 算法进行改进，试图提出一种基于概率性意图欺骗（probabilistic intentional deception，PID）代价函数的DTI-A*（deception of tactical intention-A*）算法，使算法在保留传统A*算法优点的基础上，能够规划出一条既能控制长度成本，又能满足欺骗需求的最优决策航路，从而帮助己方无人舰艇隐瞒真实意图，顺利完成战术任务。

1 欺骗性航路规划模型

基本航路规划问题的本质是在一个环境地图中从给定的起点到给定的终点之间寻找最优路径。可用三元组来描述［10］：

〈D，s，gr〉

其中，s 为给定的起点，gr为真实目标点，D 为规划域，有：

N 为地图中非空节点的集合，E 为节点与节点之间边的集合，c 为边的长度代价。

对于通过规划域D 所规划出的一条航路d，本质上是一个非空节点构成的序列d=n1，n2，…，nk，整条航路d 的代价cost（d）等于路径中每条边的代价和，即：

其中，di表示路径d 中的第i 个节点，有i∈｛0，1，…，k-1｝；（di，di+1）表示路径中节点之间的边c（di，di+1），表示节点di与di+1之间的边的代价，对于基本的航路规划，边的代价通常为边的长度。

相比于基本航路规划问题，意图欺骗性航路的规划问题还要额外考虑3 个因素指标［11］：用来欺骗敌方的虚假目标点、节点对应各目标的概率分布以及各节点的欺骗性能。其元组表示形式如下：

其中，〈D，s，gr〉为基本航路规划问题；gf为虚假目标点，为异于真实目标点gr的一个非空节点，通常由指挥官和专家根据战场态势确定；p 为节点对应目标概率分布；c'为考虑了节点欺骗性能后的代价。

2 A*算法基本原理

A*算法是一种高效、直接的启发式搜索算法。其原理是以起始节点为第一个搜索点，向其周围待搜索节点拓延并将周围节点纳入搜索域，随后通过代价函数计算搜索域内各节点的估计代价，并选取估计代价最小的节点作为下一个搜索点，不断重复此步骤，直至搜索到目标节点时便可生成一条最优航路。

在栅格地图中，各节点为栅格的中心点，A*算法在从当前搜索点nnow向周围节点进行拓延搜索时，其搜索规则如图1 所示，会将周围上、下、左、右、上左、上右、下左、下右共8 个方位的节点纳入搜索域：

图1 A*算法拓延搜索示意图Fig.1 Illustration of A*algorithm with extended search

代价函数f（n）影响着搜索点的确定规则，它对A*算法至关重要，对于传统A*算法而言，其代价函数形式为［5］：

其中，f（n）为总代价函数，g（n）为实价函数，表示待搜索节点n 到起始节点的实际代价，h（n）为启发函数，也称估价函数，是决定A*算法搜索精度的关键，通过启发函数可计算节点n 的估计代价值，得到启发信息。

传统A*算法的实价函数g（n）通常是通过累加边权来计算的，而启发函数h（n）的估计值则是通过曼哈顿距离（Manhattan distance）、欧几里得距离（Euclidean distance）等来计算，以欧几里得距离为例，对应的启发函数表达式为［9］：

其中，nx、ny为待搜索节点n 的横纵坐标，gx、gy为最终目标点的横纵坐标。

3 基于战术意图欺骗的DTI-A＊航路规划算法

3.1 基于目标概率差值的欺骗性能表征方法

欺骗性航路规划需要对无人舰艇周围的环境空间进行栅格化离散处理，并对各栅格的中心节点进行欺骗性能表征。利用无人舰艇在各节点上可能前往的终点目标概率来进行节点欺骗性能表征：设共有m 个可能存在的目标，则地图中的任意一个节点所对应的目标概率分布可由节点到各目标的距离长度计算得出，其式为：

其中，gi为可能的任意一个目标（i=0，1，…，m），为节点对应的目标为gi时的概率，li表示节点到目标gi的最短路径长度。

由此，节点欺骗性能值可借助节点对应目标概率的差值来表征，其含义为节点在航路规划问题中欺骗性能的优劣，表达式为：

其中，dp（n）表示节点n 的欺骗性能值，值越大代表节点n 的欺骗效果越好，p（gi）、p（gr）分别为节点n对应的虚假目标概率和真实目标概率。通过该计算过程，可得到无人舰艇在行驶到各节点时的意图欺骗性，完成作战空间欺骗性能的离散表征。

3.2 PID 代价函数的构建与融入

为使规划出的航路具有意图欺骗性，构建PID代价函数融入算法，PID 代价值应与节点的欺骗性能值dp（n）呈负相关，即节点的欺骗性能越好，其PID 代价就越低，考虑代价函数的收敛性，设定PID代价函数表达式如下：

其中，gi、gr分别代表真实目标点和虚假目标点，dp（n）表示节点n 的欺骗性能值。

由式（7）可见：当节点n 越靠近真实目标点时，根据式（5）和式（6）可知，其对应的真实目标概率p（gr）越大，欺骗性能值dp（n）越小，此时的PID（n）也越大；反之，当节点n 越靠近虚假目标点时，其PID（n）就越小。

在式（3）中，传统A*算法考虑的节点代价完全是从航路的距离长度出发，规划出的最优解为一条总长度距离最短的航路。距离长度成本是航路规划中必须考虑的问题，降低航路距离可以提升无人舰艇的作战效率，为保持这一特性，综合考虑航路距离长度和欺骗性两个因素，在传统A*算法代价函数中融入PID 代价作为DTI-A*算法的代价函数，如式（8）所示：

其中，g（n），h（n）为传统A*算法中的实价函数与估价函数；考虑无人舰艇的航行方向可以斜对角移动，h（n）取式（4）的欧几里得距离。

e 为欺骗因子，值为一个大于等于1 的常系数。当e 取值越小，PID 代价的权重越小，则代表在航路规划中更多考虑航路的距离成本而非欺骗效果；相反，当e 取值较大时，则代表在规划时更多考虑航路的欺骗性。通过对e 数值的调整，可以实现不同强度的战术意图欺骗策略，e 值越大，则规划出的航路，欺骗时间往往就越长，二者总体呈正相关。但由于不同战场任务对航路欺骗性的阈值定于不同，具体e 值需要结合战场任务条件来进行设定，以达到期望的欺骗时间。

3.3 算法流程

本文提出的DTI-A*算法沿用传统A*算法中对代搜索节点的处理方式，即使用开放列表（open list）和封闭列表（close list）对节点进行管理。开放列表中的节点为正在被搜索的，其初始值为起始节点，而封闭列表中的节点为已经搜索过的。算法流程图如图2 所示。

图2 DTI-A*算法流程图Fig.2 The flowchart of DTI-A*algorithm

4 航路规划算法仿真

为验证DTI-A*算法性能，从Moving-AI 地图测试集［12］中随机抽取出一副水域环境地图，采用正四边形栅格对其进行栅格化处理进行仿真实验，每个正四边形的中心点为节点。仿真在Ubuntu20.04、Intel Core i5-8300H CPU@2.30Ghz、16GB RAM 的计算机环境下进行。

4.1 仿真设计

为模拟真实水面战场环境，融入战场态势信息，在某次作战任务中：节点（2，11）设为我方无人舰船起始节点，以船标表示；节点（18，17）设为真实目标点，以绿色表示；节点（18，5）设为虚假目标点，以紫色表示；中间3×3 的红色区域为敌方警戒区，我方舰船不能经过，属于不可通行区域。为使模型更贴合实际，还需作出如下战场条件假设：

1）敌方的航路意图识别器采用基于代价的快速航路意图识别方法［13］。

2）航路被识别出的“攻击真实目标点概率”小于0.5 时，视为航路具有欺骗性；大于0.5 时敌方会采取防御手段，采取防御手段10 min 后若我方无人舰艇仍未到达真实目标点，视为任务失败。

3）无人舰船可在各相邻节点间进行单位直线移动和单位斜线移动，且所需时间都为1 min。

融入战场态势信息后的栅格化环境地图如图3所示。

图3 融合了战场态势信息的栅格地图Fig.3 Grid map fused with battlefield situation information

4.2 仿真结果分析

为模拟不同强度的战术意图欺骗策略，将式（9）中欺骗因子e 分别设定为1、2、3，模拟轻度欺骗、中度欺骗和重度欺骗3 种策略。在图3 的战场态势栅格地图上分别对蚁群算法、传统A*算法和本文提出的DTI-A*算法进行仿真验证，其中蚁群算法的主要参数设定为：信息素重要程度因子alpha为1，启发函数重要程度因子beta 为2，蚂蚁数量20，迭代次数50，测试结果如图4 所示。

图4 各种算法规划的航路对比图Fig.4 Comparison of routes planned by various kinds of algorithms

通过意图识别器对不同航路进行航路终点意图识别，识别结果如图5 所示。

图5 5 条航路的意图识别结果Fig.5 Intent recognition results of the five flight routes

将上述信息转化为表格，各航路的质量对比如表1 所示。

表1 5 条航路对比Table 1 Comparison five routes

通过表1 中的指标可知：本文提出的DTI-A*算法相比传统A*算法和蚁群算法，可以将任务结果从失败变为成功。在设定不同的欺骗因子时，可实现不同强度的欺骗策略，随着欺骗策略强度的增加（欺骗因子e 的增大），航路的欺骗性能也会显著提升，最多可使敌方在第22 min 时才采取防御手段，使航路欺骗时间占比增加77.78%，被识别出的攻击真实目标点的概率最小值降至0.07。这意味着DTI-A*算法可以很好地延误敌方采取反制防御手段的时间，满足意图欺骗性航路规划问题的需求，能够极大程度提升无人舰艇执行作战任务的成功率。

5 结论

针对“现有研究对A*算法的改进方向难以满足航路意图欺骗需求”这一局限性，为实现无人舰艇在水面战场中的航路战术意图欺骗，本文重点研究了基于欺骗思想的航路规划算法。相比现有研究，本文构建了欺骗航路规划模型，探索性地提出了作战空间节点欺骗性能的表征方法，以此构建和融入PID 代价函数来实现欺骗航路规划算法DTI-A*。

通过仿真实验验证，本文提出的DTI-A*算法延长了欺骗时间及其占比，极大降低了攻击真实目标点被识别的概率，可使任务执行结果由失败转为成功；相比其他航路规划算法，能够有效提高水面战场中无人舰艇的欺骗性航路规划质量，这对于在未来的海战场中增强我方作战能力和信息化水平、提高我方电子战装备的智能化程度具有现实意义，力图为维护海上安全、完成海上作战任务做出更大的贡献。在未来的研究中，将在欺骗航路规划模型中可以探索更多的参数设置和优化策略，进一步提高欺骗性能并适应更加复杂的水面战场环境。