一種面向立體跨域耦合任務(wù)的無人集群協(xié)同任務(wù)規(guī)劃技術(shù)

梁月乾， 張 瀟， 楊 毅

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

0 引 言

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

任務(wù)規(guī)劃方法大致可以分為兩類[1]：精確優(yōu)化方法和啟發(fā)式方法。精確優(yōu)化方法利用匈牙利法、分支定界法等對建模的旅行商問題、車輛路由問題、網(wǎng)絡(luò)流問題等進(jìn)行求解，通常可以得到最優(yōu)任務(wù)規(guī)劃方案[2-3]。啟發(fā)式方法包括從生物系統(tǒng)的群集行為中發(fā)現(xiàn)的遺傳算法、粒子群優(yōu)化算法、蟻群優(yōu)化算法等[4-8]，以及從社會規(guī)律中發(fā)現(xiàn)的基于市場機制的方法等[9-10]。通過設(shè)置不同迭代次數(shù)，啟發(fā)式方法可以獲得不同優(yōu)化程度的任務(wù)規(guī)劃方案。

本文以異構(gòu)集群的立體跨域協(xié)同為背景，研究存在不同類型和任務(wù)域的多個目標(biāo)區(qū)域、處于不同任務(wù)域的多種集群平臺的耦合時序任務(wù)的協(xié)同規(guī)劃問題。

1 立體跨域耦合任務(wù)規(guī)劃模型

1.1 問題描述

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

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

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

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

1.2 模型建立

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

(1)

(2)

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

(3)

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

(4)

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

(5)

其中，整數(shù)決策變量滿足ui

要保證完成每個需求任務(wù)，需要滿足

(6)

其中，rj表示任務(wù)j的類型序號。

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

(7)

即其到達(dá)哪個任務(wù)，下一步就需要從哪個任務(wù)出發(fā)。

對每個無人裝備，它從初始狀態(tài)出發(fā)，并最終回到初始位置，這要求

(8)

(9)

(10)

不同類型任務(wù)的時序關(guān)系要求下式滿足

(11)

式中：Δt為對同一個目標(biāo)區(qū)域的兩個連續(xù)類型任務(wù)之間的最小時間間隔。

為節(jié)省任務(wù)時間，每個無人裝備上的彈藥全部用于對一個目標(biāo)區(qū)域的攻擊，而不是在多個目標(biāo)區(qū)域各使用一部分彈藥，這需要滿足

(12)

不同域的無人裝備只能執(zhí)行其所在域的任務(wù)，據(jù)此，我們有

(13)

對無需執(zhí)行的任務(wù)，有

(14)

對每個無人裝備，當(dāng)它的某種任務(wù)能力為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 分支定界法

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

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

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

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

3 仿真結(jié)果

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

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

表2 各區(qū)域的需求任務(wù)能力值

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

圖1 任務(wù)規(guī)劃結(jié)果

表3 任務(wù)規(guī)劃結(jié)果

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

5 結(jié) 語

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