基于聚類與時間耦合執行序列的任務分解方法

龔 雪，彭鵬菲，姜 俊

(1.海軍工程大學 電子工程學院，武漢 430033；2.海軍工程大學 作戰運籌與規劃系，武漢 430033)

0 引言

作戰任務分析[1]是作戰任務規劃[2-3]的基礎和前提，多軍種聯合復雜任務規劃已成為軍事指揮決策領域的重點研究方向。因此，眾多學者對復雜任務分析方法進行了更加深入的研究，以進一步推動作戰任務規劃應用技術的發展。例如，傳統任務分析方法-空間搜索法，周凌超[4]通過改進模擬退火算法對導彈目標進行分析規劃，得到一個較好的導彈目標的分配方案。仿生物學方法-遺傳算法，閆玉鐸[5]著力分析武器目標的內在聯系，應用改進遺傳算法，得到武器目標較優的任務分配方案。智能規劃方法-基于分層任務網絡規劃，胡曉峰[6]等人針對決策問題智能化的分析，得出游戲博弈和作戰指揮的密切的內在聯系。

雖然，以上方法能夠解決任務分析領域中的特定問題，但是目前復雜任務分析仍然面臨的許多難點問題，這些問題主要體現在：一是任務分析過程中影響因素過多構造模型困難[7]。二是建立的任務分析模型過于繁瑣，時效性較差。三是任務分析模型完備性較差無法實時對情況進行分析。

本文針對作戰任務分析中的高度耦合[8-9]任務不易分解且需重構排序的問題[10]，提出了一種基于聚類分析與改進時間-耦合執行序列的自適應任務分解方法[11]。該方法的主要思想是：對任務矩陣中的每一個任務進行定量分析，再利用聚類后的改進時間—耦合度的執行序列優選方(TATC)耦合度分解算法對最小粒度的任務集解耦運算進行最小粒度的耦合任務集解耦運算。最終，得到一個耦合度較低之后的任務序列執行層次結構圖。最后，通過仿真實驗，驗證了該方法對解決復雜任務的解耦及序列重構難點問題具有較好的運用效果，在復雜任務分析及規劃領域應用前景廣闊。

1 任務分析的問題描述

1.1 作戰任務分析

任務的多樣性、任務間的復雜性與不確定性等不確定因素限制了作戰任務的詳細規劃，因此在任務規劃前需進行任務分析，將強耦合任務分解，優先級高的任務優先執行。

本文針對作戰任務分析中高耦合性任務分解問題[12]，實現高耦合性任務粒度自動分解至最佳粒度的解耦合任務集的解耦[13-15]操作思路，提出了基于自動粒度控制的循環解耦的方法。創新改進了基于任務集解耦算法，本文運用的解耦算法是改進的時間—耦合度的執行序列優選方法。得到了清晰的基于粒度分解的解耦任務集，任務集內子任務執行序列[16]以及解耦任務集中子任務可執行系數。

1.2 任務協同關系類型

因為任務與任務之間存在著繁瑣而復雜[17]的關聯關系，每個作戰任務之間相互影響并彼此相互作用，即對外表現出協同關系。則這種對外的協同模式表現出三種模式[18](假設有兩個作戰任務Ts和Th)：

1)依賴型任務：任務Ts對任務Th具有單一方向的傳遞關系并且Ts依賴Th的輸出才能執行如圖1所示。

2)獨立型任務：Ts和Th沒有彼此相互作用的信息交互，Ts和Th各自獨立的在不同軌道單獨運行如圖2所示。

圖2 獨立型任務

3)耦合型任務：Ts和Th具有雙向信息依賴關系也即Ts需要Th提供的信息流來作為輸入且Th需要Ts提供的信息流作為輸入，任務Ts和任務Th需要通過多次的彼此相互作用才能完成的耦合任務如圖3所示。

圖3 耦合型任務

其中圖1～3中的“*”應在[0，1]取值，表示為任務間耦合系數。

任務間越是信息交互頻繁，則耦合性越高，復雜程度越高，則進行任務分析就越發困難；在緊急的情況下，人腦計算能力有限，且經驗性決斷過多，因而在很多情況下無法做出決定性的選擇，有可能會決斷失誤。因而任務分析顯得尤為重要，所以本文從多種復雜信息交互的角度，設計自適應性任務粒度調整機制，最終達到解耦合的目的。

1.3 任務協同關系表達

本文是基于任務矩陣來進行分類耦合關聯任務塊，則任務間復雜關系表示如圖1，圖2，圖3所示。

1.4 耦合任務問題描述

信息耦合指的是不同優化問題的求解模塊或算法的內在機理上存在信息的的傳遞、調用、影響的作用。有多個算法組成的系統，在算法之間的關系上，可以對系統的信息耦合程度進行量化。針對任意兩個問題進行求解時，若是這兩者的運行過程相互獨立，則兩個算法之間不存在信息耦合；若是兩者之間存在共享輸入，兩者之間為松弛耦合狀態；如果兩者之間存在影響算法運行過程的信息，則兩者為緊密耦合狀態。

則針對以上敘述，假設在一個作戰任務集中，有多個強耦合任務存在。定義任務集合為T={T1，T2，…，Ts}，其中Ts表示的是任務集合中的第s個任務。

若任務分解粒度過小，任務執行難度變大，所需代價太高。若任務分解粒度大，任務整體的執行效果差。因此，對于解耦問題，最關鍵的一步是設置合適的任務分解粒度。

若一個任務集合中強耦合任務過多，執行強耦合任務時難度系數較高，因此需要進行任務分析時，需要對耦合任務集進行解耦。則耦合任務模型可描述如圖4所示。

圖4 耦合任務信息交互圖

2 任務分析模型構建

在設計任務協同的過程中，設計時不會考慮任務之間的耦合關系，但是在實際情況中多個任務之間存在大量的信息交互且緊密耦合，解耦合就是將任務間的關系斬斷，并且研究任務之間存在的耦合關系。本文基于這種特性，構建了任務分析模型。主要分為兩個方面：任務分析基本框架的設計和任務分析建模。任務分析基本框架主要是在任務分析模型的基礎進行粒度分解和循環解耦的過程，最重要的一環是循環解耦的算法設計。

2.1 任務分析基本框架

本文基于任務間的關聯性構建任務關聯矩陣，在已知任務間關聯關系的基礎上設計任務連通效應矩陣。通過連通效應矩陣進行聚類[19-20]分析，設置初始粒度為3(也即將其作為聚類分析的初始分類)。依據初始粒度進行耦合數據集解耦。在解耦之后，計算任務集間的jaccard系數J，若J>0.3，初始粒度增加一個單位，并進行以上循環。若J<0.3，跳出循環，得到解耦后的任務集并計算任務集的子任務可執行性。

循環解耦大致步驟為：

1)初始化參數，令J=1，初始分解粒度G=3。

2)若J>0.3，則進入循環：聚類分析得到任務集合TCE，將標記任務分類的標簽存入TCO矩陣。

(1)循環取TCO矩陣中標記系數：

①依據標記類別將分類集分類轉存。

②引入了基于中間任務序列的任務矩陣分割算法，通過任務執行周期對連通效應矩陣唯任務分割(也即若該任務屬于該耦合任務集則效應連通矩陣對其保留反之刪除)。

③TATC解耦合操作，得解耦之后任務集。

④計算每個任務集的平均jaccard系數。

(2)對基于粒度分解的每個任務集進行維度查詢，若維度小于3，則將解耦后刪除的任務集與之合并，生成一個新的任務集。并對新合并的任務集進行子任務可行性系數的計算，若可行，則保留；否則對該任務集進行再次解耦。

(3)計算基于粒度分解的任務集平均jaccard系數，若大于0.3循環繼續，粒度增加1，若小于0.3，退出循環。

3)計算解耦之后任務集可執行性矩陣，若不符合要求，粒度加一；對不符合要求的任務集單獨解耦。循環解耦的簡易流程圖如圖5所示。

2.2 任務分析建模

2.2.1 任務關聯矩陣

本文首先設計任務結構矩陣，計算任務Ts與其他任務Th的關聯系數，并將生成的關聯系數存入矩陣得到相關系數矩陣；將上一步得到的系數矩陣通過公式(1)進行任務間相關性進行比對，最后得到任務Ts和Th的相關的顯著程度的對比，從而得到強耦合任務關聯矩陣。

(1)

其中：ts為任務Ts服從自由分布t的概率，Rs則為任務Ts的相關系數。最后計算出每一個任務與其他任務的相關聯的相關系數矩陣。

2.2.2 任務連通效應矩陣

在任務關聯矩陣的基礎之上建立基于設計結構矩陣(DSM，design structure matrix)模型[21]得到任務連通效應矩陣。為精確反映任務之間相互作用的強弱程度，本文采用上文任務間相關系數矩陣(RF)來定量描述任務之間相互作用的強弱程度。在現實意義中，該矩陣反應了在不同程度下迭代導致的任務之間相互影響概率。確定M個指標RF1(i，j)，RF2(i，j)，···，RFm(i，j)，采用公式(2)進行相乘效用函數法計算，并對任務相關系數矩陣取λ(0<λ)截集，得到布爾型BRFij。

(2)

由于影響因素不同，則λ取值也應該不同，因而可得到不同λ強度下的BFij矩陣。主對角線上的元素代表了任務本身產生的影響，其相關程度是最強的，得BFii=1。若令λ=0.5，得到λ=0.5相關效應矩陣，如當RFij<0.5時，BFii=0表示Ti和Tj之間無相互作用效果的影響；當RFij=0.5時且RFij>0.5，BFii=1表示Ti和Tj之間有相互作用。其中下標i和j表示[1，N]，N表示RF矩陣的維度。

2.2.3 計算可達矩陣

利用關聯任務分離算法對連通效應矩陣進行運算，將任務連接通效應矩陣中包含的多個獨立的耦合任務塊進行分解，并用粗粒度關聯任務對連接的大任務模塊進行分解。粗粒度的分解實質是一個模塊化的聚類過程，它把多個強耦合的耦合任務作為一個整體，通過識別任務模式和重組耦合任務，把各個耦合任務與外界聯系轉化為耦合的任務集合。

在圖論的觀點上，為了確定耦合任務塊中包含各種任務間數據流相互作用而形成的圖的數據流環路，本文采用圖論中關鍵路徑的相關算法設計算法模塊.由于任務連通效應矩陣的特殊性可被看作圖的鄰接矩陣，利用任務連通效應矩陣的冪運算來搜索所有的數據流環，從而初步確定耦合任務塊，為后續初始粒度的設置做鋪墊。

定義1：和算子?

矩陣P和Q的邏輯和為：

P?Q=M，mij=max(pij，qij)

(3)

定義2：乘算子*

矩陣P和Q的邏輯乘為：

P*Q=M，mji=min(pij，qij)

(4)

定義3：算子?

(5)

則根據路徑搜索算法得強連通圖，并通過矩陣信息的遍歷，建立可達矩陣。

則可達矩陣V：

(6)

通過公式(6)計算可達矩陣P，根據上文所述根據任務連通效應矩陣來定量反映任務間的聯系強弱程度，用[0，1]數值來詮釋它們之間的依賴關系的強弱。通過聚類分析得到初始耦合任務集并將其作為迭代的初始耦合任務集。首先設置的初始粒度為3也即將其作為聚類分析的初始分類，然后，對其進行耦合數據集的解耦操作。解耦之后，計算任務集間的jaccard系數J，若J>0.3，初始粒度增加一個單位，并進行以上循環。若J<0.3，跳出循環，得到解耦后的任務集并計算任務集的子任務可執行性。

3 耦合任務集分解

當Ts任務在Th之前執行時，假設Th之后沒有任務來執行，那么Th將促使Ts返工，和公式(6)的返工概率一樣，通常促使Ts不止一次返工，因此會不斷地產生返工概率。假設每個任務的執行周期為Si={S1，S2，…，Sm}，促使Ts返工的概率Di={D1，D2，…，Dm}，則Ts返工的期望總和為：

(7)

因為Ts對其他任務的返工則即其他任務對Ts返工的返工概率假設為DDi={DD1，DD2，…，DDm}，DDi的計算方式是：假設的Ts對其他任務的返工概率和其他任務對Ts的返工概率是相斥的，則其他任務對Ts返工的返工期望為：

(8)

綜合考慮時間周期對耦合任務塊的影響，為此引入基于時間-耦合度的解耦算法，在時間-耦合度的解耦算法中設置計數器，進行任務間優先級計算并對耦合任務塊內的子任務進行排序。

則改進的時間-耦合度的解耦算法如下。

Step 1：令k=0，T為任務集合，L1為空矩陣其作用是儲存每次得到的最大任務的優先級的任務序號。

Step 2：對于每個耦合任務集合中的某一任務Ts，計算其優先級的系數。

(9)

Step 3：將矩陣最值遴選模型和任務序列轉移策略相結合，即令Sortmax=max[Sorti]，Sortmax對應的任務Ti存到矩陣L1之中。

Step 4：將解除耦合的任務序列存入L2矩陣，并將剩下的任務的序列存入L3矩陣。

Step 5：k=k+1，若k

最后得到按優先級排序的該耦合模塊或者該任務集合中子任務的執行順序。

4 子任務可行性分析

對解耦合后得到的子任務集進行可執行性分析的判定，只有任務在解耦合之后，重新得到的任務集能夠執行，則判斷解耦合成功，下面是子任務可執行性判定算法。

首先，專家對各個解耦之后任務集中單個任務進行描述。用RG(k)i來描述第K個任務集，第i個任務。RG(k)i的矩陣元素是由任務的功能和任務屬性序列這兩個重要的影響因素構成，通過兩個因素初步確定子任務的可行性。引入用戶對該任務的側重水平，定義模糊性語言變量集合Ix={不重要，無要求，基本重要，相較重要，及其重要}來進行表示，并以數值集合{0，0.3，0.5，0.7，1.0}的數值分別量化。設置子任務可行度可用公式(9)表示為：

(10)

式中，RSQ(k)i表示任務執行者對第K個任務集中的第i個任務的屬性能否符合要求，若數值為0則表示不符合，否則數值為1就表示符合。

設定一個閾值λ，如果存在執行者使D>λ，則說明分解合適；反之，則說明分解粒度不適合，需進一步對任務集進行分解。閾值的設置需綜合分析子任務重要性、創新程度及任務執行者狀況等內容，取值范圍為(0，1.0]，本文取值為0.5。

5 案例仿真

在作戰過程中，任務分析往往是及其最基礎的一環。并針對基于矩陣的作戰任務建模及重組問題，進行應用拓展。先根據任務在時間、空間和資源上的相互制約和依賴關系確定15個任務指標設計原始任務結構矩陣F，如式(11)所示，可以明顯看到任務在量化過程中，任務重要程度的指標以及任務間的信息交互程度的表現：

(11)

再次根據(1)式和(2)式確定任務關聯矩陣Fq如式(12)所示，式中各個任務的通路已然可以通過數據可以表現出，例如任務一合任務二連通且任務一與任務五不連通：

(12)

將λ定義為0.5得到λ-任務連通效應矩陣B如式(13)所示。

(13)

根據關鍵路徑冪乘算法調用公式(6)進行可達矩陣的計算，得到矩陣P如式(14)所示：

(14)

設置最小的分解粒度為3，也即進行聚類分析分成生成3類將要被解耦合的耦合集，其次將這三類分別用數組轉存并分別通過引入任務時間周期D=[0.1 0.2 0.8 0.3 0.1 0.4 0.2 0.1 0.6 0.1 0.1 0.4 0.1 0.1 0.2],將引入改進的時間-耦合度的解耦算法進行計算操作，將解耦合后的任務集進行轉存，同時進行計算子任務間的jaccard系數。將jaccard系數進行平均算法操作得到各個解耦合后的任務集的jaccard系數，并計算子任務可行性系數，最終實驗結果的可行性系數如表1～3。

表1 初始解耦合任務集

其中圖中的ledi其中i∈{1，2，3，4}，表示初始解耦合任務集合，由表一可以看出初始進行解耦時，任務的粒度劃分已然完成并且如表2可以看出任務粒度的劃分在不斷進行優化。

表2 最終解耦任務集

其中圖中的RGi其中i∈{1，2，3，4}，表示最終解耦之后的任務集合。

其中圖中的fesibleDi其中i∈{1，2，3，4}，表示最終解耦之后的每個任務集合的子任務可行性系數。

對于解耦任務集子任務可行性系數，本文設置的子任務可執行的閾值為0.5，大于0.5則該子任務可執行否則不可執行。從表3中可以看出第一個解耦合之后的任務集中‘NaN’是其任務本身，對其任務本身則不可做評價因為任務本身的可執行距離為0。則得到最終的任務層次結構圖如圖6示，任務執行次序是從第一層到第四層。其中，第一層中任務執行順序為：任務1→任務4→任務10→任務13→任務14；第二層次的任務執行順序為：任務9→任務8→任務5；第三層的任務執行順序為：任務6→任務7→任務12→任務15；第四層的任務執行順序為：任務11→任務3→任務2。每個層次間互不干擾，層次間的數據傳遞不具時效性但是層級順序不可變。因此，任務鏈(任務1→任務4→任務10→任務13→任務14→任務9→任務8→任務5→任務6→任務7→任務12→任務15→任務11→任務3→任務2。)依據實際情況，在同一層次的任務可進行次序調整，本文中基于聚類分析與改進時間-耦合執行序列的自適應任務分解方法運用耦合任務分析的思想對任務矩陣中的每一個任務進行定量分析，然后采用聚類方法尋找耦合最緊密的任務，再利用粒度自主循環調整機制運行改進TATC算法對最小粒度的任務集進行解耦。最終，得到一個耦合度較低之后的任務序列執行層次結構圖，從而解決了復雜任務分析中的高度耦合任務不易分解且需重構排序的問題。

表3 解耦任務集子任務可行性系數

圖6 任務層次結構

6 結束語

本文針對作戰任務分析中的高度耦合任務分解及任務序列重新組合問題，提出了基于聚類分析的自適應粒度解耦的任務分解算法。基于聚類分析的自適應粒度解耦算法初始進行初始粒度設置，之后通過初始粒度對初始任務進行聚類分析。通過聚類分析算法分析之后得到初始耦合任務集，之后對耦合任務集進行基于改進時間-耦合執行序列解耦算法解耦合操作得到最終解耦任務集。對解耦任務集進行jaccard系數的計算并判定，若jaccard系數小于設定閾值，則粒度增加與重新解耦。

改進時間-耦合執行序列解耦算法是通過傳入耦合任務集序列，基于耦合任務集分割連通效應矩陣以及唯任務分割時間序列矩陣。然后通過對耦合任務集進行計算基于時間序列的優先級，并將高優先級任務進行存儲。從而達到解耦合的效果，最終，得到解耦任務集的層次結構圖。

最后進行仿真實驗，實驗結果表明，該解耦合算法可以得到一個更加可行和更加優化的一個解耦合任務集。該算法針對任務集高度耦合的問題，達到了基于粒度的任務集解耦并進行任務序列重構的效果。最終，指揮員可以通過實際操作情況得到一個執行力度較好的任務鏈。

但是本文對實際情況的不確定性，任務進度的不確定性，任務影響因素的不確定性和任務的突發性等研究多有不足，有待于進一步研究。