基于STN 的两栖兵力投送任务时间协同规划*

胡忠凯，黄炎焱

（南京理工大学自动化学院，南京 210094）

0 引言

两栖兵力投送是两栖登陆作战中最关键、最激烈、最复杂的阶段，如何保证两栖兵力投送任务的顺利执行是备受关注的重点与难点。时间协同规划是两栖兵力投送任务规划中的重要组成部分，通过时间协同规划保证两栖兵力投送任务行动在时间上的协调统一、互不冲突。STN 是构建两栖兵力投送任务模型与时间协同规划冲突检测与消解的基础。Dechter 在Artificial Intelligence 杂志上提出时间约束网的理论，Ghallab 等利用简单时间网络对规划进行建模解决时间约束冲突问题。国内学者也对简单时间网络在作战任务上的应用开展了进一步的研究。谢斌等从时间角度出发，设计了一种基于STN 的、在执行过程中自动消解资源冲突的方法，并证明了该法的可行性。张华提出了一种基于STN 表示的作战任务时间冲突检测方法，并对任务时间规划提供参考范围。张道萍等采用时间网络图描述作战行动，设计了一种基于关键任务的时间冲突消解方法，对作战任务的时间冲突进行消解。本文在利用简单时间网络对两栖兵力投送任务建模的基础上，对时间规划进行冲突检测与消解，得到合理的两栖兵力投送任务时间协同规划。

1 两栖兵力投送任务建模

1.1 STN

时间点以及时间区间是描述行为的一种方式。时间点用于表示在发生一瞬间的行为；时间区间用于表示具有一定持续时间的行为，也可以转化为开始时刻和结束时刻的两个时间点。

图1 是将一定的简单时间约束等价转化为相应STN 的例子。

图1 简单时间约束及STN

在简单时间约束问题中，当时间变量集合至少存在一组满足所有时间约束的值时，则称STN 是一致的，即任务规划满足相应的时间约束，该规划是合理的。

如图2 所示，将图1 中的STN 等价转化成相应的距离图。

图2 距离图

1.2 两栖兵力投送任务STN 模型

1.2.1 两栖兵力投送任务分解

两栖兵力投送过程具有多编队、多波次的特点。两栖兵力投送采用气垫登陆艇、两栖突击车和武装直升机等多种载具相结合的多编队兵力投送方式，极大地提高了作战效能与打击能力；两栖兵力投送过程中兵力需要根据作战任务分多个波次上陆，一方面需要保证异波编队攻击的持续性，但又要避免各波次间作战单位的相互影响；另一方面需要确保同波编队聚力突袭的同时性，冲滩上陆力量形成强大的冲击合力，迅速建立起登陆方的优势，也就是说一个波次内的兵力要求在同一时间上陆。

对两栖兵力投送总任务中进行合理分解，构建时间约束网络。在两栖兵力投送过程中包含着多个波次任务，在每个波次任务中又有不同的编队任务，任务分解如图3 所示。

图3 两栖兵力投送任务分解

1.2.2 多波次任务STN 模型

图4 多波次任务STN

两栖兵力投送总任务开始时间节点为T，总任务结束时间节点为T，各个波次上陆任务开始与结束时间节点分别为T和T。由于总任务结束与第3波次任务结束为同一个时间点，可以用T代替总任务结束时间节点。多波次任务各时间约束条件在STN 中的各边上予以显示。

如图5 所示，将二元时间约束双边不等式转化为单边不等式，多波次任务STN 可等价转换为多波次任务距离图。

图5 多波次任务距离图

1.2.3 多编队任务STN 模型

图6 多编队任务STN

多编队任务开始时间节点为T'、结束时间节点为T'，各编队任务开始时间节点分别为T'。由于多编队任务结束与各编队任务结束为同一个时间点，可以统一用T'表示该时间节点。多编队任务各时间约束条件在STN 中的各边上予以显示。

如图7 所示，将二元时间约束双边不等式转化为单边不等式，将多编队任务STN 等价转换为多编队任务距离图。

图7 多编队任务距离图

2 时间协同规划算法

2.1 时间协同规划冲突检测

STN 是一致的等价于与其对应的距离图没有负环。

负环指的是在STN 距离图中由一系列点与权值和为负的同向有向边构成的环。如图2 中的STN距离图所示，按序经过顶点1、2、4、3 的环路权值和为-2，是一个负环。对冲突的存在与否可以转化为在与相应时间约束对应的STN 距离图中是否可以找到负环。本文通过Johnson 算法找出STN 距离图中的所有简单环路，根据环路有向边的权值和，判断其是否是负环。

Johnson 算法采用深度优先搜索的搜索策略，遍历有向图中的每个节点，寻找以其为起始点与终止点的简单环路。在寻找以某个顶点为起始点与终止点的简单环路的过程中，需要一个标志变量Flag 记录是否在路径上找到环，一个堆栈Stack 记录当前深度优先搜索的状态，一个阻塞记录表BlockedSet记录着搜索过程中的顶点状态，一个阻塞关系表BlockedMap 记录顶点阻塞依赖关系，具体步骤如表1 所示。在该点搜索完毕后，会将该顶点及其邻边从有向图中移除，之后继续在新的有向图中重复寻找负环的步骤，直到有向图中不能构成强连通分量或者只剩下一个顶点。

表1 Johnson 算法步骤表

2.2 时间协同规划冲突消解

灵活因子是为了保证STN 的调整灵活性。同时原先的约束条件具有实际意义，约定边的权重调整量不超过边权重绝对值的η（η 为百分数）。

度是针对STN 距离图上的某一边（约束）来说的，用包含该边的不同负环的数量进行表示。度可以一定程度上表示该边对冲突消解的潜在贡献。

某边上的调整优先度是指该约束在整个任务中的调整优先级别。调整优先度是从整体任务中不同任务的性质进行考虑的。如在多波次任务STN 模型中，不同波次编队到达时间间隔受到登陆场等诸多环境因素影响，需要保证一定的间隔时间，调整优先度较低；而总任务出发时间相较来说调整优先度较高。调整优先度根据总体任务情况进行综合评估，利用层次分析法等方法得到。在本文中，调整优先度作为已知条件给出。

本文提出了综合优先调整度的概念。考虑约束度的同时，结合约束本身的调整优先度，衡量约束对冲突消解的贡献，对约束进行调整。某条边的综合优先调整度可以表示为

式中，prio表示边i 的调整优先度，k表示边的度。

伯虎终于说到正题。只见他们三人面前的空中，三维画面像一朵花瓣似地打开了，应用里出现了一个导航页。而就是这个导航页当中的“降维安全监测”六个字，使得安文浩一怔。

如图8 所示，不断检测负环集合是否为空，选择综合优先调整度最大的边进行调整，将该边设置为不可再调整，更新负环集合状态，直至全部负环被消除。

图8 负环消解流程

2.3 Floyd-Warshall 算法

Floyd-Warshall 算法用于求解有向加权图中任意两点之间的最短距离，通过考虑最佳子路径来得到最佳路径。初始化矩阵DIST［］，DIST［i，j］表示从顶点i 到顶点j 的最短距离。对于i 等于j，初始化DIST［i，j］；否则初始化DIST［i，j］=+∞。从第1 个顶点开始，依次将每个顶点作为中介k，若满足

则更新

即如果存在一条经过k 且距离较已知路径更短的路径，更新i、j 间的最短距离。

3 案例分析

两栖兵力投送任务总体想定：两栖兵力投送总任务在早晨6：00 开始，共分为4 个波次任务进行，每个波次任务中包含着3 个编队（直升机、气垫艇、两栖战车），总共持续时间在40 min～50 min 之间。

3.1 多波次任务分析

多波次任务想定规划：第1 波次任务在30 min～40 min 之间完成，第2 波次任务在25 min～35 min之间完成，第3 波次任务在30 min～35 min 之间完成，第4 波次任务在35 min～40 min 之间完成。第1波次开始时间距总任务开始时间在5 min～10 min 之间。每个波次任务的开始时间间隔为6 min～9 min，每个波次任务的结束时间间隔为7 min～8 min。

选定极限调整值η 为40%，灵活因子μ 取1。

各约束的调整优先度在想定多波次任务距离图调整表中作为条件给出。

图9 想定多波次任务STN

图10 想定多波次任务距离图

根据Johnson 算法，发现想定多波次任务STN距离图中共有5 个负环，分别是：T→T→T→T→T→T→T、T→T→T→T→T→T→T、T→T→T→T→T→T→T→T→T、T→T→T→T→T→T→T→T→T以及T→T→T→T31→T→T→T。

统计负环集合中各边的度，结合各边的调整优先度，得到各边的综合优先调整度。通过想定多波次任务距离图调整表呈现，如表2，根据此表进行冲突消解。

表2 想定多波次任务距离图调整表

具体消解步骤如下所示：

图11 冲突消解后的想定多波次任务距离图

根据Floyd-Warshall 算法，确定任意两点时间之间的最短距离，可以得到多波次任务距离图最短距离表，如表3 所示。

表3 多波次任务距离图最短距离表

根据表3，以T为基点，各个时间节点范围：T为［3，4］，T为［33，34］，T为［9，12.8］，T为［40，41］，T为［12.6，16.4］，T为［47，48］，T为［16.2，20］，T为［54，55］。其中，一组可行解取T为3，T为33，T为10，T为40，T为16，T为47，T为20，T为55。即：两栖上陆总任务开始时间为6：00，第1 波次任务开始时间6：03，第1 波次任务结束时间为6：33；第2 波次任务开始时间6：10，第2 波次任务结束时间为6：40；第3 波次任务开始时间6：16，第3 波次任务结束时间为6：47；第4 波次任务开始时间6：20，第4 波次任务结束时间为6：55，上陆总任务在6：55 结束。

3.2 多编队任务分析

根据多波次任务的分析，第1、2、3、4 波次任务分别需要在30 min、30 min、31 min、35 min 内完成。

多编队任务想定规划：每个波次任务可分为直升机、气垫艇、两栖战车3 个编队任务。直升机编队任务持续时间在5 min～10 min 之间，气垫艇编队任务持续时间在10 min～15 min 之间，两栖战车编队任务持续时间在25 min～35 min 之间。

以第1 波次多编队任务为例进行时间协同规划分析。第1 波次任务需要在30 min 内完成，也就是说第1 波次任务持续时间在0 min～30 min 之间。构建想定第1 波次多编队任务STN 如图12 所示。

图12 想定第1 波次多编队任务STN

将想定第1 波次多编队任务STN 等价转化为想定第1 波次多编队任务距离图，如图13 所示。

图13 想定第1 波次多编队任务距离图

根据Johnson 算法，想定第1 波次多编队任务STN 距离图中的环中不存在负环，说明第1 波次多编队任务规划上不存在时间冲突。

根据Floyd-Warshall 算法，得到想定第1 波次多编队任务STN 距离图最短路径表，如表4 所示。

表4 第1 波次多编队任务距离图最短路径表

根据表4，以T'为基点，各个时间节点范围：T'为［0，5］，T' 为［10，15］，T' 为［15，25］，T' 为［25，30］。其中，一组可行解取T'为5，T'为15，T'为25，T'为30。即：第1 波次多编队任务开始时间为6：03，第1 编队（直升机）出发时间6：08，第2 编队（气垫艇）出发时间6：18，第3 编队（两栖战车）出发时间6：28，第1 波次多编队任务在6：33 结束。

第2、3、4 波次多编队任务同理根据上文进行STN 建模，等价转化为距离图，进行时间协同规划冲突检测与消解，得到各剩余波次多编队任务相应的时间协同规划，如表5 所示。

表5 两栖兵力投送任务时间协同规划表

通过对多波次任务及多编队任务的分析进行汇总整合，最终得到两栖兵力投送任务时间协同规划，呈现在两栖兵力投送任务时间协同规划表中。

4 结论

本文分析了两栖兵力投送任务的特点，利用简单时间网络对两栖兵力投送任务及相应的时间约束规划进行建模及表示，检测原规划在时间约束上的一致性，基于综合优先调整度对规划存在的时间冲突进行消解，得到合理的时间协同规划，为两栖兵力投送任务的顺利执行提供有力的保证与帮助。