1 引言
空域的使用需要在严格的时间约束下执行，但在划设空域过程中，由于作战任务需求不同，同时受到恶劣天气、环境变化的影响，空域使用需求会在时间上产生冲突，从而造成作战任务的冲突。为保证空域使用安全，需要对空域时间进行约束。
当前，众多学者对空域冲突检测及消解开展了研究，毛亿等[1]提出了一种空域冲突快速检测的方法，采用“由粗到精，逐步排除”的方法对空域时间、垂直方向、水平维度上逐步进行冲突检测；杨毅等[2]提出了基于栅格模型的大规模空域使用计划冲突检测与解脱方法，根据空域使用计划将空域栅格化并编码，建立空域网格内置属性并判断计划冲突空域；龚玮等[3]提出一种基于栅格模型的空域冲突检测解脱技术，对大量空域使用计划之间的空域冲突进行检测及解脱。
以上学者对空域使用冲突进行了研究，目前对于空域预先时间冲突的处理方法主要采用以甘特图为基础对作战任务时间区间进行逐一比对，从而发现时间冲突，这种方法具有计算效率低、计算不精确、复杂性低等缺点。而简单时间网络(simple temporal network，STN)是一种可以表示时间约束的模型，具有计算简便、使用灵活等特点，适用于对空域预先规划时间冲突的处理。
对STN的应用方面，也有许多学者进行了深入研究，汤罗浩[4]基于STN对行动计划时间的表示和冲突处理开展了研究，设计了迭代检测冲突和消解的CDR算法；李娟[5]提出并实现了一种基于STN的时间、空间、资源冲突检测和消解算法；李远等[6]提出了基于最小冲突集的冲突检测算法，在此基础上设计了基于最小承诺的冲突消解算法；谢斌等[7]设计了一种基于STN的任务在执行过程中资源冲突自动消解的方法。以上研究均以行动计划为背景，利用STN对计划时间进行了时间一致性检测及消解，为空域的时间冲突检测及消解提供了一种新的思路。
在制定空域使用计划时，对时间有很强的约束要求，首先需要在时间层面进行冲突检测和消解，而STN以图论形式满足时间约束来检测和消解空域之间的时间冲突，相比传统的时间冲突判断方法，具有计算快速的特点[8]。对此，本文提出基于STN对空域预先规划时间冲突处理。
2 空域预先规划时间建模
STN是一种针对计划执行的时间约束网络，基于空域的起始和结束时间、任务时间、活动执行顺序等要素，可以画出STN图[9]。在空域划设过程中，根据提交的空域使用需求，对空域添加时间约束，将空域使用转化为计划执行，得到基于空域使用需求的STN。STN由点时间变量集X和事件约束集C表示，X中的元素是各点时间变量，表示事件的开始/结束时刻，C由约束不等式构成，表示事件之间的时间约束关系。
STN中利用有向约束图G=(V，E)构成时间约束网络，网络中的顶点集合V表示点时间变量集，边集合E表示时间约束集[13]。顶点Xi和Xj连接的弧i→j表示时间约束Cij。i→j∈[l，u]表示事件Xi和事件Xj满足时间约束，l≤Xj-Xi≤u(l和u均为时间)表示Xj在Xi至少l后发生，且最多不超过u前发生。时间冲突检测实质是判断时间约束网络一致性，如果行动方案满足所有的时间约束，则称STN满足一致性，否则表明方案存在时间冲突。一般在处理过程中，将STN转化为STN距离图，即有向加权图Gd=(V，E)，将时间约束l≤Xj-Xi≤u转化为权值为u的弧Xi→Xj，以及权值为-l的弧Xj→Xi，更加便于计算，如图1所示。
图1 STN图与STN距离图的转换示意图
Fig.1 Conversion of STN map and STN distance map
2.1 预先规划时间约束网络表达
对空域时间冲突的处理，首先对空域使用计划进行系统性的表达，从用空行动的角度分析，空域使用计划可表示为：
式(1)中：N为空域名称(name)；O为用空目的(objective)；TC为时间约束(time constrain-t)；D为用空单位(department)；
为最小时间安全间隔(minimum safe time interva)。
在时间约束中，用时间点和时间区间来共同描述空域时间，时间点T表示在某一时刻或短时间内的空域内的用空行动，时间区间表示在一定时间范围内的用空行动，即空域的使用时间范围，时间区间I可由Is和If分别来表示空域使用时间的开始时刻和结束时刻。
为了便于计算需要将时间点和时间区间的定性约束关系转换为定量约束关系，如表1所示。
2.2 时间冲突检测流程
对空域使用时间进行冲突检测前，首先对空域使用计划和时间约束网络构建数学模型，以定量不等式的形式进行表示，并构建STN距离图。利用最短路径快速算法(shortest path faster algorithm，SPFA)算法对STN距离图进行负环检测，检测流程如图2所示。
表1 定性约束转换为定量约束
Table 1 Conversion of qualitative constraints to quantitative constraints
约束关系定量约束关系T1
图2 时间冲突检测流程框图
Fig.2 Time conflict detection process
在时间冲突检测中，首先制定空域使用计划，根据空域使用计划的要素，构建时间约束网络，即STN图，再将其转换为STN距离图，将时间冲突问题转化为图论的一致性检测问题，利用SPFA算法对STN距离图进行负环检测，若存在负环，则有向图中存在冲突，即空域使用计划存在时间冲突。
2.3 SPFA算法
最短路径快速算法(shortest path faster algorithm，SPFA)是求解单源最短路径的算法之一[9]，其原理是对图进行n-1次松弛(n为图中顶点数)，得到源点到所有顶点可能的最短路径，相较于常用的最短路径算法Bellman-ford和Dijkstra算法，SPFA算法可以在负权图中进行计算，缺点是时间复杂度更高[15]。SPFA算法用一个数组dis来记录各个结点的最短路径估计值，首先设立一个先进先出队列(FIFO)Q，每次优化时取出队首结点u，同时u点的最短路径估计值对离开u点所指向的结点v进行松弛，如果v点的最短路径估计值有变化，且v点不在此FIFO中，将v点放到队尾。以此类推，不断从队列中取结点进行松弛操作，直到队列为空时，停止操作。如果某个结点出队列的次数大于等于n次，则存在负环(n为图的顶点数)，SPFA算法检测流程如图3所示。
SPFA算法中的松弛和Bellman-ford算法中对同一个点的松弛一样，Bellman-ford算法是求解最短路径的算法，最短路径是一条路径必然不是一个环，在有V条边的有向图G=(V，E)中，路径的最大长度为V-1，因此当迭代次数大于等于V时，说明存在负权环，因此在SPFA算法中若某顶点出队次数大于等于n，则存在负权环。
图3 SPFA负环检测算法流程框图
Fig.3 SPFA negative loop detection algorithm flow
以图4为例，首先确定有向约束图G=(V，E)的源点s，将s赋值为0，其余顶点赋值为+∞，得到初始化数组dis(s=0，X1=+∞，X2=+∞，X3=+∞，X4=+∞)，同时将s加入队列Q中，此时Q={s}；继续之前的循环，第1次循环时，Q的队首元素出队列，即s出队列，对以s为弧顶的点进行松弛，s到X1，X2的最短路径缩小，更新数组dis(s=0，X1=-1，X2=4，X3=+∞，X4=+∞)，可以看到X1、X2之前不在队列Q中，将他们入队列，此时先入先出队列为Q={X1，X2}。
进入第2次循环，队首顶点X1出队列，对以X1为弧顶的点进行松弛，可以看到X1到X2、X3、X4的最短路径缩小，更新数组得到dis(s=0，X1=-1，X2=2，X3=1，X4=1)，同时X3、X4不在队列Q中，将其加入队列，此时先入先出队列为Q={X2，X3，X4}。
用上述方法不断迭代更新数组和队列，循环迭代至数组为dis(s=0，X1=-4，X2=-1，X3=-5，X4=-1)时，此时X2出队列5次，可以判断出图4存在负环X1→X2→X3→X1。
图4 有向约束示意图
Fig.4 Directed constrained graph
2.4 基于前驱节点数组的改进SPFA算法
2.3节中对SPFA算法的优点和算法流程进行了描述，在图3中通过记录顶点的出队次数判断图中是否存在负环，而在计算过程中有多次多余的入队操作，增加了计算的复杂性，没有及时输出负环判断结果。迭代循环输出数组dis是基于寻找最短路径来记录松弛变化的，而在负环检测方面可以定义一个记录各顶点的前驱节点数组pre，通过对该数组中的顶点关系进行描述来判断是否存在负环，当某顶点没有前驱节点时用-1表示，改进算法流程如图5所示。
图5 SPFA负环检测改进算法流程框图
Fig.5 SPFA negative loop detection improved algorithm flow
在图5中，第1次循环时s出队，数组为dis(s=0，X1=-1，X2=4，3=+∞，X4=+∞)，此时的前驱节点数组pre(s=-1，X1=0，X2=0，X3=-1，X4=-1)；第2次更新数组dis(s=0，X1=-1，X2=2，X3=1，X4=1)，此时pre(s=-1，X1=0，X2=1，X3=1，X4=1)，按照同样的方式松弛约束，到第4次循环时X3出队，此时的数组更新为dis(s=0，X1=-2，X2=2，X3=-3，X4=1)，前驱节点数组更新为 pre(s=-1，X1=3，X2=1，X3=2，X4=1)，此时出现死循环，即可判断图中存在负环X1→X2→X3→X1。
相较普通的SPFA算法，本节提出的方法通过4次循环中就找到了负环，大大提升了计算效率，减少了不必要的入队和出队操作。
3 时间冲突消解
3.1 负环消解流程
在STN图中出现负环后需要对负环进行消解，由于出现负环意味着存在时间冲突，因此对负环进行消解的过程就是调整时间约束的过程。
调整约束包括松弛约束、加紧约束、删减约束、添加约束；加紧约束和添加约束会使约束程度更高，不适用于空域时间的冲突消解方面。删减约束是极端的松弛约束，以删除部分约束来达成时间一致性，但同时会影响任务的完整性。因此，利用松弛约束对负环进行消解。
在列出了某作战行动的各类时间约束后，在对任务完成影响最小的前提下进行松弛约束，对约束添加代价系数ki，表示调整该约束需要付出的代价，再按照优先选择代价最小的约束进行松弛。
3.2 基于最小代价的负环消解
在STN负环的消解中，将负环权值-d加上权重d可以消解负环，但会导致事件发生的时间相对固定，缺少了STN图的灵活性，因此对负环权值-d加上权重d+σ(σ>0)，σ为灵活因子[16]。
对权值为负的弧进行松弛约束时，不能将其权值调整为正值，例如权值为a(a<0)的弧i→j表示事件i在事件j后a个单位时间发生，若对权值进行调整使得a>0则表示i先于j至少a个单位时间发生，变换了事件的发生顺序，因此对权值为负的弧进行调整时，不能使其权值大于0。
不同约束有着不同的含义，其优先程度也不同，对此给每条约束添加重要程度系数impi，表示该约束的重要程度，调整优先权prioi表示调整约束的优先程度。prioi=0时，该约束不允许调整。同时设置
(k为大于0的常数)，表示随着调整次数的增多，调整优先级会降低。
综上所述，可得到调整代价函数为：
式(2)中：Δli表示约束的变化量；ki为代价系数。
对由n条弧构成的负环进行消解时，基于最小代价的目标函数为：
式(3)中，
即约束的调整量为d+σ并且在调整后负弧的权值不得大于0。
检测到负环后采用贪心算法，寻找代价最小的约束尽可能大的增加权值，到其无法增加后寻找代价次小的约束进行调整，直到负环消解，基于最小代价的负环消解算法流程如图6所示。
图6 基于最小代价的负环消解算法流程框图
Fig.6 Negative loop digestion process based on minimum cost
4 实例分析
某年某月某日，开展远程火力打击训练任务，1编队担负火力突击任务，2编队担负空中加油任务，3编队担负对目标区域空情侦察任务，4编队担负拦截敌突击任务。区域A为敌入侵空域，区域B为我方拦截空域，区域C为我方机场空域。打击训练任务流程如图7所示。
图7 打击训练任务流程示意图
Fig.7 Combat training task flow chart
任务流程为：上午8时，3编队前往区域A对敌空中力量进行侦察，侦察完毕后返回并上传情报，4编队接收情报后向区域B进行拦截攻击，4编队拦截结束后，2编队由区域C前往区域B，同时1编队由区域C前往区域B加油，完成加油后 1编队前往区域C对目标进行火力突击，规定8时32分前完成任务。
根据上述任务流程得到时间约束,见表2。
表2 任务时间约束
Table 2 Task time constraint table
约束类型时间约束期限时间约束C1:任务总完成时间不超过32 min持 续 时 间 约 束C2:3编队到达目的地需要5～8 minC3:3编队侦察需要6～9 minC4:3编队上传情报需3～4 minC5:4编队架设需5～8 minC6:4编队拦截目标需6～7 minC7:2编队前往加油区需8～10 minC8:2编队给1编队加油需5～7 minC9:1编队前往加油区需3～5 minC10:1编队前往打击目标区需6～10 minC11:1编队完成打击需1～2 min先后约束C12:4编队在3编队上传情报后开始拦截C13:1编队在完成加油后前往目标区域
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图
Fig.8 Training task STN graph
训练任务STN距离图如图9所示，用SPFA改进算法对图8进行一致性检测，检测发现该网络图存在负环(见图9中红色虚线部分)。该任务完成时间为33 min与任务计划在32 min内完成矛盾，因此出现负环。
图9 训练任务STN距离图
Fig.9 Training task STN distance map
对案例添加代价系数如表3所示。
表3 任务时间约束代价系数
Table 3 Task time constraint cost coefficient
约束类型时间约束松弛代价系数ki期限时间约束C1:任务总完成时间不超过32 min10持 续 时 间 约 束C2:3编队到达目的地需5～8 min4C3:3编队侦察需6～9 min6C4:3编队上传情报需3～4 min7C5:4编队架设需5～8 min7C6:4编队拦截目标需6～7 min8C7:2编队前往加油区需8～10 min3C8:2编队给1编队加油需5-7 min5C9:1编队前往加油区需3～5 min4C10:1编队前往打击目标区需6～10 min7C11:1编队完成打击需1～2 min∞先后约束C12:4编队在3编队上传情报后开始拦截∞C13:1编队在完成加油后前往目标区域5
对负环消解前列出负环包含的约束，图9中包含的约束为C1、C2、C3、C4、C6、C7、C8、C10、C11，其中C11不可调整，其余约束根据式(2)计算出调整代价COSTi。约束中代价系数最小的为k7=3，计算出其调整代价为COST7=3·(1+σ)，此处σ=1。
故对C7进行松弛调整，对其负弧权值加2，此时消解冲突的同时保证调整代价最小。对负环进行消解后其消解冲突结果如图10所示。
对图10结果再次进行负环检测，结果不存在负环，即时间冲突得到消解。
图10 消解冲突结果示意图
Fig.10 Resolve conflict results
5 结论
1) 提出基于STN图的空域预先规划时间冲突处理方法，对空域预先规划时间约束进行建模，用STN时间约束网络图进行表达，提高了冲突处理的科学性；
2) 提出了基于前驱节点的改进SPFA算法，在负环检测过程中减少了不必要的循环，提高了计算效率并通过SPFA改进算法对时间约束网络进行一致性检测，检测空域使用计划是否存在时间冲突；
3) 采用基于最小代价的方法对时间冲突进行消解，并通过对案例的分析证明了方法的可行性。
4) 结合图论相关内容对空域预先规划时间冲突处理问题进行研究，提供了一种新的研究思路和方法。后续将针对联合作战的特点进行研究。
[1] 毛亿.战术空域管理技术研究[D].南京：南京航空航天大学，2018.
Mao Y.Research on technologies of tactical airspace management[D].Nanjing University of Aeronautics and Astronautics，2018.
[2] 杨毅，丁洋，严勇杰，等.基于栅格模型的大规模空域使用计划冲突检测与解脱方法[P].中国CN111477034B，2021-01-29.
Yang Y，Ding Y，Yan Y J，et al.Conflict detection and relief method for large-scale airspace use plan based on grid model[P].CN111477034B，2021-01-29.
[3] 龚玮，陶德进，闫嘉明.基于栅格模型的空域冲突检测解脱技术研究[J].信息化研究，2021，47(03)：46-50.
Gong W，Tao D J，Yan J M.Research on airspace conflict detection and release technology based on grid-model[J].Informatization Research，2021，47(03)：46-50.
[4] 汤罗浩.基于STN的行动计划时间表示和冲突处理研究[D].长沙：国防科学技术大学，2010.
Tang L H.Research on time representation and conflict handling of action plan based on STN[D].National University of Defense Technology，2010.
[5] 李娟.冲突检测和消解算法的研究与实现[D].北京：北京理工大学，2016.
Li J.The Research and implementation Conflict detection and resolution[D].Beijing Institute of Technology，2016.
[6] 李远，彭辉，沈林成.协同任务规划中基于约束满足的资源冲突检测与消解[J].系统工程与电子技术，2009，31(04)：868-873.
Li Y，Peng H，Shen L C.Constraint satisfaction based resource conflicts detection and resolutionin collaborative mission planning[J].Systems Engineering and Electronics，2009，31(04)：868-873.
[7] 谢斌，林华，邢昌风.基于STN的任务执行过程中的资源冲突自动消解[J].火力与指挥控制，2015，40(06)：48-51，56.
Xie B，Lin H，Xing C F.Autom atic resource conflict resolution in process of task execution based on STN[J].Fire Control&Command Control，2015，40(06)：48-51，56.
[8] Moffitt M D，Pollack M E.Partial constraint satisfaction of disjunctive temporal problems[C]//Proceedings of the Eighteenth International Florida Artificial Intelligence Research Society Conference，Clearwater Beach，Florida，USA.DBLP，2005.
[9] Smith S F，Cortellessa G，Hildum D W，et al.Using a scheduling domain ontology to compute user-oriented explanations[C]//Castillo L，Borrajo D，Salido M A，et al.Planning，Scheduling，and Constraint Satisfaction：From Theory to Practice，IOS Press，2005.
[10]Bresina J，Morris P.Explanations and recommendationsfor temporal inconsistencies[EB/OL].https：//www.researchgate.net/publication/228994604，2022-01-19.
[11]Zhou X.An improved SPFA algorithm for single-source shortest path problem using forward star data structure full text[J].International Journal of Managing Information Technology(IJMIT)，2014，6(01)：15-21.
[12]Cesta A，Oddi A，Smith S F.Scheduling multicapacitated resources under complex temporal constraints[C]//Proceedings of 4th International Conference on Principles and Practice of Constraint Programming.London：Springer-Verlag，1998.
[13]Ramalingam G，Song J，Joskowicz L，et al.Solving systems of difference constraints incrementally[J].Algorithmica，1999，23(03)：261-275.
[14]Cherkassky B V，Georgiadis L，Goldberg A，et al.Shortest-Path Feasibility Algorithms：An Experimental Evaluation[J].ACM Journal of Experimental Algorithmics，2009(14)：118-132.
[15]Schwalb E，Dechter R.Processing disjunctions in temporal constraint networks[J].Eddie Schwalb，Rina Dechter.Artificial Intelligence，1997，93(01)：29-62.
[16]Kennell J，Williams B C，Smith A C.Generative temporal planning with complex processes[D].Cambridge，CA：Department of Electrical Engineering and Computer Science，Massach usetts Institute of Technology，2003.
[17]安籽鹏，李锋，万刚，等.基于时间约束网的作战行动时间冲突检测[J].系统仿真学报，2017，29(S1)：167-172.
An Z P，Li F，Wan G，et al.Research on operational time conflict detection based on temporal constraint network[J].Journal of System Simulation，2017，29(S1)：167-172.