范學滿,王新鵬,薛昌友

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

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

目前,常用的UUV協(xié)同任務(wù)分配方法包括合同網(wǎng)法、線性規(guī)劃法、群體智能法等。文獻[2]基于傳統(tǒng)合同網(wǎng)算法和蟻群算法,提出一種改進的合同網(wǎng)優(yōu)化算法,為每個目標函數(shù)分配一個蟻群,綜合多個優(yōu)化函數(shù),確定任務(wù)分配方案。文獻[3]將協(xié)同任務(wù)分配問題等價于0-1整數(shù)線性規(guī)劃問題,提出一種單編隊、多目標時序約束條件下的任務(wù)分配模型。文獻[4]針對不確定性環(huán)境中的任務(wù)重分配需求,提出一種滾動時域微分進化量子蜂群優(yōu)化算法,使得UUV可以根據(jù)即時位置和航向等信息,定期或不定期地實現(xiàn)任務(wù)重分配。上述算法通常將多UUV的任務(wù)分配與航路規(guī)劃作為兩個相對獨立的步驟進行分析,通過任務(wù)分配確定各UUV的任務(wù)集合,隨后進行航路規(guī)劃,確定各UUV的任務(wù)執(zhí)行序列。這種分步策略,雖然降低了任務(wù)分配問題的復雜度,但增加了航路規(guī)劃問題的難度,也在很大程度上導致了以時間最短為目標函數(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、多目標情況下的協(xié)同偵察任務(wù)分配問題,以遺傳算法[5]作為方案尋優(yōu)的基本框架,在此基礎(chǔ)上引入動態(tài)規(guī)劃法[6]解決UUV遍歷任務(wù)節(jié)點時的最短路徑問題,即旅行商問題(Traveling Salesman Problem,TSP),綜合確定高效合理、負載均衡的任務(wù)分配方案。

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

1.1 模型假設(shè)

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

1)任務(wù)目標事先確定,同時環(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)目標集。dij為節(jié)點i與節(jié)點j間的距離(i,j∈V),且dij=dji。ri為完成對目標i的偵察所得的收益,且ri>0(i≠0)。ti為UUV到達目標i后對其完成偵察任務(wù)所需的時間。Tmax1、Tmax2分別為協(xié)同偵察任務(wù)的時間上限和最長UUV續(xù)航時間,如果一個UUV到達目標i,且任務(wù)剩余時間或續(xù)航剩余時間小于ti,則該UUV不能獲得收益ri。

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

(1)

式中,yik為布爾變量,當UUVk負責偵察目標i時,取值為1,反之為0;xijk為布爾變量,當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ù)。

對于上述多目標優(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ù)分配是一個多目標優(yōu)化問題,可以利用遺傳算法、差分進化算法、粒子群算法等進化算法進行解決[9]。對于遺傳算法,目前具有代表性的多目標優(yōu)化遺傳算法有帕累托排序法、非支配排序法、多目標函數(shù)加權(quán)以及基于參考點的多目標進化算法等。本文選擇經(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-Ⅱ作為基本框架用于求解多目標優(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ù)之一,其基本思想是把復雜的多階段決策問題劃分為多個易于解決的子問題,每個子問題對應(yīng)決策過程的一個階段。通常,劃分所得的子問題之間有一定重疊。動態(tài)規(guī)劃法在求得子問題的解后,會記錄在表中,后續(xù)用到子問題解時,只需查表即可,無須重復計算,從而避免了大量重復計算,提升了尋優(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|,即待偵察目標總數(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,表示目標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)一個二元目標函數(shù)值矩陣:

(8)

式中,f1(·)=N、f2(·)=T分別對應(yīng)兩個最小化優(yōu)化目標;每行對應(yīng)Chrom中相應(yīng)個體的目標函數(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ù)序列上計算目標函數(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個待偵察目標,想定場景如圖7所示。圖中,“■”表示UUV母港,“●”表示待偵察目標。

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

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

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

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

對比圖10與圖13可知,圖13的任務(wù)分配方案中存在大量往復、折返航行的情況,從而導致浪費大量航程和任務(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)化目標等復雜情況,進行更深入的研究。