基于STN 的兩棲兵力投送任務(wù)時間協(xié)同規(guī)劃*

胡忠凱，黃炎焱

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

0 引言

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

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

1.1 STN

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

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

圖1 簡單時間約束及STN

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

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

圖2 距離圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 Johnson 算法步驟表

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

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

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

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

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

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

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

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

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

2.3 Floyd-Warshall 算法

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

則更新

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

3 案例分析

兩棲兵力投送任務(wù)總體想定：兩棲兵力投送總?cè)蝿?wù)在早晨6：00 開始，共分為4 個波次任務(wù)進行，每個波次任務(wù)中包含著3 個編隊（直升機、氣墊艇、兩棲戰(zhàn)車），總共持續(xù)時間在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波次開始時間距總?cè)蝿?wù)開始時間在5 min～10 min 之間。每個波次任務(wù)的開始時間間隔為6 min～9 min，每個波次任務(wù)的結(jié)束時間間隔為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 個負環(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)計負環(huán)集合中各邊的度，結(jié)合各邊的調(diào)整優(yōu)先度，得到各邊的綜合優(yōu)先調(diào)整度。通過想定多波次任務(wù)距離圖調(diào)整表呈現(xiàn)，如表2，根據(jù)此表進行沖突消解。

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

具體消解步驟如下所示：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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