胡忠凱，黃炎焱

（南京理工大學(xué)自動(dòng)化學(xué)院，南京 210094）

0 引言

兩棲兵力投送是兩棲登陸作戰(zhàn)中最關(guān)鍵、最激烈、最復(fù)雜的階段，如何保證兩棲兵力投送任務(wù)的順利執(zhí)行是備受關(guān)注的重點(diǎn)與難點(diǎn)。時(shí)間協(xié)同規(guī)劃是兩棲兵力投送任務(wù)規(guī)劃中的重要組成部分，通過時(shí)間協(xié)同規(guī)劃保證兩棲兵力投送任務(wù)行動(dòng)在時(shí)間上的協(xié)調(diào)統(tǒng)一、互不沖突。STN 是構(gòu)建兩棲兵力投送任務(wù)模型與時(shí)間協(xié)同規(guī)劃沖突檢測與消解的基礎(chǔ)。Dechter 在Artificial Intelligence 雜志上提出時(shí)間約束網(wǎng)的理論，Ghallab 等利用簡單時(shí)間網(wǎng)絡(luò)對(duì)規(guī)劃進(jìn)行建模解決時(shí)間約束沖突問題。國內(nèi)學(xué)者也對(duì)簡單時(shí)間網(wǎng)絡(luò)在作戰(zhàn)任務(wù)上的應(yīng)用開展了進(jìn)一步的研究。謝斌等從時(shí)間角度出發(fā)，設(shè)計(jì)了一種基于STN 的、在執(zhí)行過程中自動(dòng)消解資源沖突的方法，并證明了該法的可行性。張華提出了一種基于STN 表示的作戰(zhàn)任務(wù)時(shí)間沖突檢測方法，并對(duì)任務(wù)時(shí)間規(guī)劃提供參考范圍。張道萍等采用時(shí)間網(wǎng)絡(luò)圖描述作戰(zhàn)行動(dòng)，設(shè)計(jì)了一種基于關(guān)鍵任務(wù)的時(shí)間沖突消解方法，對(duì)作戰(zhàn)任務(wù)的時(shí)間沖突進(jìn)行消解。本文在利用簡單時(shí)間網(wǎng)絡(luò)對(duì)兩棲兵力投送任務(wù)建模的基礎(chǔ)上，對(duì)時(shí)間規(guī)劃進(jìn)行沖突檢測與消解，得到合理的兩棲兵力投送任務(wù)時(shí)間協(xié)同規(guī)劃。

1 兩棲兵力投送任務(wù)建模

1.1 STN

時(shí)間點(diǎn)以及時(shí)間區(qū)間是描述行為的一種方式。時(shí)間點(diǎn)用于表示在發(fā)生一瞬間的行為；時(shí)間區(qū)間用于表示具有一定持續(xù)時(shí)間的行為，也可以轉(zhuǎn)化為開始時(shí)刻和結(jié)束時(shí)刻的兩個(gè)時(shí)間點(diǎn)。

圖1 是將一定的簡單時(shí)間約束等價(jià)轉(zhuǎn)化為相應(yīng)STN 的例子。

圖1 簡單時(shí)間約束及STN

在簡單時(shí)間約束問題中，當(dāng)時(shí)間變量集合至少存在一組滿足所有時(shí)間約束的值時(shí)，則稱STN 是一致的，即任務(wù)規(guī)劃滿足相應(yīng)的時(shí)間約束，該規(guī)劃是合理的。

如圖2 所示，將圖1 中的STN 等價(jià)轉(zhuǎn)化成相應(yīng)的距離圖。

圖2 距離圖

1.2 兩棲兵力投送任務(wù)STN 模型

1.2.1 兩棲兵力投送任務(wù)分解

兩棲兵力投送過程具有多編隊(duì)、多波次的特點(diǎn)。兩棲兵力投送采用氣墊登陸艇、兩棲突擊車和武裝直升機(jī)等多種載具相結(jié)合的多編隊(duì)兵力投送方式，極大地提高了作戰(zhàn)效能與打擊能力；兩棲兵力投送過程中兵力需要根據(jù)作戰(zhàn)任務(wù)分多個(gè)波次上陸，一方面需要保證異波編隊(duì)攻擊的持續(xù)性，但又要避免各波次間作戰(zhàn)單位的相互影響；另一方面需要確保同波編隊(duì)聚力突襲的同時(shí)性，沖灘上陸力量形成強(qiáng)大的沖擊合力，迅速建立起登陸方的優(yōu)勢，也就是說一個(gè)波次內(nèi)的兵力要求在同一時(shí)間上陸。

對(duì)兩棲兵力投送總?cè)蝿?wù)中進(jìn)行合理分解，構(gòu)建時(shí)間約束網(wǎng)絡(luò)。在兩棲兵力投送過程中包含著多個(gè)波次任務(wù)，在每個(gè)波次任務(wù)中又有不同的編隊(duì)任務(wù)，任務(wù)分解如圖3 所示。

圖3 兩棲兵力投送任務(wù)分解

1.2.2 多波次任務(wù)STN 模型

圖4 多波次任務(wù)STN

兩棲兵力投送總?cè)蝿?wù)開始時(shí)間節(jié)點(diǎn)為T，總?cè)蝿?wù)結(jié)束時(shí)間節(jié)點(diǎn)為T，各個(gè)波次上陸任務(wù)開始與結(jié)束時(shí)間節(jié)點(diǎn)分別為T和T。由于總?cè)蝿?wù)結(jié)束與第3波次任務(wù)結(jié)束為同一個(gè)時(shí)間點(diǎn)，可以用T代替總?cè)蝿?wù)結(jié)束時(shí)間節(jié)點(diǎn)。多波次任務(wù)各時(shí)間約束條件在STN 中的各邊上予以顯示。

如圖5 所示，將二元時(shí)間約束雙邊不等式轉(zhuǎn)化為單邊不等式，多波次任務(wù)STN 可等價(jià)轉(zhuǎn)換為多波次任務(wù)距離圖。

圖5 多波次任務(wù)距離圖

1.2.3 多編隊(duì)任務(wù)STN 模型

圖6 多編隊(duì)任務(wù)STN

多編隊(duì)任務(wù)開始時(shí)間節(jié)點(diǎn)為T'、結(jié)束時(shí)間節(jié)點(diǎn)為T'，各編隊(duì)任務(wù)開始時(shí)間節(jié)點(diǎn)分別為T'。由于多編隊(duì)任務(wù)結(jié)束與各編隊(duì)任務(wù)結(jié)束為同一個(gè)時(shí)間點(diǎn)，可以統(tǒng)一用T'表示該時(shí)間節(jié)點(diǎn)。多編隊(duì)任務(wù)各時(shí)間約束條件在STN 中的各邊上予以顯示。

如圖7 所示，將二元時(shí)間約束雙邊不等式轉(zhuǎn)化為單邊不等式，將多編隊(duì)任務(wù)STN 等價(jià)轉(zhuǎn)換為多編隊(duì)任務(wù)距離圖。

圖7 多編隊(duì)任務(wù)距離圖

2 時(shí)間協(xié)同規(guī)劃算法

2.1 時(shí)間協(xié)同規(guī)劃沖突檢測

STN 是一致的等價(jià)于與其對(duì)應(yīng)的距離圖沒有負(fù)環(huán)。

負(fù)環(huán)指的是在STN 距離圖中由一系列點(diǎn)與權(quán)值和為負(fù)的同向有向邊構(gòu)成的環(huán)。如圖2 中的STN距離圖所示，按序經(jīng)過頂點(diǎn)1、2、4、3 的環(huán)路權(quán)值和為-2，是一個(gè)負(fù)環(huán)。對(duì)沖突的存在與否可以轉(zhuǎn)化為在與相應(yīng)時(shí)間約束對(duì)應(yīng)的STN 距離圖中是否可以找到負(fù)環(huán)。本文通過Johnson 算法找出STN 距離圖中的所有簡單環(huán)路，根據(jù)環(huán)路有向邊的權(quán)值和，判斷其是否是負(fù)環(huán)。

Johnson 算法采用深度優(yōu)先搜索的搜索策略，遍歷有向圖中的每個(gè)節(jié)點(diǎn)，尋找以其為起始點(diǎn)與終止點(diǎn)的簡單環(huán)路。在尋找以某個(gè)頂點(diǎn)為起始點(diǎn)與終止點(diǎn)的簡單環(huán)路的過程中，需要一個(gè)標(biāo)志變量Flag 記錄是否在路徑上找到環(huán)，一個(gè)堆棧Stack 記錄當(dāng)前深度優(yōu)先搜索的狀態(tài)，一個(gè)阻塞記錄表BlockedSet記錄著搜索過程中的頂點(diǎn)狀態(tài)，一個(gè)阻塞關(guān)系表BlockedMap 記錄頂點(diǎn)阻塞依賴關(guān)系，具體步驟如表1 所示。在該點(diǎn)搜索完畢后，會(huì)將該頂點(diǎn)及其鄰邊從有向圖中移除，之后繼續(xù)在新的有向圖中重復(fù)尋找負(fù)環(huán)的步驟，直到有向圖中不能構(gòu)成強(qiáng)連通分量或者只剩下一個(gè)頂點(diǎn)。

表1 Johnson 算法步驟表

2.2 時(shí)間協(xié)同規(guī)劃沖突消解

靈活因子是為了保證STN 的調(diào)整靈活性。同時(shí)原先的約束條件具有實(shí)際意義，約定邊的權(quán)重調(diào)整量不超過邊權(quán)重絕對(duì)值的η（η 為百分?jǐn)?shù)）。

度是針對(duì)STN 距離圖上的某一邊（約束）來說的，用包含該邊的不同負(fù)環(huán)的數(shù)量進(jìn)行表示。度可以一定程度上表示該邊對(duì)沖突消解的潛在貢獻(xiàn)。

某邊上的調(diào)整優(yōu)先度是指該約束在整個(gè)任務(wù)中的調(diào)整優(yōu)先級(jí)別。調(diào)整優(yōu)先度是從整體任務(wù)中不同任務(wù)的性質(zhì)進(jìn)行考慮的。如在多波次任務(wù)STN 模型中，不同波次編隊(duì)到達(dá)時(shí)間間隔受到登陸場等諸多環(huán)境因素影響，需要保證一定的間隔時(shí)間，調(diào)整優(yōu)先度較低；而總?cè)蝿?wù)出發(fā)時(shí)間相較來說調(diào)整優(yōu)先度較高。調(diào)整優(yōu)先度根據(jù)總體任務(wù)情況進(jìn)行綜合評(píng)估，利用層次分析法等方法得到。在本文中，調(diào)整優(yōu)先度作為已知條件給出。

本文提出了綜合優(yōu)先調(diào)整度的概念?？紤]約束度的同時(shí)，結(jié)合約束本身的調(diào)整優(yōu)先度，衡量約束對(duì)沖突消解的貢獻(xiàn)，對(duì)約束進(jìn)行調(diào)整。某條邊的綜合優(yōu)先調(diào)整度可以表示為

式中，prio表示邊i 的調(diào)整優(yōu)先度，k表示邊的度。

伯虎終于說到正題。只見他們?nèi)嗣媲暗目罩?，三維畫面像一朵花瓣似地打開了，應(yīng)用里出現(xiàn)了一個(gè)導(dǎo)航頁。而就是這個(gè)導(dǎo)航頁當(dāng)中的“降維安全監(jiān)測”六個(gè)字，使得安文浩一怔。

如圖8 所示，不斷檢測負(fù)環(huán)集合是否為空，選擇綜合優(yōu)先調(diào)整度最大的邊進(jìn)行調(diào)整，將該邊設(shè)置為不可再調(diào)整，更新負(fù)環(huán)集合狀態(tài)，直至全部負(fù)環(huán)被消除。

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

2.3 Floyd-Warshall 算法

Floyd-Warshall 算法用于求解有向加權(quán)圖中任意兩點(diǎn)之間的最短距離，通過考慮最佳子路徑來得到最佳路徑。初始化矩陣DIST［］，DIST［i，j］表示從頂點(diǎn)i 到頂點(diǎn)j 的最短距離。對(duì)于i 等于j，初始化DIST［i，j］；否則初始化DIST［i，j］=+∞。從第1 個(gè)頂點(diǎn)開始，依次將每個(gè)頂點(diǎn)作為中介k，若滿足

則更新

即如果存在一條經(jīng)過k 且距離較已知路徑更短的路徑，更新i、j 間的最短距離。

3 案例分析

兩棲兵力投送任務(wù)總體想定：兩棲兵力投送總?cè)蝿?wù)在早晨6：00 開始，共分為4 個(gè)波次任務(wù)進(jìn)行，每個(gè)波次任務(wù)中包含著3 個(gè)編隊(duì)（直升機(jī)、氣墊艇、兩棲戰(zhàn)車），總共持續(xù)時(shí)間在40 min～50 min 之間。

3.1 多波次任務(wù)分析

多波次任務(wù)想定規(guī)劃：第1 波次任務(wù)在30 min～40 min 之間完成，第2 波次任務(wù)在25 min～35 min之間完成，第3 波次任務(wù)在30 min～35 min 之間完成，第4 波次任務(wù)在35 min～40 min 之間完成。第1波次開始時(shí)間距總?cè)蝿?wù)開始時(shí)間在5 min～10 min 之間。每個(gè)波次任務(wù)的開始時(shí)間間隔為6 min～9 min，每個(gè)波次任務(wù)的結(jié)束時(shí)間間隔為7 min～8 min。

選定極限調(diào)整值η 為40%，靈活因子μ 取1。

各約束的調(diào)整優(yōu)先度在想定多波次任務(wù)距離圖調(diào)整表中作為條件給出。

圖9 想定多波次任務(wù)STN

圖10 想定多波次任務(wù)距離圖

根據(jù)Johnson 算法，發(fā)現(xiàn)想定多波次任務(wù)STN距離圖中共有5 個(gè)負(fù)環(huán)，分別是：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。

統(tǒng)計(jì)負(fù)環(huán)集合中各邊的度，結(jié)合各邊的調(diào)整優(yōu)先度，得到各邊的綜合優(yōu)先調(diào)整度。通過想定多波次任務(wù)距離圖調(diào)整表呈現(xiàn)，如表2，根據(jù)此表進(jìn)行沖突消解。

表2 想定多波次任務(wù)距離圖調(diào)整表

具體消解步驟如下所示：

圖11 沖突消解后的想定多波次任務(wù)距離圖

根據(jù)Floyd-Warshall 算法，確定任意兩點(diǎn)時(shí)間之間的最短距離，可以得到多波次任務(wù)距離圖最短距離表，如表3 所示。

表3 多波次任務(wù)距離圖最短距離表

根據(jù)表3，以T為基點(diǎn)，各個(gè)時(shí)間節(jié)點(diǎn)范圍：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。即：兩棲上陸總?cè)蝿?wù)開始時(shí)間為6：00，第1 波次任務(wù)開始時(shí)間6：03，第1 波次任務(wù)結(jié)束時(shí)間為6：33；第2 波次任務(wù)開始時(shí)間6：10，第2 波次任務(wù)結(jié)束時(shí)間為6：40；第3 波次任務(wù)開始時(shí)間6：16，第3 波次任務(wù)結(jié)束時(shí)間為6：47；第4 波次任務(wù)開始時(shí)間6：20，第4 波次任務(wù)結(jié)束時(shí)間為6：55，上陸總?cè)蝿?wù)在6：55 結(jié)束。

3.2 多編隊(duì)任務(wù)分析

根據(jù)多波次任務(wù)的分析，第1、2、3、4 波次任務(wù)分別需要在30 min、30 min、31 min、35 min 內(nèi)完成。

多編隊(duì)任務(wù)想定規(guī)劃：每個(gè)波次任務(wù)可分為直升機(jī)、氣墊艇、兩棲戰(zhàn)車3 個(gè)編隊(duì)任務(wù)。直升機(jī)編隊(duì)任務(wù)持續(xù)時(shí)間在5 min～10 min 之間，氣墊艇編隊(duì)任務(wù)持續(xù)時(shí)間在10 min～15 min 之間，兩棲戰(zhàn)車編隊(duì)任務(wù)持續(xù)時(shí)間在25 min～35 min 之間。

以第1 波次多編隊(duì)任務(wù)為例進(jìn)行時(shí)間協(xié)同規(guī)劃分析。第1 波次任務(wù)需要在30 min 內(nèi)完成，也就是說第1 波次任務(wù)持續(xù)時(shí)間在0 min～30 min 之間。構(gòu)建想定第1 波次多編隊(duì)任務(wù)STN 如圖12 所示。

圖12 想定第1 波次多編隊(duì)任務(wù)STN

將想定第1 波次多編隊(duì)任務(wù)STN 等價(jià)轉(zhuǎn)化為想定第1 波次多編隊(duì)任務(wù)距離圖，如圖13 所示。

圖13 想定第1 波次多編隊(duì)任務(wù)距離圖

根據(jù)Johnson 算法，想定第1 波次多編隊(duì)任務(wù)STN 距離圖中的環(huán)中不存在負(fù)環(huán)，說明第1 波次多編隊(duì)任務(wù)規(guī)劃上不存在時(shí)間沖突。

根據(jù)Floyd-Warshall 算法，得到想定第1 波次多編隊(duì)任務(wù)STN 距離圖最短路徑表，如表4 所示。

表4 第1 波次多編隊(duì)任務(wù)距離圖最短路徑表

根據(jù)表4，以T'為基點(diǎn)，各個(gè)時(shí)間節(jié)點(diǎn)范圍：T'為［0，5］，T' 為［10，15］，T' 為［15，25］，T' 為［25，30］。其中，一組可行解取T'為5，T'為15，T'為25，T'為30。即：第1 波次多編隊(duì)任務(wù)開始時(shí)間為6：03，第1 編隊(duì)（直升機(jī)）出發(fā)時(shí)間6：08，第2 編隊(duì)（氣墊艇）出發(fā)時(shí)間6：18，第3 編隊(duì)（兩棲戰(zhàn)車）出發(fā)時(shí)間6：28，第1 波次多編隊(duì)任務(wù)在6：33 結(jié)束。

第2、3、4 波次多編隊(duì)任務(wù)同理根據(jù)上文進(jìn)行STN 建模，等價(jià)轉(zhuǎn)化為距離圖，進(jìn)行時(shí)間協(xié)同規(guī)劃沖突檢測與消解，得到各剩余波次多編隊(duì)任務(wù)相應(yīng)的時(shí)間協(xié)同規(guī)劃，如表5 所示。

表5 兩棲兵力投送任務(wù)時(shí)間協(xié)同規(guī)劃表

通過對(duì)多波次任務(wù)及多編隊(duì)任務(wù)的分析進(jìn)行匯總整合，最終得到兩棲兵力投送任務(wù)時(shí)間協(xié)同規(guī)劃，呈現(xiàn)在兩棲兵力投送任務(wù)時(shí)間協(xié)同規(guī)劃表中。

4 結(jié)論

本文分析了兩棲兵力投送任務(wù)的特點(diǎn)，利用簡單時(shí)間網(wǎng)絡(luò)對(duì)兩棲兵力投送任務(wù)及相應(yīng)的時(shí)間約束規(guī)劃進(jìn)行建模及表示，檢測原規(guī)劃在時(shí)間約束上的一致性，基于綜合優(yōu)先調(diào)整度對(duì)規(guī)劃存在的時(shí)間沖突進(jìn)行消解，得到合理的時(shí)間協(xié)同規(guī)劃，為兩棲兵力投送任務(wù)的順利執(zhí)行提供有力的保證與幫助。