梁月乾， 張 瀟， 楊 毅

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

0 引 言

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

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

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

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

1.1 問(wèn)題描述

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

設(shè)有M個(gè)目標(biāo)區(qū)域，其中包含未知數(shù)量和類型的目標(biāo)。將區(qū)域位置記為qm，m=1,2,…,M。陸域、海域目標(biāo)區(qū)域的集合分別記為Bg、Bw。與所在域無(wú)關(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ū)域的個(gè)數(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ū)域中的分布情況等，量化每個(gè)目標(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，表示無(wú)需對(duì)相應(yīng)目標(biāo)區(qū)域執(zhí)行該類型的任務(wù)。對(duì)每個(gè)目標(biāo)區(qū)域，將其對(duì)應(yīng)的四類任務(wù)分別記為m、M+m、2M+m、3M+m。任務(wù)總個(gè)數(shù)記為N=4M。根據(jù)前述三種目標(biāo)區(qū)域類型，即A1、A2、A3，將需要執(zhí)行的任務(wù)集合記為W1，將不需要執(zhí)行的任務(wù)集合記為W2={1,2,…,N}-W1。

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

1.2 模型建立

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

(1)

(2)

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

(3)

所有無(wú)人裝備需要滿足其最大航時(shí)約束，即

(4)

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

(5)

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

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

(6)

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

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

(7)

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

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

(8)

(9)

(10)

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

(11)

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

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

(12)

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

(13)

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

(14)

對(duì)每個(gè)無(wú)人裝備，當(dāng)它的某種任務(wù)能力為0時(shí)，需要有

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

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

步驟3：?jiǎn)栴}選取。從L中選取一個(gè)問(wèn)題Pl，并將其從L中移除。

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

3 仿真結(jié)果

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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