基于混合優(yōu)化算法的多UUV協(xié)同偵察任務(wù)分配方法研究

范學(xué)滿,王新鵬,薛昌友

(1.海軍潛艇學(xué)院,山東 青島 266199;2.中國人民解放軍92682部隊,廣東 湛江 524000)

利用搭載傳感器載荷的無人潛航器(Unmanned Underwear Vehicle,UUV)執(zhí)行對海偵察任務(wù)是UUV典型的應(yīng)用方向之一。單個UUV存在巡航時間、載荷數(shù)量以及種類等諸多限制,造成其偵察能力有限,往往需要多UUV協(xié)同完成對敵方目標(biāo)的偵察任務(wù)。此時,根據(jù)任務(wù)的復(fù)雜度、UUV數(shù)量以及任務(wù)能力等,對任務(wù)進行合理分配,對于提高任務(wù)執(zhí)行效率至關(guān)重要[1]。

目前,常用的UUV協(xié)同任務(wù)分配方法包括合同網(wǎng)法、線性規(guī)劃法、群體智能法等。文獻[2]基于傳統(tǒng)合同網(wǎng)算法和蟻群算法,提出一種改進的合同網(wǎng)優(yōu)化算法,為每個目標(biāo)函數(shù)分配一個蟻群,綜合多個優(yōu)化函數(shù),確定任務(wù)分配方案。文獻[3]將協(xié)同任務(wù)分配問題等價于0-1整數(shù)線性規(guī)劃問題,提出一種單編隊、多目標(biāo)時序約束條件下的任務(wù)分配模型。文獻[4]針對不確定性環(huán)境中的任務(wù)重分配需求,提出一種滾動時域微分進化量子蜂群優(yōu)化算法,使得UUV可以根據(jù)即時位置和航向等信息,定期或不定期地實現(xiàn)任務(wù)重分配。上述算法通常將多UUV的任務(wù)分配與航路規(guī)劃作為兩個相對獨立的步驟進行分析,通過任務(wù)分配確定各UUV的任務(wù)集合,隨后進行航路規(guī)劃,確定各UUV的任務(wù)執(zhí)行序列。這種分步策略,雖然降低了任務(wù)分配問題的復(fù)雜度,但增加了航路規(guī)劃問題的難度,也在很大程度上導(dǎo)致了以時間最短為目標(biāo)函數(shù)的任務(wù)分配方案的次優(yōu)性。

針對上述問題,本文在多UUV協(xié)同偵察任務(wù)分配中,顯式地考慮任務(wù)節(jié)點間的距離,利用UUV從母港出發(fā)遍歷任務(wù)節(jié)點并返回母港的最短路徑,來輔助確定各UUV的任務(wù)集合及執(zhí)行序列,從而將多UUV協(xié)同任務(wù)分配與單UUV全局路徑規(guī)劃有機融合,有效緩解任務(wù)分配與路徑規(guī)劃分離造成的次優(yōu)性問題。本文研究多UUV、多目標(biāo)情況下的協(xié)同偵察任務(wù)分配問題,以遺傳算法[5]作為方案尋優(yōu)的基本框架,在此基礎(chǔ)上引入動態(tài)規(guī)劃法[6]解決UUV遍歷任務(wù)節(jié)點時的最短路徑問題,即旅行商問題(Traveling Salesman Problem,TSP),綜合確定高效合理、負(fù)載均衡的任務(wù)分配方案。

1 多UUV協(xié)同偵察任務(wù)分配模型

1.1 模型假設(shè)

多UUV協(xié)同偵察任務(wù)分配問題是一個典型的多約束、多參數(shù)的非確定多項式(Non-deterministic Polynomial,NP)問題,該問題涉及系統(tǒng)結(jié)構(gòu)、單體UUV、任務(wù)目標(biāo)和外界環(huán)境等多方面因素,考慮不同因素時的模型求解策略有較大不同。本文的基本假設(shè)如下:

1)任務(wù)目標(biāo)事先確定,同時環(huán)境因素已知且不發(fā)生重大變化;

2)任務(wù)之間不存在約束關(guān)系;

3)每個偵察任務(wù)由單個UUV即可完成;

4)執(zhí)行偵察任務(wù)的UUV總數(shù)是固定的。

1.2 問題描述

UUV協(xié)同偵察任務(wù)分配屬于團隊定向問題(Team Orienteering Problem,TOP)的范疇[7],即在考慮UUV航程、UUV個體數(shù)量以及任務(wù)時間等限制條件下使收益最大化。TOP問題可以用有向圖表示。假設(shè)G=(V,A)為完全圖,其中,V為節(jié)點集,A為邊集。V中0號節(jié)點對應(yīng)母港的位置,集合M=V{0}={1,2,…,m}對應(yīng)目標(biāo)集。dij為節(jié)點i與節(jié)點j間的距離(i,j∈V),且dij=dji。ri為完成對目標(biāo)i的偵察所得的收益,且ri>0(i≠0)。ti為UUV到達目標(biāo)i后對其完成偵察任務(wù)所需的時間。Tmax1、Tmax2分別為協(xié)同偵察任務(wù)的時間上限和最長UUV續(xù)航時間,如果一個UUV到達目標(biāo)i,且任務(wù)剩余時間或續(xù)航剩余時間小于ti,則該UUV不能獲得收益ri。

假設(shè)K為UUV集合,綜合考慮所需UUV數(shù)量和協(xié)同完成偵察任務(wù)所需總時間,設(shè)置兩個優(yōu)化目標(biāo):其一是使用于偵察的UUV數(shù)量盡可能少,其二是使任務(wù)完成時間盡可能短。由此,可得多目標(biāo)優(yōu)化問題:

(1)

式中,yik為布爾變量,當(dāng)UUVk負(fù)責(zé)偵察目標(biāo)i時,取值為1,反之為0;xijk為布爾變量,當(dāng)UUVk的航路經(jīng)由邊(i,j)時,取值為1,反之為0;sk為UUV的航速;|K|為可用于偵察的UUV總數(shù)目;N表示實際用于執(zhí)行偵察任務(wù)的UUV數(shù)量,N≤|K|;T為多UUV協(xié)同完成偵察任務(wù)的時間,即參與偵察UUV任務(wù)執(zhí)行時間的最大值:

T=max{T1,T2,…,Tk,…,TN}

(2)

式中,Tk為UUVk完成偵察任務(wù)的時間。

通過求解式(1),可以確定實際用于偵察的UUV數(shù)量N,以及每個UUV的任務(wù)子集

(3)

式中,ni為UUVi需要執(zhí)行的任務(wù)個數(shù)。

對于上述多目標(biāo)優(yōu)化問題,使用的UUV數(shù)量盡可能少與任務(wù)完成時間盡可能短之間存在沖突,通常不能同時達到最優(yōu),所以,最優(yōu)解不一定只有一個,這樣的最優(yōu)解稱為Pareto最優(yōu)解或“非支配解”,所有Pareto最優(yōu)解構(gòu)成的集合稱為Pareto前沿[8]。

2 基于混合優(yōu)化算法的任務(wù)分配方法

多UUV協(xié)同偵察任務(wù)分配是一個多目標(biāo)優(yōu)化問題,可以利用遺傳算法、差分進化算法、粒子群算法等進化算法進行解決[9]。對于遺傳算法,目前具有代表性的多目標(biāo)優(yōu)化遺傳算法有帕累托排序法、非支配排序法、多目標(biāo)函數(shù)加權(quán)以及基于參考點的多目標(biāo)進化算法等。本文選擇經(jīng)典的非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm Ⅱ,NSGA-Ⅱ)進行優(yōu)化。

對于同一任務(wù)子集,執(zhí)行順序不同,收益和代價會有顯著不同,因此,將任務(wù)規(guī)劃劃分為任務(wù)分配與路徑規(guī)劃兩個相對獨立的階段,通過任務(wù)分配確定任務(wù)子集,在此基礎(chǔ)上,通過路徑規(guī)劃確定執(zhí)行順序,極易造成總體任務(wù)規(guī)劃方案的次優(yōu)性問題[10]。為了有效解決這一問題,將航路規(guī)劃的部分操作前移,在任務(wù)分配階段考慮任務(wù)執(zhí)行順序?qū)θ蝿?wù)執(zhí)行時間的影響。出于效率的考慮,本文選擇動態(tài)規(guī)劃算法用于任務(wù)子集執(zhí)行順序的優(yōu)化。

綜上所述,本文將NSGA-Ⅱ與動態(tài)規(guī)劃算法相結(jié)合,以NSGA-Ⅱ作為基本框架用于求解多目標(biāo)優(yōu)化問題,將動態(tài)規(guī)劃算法嵌入NSGA-Ⅱ框架中,用于優(yōu)化確定任務(wù)子集的執(zhí)行順序,基于優(yōu)化后的執(zhí)行順序計算相應(yīng)任務(wù)子集的收益和代價。可得混合優(yōu)化算法的流程如圖1所示。

圖1 混合優(yōu)化算法流程

2.1 基于動態(tài)規(guī)劃的TSP問題求解

圖2 TSP問題示意圖

動態(tài)規(guī)劃法是求解多階段決策最優(yōu)化問題的技術(shù)之一,其基本思想是把復(fù)雜的多階段決策問題劃分為多個易于解決的子問題,每個子問題對應(yīng)決策過程的一個階段。通常,劃分所得的子問題之間有一定重疊。動態(tài)規(guī)劃法在求得子問題的解后,會記錄在表中,后續(xù)用到子問題解時,只需查表即可,無須重復(fù)計算,從而避免了大量重復(fù)計算,提升了尋優(yōu)效率[11]。圖3給出了動態(tài)規(guī)劃法的求解過程。

圖3 動態(tài)規(guī)劃法的求解過程

對于單個UUV,其任務(wù)點和母港構(gòu)成節(jié)點集V,節(jié)點間的兩兩連線構(gòu)成邊集E,可用圖G=(V,E)表示。d(s,V′)表示從母港s出發(fā),經(jīng)所有任務(wù)節(jié)點V′=V-{s}一次且只有一次,最后返回母港s的最短路徑長度,則動態(tài)規(guī)劃函數(shù)為

d(s,V′)=min{cks+d(k,V′-{k})},k∈V′

(4)

式中,cks為節(jié)點k到s的路徑長度:

cks=d(k,s),k≠s

(5)

通過動態(tài)規(guī)劃進行優(yōu)化,可以得到每個UUV任務(wù)子集的任務(wù)執(zhí)行序列,該任務(wù)序列將作為NSGA-Ⅱ的種群個體參與多UUV任務(wù)分配的進化尋優(yōu)。

2.2 NSGA-Ⅱ優(yōu)化框架

NSGA-Ⅱ算法的基本思想為:首先,進行種群的隨機初始化,非支配排序后通過選擇、交叉、變異等進化操作得到第一代子代種群;然后,從第二代開始,將合并父代與子代種群,進行快速非支配排序,同時對每個非支配層中的個體進行擁擠度計算,根據(jù)非支配關(guān)系以及個體的擁擠度選取合適的個體組成新的父代種群;最后,通過遺傳進化操作產(chǎn)生新的子代種群;依此類推,直到滿足終止條件為止[12]。

本文將種群染色體表示為二維矩陣,記為

(6)

式中,Nind為種群的規(guī)模,即種群的個體數(shù);Lind為種群個體的染色體長度,此處Lind=|M|,即待偵察目標(biāo)總數(shù)。

Chrom中每行對應(yīng)一個個體的染色體,個體染色體采用“整數(shù)編碼”方式,對于Chrom中的任一個體可表示為如下行向量

Chromi=(xi,1,xi,2,…,xi,Lind),i=1,2,…,Nind

(7)

式中,xi,j∈{1,2,…,|K|},j=1,2,…,Lind,表示目標(biāo)j分配給UUVi進行偵察。Chromi則對應(yīng)多UUV協(xié)同偵察任務(wù)分配的一個方案,如圖4所示。

圖4 協(xié)同任務(wù)分配方案

圖4中,N≤|K|,即可能只需要使用部分UUV即可完成協(xié)同偵察任務(wù);{m1,m2,…,mh1}為分配給UUV 1的任務(wù)子集,不同UUV的任務(wù)子集的交集為空。

由式(1)可知,式(6)所示的種群矩陣對應(yīng)一個二元目標(biāo)函數(shù)值矩陣:

(8)

式中,f1(·)=N、f2(·)=T分別對應(yīng)兩個最小化優(yōu)化目標(biāo);每行對應(yīng)Chrom中相應(yīng)個體的目標(biāo)函數(shù)值。

圖5 協(xié)同任務(wù)分配方案(動態(tài)規(guī)劃優(yōu)化后)

本文將動態(tài)規(guī)劃的尋優(yōu)結(jié)果納入NSGA-Ⅱ優(yōu)化框架,只需要在進行快速非支配排序前,利用動態(tài)規(guī)劃算法進行任務(wù)子集的TSP尋優(yōu),在尋優(yōu)所得的任務(wù)序列上計算目標(biāo)函數(shù)值,然后,進行非支配排序即可。改進后的NSGA-Ⅱ如圖6所示。

圖6 改進后的NSGA-Ⅱ算法流程

通過將動態(tài)規(guī)劃嵌入NSGA-Ⅱ優(yōu)化框架中,可以利用動態(tài)規(guī)劃法優(yōu)化得到的任務(wù)執(zhí)行序列作為啟發(fā)信息,減小NSGA-Ⅱ的搜索寬度,增大NSGA-Ⅱ的搜索深度,有效提升NSGA-Ⅱ優(yōu)化效率。

3 實驗分析

假設(shè)共有7個可用于偵察的UUV,UUV的航速為8 kn,所有UUV均從同一母港出發(fā)。待偵察區(qū)域為20 nmile×20 nmile的正方形區(qū)域,其中,隨機分布40個待偵察目標(biāo),想定場景如圖7所示。圖中,“■”表示UUV母港,“●”表示待偵察目標(biāo)。

圖7 想定場景示意圖

為了驗證混合優(yōu)化算法的可行性,將經(jīng)典NSGA-Ⅱ算法作為基線算法。對于混合算法和經(jīng)典NSGA-Ⅱ算法,均設(shè)置種群規(guī)模Nind=100,進化代數(shù)maxGen=200,變異算子的變異概率Pm=0.3,交叉算子的交叉概率Pr=0.9。軟件方面,使用Python開源進化算法工具箱Geatpy2[13]進行算法開發(fā);硬件配置為:Intel(R)_Core(TM)_i7-6700HQ CPU,主頻2.60 GHz,內(nèi)存16 GB。

3.1 混合優(yōu)化算法結(jié)果分析

混合優(yōu)化算法得到的Pareto非支配解集中共95個解,對應(yīng)的Pareto前沿如圖8所示。

圖8 混合優(yōu)化算法的Pareto前沿

由圖8可知,95個非支配解在兩個優(yōu)化目標(biāo)上大多數(shù)是重合的,因此,在圖上融合為兩個點。實際應(yīng)用中,可以根據(jù)任務(wù)需求和偏好任選一個方案。當(dāng)然,出于節(jié)省能源考慮,可以將各UUV航行距離之和盡可能小作為方案進一步優(yōu)選的依據(jù)。95個非支配解對應(yīng)的總航行距離如圖9所示。

圖9 混合優(yōu)化算法各方案的UUV總航行距離

由圖9可見,各方案在總航行距離這一指標(biāo)上有較大差異,95個方案中最小總航程為220.13 nmile,對應(yīng)72號方案;最大總航程為258.57 nmile,對應(yīng)75號方案。另外,72號方案對應(yīng)的UUV數(shù)目為6,任務(wù)完成時間為4.85 h;75號方案對應(yīng)的UUV數(shù)目為7,任務(wù)完成時間為4.83 h。72號方案在減少出動1個UUV的基礎(chǔ)上,進一步縮短了總航程,因此,在任務(wù)不緊迫的情況下推薦使用72號方案,其對應(yīng)的任務(wù)分配結(jié)果如圖10所示。

圖10 混合優(yōu)化算法的任務(wù)分配方案

3.2 NSGA-Ⅱ算法結(jié)果分析

NSGA-Ⅱ算法得到的Pareto非支配解集中共9個解,對應(yīng)的Pareto前沿如圖11所示?？梢?9個解重疊為3個前沿點,與圖8對比可知,無論實際使用幾個UUV,任務(wù)完成時間均長于混合算法得到的方案。

圖11 NSGA-Ⅱ算法的Pareto前沿

9個非支配解對應(yīng)的總航行距離如圖12所示。

圖12 各方案的UUV總航行距離

由圖12可見,各方案在總航行距離這一指標(biāo)上有較大差異,0號方案總航程最小,為330.07 nmile;4號方案總航程最大,為376.48 nmile。即便是最小航程也明顯大于混合優(yōu)化算法的最長航程。下面給出任務(wù)完成時間最短方案(0號方案)的任務(wù)分配結(jié)果如圖13所示。

圖13 NSGA-Ⅱ算法的任務(wù)分配方案

對比圖10與圖13可知,圖13的任務(wù)分配方案中存在大量往復(fù)、折返航行的情況,從而導(dǎo)致浪費大量航程和任務(wù)時間。而混合優(yōu)化算法通過利用動態(tài)規(guī)劃優(yōu)化任務(wù)序列,有效緩解了上述問題,提升了任務(wù)分配方案的合理性。

4 結(jié)束語

為了提升多UUV協(xié)同偵察靜態(tài)任務(wù)規(guī)劃方案的整體最優(yōu)性,將航路規(guī)劃的部分工作前移至靜態(tài)任務(wù)分配階段,使得任務(wù)分配在為各UUV指派任務(wù)子集的基礎(chǔ)上,還能給出具有一定參考價值的任務(wù)執(zhí)行序列?；谏鲜鏊枷?將動態(tài)規(guī)劃法嵌入NSGA-Ⅱ的進化框架,提出一種混合優(yōu)化算法,該算法能夠在兼顧UUV數(shù)目和任務(wù)完成時間的基礎(chǔ)上,給出總航程更優(yōu)的任務(wù)執(zhí)行序列。在典型場景下進行仿真對比實驗,實驗結(jié)果表明:在任務(wù)分配過程中顯式地考慮任務(wù)執(zhí)行順序?qū)Ψ桨感阅艿挠绊?能夠提升尋優(yōu)方案的質(zhì)量。后續(xù)將在此基礎(chǔ)上,考慮多約束條件、多優(yōu)化目標(biāo)等復(fù)雜情況,進行更深入的研究。