空域预先规划时间的冲突处理方法研究

高志周，万路军，钟 赟，蔡 明，徐鑫宇

(1.空军工程大学 空管领航学院， 西安 710051； 2.空军工程大学 装备管理与无人机工程学院， 西安 710051； 3.中国人民解放军94040部队， 新疆 库尔勒 841000)

1 引言

空域的使用需要在严格的时间约束下执行，但在划设空域过程中，由于作战任务需求不同，同时受到恶劣天气、环境变化的影响，空域使用需求会在时间上产生冲突，从而造成作战任务的冲突。为保证空域使用安全，需要对空域时间进行约束。

当前，众多学者对空域冲突检测及消解开展了研究，毛亿等提出了一种空域冲突快速检测的方法，采用“由粗到精，逐步排除”的方法对空域时间、垂直方向、水平维度上逐步进行冲突检测；杨毅等提出了基于栅格模型的大规模空域使用计划冲突检测与解脱方法，根据空域使用计划将空域栅格化并编码，建立空域网格内置属性并判断计划冲突空域；龚玮等提出一种基于栅格模型的空域冲突检测解脱技术，对大量空域使用计划之间的空域冲突进行检测及解脱。

以上学者对空域使用冲突进行了研究，目前对于空域预先时间冲突的处理方法主要采用以甘特图为基础对作战任务时间区间进行逐一比对，从而发现时间冲突，这种方法具有计算效率低、计算不精确、复杂性低等缺点。而简单时间网络(simple temporal network，STN)是一种可以表示时间约束的模型，具有计算简便、使用灵活等特点，适用于对空域预先规划时间冲突的处理。

对STN的应用方面，也有许多学者进行了深入研究，汤罗浩基于STN对行动计划时间的表示和冲突处理开展了研究，设计了迭代检测冲突和消解的CDR算法；李娟提出并实现了一种基于STN的时间、空间、资源冲突检测和消解算法；李远等提出了基于最小冲突集的冲突检测算法，在此基础上设计了基于最小承诺的冲突消解算法；谢斌等设计了一种基于STN的任务在执行过程中资源冲突自动消解的方法。以上研究均以行动计划为背景，利用STN对计划时间进行了时间一致性检测及消解，为空域的时间冲突检测及消解提供了一种新的思路。

在制定空域使用计划时，对时间有很强的约束要求，首先需要在时间层面进行冲突检测和消解，而STN以图论形式满足时间约束来检测和消解空域之间的时间冲突，相比传统的时间冲突判断方法，具有计算快速的特点。对此，本文提出基于STN对空域预先规划时间冲突处理。

2 空域预先规划时间建模

STN是一种针对计划执行的时间约束网络，基于空域的起始和结束时间、任务时间、活动执行顺序等要素，可以画出STN图。在空域划设过程中，根据提交的空域使用需求，对空域添加时间约束，将空域使用转化为计划执行，得到基于空域使用需求的STN。STN由点时间变量集和事件约束集表示，中的元素是各点时间变量，表示事件的开始结束时刻，由约束不等式构成，表示事件之间的时间约束关系。

STN中利用有向约束图=(，)构成时间约束网络，网络中的顶点集合表示点时间变量集，边集合表示时间约束集。顶点和连接的弧→表示时间约束。→∈[，]表示事件和事件满足时间约束，≤-≤(和均为时间)表示在至少后发生，且最多不超过前发生。时间冲突检测实质是判断时间约束网络一致性，如果行动方案满足所有的时间约束，则称STN满足一致性，否则表明方案存在时间冲突。一般在处理过程中，将STN转化为STN距离图，即有向加权图=(，)，将时间约束≤-≤转化为权值为的弧→，以及权值为-的弧→，更加便于计算，如图1所示。

图1 STN图与STN距离图的转换示意图

2.1 预先规划时间约束网络表达

对空域时间冲突的处理，首先对空域使用计划进行系统性的表达，从用空行动的角度分析，空域使用计划可表示为：

在时间约束中，用时间点和时间区间来共同描述空域时间，时间点表示在某一时刻或短时间内的空域内的用空行动，时间区间表示在一定时间范围内的用空行动，即空域的使用时间范围，时间区间可由和分别来表示空域使用时间的开始时刻和结束时刻。

为了便于计算需要将时间点和时间区间的定性约束关系转换为定量约束关系，如表1所示。

2.2 时间冲突检测流程

对空域使用时间进行冲突检测前，首先对空域使用计划和时间约束网络构建数学模型，以定量不等式的形式进行表示，并构建STN距离图。利用最短路径快速算法(shortest path faster algorithm，SPFA)算法对STN距离图进行负环检测，检测流程如图2所示。

表1 定性约束转换为定量约束

图2 时间冲突检测流程框图

在时间冲突检测中，首先制定空域使用计划，根据空域使用计划的要素，构建时间约束网络，即STN图，再将其转换为STN距离图，将时间冲突问题转化为图论的一致性检测问题，利用SPFA算法对STN距离图进行负环检测，若存在负环，则有向图中存在冲突，即空域使用计划存在时间冲突。

2.3 SPFA算法

最短路径快速算法(shortest path faster algorithm，SPFA)是求解单源最短路径的算法之一，其原理是对图进行-1次松弛(为图中顶点数)，得到源点到所有顶点可能的最短路径，相较于常用的最短路径算法Bellman-ford和Dijkstra算法，SPFA算法可以在负权图中进行计算，缺点是时间复杂度更高。SPFA算法用一个数组来记录各个结点的最短路径估计值，首先设立一个先进先出队列(FIFO)，每次优化时取出队首结点，同时点的最短路径估计值对离开点所指向的结点进行松弛，如果点的最短路径估计值有变化，且点不在此FIFO中，将点放到队尾。以此类推，不断从队列中取结点进行松弛操作，直到队列为空时，停止操作。如果某个结点出队列的次数大于等于次，则存在负环(为图的顶点数)，SPFA算法检测流程如图3所示。

SPFA算法中的松弛和Bellman-ford算法中对同一个点的松弛一样，Bellman-ford算法是求解最短路径的算法，最短路径是一条路径必然不是一个环，在有条边的有向图=(，)中，路径的最大长度为-1，因此当迭代次数大于等于时，说明存在负权环，因此在SPFA算法中若某顶点出队次数大于等于，则存在负权环。

图3 SPFA负环检测算法流程框图

以图4为例，首先确定有向约束图=(，)的源点，将赋值为0，其余顶点赋值为+∞，得到初始化数组(=0，=+∞，=+∞，=+∞，=+∞)，同时将加入队列中，此时={}；继续之前的循环，第1次循环时，的队首元素出队列，即出队列，对以为弧顶的点进行松弛，到，的最短路径缩小，更新数组(=0，=-1，=4，=+∞，=+∞)，可以看到、之前不在队列中，将他们入队列，此时先入先出队列为={，}。

进入第2次循环，队首顶点出队列，对以为弧顶的点进行松弛，可以看到到、、的最短路径缩小，更新数组得到(=0，=-1，=2，=1，=1)，同时、不在队列中，将其加入队列，此时先入先出队列为={，，}。

用上述方法不断迭代更新数组和队列，循环迭代至数组为(=0，=-4，=-1，=-5，=-1)时，此时出队列5次，可以判断出图4存在负环→→→。

图4 有向约束示意图

2.4 基于前驱节点数组的改进SPFA算法

2.3节中对SPFA算法的优点和算法流程进行了描述，在图3中通过记录顶点的出队次数判断图中是否存在负环，而在计算过程中有多次多余的入队操作，增加了计算的复杂性，没有及时输出负环判断结果。迭代循环输出数组是基于寻找最短路径来记录松弛变化的，而在负环检测方面可以定义一个记录各顶点的前驱节点数组，通过对该数组中的顶点关系进行描述来判断是否存在负环，当某顶点没有前驱节点时用-1表示，改进算法流程如图5所示。

图5 SPFA负环检测改进算法流程框图

在图5中，第1次循环时出队，数组为(=0，=-1，=4，=+∞，=+∞)，此时的前驱节点数组(=-1，=0，=0，=-1，=-1)；第2次更新数组(=0，=-1，=2，=1，=1)，此时(=-1，=0，=1，=1，=1)，按照同样的方式松弛约束，到第4次循环时出队，此时的数组更新为(=0，=-2，=2，=-3，=1)，前驱节点数组更新为(=-1，=3，=1，=2，=1)，此时出现死循环，即可判断图中存在负环→→→。

相较普通的SPFA算法，本节提出的方法通过4次循环中就找到了负环，大大提升了计算效率，减少了不必要的入队和出队操作。

3 时间冲突消解

3.1 负环消解流程

在STN图中出现负环后需要对负环进行消解，由于出现负环意味着存在时间冲突，因此对负环进行消解的过程就是调整时间约束的过程。

调整约束包括松弛约束、加紧约束、删减约束、添加约束；加紧约束和添加约束会使约束程度更高，不适用于空域时间的冲突消解方面。删减约束是极端的松弛约束，以删除部分约束来达成时间一致性，但同时会影响任务的完整性。因此，利用松弛约束对负环进行消解。

在列出了某作战行动的各类时间约束后，在对任务完成影响最小的前提下进行松弛约束，对约束添加代价系数，表示调整该约束需要付出的代价，再按照优先选择代价最小的约束进行松弛。

3.2 基于最小代价的负环消解

在负环的消解中，将负环权值-加上权重可以消解负环，但会导致事件发生的时间相对固定，缺少了STN图的灵活性，因此对负环权值-加上权重+(>0)，为灵活因子。

对权值为负的弧进行松弛约束时，不能将其权值调整为正值，例如权值为(<0)的弧→表示事件在事件后个单位时间发生，若对权值进行调整使得>0则表示先于至少个单位时间发生，变换了事件的发生顺序，因此对权值为负的弧进行调整时，不能使其权值大于0。

综上所述，可得到调整代价函数为：

式(2)中：Δ表示约束的变化量；为代价系数。

对由条弧构成的负环进行消解时，基于最小代价的目标函数为：

检测到负环后采用贪心算法，寻找代价最小的约束尽可能大的增加权值，到其无法增加后寻找代价次小的约束进行调整，直到负环消解，基于最小代价的负环消解算法流程如图6所示。

图6 基于最小代价的负环消解算法流程框图

4 实例分析

某年某月某日，开展远程火力打击训练任务，1编队担负火力突击任务，2编队担负空中加油任务，3编队担负对目标区域空情侦察任务，4编队担负拦截敌突击任务。区域A为敌入侵空域，区域B为我方拦截空域，区域C为我方机场空域。打击训练任务流程如图7所示。

图7 打击训练任务流程示意图

任务流程为：上午8时，3编队前往区域A对敌空中力量进行侦察，侦察完毕后返回并上传情报，4编队接收情报后向区域B进行拦截攻击，4编队拦截结束后，2编队由区域C前往区域B，同时1编队由区域C前往区域B加油，完成加油后 1编队前往区域C对目标进行火力突击，规定8时32分前完成任务。

根据上述任务流程得到时间约束,见表2。

表2 任务时间约束

1编队前往加油区需要3～5 min，加油过程需要5～7 min，加油完成后到达目标区域需要6～10 min，完成对目标的攻击需要1～2 min，2编队前往加油区需要8～10 min，加油过程需要5～7 min，3编队到达指定区域需要5～8 min，侦察过程需要6～9 min，发现敌方并上传情报需要3～4 min，4编队准备架设需要5～8 min，实施拦截需要6～7 min。整个行动时间不得超过35 min。打击行动的STN图如图8所示。

图8 训练任务STN图

训练任务STN距离图如图9所示，用SPFA改进算法对图8进行一致性检测，检测发现该网络图存在负环(见图9中红色虚线部分)。该任务完成时间为33 min与任务计划在32 min内完成矛盾，因此出现负环。

图9 训练任务STN距离图

对案例添加代价系数如表3所示。

表3 任务时间约束代价系数

对负环消解前列出负环包含的约束，图9中包含的约束为、、、、、、、、，其中不可调整，其余约束根据式(2)计算出调整代价。约束中代价系数最小的为=3，计算出其调整代价为=3·(1+)，此处=1。

故对进行松弛调整，对其负弧权值加2，此时消解冲突的同时保证调整代价最小。对负环进行消解后其消解冲突结果如图10所示。

对图10结果再次进行负环检测，结果不存在负环，即时间冲突得到消解。

图10 消解冲突结果示意图

5 结论

1) 提出基于STN图的空域预先规划时间冲突处理方法，对空域预先规划时间约束进行建模，用STN时间约束网络图进行表达，提高了冲突处理的科学性；

2) 提出了基于前驱节点的改进SPFA算法，在负环检测过程中减少了不必要的循环，提高了计算效率并通过SPFA改进算法对时间约束网络进行一致性检测，检测空域使用计划是否存在时间冲突；

3) 采用基于最小代价的方法对时间冲突进行消解，并通过对案例的分析证明了方法的可行性。

4) 结合图论相关内容对空域预先规划时间冲突处理问题进行研究，提供了一种新的研究思路和方法。后续将针对联合作战的特点进行研究。