一種面向立體跨域耦合任務的無人集群協同任務規劃技術

梁月乾， 張 瀟， 楊 毅

(1. 中國電子科技集團公司智能科技研究院， 北京 100041;2.海軍裝備部裝備招標中心， 北京 100080)

0 引 言

近幾年來，集群系統的巨大優勢受到了越來越多的關注。特別是當集群是由搭載不同類型載荷的來自陸、海、空不同域多種不同類型平臺組成時，每個集群成員可以充分發揮各自的優勢，多個集群成員組成的子群可以優勢互補，相比于由同類型平臺組成的同構集群，這使得整個異構集群能高效完成更為復雜的體系任務。異構集群能充分顯示其整體效能的一項基本保證是合適的任務規劃。任務規劃涉及在諸多實際約束條件下，如何安排每個集群成員或每個子群在每個任務階段的角色，使某項整體效能達到最優。

任務規劃方法大致可以分為兩類[1]：精確優化方法和啟發式方法。精確優化方法利用匈牙利法、分支定界法等對建模的旅行商問題、車輛路由問題、網絡流問題等進行求解，通?？梢缘玫阶顑炄蝿找巹澐桨竅2-3]。啟發式方法包括從生物系統的群集行為中發現的遺傳算法、粒子群優化算法、蟻群優化算法等[4-8]，以及從社會規律中發現的基于市場機制的方法等[9-10]。通過設置不同迭代次數，啟發式方法可以獲得不同優化程度的任務規劃方案。

本文以異構集群的立體跨域協同為背景，研究存在不同類型和任務域的多個目標區域、處于不同任務域的多種集群平臺的耦合時序任務的協同規劃問題。

1 立體跨域耦合任務規劃模型

1.1 問題描述

考慮一個由多個任務域的無人裝備組成的跨域集群對多個陸域、海域選定目標區域執行類型1～4四種耦合任務的場景。這四種任務之間存在時序關系：類型1任務需要在其他任務開始前完成；類型4任務需要在類型3任務完成后執行；當需要對同一個目標區域既實施干擾任務也實施類型3任務時，這里假設這兩種任務需要同時執行。

設有M個目標區域，其中包含未知數量和類型的目標。將區域位置記為qm，m=1,2,…,M。陸域、海域目標區域的集合分別記為Bg、Bw。與所在域無關，假設目標區域包括三種類型：第一種類型的目標區域只需執行類型1、類型2任務；第二種類型的目標區域需要執行類型1、類型3、類型4任務；第三種類型的目標區域需要執行所有四類任務。這三種類型的目標區域的個數分別記為M1、M2、M3。不失一般性，可將這三種類型目標區域的集合分別記為A1={1,2,…,M1}、A2={M1+1,M1+2,…,M1+M2}、A3={M1+M2+1,M1+M2+2,…,M}。

根據各目標區域的大小、其中目標的可能數量及類型、目標在區域中的分布情況等，量化每個目標區域的不同類型任務的能力需求，即類型1任務能力需求QR,m、類型2任務能力需求QEI,m、類型3任務能力需求QA,m、類型4任務能力需求QDA,m，其中m=1,2,…,M。需求量為0，表示無需對相應目標區域執行該類型的任務。對每個目標區域，將其對應的四類任務分別記為m、M+m、2M+m、3M+m。任務總個數記為N=4M。根據前述三種目標區域類型，即A1、A2、A3，將需要執行的任務集合記為W1，將不需要執行的任務集合記為W2={1,2,…,N}-W1。

設集群由K個無人裝備組成，其中K1個為跨域或兩棲裝備，K2個為陸域裝備，K3個為海域裝備。將陸域、海域無人裝備的集合分別記為Cg、Cw。根據每個無人裝備上搭載的載荷的性能，可以將其四類任務能力分別量化為PR,m、PEI,m、PA,m、PDA,m。對小型無人裝備，可能只有一種任務載荷，即只有一個任務能力非0，其余任務能力均為0.將每個無人裝備的平均任務速度記為Vk，航時記為Tk，初始位置記為qV,k，其中k=1,2,…,K。

1.2 模型建立

上述任務規劃問題可以建模為混合整數線性規劃(Mixed Integer Linear Programming, MILP)模型。該模型的目標函數為

(1)

(2)

其中,每個無人裝備的任務總時間滿足

(3)

所有無人裝備需要滿足其最大航時約束，即

(4)

為避免每個無人裝備循環執行某些任務，形成子回路，需要加入Miller-Tucker-Zemlin子回路消除約束[11]。由于每個任務需要多個集群成員同時執行才能完成，所以原子回路消除約束需要變更為如下形式

(5)

其中，整數決策變量滿足ui

要保證完成每個需求任務，需要滿足

(6)

其中，rj表示任務j的類型序號。

對每個無人裝備，為保證其任務連續性，需要滿足

(7)

即其到達哪個任務，下一步就需要從哪個任務出發。

對每個無人裝備，它從初始狀態出發，并最終回到初始位置，這要求

(8)

(9)

(10)

不同類型任務的時序關系要求下式滿足

(11)

式中：Δt為對同一個目標區域的兩個連續類型任務之間的最小時間間隔。

為節省任務時間，每個無人裝備上的彈藥全部用于對一個目標區域的攻擊，而不是在多個目標區域各使用一部分彈藥，這需要滿足

(12)

不同域的無人裝備只能執行其所在域的任務，據此，我們有

(13)

對無需執行的任務，有

(14)

對每個無人裝備，當它的某種任務能力為0時，需要有

(15)

式中:i=0,1,2,…,N;j=(r-1)M+1,(r-1)M+2,…,rM;k=1,2,…,K;r=1,2,3,4且滿足Pk,r=0。

2 分支定界法

分支定界法是求解混合整數線性規劃問題的一種經典且有效的方法，該方法能保證得到問題的最優解(前提是問題有最優解)。該方法首先求解不考慮整數約束(稱為松弛)的線性規劃問題，根據其解對原問題進行“分支”，繼續對分支問題進行松弛、求解，確定出原問題的上界和下界(“定界”)，直到滿足所有整數約束。

分支定界法的步驟為[12]：

步驟3：問題選取。從L中選取一個問題Pl，并將其從L中移除。

步驟5：添加割平面。尋找解xlR不滿足的割平面。若能找到，將其添加到松弛問題，并轉到步驟4。

3 仿真結果

考慮下面的立體跨域任務規劃場景。集群由K=20個無人裝備組成，其中13個(K1)為跨域裝備，4個(K2)為陸域裝備，3個(K3)為海域裝備。各裝備的航時、平均速度、任務能力值如1所示。共有5個目標區域，前兩個為海面區域，后三個為陸地區域，即Bw={1,2}、Bg={3,4,5}。三種類型區域的集合分別為A1={1}、A2={2,3}、A3={4,5}。各區域的需求任務能力值如表2所示。

表1 各裝備的航時、平均速度、任務能力值

表2 各區域的需求任務能力值

利用本文方法得到的任務規劃結果如圖1和表3所示。5個目標區域的任務分別用紅色、藍色、黑色、綠色、品紅色方塊表示，方塊對應的橫坐標為任務完成時間，對應的縱坐標為執行該任務的無人裝備集。圖中的橢圓形為每個無人裝備的返回時間。從表4的第三、四列可以看到，不同類型任務的時序約束是滿足的。表4的第六、七列分別為對應任務的能力需求值和分配給該任務的總能力值，可以看到，每個需求任務均由有足夠能力的無人裝備子群完成，第五列給出了完成每個需求任務的無人裝備子群。不難看到，陸域無人裝備(14、15、16、17)僅對陸域的目標區域(區域3、4、5)執行任務，而海域無人裝備(18、19、20)僅對海域的目標區域(區域1、2)執行任務。若不計無人裝備的返回，最優總任務時間約為1 646.42 s。若計入無人裝備的返回，最優總任務時間約為1 718 s。

圖1 任務規劃結果

表3 任務規劃結果

值得注意的是，除本文所使用的分支定界法外，一些常用的啟發式方法，如蟻群算法、粒子群算法、遺傳算法等，也可以用于求解所討論的立體跨域耦合任務規劃問題。本文所使用的分支定界法盡管所用計算時間較長，但能保證獲取規劃的最優解；相比之下，啟發式方法雖然在問題規模較小、群體規模較小、迭代次數較少時計算時間較短，但并不能保證所獲得的解為最優解，可能僅為局部最優解。因此，本文所述方法可以用于離線規劃，啟發式方法可以用于問題規模較小時的在線規劃。

5 結 語

本文給出了一種基于分支定界法的面向立體跨域耦合任務的無人集群協同任務規劃技術。任務規劃以最小化總任務時間為優化目標，考慮了四種類型任務之間的時序約束關系，考慮了不同類型集群裝備的任務域約束、載荷能力約束、航時約束等。從仿真結果中可以看到，所設計技術能為異構無人集群的跨域協同任務提供最優策略。作為一個未來的研究工作，我們將為立體跨域耦合任務規劃問題尋求一種次優、計算代價較小的啟發式解決方案。