面向任務的云、邊、端分布式異構資源優選技術

李大偉，李 丹，劉博文，劉賽賽，王 棟

(中國電子科學研究院，北京 100041)

0 引 言

自然界中發現的大多數系統都是復雜的分布式系統，需要溝通和合作以實現共同目標。現代社會隨著科技的不斷發展，由異構節點構成的物聯網、運輸網等復雜體系也呈現出“網絡極大化”的發展趨勢，如何讓復雜體系中的各節點各司其職就成了一個亟需解決的問題。

文獻[1]將復雜體系中群體的組織模式分為網絡、層次和聯盟3類，每類模式具有其自身特性，往往根據任務場景需要采取相適應的群體結構組織模式。網絡結構模式的群體內各節點之間可任意建立關系，具有極大的不確定性和自組織特性；層次結構模式中，群體可自頂向下按等級劃分，高層級的節點具有較高的指揮控制權限，體現了任務由宏觀到微觀的逐級傳遞；聯盟結構模式中，根據節點的特定屬性可被劃分為不同領域，任務可按領域進行拆分執行。

在軍事應用中，層次結構是一種較為普遍和適用的多節點組織運用模式。文獻[2]提出了多態認知智能體架構(polymorphic cognitive agent architecture，PCAA)，建立宏觀(Macro)、微觀(Micro)、原子(Proto)這3層認知架構，是一種多分辨率的層次結構。美國國防部高級研究計劃局(DARPA)開展的進攻性蜂群使能戰術(offensive swarm-enabled tactics，OFFSET)項目[3]，提出基于任務的集群系統架構，將無人蜂群作戰行動自上而下分解為任務層、戰術層、原語層、算法層，如圖1所示。集群任務層主要表征粗粒度的整體使命需求，集群戰術層對使命需求中的戰術活動任務樹進行建模，原子層對具體戰術任務活動中的蜂群行為進行建模，算法層為具體蜂群行為提供基礎功能模型。OFFSET也是典型的層次化體系架構，旨在推動蜂群自主性和人與蜂群協同工作方面的革命性發展，尤其關注蜂群自主戰術行動的可行性，相關研究成果將直接應用到“馬賽克戰”體系中，推動低成本無人蜂群作戰能力的快速構建形成。

圖1 OFFSET集群系統架構

美國聯合全域指揮控制條令規定使用集中式指揮和分布式控制執行的原則進行聯合空中作戰，推動這一空中力量組織運用原則的原因是，集中式指揮使高級梯隊指揮官能夠有效地控制、集結和領導部隊；執行權力下放使部隊能夠掌握主動權，應對不確定和不斷變化的環境，并提升末端的自組織靈活性[4]。

對于復雜群體結構的多智能體節點，處理分布式任務時，由于復雜性、高動態等因素具有較大挑戰性。此外，多個智能體的存在提高了執行任務的性能和可信度，因為更多的智能體可以合作更快地完成相同的任務，并且系統對智能體的丟失或故障更加具有魯棒性。此外，全局智能體分布式合作完成任務可能會降低油、電等資源消耗成本。然而，當使用多智能體系統來完成多項任務時，就會出現分工問題。

當前流行的多智能體強化學習方法則主要專注于構建完全分布式系統用于多智能體合作。在分布式系統中，每個智能體單獨運行，它們自己觀察環境并可通過點對點通信交換信息，實現多智能體合作。這樣的分布式系統可以靈活構建大規模多智能體系統，并且具有極低的通信成本。但是在大多數情況下，分布式策略不穩定且難以學習，因為它們通常會互相影響，導致環境動態過程不穩定。雖然這個問題通過最近流行的“集中式訓練和分布式執行”AC(Actor-Critic)方法得到緩解[5]，但如何有效地訓練集中式的“Critic”至今仍是一個挑戰。

任務分配問題的求解方法可分為集中式、分布式、混合式。集中式算法是過去研究較多的一類算法，中央協調或類似模塊與所有其它智能體均有通信渠道，并決定必須分配給其它智能體的任務[6，7]。集中式任務分配方法主要包括蟻群算法[8]、粒子群算法[9]、遺傳算法[10]等，這些方法的優點是它們使用較少的系統資源并且可能具有較低的實現成本，但是通信、計算成本高并且不適用于動態環境，因此它們主要用于少量智能體或靜態任務的分配。此外所有智能體都與中央處理單元進行通信這一前提條件限制了它們的可擴展性[11，12]。

分布式算法克服了集中式算法的一些缺點[13，14]，引起了研究人員的廣泛關注。分布式任務分配算法主要采用基于博弈論和基于市場的機制。在這種類型的算法中，沒有中央協調模塊，智能體對環境有局部感知，并且可能會彼此之間進行任務協商而不是被統一分配任務。每個智能體都有自己的收益函數。分布式算法將部分智能體的故障對整體的性能影響降到較小，同時具有較好的節點擴展性，但是由于局部的溝通結果可能會導致全局的任務沖突[11]。這種完全自主和分布式覆蓋任務分配算法的主要特點和優勢是，能夠讓感知和通信能力有限的無人機在未知環境下進行協同與控制。文獻[15]針對異構多無人機執行偵察、攻擊等多任務時的分配問題，提出帶有時間窗的基于共識的捆綁算法(windows consensus-based bundle algorithm，WCBBA)。

混合式算法將上述兩種方法進行結合，文獻[16]將集中式優化和分布式拍賣的方法相結合，文獻[17]將進化算法與貪心算法相結合，文獻[18]將博弈論的方法與學習算法相結合。

本文主要聚焦解決實際作戰場景中戰役集中式指揮與戰術分布式指揮控制相結合的任務分配模式，重點提出戰術末端分布式任務分配方法，通過構建包含任務要素、多智能體要素的任務空間，分析智能體任務包構建、沖突消解等關鍵技術，將全局任務在收益最大化的要求下指派給合適的作戰單元，研究特定時間窗口下的分布式無人作戰資源優選技術，并在典型空海場景中進行仿真驗證，具有較好的分布式任務分配效果。

1 任務空間

1.1 任務空間要素

任務空間要素主要包括任務、服務和作戰單元，三者之間的關系如圖2所示，作戰單元提供服務，服務支撐上層任務的執行，三者之間存在內在聯動的映射關系。

圖2 任務、服務、作戰單元三元關系

服務集合S={S1，S2，…，SK}。 尋求滿足資源本體和任務執行等約束條件下的最優任務分配方案，從而發揮體系最大效能。

作戰單元集合A={A1，A2，…，AN}， 其中N為作戰單元的總數。作戰單元通過服務的形式供任務組織編排和調用。

1.2 智能體屬性

聚焦分布式任務分配，對作戰單元進行基于多智能體的建模，首先給出作戰單元關鍵屬性要素如下：

(1)任務包

智能體i被分配的任務有序集合表示為bi={bi1，bi2，…，bi|bi|}，bi中的任務元素按加入包的先后順序排列，|bi| 表示該智能體被分配的任務總數。

(2)任務路徑

智能體i為完成所分配任務所需運行的矢量路徑列表表示為pi={pi1，pi2，…，pi|pi|}， 其中 |pi| 表示列表長度。

(3)任務狀態

智能體i的任務狀態表示為τi={τi1，τi2，…，τi|τi|}， 列表中的每一個變量包含了執行任務的開始時間、持續時間和結束時間，在智能體投標和任務分配時需要考慮當前任務與智能體的任務狀態是否沖突。

(4)智能體成功競標矩陣

(5)任務中標矩陣

每個智能體對任務的中標者具有局部任務，即任務中標列表vi={vi1，vi2，…，viM}， 其中vij表示任務j的中標值，vij=0即意味著該任務尚沒有中標的智能體。

(6)智能體信息時間戳

這里將智能體i的信息時間戳定義為si={si1，si2，…，si|si|}， 列表中的元素sik表示智能體i最后一次獲知智能體k信息的時間，可以是直接信息交互或通過其它智能體進行間接信息交互。

1.3 任務分配問題建模

異構無人系統的任務分配問題可以定義為將一組復雜任務分配給一組智能體的問題，其中智能體和任務都可能隨著時間的推移進入和離開系統。任務分配問題可轉換為典型的混合整數線性規劃問題，即：對給定的任務集合T={T1，T2，…，TM} 和作戰單元集合A={A1，A2，…，AN}， 在規定的條件約束下尋求任務最大完成度的最優分配方案。上述問題可建模為

(1)

式中：Na為作戰單元的數量，Nt為任務的數量，pi為作戰單元i執行所分配任務的順序，xij為作戰單元Ai被分配了任務Tj，xi={xi1，xi2，…，xiN}， 求解目標為尋求全局收益最大化的任務分配模式。任務分配過程中服從以下約束條件

(2)

式中：Lt為作戰單元最多可以被分配的任務數量。

智能體i對任務j的投標函數cij(xi，pi) 可以是任務分配結果xi或者路徑pi的函數，與路徑總長、任務完成時間等相關。

考慮任務執行的先后順序以及任務的時間窗口，各作戰單元需要在規定的時間內抵達指定的位置，任務分配需要將完成整體任務的消耗時間、路徑代價最小化。

2 分布式任務分配算法

2.1 “云-邊-端”跨層任務分配模式

“云-邊-端”體現層次結構，“云”側強調人在回路，重點對任務進行分解，并按照領域、方向將分解后的任務分配給“邊”，“邊”側人機協作，為聯盟結構，圍繞特定領域開展任務分配；“端”側為網絡結構，強調末端作戰單元的自主組織。“云-邊-端”分布式任務分配模式的工作流程如圖3所示。

圖3 “云-邊-端”跨層跨域任務分配和資源優選模式

“云”側在任務分解時，依據混合知識空間的通用任務清單，通過OV-5a作戰活動分解樹模型[19]，呈現作戰構想中的戰略/戰役/戰術作戰任務層次結構清單，通過將任務關聯到作戰活動分解樹模型中的具體任務項，檢索任務項下的子任務，實現將高層級任務進行分解，并將子任務按領域分配給“邊”，由“邊”進行具體的任務到資源的分配，是一個面向任務的資源優選過程。

“邊”側依據混合知識空間的“任務-服務-資源”內在聯動知識模型，按需抽取任務所關聯的作戰單元資源池，其關聯關系如上文圖2中任務空間要素的三元關系所示。在具體任務分配時，各智能體作為“端”節點，采用分布式任務分配模式，根據自身功能屬性、能力指標、任務狀態等情況，對任務進行競標，通過分布式節點局部信息交互共享，對存在沖突的競標結果進行消解，不斷迭代以達成全局收益最大化。

2.2 算法原理

本文提出一種基于分布式拍賣機制的“云-邊-端”跨層 多任務分配算法，算法包含兩個階段，即智能體任務包構建和基于全局共識的沖突消解。在智能體任務包構建階段，每個智能體根據自身能力、位置、狀態、收益等情況投標合適的任務，生成自己的任務包，任務包中的任務按時間次序執行，并能夠按照一定的路徑串聯起來；在基于全局共識的沖突消解階段，相鄰智能體之間進行信息交互，根據投標值高低更新自己的任務包信息，并采用沖突消解規則達成共識，通過不斷迭代促進分布式智能體完成全局信息交換并達成全局共識，算法思路如圖4所示。

圖4 算法思路

2.3 智能體任務包構建

每個智能體僅創建其自身任務包，該任務包會隨著分配過程的進行而更新。在智能體具備的能力約束條件范圍內，每個智能體按照最大化自身任務收益為原則進行任務投標，任務包具有兩個任務相關向量：bi和pi，其中bi是按照任務的添加順序，pi是按照任務的執行順序。

設智能體i初始任務包為bi，則其在后續的任務投標過程中會選擇將邊際收益最大的任務Tj∈T加入到bi中，直到無法添加。

任務包的更新如下

bi←(bi⊕endj)

(3)

pi←(pi⊕njj)

(4)

式中：⊕nj表示增加在位置n的任務j。

在所有任務完成分配后，當出現某服務失效或失去連接時，該服務需求會再次發布。任務包中的任務根據添加順序進行排序，而路徑中的任務根據其預測的執行時間進行排序。

(5)

算法1：任務包構建

輸入:Wi(t-1),Vi(t-1),bi(t-1)和pi(t-1)

輸出:Wi(t),Vi(t),bi(t),pi(t)

While |bi(t-1)|

cij=maxSi(pi⊕{j})

for ?j∈J

hij=1

hij=1

else

hij=0

end

else

end

end

end

Ji=agmaxjcijhij

ni,Ji=agmaxnSi(pi⊕{j})

bi(t)=bi(t-1)⊕end{j})

pi(t)=pi(t-1)⊕ni,Ji{j})

end while

2.4 基于全局共識的沖突消解

在構建完成自身的任務包后，各智能體之間是不知道相互之間的任務分配狀態情況的，由于智能體之間可能存在沖突任務，例如不同智能體分配到同一任務，因此需要智能體之間進行信息交互和共享，重置或更新自身的任務包，從而確保每個智能體的任務包都是正確的，在全局智能體之間達成任務分配的共識。在基于全局共識的任務沖突消解階段，所有智能體需要與相鄰智能體之間進行信息交換，包括獲勝智能體列表、獲勝投標列表和時間戳列表，并按照一定的規則更新自身信息以達成面向任務的全局共識。

從具體規則來看，智能體Ai會通過比較其它智能體對相同任務的投標值來確定自己是否會中標。如果自身投標值更高，則它將通過競標分配到任務。如果獲知任務Tj有更高的投標值，則Aj會釋放Tj， 并將任務包中后續的任務進行刪除和再分配。智能體選擇全局最高收益任務如下所示

(6)

其中，hij=I(cij(pij)>vij)， 表示智能體i之外高于vij的有效投標值。

在全局最高收益下，智能體i的任務包更新情況可表示為

bi←(bi⊕endj*)

(7)

pi←(pi⊕nj*j*)

(8)

任務路徑pi在該任務后的所有任務也會隨之刪除，在下一次的迭代中進行重新分配。

全局共識是為了避免由于廣域分布的智能體之間信息不共享導致同一任務被加入到不同智能體的任務包中。在相鄰智能體之間進行信息交互共享時，當發現別的智能體投標值更高的情況，則進行任務更新；當路徑出現變動時，則后續任務進行重置；當自身投標值高時，進行任務保持，沖突消解規則公式如下：

(1)任務更新：wij=wkj，vij=vkj；

(2)任務重置：wij=?，vij=0；

(3)任務保持：wij=wij，vij=vij。

3 算法仿真

在本節中，我們對提出的方法進行仿真驗證。仿真環境配置為Intel(R)Core(TM)i7-8700K @3.70 GHz CPU處理器，Window 10操作系統。設定在某空海場景中，任務空間范圍設定為30 km×30 km×10 km，作戰單元包含有無人誘餌平臺、無人偵察平臺、無人打擊平臺、察打一體無人平臺、遠距離無人通信平臺5類6種異構無人系統，可以執行誘騙、偵察、打擊、通信4類任務，任務遵循OODA環的順序，在場景中可根據需求隨機生成所需任務清單列表，并且可根據需要隨時加入或刪除任務和資源，每個任務具有任務類型、坐標位置、最晚完成時間、任務需持續時間等信息。無人平臺、服務的關聯關系見表1。

表1 某空海場景下無人平臺類型

3.1 跨域分布式任務分配

假定該空海場景中共有6型異構無人系統共10個，需執行誘騙、偵察、打擊、通信4類任務共計22項，各無人系統及任務的位置由MatLab中的rand函數生成。設定該空海場景下優化目標為所有任務執行完成用時最小化，各無人平臺的任務分配結果如圖5所示，圓圈代表各類異構無人系統，線段表示異構無人系統的運行路徑，兩個相鄰的三角形之間的連線代表在執行相關的任務，無人平臺在任務分配中可能執行多個任務，結果清晰地展現了各無人系統的任務分配結果及執行任務的路線圖。算法確保無人平臺在任務執行過程中路徑及消耗相對較少，全局收益趨向極大值，且智能體所執行的任務之間不會出現任務和路線沖突。

圖5 時間窗口下的任務分配結果(A=10，T=22)

3.2 面向擾動的適變調整

面向復雜、高動態的環境，在任務完成初始分配后，主要存在2種變數，一是“端”節點發生變化，比如由于某些作戰單元被打擊失效或失去連接無法使用；二是任務發生變化，比如出現新增任務或任務出現判斷分支。面對這些變化時就需要對任務分配進行動態調整，適變任務分配流程如圖6所示。“邊”側實時更新可用的作戰單元，同時發布新的“任務-服務”需求，“端”側各作戰單元根據自身功能屬性、能力匹配、任務狀態、預期收益判斷是否投標以及具體投標值，通過全局共識確認是否中標，從而執行新的任務。

圖6 任務適變調整流程

為簡化問題，任務取誘騙、偵查、打擊3種，任務數量及類型見表2，作戰單元共有3種，每種數量有3個，每種作戰單元可以執行任一任務。

表2 任務類型及數量

在t時刻，假定智能體9失效，其原先被分配的后續任務將無法執行，此時需要對所有尚未執行完的任務進行適變分配調整，根據當前智能體的位置、能力、狀態等情況，將尚未完成的任務重新分配給剩下的智能體1-8，分配后的智能體任務計劃如圖7所示，各智能體執行任務的空間路徑如圖8所示。

圖7 不同無人平臺的任務分配計劃

圖8 時間窗口下的任務分配結果(A=8，T=20)

3.3 不同服務集成度的效能分析

不同作戰單元會具有不同集成度的服務，平臺越大功能越多，其集成度也越高。美軍的“馬賽克戰”新型作戰概念提出采用分布式小平臺的馬賽克單元構建分布式殺傷網，基于多智能體建模方法對可快速分散、組合且異構作戰力量進行建模仿真，并得出結論：分布式小平臺的作戰適變性和造價性價比要高于大平臺[20]。

圖9 不同服務集成度的任務完成效果

4 結束語

針對異構無人系統的分布式任務分配和優選問題，基于全局動態合約共識，提出知識驅動的“云-邊-端”跨層分布式任務分配模式，重點設計針對端側的分布式任務分配算法，實現戰場上任務與資源的匹配和優選，并結合典型場景進行仿真驗證，結果表明該算法能夠實現跨域分布式任務分配，并能夠面向擾動進行動態適變，具備面向未來復雜動態環境的適應能力。