空域預(yù)先規(guī)劃時(shí)間的沖突處理方法研究

高志周，萬路軍，鐘 赟，蔡 明，徐鑫宇

(1.空軍工程大學(xué) 空管領(lǐng)航學(xué)院， 西安 710051； 2.空軍工程大學(xué) 裝備管理與無人機(jī)工程學(xué)院， 西安 710051； 3.中國人民解放軍94040部隊(duì)， 新疆 庫爾勒 841000)

1 引言

空域的使用需要在嚴(yán)格的時(shí)間約束下執(zhí)行，但在劃設(shè)空域過程中，由于作戰(zhàn)任務(wù)需求不同，同時(shí)受到惡劣天氣、環(huán)境變化的影響，空域使用需求會在時(shí)間上產(chǎn)生沖突，從而造成作戰(zhàn)任務(wù)的沖突。為保證空域使用安全，需要對空域時(shí)間進(jìn)行約束。

當(dāng)前，眾多學(xué)者對空域沖突檢測及消解開展了研究，毛億等提出了一種空域沖突快速檢測的方法，采用“由粗到精，逐步排除”的方法對空域時(shí)間、垂直方向、水平維度上逐步進(jìn)行沖突檢測；楊毅等提出了基于柵格模型的大規(guī)?？沼蚴褂糜?jì)劃沖突檢測與解脫方法，根據(jù)空域使用計(jì)劃將空域柵格化并編碼，建立空域網(wǎng)格內(nèi)置屬性并判斷計(jì)劃沖突空域；龔瑋等提出一種基于柵格模型的空域沖突檢測解脫技術(shù)，對大量空域使用計(jì)劃之間的空域沖突進(jìn)行檢測及解脫。

以上學(xué)者對空域使用沖突進(jìn)行了研究，目前對于空域預(yù)先時(shí)間沖突的處理方法主要采用以甘特圖為基礎(chǔ)對作戰(zhàn)任務(wù)時(shí)間區(qū)間進(jìn)行逐一比對，從而發(fā)現(xiàn)時(shí)間沖突，這種方法具有計(jì)算效率低、計(jì)算不精確、復(fù)雜性低等缺點(diǎn)。而簡單時(shí)間網(wǎng)絡(luò)(simple temporal network，STN)是一種可以表示時(shí)間約束的模型，具有計(jì)算簡便、使用靈活等特點(diǎn)，適用于對空域預(yù)先規(guī)劃時(shí)間沖突的處理。

對STN的應(yīng)用方面，也有許多學(xué)者進(jìn)行了深入研究，湯羅浩基于STN對行動(dòng)計(jì)劃時(shí)間的表示和沖突處理開展了研究，設(shè)計(jì)了迭代檢測沖突和消解的CDR算法；李娟提出并實(shí)現(xiàn)了一種基于STN的時(shí)間、空間、資源沖突檢測和消解算法；李遠(yuǎn)等提出了基于最小沖突集的沖突檢測算法，在此基礎(chǔ)上設(shè)計(jì)了基于最小承諾的沖突消解算法；謝斌等設(shè)計(jì)了一種基于STN的任務(wù)在執(zhí)行過程中資源沖突自動(dòng)消解的方法。以上研究均以行動(dòng)計(jì)劃為背景，利用STN對計(jì)劃時(shí)間進(jìn)行了時(shí)間一致性檢測及消解，為空域的時(shí)間沖突檢測及消解提供了一種新的思路。

在制定空域使用計(jì)劃時(shí)，對時(shí)間有很強(qiáng)的約束要求，首先需要在時(shí)間層面進(jìn)行沖突檢測和消解，而STN以圖論形式滿足時(shí)間約束來檢測和消解空域之間的時(shí)間沖突，相比傳統(tǒng)的時(shí)間沖突判斷方法，具有計(jì)算快速的特點(diǎn)。對此，本文提出基于STN對空域預(yù)先規(guī)劃時(shí)間沖突處理。

2 空域預(yù)先規(guī)劃時(shí)間建模

STN是一種針對計(jì)劃執(zhí)行的時(shí)間約束網(wǎng)絡(luò)，基于空域的起始和結(jié)束時(shí)間、任務(wù)時(shí)間、活動(dòng)執(zhí)行順序等要素，可以畫出STN圖。在空域劃設(shè)過程中，根據(jù)提交的空域使用需求，對空域添加時(shí)間約束，將空域使用轉(zhuǎn)化為計(jì)劃執(zhí)行，得到基于空域使用需求的STN。STN由點(diǎn)時(shí)間變量集和事件約束集表示，中的元素是各點(diǎn)時(shí)間變量，表示事件的開始結(jié)束時(shí)刻，由約束不等式構(gòu)成，表示事件之間的時(shí)間約束關(guān)系。

STN中利用有向約束圖=(，)構(gòu)成時(shí)間約束網(wǎng)絡(luò)，網(wǎng)絡(luò)中的頂點(diǎn)集合表示點(diǎn)時(shí)間變量集，邊集合表示時(shí)間約束集。頂點(diǎn)和連接的弧→表示時(shí)間約束?！蔥，]表示事件和事件滿足時(shí)間約束，≤-≤(和均為時(shí)間)表示在至少后發(fā)生，且最多不超過前發(fā)生。時(shí)間沖突檢測實(shí)質(zhì)是判斷時(shí)間約束網(wǎng)絡(luò)一致性，如果行動(dòng)方案滿足所有的時(shí)間約束，則稱STN滿足一致性，否則表明方案存在時(shí)間沖突。一般在處理過程中，將STN轉(zhuǎn)化為STN距離圖，即有向加權(quán)圖=(，)，將時(shí)間約束≤-≤轉(zhuǎn)化為權(quán)值為的弧→，以及權(quán)值為-的弧→，更加便于計(jì)算，如圖1所示。

圖1 STN圖與STN距離圖的轉(zhuǎn)換示意圖

2.1 預(yù)先規(guī)劃時(shí)間約束網(wǎng)絡(luò)表達(dá)

對空域時(shí)間沖突的處理，首先對空域使用計(jì)劃進(jìn)行系統(tǒng)性的表達(dá)，從用空行動(dòng)的角度分析，空域使用計(jì)劃可表示為：

在時(shí)間約束中，用時(shí)間點(diǎn)和時(shí)間區(qū)間來共同描述空域時(shí)間，時(shí)間點(diǎn)表示在某一時(shí)刻或短時(shí)間內(nèi)的空域內(nèi)的用空行動(dòng)，時(shí)間區(qū)間表示在一定時(shí)間范圍內(nèi)的用空行動(dòng)，即空域的使用時(shí)間范圍，時(shí)間區(qū)間可由和分別來表示空域使用時(shí)間的開始時(shí)刻和結(jié)束時(shí)刻。

為了便于計(jì)算需要將時(shí)間點(diǎn)和時(shí)間區(qū)間的定性約束關(guān)系轉(zhuǎn)換為定量約束關(guān)系，如表1所示。

2.2 時(shí)間沖突檢測流程

對空域使用時(shí)間進(jìn)行沖突檢測前，首先對空域使用計(jì)劃和時(shí)間約束網(wǎng)絡(luò)構(gòu)建數(shù)學(xué)模型，以定量不等式的形式進(jìn)行表示，并構(gòu)建STN距離圖。利用最短路徑快速算法(shortest path faster algorithm，SPFA)算法對STN距離圖進(jìn)行負(fù)環(huán)檢測，檢測流程如圖2所示。

表1 定性約束轉(zhuǎn)換為定量約束

圖2 時(shí)間沖突檢測流程框圖

在時(shí)間沖突檢測中，首先制定空域使用計(jì)劃，根據(jù)空域使用計(jì)劃的要素，構(gòu)建時(shí)間約束網(wǎng)絡(luò)，即STN圖，再將其轉(zhuǎn)換為STN距離圖，將時(shí)間沖突問題轉(zhuǎn)化為圖論的一致性檢測問題，利用SPFA算法對STN距離圖進(jìn)行負(fù)環(huán)檢測，若存在負(fù)環(huán)，則有向圖中存在沖突，即空域使用計(jì)劃存在時(shí)間沖突。

2.3 SPFA算法

最短路徑快速算法(shortest path faster algorithm，SPFA)是求解單源最短路徑的算法之一，其原理是對圖進(jìn)行-1次松弛(為圖中頂點(diǎn)數(shù))，得到源點(diǎn)到所有頂點(diǎn)可能的最短路徑，相較于常用的最短路徑算法Bellman-ford和Dijkstra算法，SPFA算法可以在負(fù)權(quán)圖中進(jìn)行計(jì)算，缺點(diǎn)是時(shí)間復(fù)雜度更高。SPFA算法用一個(gè)數(shù)組來記錄各個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，首先設(shè)立一個(gè)先進(jìn)先出隊(duì)列(FIFO)，每次優(yōu)化時(shí)取出隊(duì)首結(jié)點(diǎn)，同時(shí)點(diǎn)的最短路徑估計(jì)值對離開點(diǎn)所指向的結(jié)點(diǎn)進(jìn)行松弛，如果點(diǎn)的最短路徑估計(jì)值有變化，且點(diǎn)不在此FIFO中，將點(diǎn)放到隊(duì)尾。以此類推，不斷從隊(duì)列中取結(jié)點(diǎn)進(jìn)行松弛操作，直到隊(duì)列為空時(shí)，停止操作。如果某個(gè)結(jié)點(diǎn)出隊(duì)列的次數(shù)大于等于次，則存在負(fù)環(huán)(為圖的頂點(diǎn)數(shù))，SPFA算法檢測流程如圖3所示。

SPFA算法中的松弛和Bellman-ford算法中對同一個(gè)點(diǎn)的松弛一樣，Bellman-ford算法是求解最短路徑的算法，最短路徑是一條路徑必然不是一個(gè)環(huán)，在有條邊的有向圖=(，)中，路徑的最大長度為-1，因此當(dāng)?shù)螖?shù)大于等于時(shí)，說明存在負(fù)權(quán)環(huán)，因此在SPFA算法中若某頂點(diǎn)出隊(duì)次數(shù)大于等于，則存在負(fù)權(quán)環(huán)。

圖3 SPFA負(fù)環(huán)檢測算法流程框圖

以圖4為例，首先確定有向約束圖=(，)的源點(diǎn)，將賦值為0，其余頂點(diǎn)賦值為+∞，得到初始化數(shù)組(=0，=+∞，=+∞，=+∞，=+∞)，同時(shí)將加入隊(duì)列中，此時(shí)={}；繼續(xù)之前的循環(huán)，第1次循環(huán)時(shí)，的隊(duì)首元素出隊(duì)列，即出隊(duì)列，對以為弧頂?shù)狞c(diǎn)進(jìn)行松弛，到，的最短路徑縮小，更新數(shù)組(=0，=-1，=4，=+∞，=+∞)，可以看到、之前不在隊(duì)列中，將他們?nèi)腙?duì)列，此時(shí)先入先出隊(duì)列為={，}。

進(jìn)入第2次循環(huán)，隊(duì)首頂點(diǎn)出隊(duì)列，對以為弧頂?shù)狞c(diǎn)進(jìn)行松弛，可以看到到、、的最短路徑縮小，更新數(shù)組得到(=0，=-1，=2，=1，=1)，同時(shí)、不在隊(duì)列中，將其加入隊(duì)列，此時(shí)先入先出隊(duì)列為={，，}。

用上述方法不斷迭代更新數(shù)組和隊(duì)列，循環(huán)迭代至數(shù)組為(=0，=-4，=-1，=-5，=-1)時(shí)，此時(shí)出隊(duì)列5次，可以判斷出圖4存在負(fù)環(huán)→→→。

圖4 有向約束示意圖

2.4 基于前驅(qū)節(jié)點(diǎn)數(shù)組的改進(jìn)SPFA算法

2.3節(jié)中對SPFA算法的優(yōu)點(diǎn)和算法流程進(jìn)行了描述，在圖3中通過記錄頂點(diǎn)的出隊(duì)次數(shù)判斷圖中是否存在負(fù)環(huán)，而在計(jì)算過程中有多次多余的入隊(duì)操作，增加了計(jì)算的復(fù)雜性，沒有及時(shí)輸出負(fù)環(huán)判斷結(jié)果。迭代循環(huán)輸出數(shù)組是基于尋找最短路徑來記錄松弛變化的，而在負(fù)環(huán)檢測方面可以定義一個(gè)記錄各頂點(diǎn)的前驅(qū)節(jié)點(diǎn)數(shù)組，通過對該數(shù)組中的頂點(diǎn)關(guān)系進(jìn)行描述來判斷是否存在負(fù)環(huán)，當(dāng)某頂點(diǎn)沒有前驅(qū)節(jié)點(diǎn)時(shí)用-1表示，改進(jìn)算法流程如圖5所示。

圖5 SPFA負(fù)環(huán)檢測改進(jìn)算法流程框圖

在圖5中，第1次循環(huán)時(shí)出隊(duì)，數(shù)組為(=0，=-1，=4，=+∞，=+∞)，此時(shí)的前驅(qū)節(jié)點(diǎn)數(shù)組(=-1，=0，=0，=-1，=-1)；第2次更新數(shù)組(=0，=-1，=2，=1，=1)，此時(shí)(=-1，=0，=1，=1，=1)，按照同樣的方式松弛約束，到第4次循環(huán)時(shí)出隊(duì)，此時(shí)的數(shù)組更新為(=0，=-2，=2，=-3，=1)，前驅(qū)節(jié)點(diǎn)數(shù)組更新為(=-1，=3，=1，=2，=1)，此時(shí)出現(xiàn)死循環(huán)，即可判斷圖中存在負(fù)環(huán)→→→。

相較普通的SPFA算法，本節(jié)提出的方法通過4次循環(huán)中就找到了負(fù)環(huán)，大大提升了計(jì)算效率，減少了不必要的入隊(duì)和出隊(duì)操作。

3 時(shí)間沖突消解

3.1 負(fù)環(huán)消解流程

在STN圖中出現(xiàn)負(fù)環(huán)后需要對負(fù)環(huán)進(jìn)行消解，由于出現(xiàn)負(fù)環(huán)意味著存在時(shí)間沖突，因此對負(fù)環(huán)進(jìn)行消解的過程就是調(diào)整時(shí)間約束的過程。

調(diào)整約束包括松弛約束、加緊約束、刪減約束、添加約束；加緊約束和添加約束會使約束程度更高，不適用于空域時(shí)間的沖突消解方面。刪減約束是極端的松弛約束，以刪除部分約束來達(dá)成時(shí)間一致性，但同時(shí)會影響任務(wù)的完整性。因此，利用松弛約束對負(fù)環(huán)進(jìn)行消解。

在列出了某作戰(zhàn)行動(dòng)的各類時(shí)間約束后，在對任務(wù)完成影響最小的前提下進(jìn)行松弛約束，對約束添加代價(jià)系數(shù)，表示調(diào)整該約束需要付出的代價(jià)，再按照優(yōu)先選擇代價(jià)最小的約束進(jìn)行松弛。

3.2 基于最小代價(jià)的負(fù)環(huán)消解

在負(fù)環(huán)的消解中，將負(fù)環(huán)權(quán)值-加上權(quán)重可以消解負(fù)環(huán)，但會導(dǎo)致事件發(fā)生的時(shí)間相對固定，缺少了STN圖的靈活性，因此對負(fù)環(huán)權(quán)值-加上權(quán)重+(>0)，為靈活因子。

對權(quán)值為負(fù)的弧進(jìn)行松弛約束時(shí)，不能將其權(quán)值調(diào)整為正值，例如權(quán)值為(<0)的弧→表示事件在事件后個(gè)單位時(shí)間發(fā)生，若對權(quán)值進(jìn)行調(diào)整使得>0則表示先于至少個(gè)單位時(shí)間發(fā)生，變換了事件的發(fā)生順序，因此對權(quán)值為負(fù)的弧進(jìn)行調(diào)整時(shí)，不能使其權(quán)值大于0。

綜上所述，可得到調(diào)整代價(jià)函數(shù)為：

式(2)中：Δ表示約束的變化量；為代價(jià)系數(shù)。

對由條弧構(gòu)成的負(fù)環(huán)進(jìn)行消解時(shí)，基于最小代價(jià)的目標(biāo)函數(shù)為：

檢測到負(fù)環(huán)后采用貪心算法，尋找代價(jià)最小的約束盡可能大的增加權(quán)值，到其無法增加后尋找代價(jià)次小的約束進(jìn)行調(diào)整，直到負(fù)環(huán)消解，基于最小代價(jià)的負(fù)環(huán)消解算法流程如圖6所示。

圖6 基于最小代價(jià)的負(fù)環(huán)消解算法流程框圖

4 實(shí)例分析

某年某月某日，開展遠(yuǎn)程火力打擊訓(xùn)練任務(wù)，1編隊(duì)擔(dān)負(fù)火力突擊任務(wù)，2編隊(duì)擔(dān)負(fù)空中加油任務(wù)，3編隊(duì)擔(dān)負(fù)對目標(biāo)區(qū)域空情偵察任務(wù)，4編隊(duì)擔(dān)負(fù)攔截?cái)惩粨羧蝿?wù)。區(qū)域A為敵入侵空域，區(qū)域B為我方攔截空域，區(qū)域C為我方機(jī)場空域。打擊訓(xùn)練任務(wù)流程如圖7所示。

圖7 打擊訓(xùn)練任務(wù)流程示意圖

任務(wù)流程為：上午8時(shí)，3編隊(duì)前往區(qū)域A對敵空中力量進(jìn)行偵察，偵察完畢后返回并上傳情報(bào)，4編隊(duì)接收情報(bào)后向區(qū)域B進(jìn)行攔截攻擊，4編隊(duì)攔截結(jié)束后，2編隊(duì)由區(qū)域C前往區(qū)域B，同時(shí)1編隊(duì)由區(qū)域C前往區(qū)域B加油，完成加油后 1編隊(duì)前往區(qū)域C對目標(biāo)進(jìn)行火力突擊，規(guī)定8時(shí)32分前完成任務(wù)。

根據(jù)上述任務(wù)流程得到時(shí)間約束,見表2。

表2 任務(wù)時(shí)間約束

1編隊(duì)前往加油區(qū)需要3～5 min，加油過程需要5～7 min，加油完成后到達(dá)目標(biāo)區(qū)域需要6～10 min，完成對目標(biāo)的攻擊需要1～2 min，2編隊(duì)前往加油區(qū)需要8～10 min，加油過程需要5～7 min，3編隊(duì)到達(dá)指定區(qū)域需要5～8 min，偵察過程需要6～9 min，發(fā)現(xiàn)敵方并上傳情報(bào)需要3～4 min，4編隊(duì)準(zhǔn)備架設(shè)需要5～8 min，實(shí)施攔截需要6～7 min。整個(gè)行動(dòng)時(shí)間不得超過35 min。打擊行動(dòng)的STN圖如圖8所示。

圖8 訓(xùn)練任務(wù)STN圖

訓(xùn)練任務(wù)STN距離圖如圖9所示，用SPFA改進(jìn)算法對圖8進(jìn)行一致性檢測，檢測發(fā)現(xiàn)該網(wǎng)絡(luò)圖存在負(fù)環(huán)(見圖9中紅色虛線部分)。該任務(wù)完成時(shí)間為33 min與任務(wù)計(jì)劃在32 min內(nèi)完成矛盾，因此出現(xiàn)負(fù)環(huán)。

圖9 訓(xùn)練任務(wù)STN距離圖

對案例添加代價(jià)系數(shù)如表3所示。

表3 任務(wù)時(shí)間約束代價(jià)系數(shù)

對負(fù)環(huán)消解前列出負(fù)環(huán)包含的約束，圖9中包含的約束為、、、、、、、、，其中不可調(diào)整，其余約束根據(jù)式(2)計(jì)算出調(diào)整代價(jià)。約束中代價(jià)系數(shù)最小的為=3，計(jì)算出其調(diào)整代價(jià)為=3·(1+)，此處=1。

故對進(jìn)行松弛調(diào)整，對其負(fù)弧權(quán)值加2，此時(shí)消解沖突的同時(shí)保證調(diào)整代價(jià)最小。對負(fù)環(huán)進(jìn)行消解后其消解沖突結(jié)果如圖10所示。

對圖10結(jié)果再次進(jìn)行負(fù)環(huán)檢測，結(jié)果不存在負(fù)環(huán)，即時(shí)間沖突得到消解。

圖10 消解沖突結(jié)果示意圖

5 結(jié)論

1) 提出基于STN圖的空域預(yù)先規(guī)劃時(shí)間沖突處理方法，對空域預(yù)先規(guī)劃時(shí)間約束進(jìn)行建模，用STN時(shí)間約束網(wǎng)絡(luò)圖進(jìn)行表達(dá)，提高了沖突處理的科學(xué)性；

2) 提出了基于前驅(qū)節(jié)點(diǎn)的改進(jìn)SPFA算法，在負(fù)環(huán)檢測過程中減少了不必要的循環(huán)，提高了計(jì)算效率并通過SPFA改進(jìn)算法對時(shí)間約束網(wǎng)絡(luò)進(jìn)行一致性檢測，檢測空域使用計(jì)劃是否存在時(shí)間沖突；

3) 采用基于最小代價(jià)的方法對時(shí)間沖突進(jìn)行消解，并通過對案例的分析證明了方法的可行性。

4) 結(jié)合圖論相關(guān)內(nèi)容對空域預(yù)先規(guī)劃時(shí)間沖突處理問題進(jìn)行研究，提供了一種新的研究思路和方法。后續(xù)將針對聯(lián)合作戰(zhàn)的特點(diǎn)進(jìn)行研究。