一種改進CSA算法的UAV多任務區(qū)偵察決策問題研究

張耀中， 陳 嵐， 張 蕾， 謝松巖

(西北工業(yè)大學電子信息學院，西安 710129)

0 引言

由于UAV具有較低的應用成本和較好的機動性，使其成為戰(zhàn)場上被廣泛使用的一種偵察手段。UAV可以在“危險、惡劣、枯燥”的任務環(huán)境中替代有人機執(zhí)行戰(zhàn)場偵察任務[1]。UAV任務偵察一般是指通過UAV所攜帶的任務載荷，來獲取特定任務區(qū)域內(nèi)情報信息的過程[2]。如何在UAV執(zhí)行偵察任務前進行最優(yōu)的任務規(guī)劃，從而有效提高UAV的任務執(zhí)行效率已經(jīng)成為該領域中的一個研究熱點問題，受到了諸多研究者的關注。如文獻[3]在考慮三維任務環(huán)境和禁飛區(qū)限制的條件下，給出了一種基于改進的遺傳算法求解方案來進行多UAV的路徑規(guī)劃，從而獲得對目標區(qū)域的最大偵察信息;文獻[4]提出了一種基于改進的自適應進化多目標優(yōu)化算法來進行多UAV協(xié)同任務偵察，取得了良好的任務偵察效果。

通過分析大量的文獻可以看出，目前研究者一般側(cè)重于任務的航路規(guī)劃和偵察搜救問題，大多未考慮UAV攜帶特定偵察載荷時的偵察信息收益最大化問題，該問題在很多應用場景中具有相應的實際意義。在高度復雜的戰(zhàn)場環(huán)境中、震后的災情分析中或大面積海域的海情偵察與搜索中，一般都有大量的熱點區(qū)域需要UAV攜帶特定偵察載荷去執(zhí)行信息收集任務。由于UAV所攜帶任務載荷的工作時間及能力都是有限的，通常難以完成對全部任務區(qū)的完全信息偵察，因此，如何能夠快速有效地完成對所有任務區(qū)的非完全信息遍歷偵察是本文的研究內(nèi)容。本文提出一種將仿生智能算法——布谷鳥搜索算法[5-7]應用于UAV多任務區(qū)的協(xié)同偵察問題，很好地解決了對該類問題求解的快速性和有效性，從而為實際應用提供了決策依據(jù)[8-10]。

1 問題描述

在戰(zhàn)場中的情報收集、震區(qū)災情搜集與救援以及廣域海上搜救等諸多任務中，經(jīng)常需要單架UAV對任務區(qū)中多個感興趣的區(qū)域進行信息偵察。由于UAV的性能、攜帶載荷的有效工作時間及載荷的工作能力都是受限的，如何規(guī)劃出最優(yōu)的任務路徑，同時規(guī)劃出載荷在各個感興趣區(qū)域的工作時間對整個偵察任務的完成效果都有極大的影響[11-12]。設定任務場景中存在N個感興趣的待偵察區(qū)域，如圖1所示。

圖1 UAV多任務區(qū)偵察規(guī)劃示意圖Fig.1 Reconnaissance planning of UAV multi-task area

圖中，tij表示從任務區(qū)i到任務區(qū)j的任務飛行時間，其中，i=0時表示基地。假定N個待偵察任務區(qū)的位置、范圍及所需任務載荷均為已知，則對任務區(qū)的偵察信息收益就主要體現(xiàn)在UAV所獲取的偵察情報，通常偵察情報的獲得主要由UAV在該任務區(qū)內(nèi)載荷的工作時間決定，載荷工作時間越長，所獲得的對該任務區(qū)的情報信息就越多。通過研究，本文引入對任務區(qū)的偵察信息確定性指標來度量任務載荷的偵察信息收益，通常在UAV進入預定任務區(qū)之前對該任務區(qū)的先驗情報信息為0，隨著偵察載荷工作時間的增加，對該任務區(qū)的信息確定性度量值將逐漸增加，當該任務區(qū)的信息確定性指標接近1時就完成對該任務區(qū)的完全信息偵察。通常UAV在偵察過程中由于續(xù)航時間及載荷持續(xù)工作時間等的約束，難以完成對全部任務區(qū)的完全信息偵察，通常也沒有必要進行完全信息偵察。因此，如何在滿足相應約束條件下使UAV對所有待偵察任務區(qū)綜合偵察信息確定性指標達到最大化是本文要解決的問題。

2 布谷鳥搜索算法(CSA)

在UAV執(zhí)行對多任務區(qū)的偵察問題中，對感興趣任務區(qū)的傳感器工作時間分配問題屬于連續(xù)時間約束的非線性規(guī)劃問題，是典型的NP Hard問題。由英國劍橋大學YANG等提出的布谷鳥搜索算法(Cuckoo Search Algorithm,CSA)在解決該類問題時表現(xiàn)出了較好的計算性能，因此，選擇CSA進行相應的改進來求解該問題。

2.1 CSA介紹

CSA主要是基于北美一種布谷鳥的寄生孵化行為，并采用Lévy飛行的隨機游走進化策略[5]來進行最優(yōu)解的獲取。該算法設計了3條基本規(guī)則:1) 每只布谷鳥每次只能產(chǎn)下一枚蛋，同時布谷鳥隨機地選取一個其他種類的鳥巢進行寄生孵化;2) 具有最優(yōu)性能的鳥巢會被保存到進化過程的下一代;3) 用來寄生孵化的鳥巢數(shù)目固定，設宿主鳥發(fā)現(xiàn)外來鳥蛋的概率為pa,假如宿主鳥發(fā)現(xiàn)了外來鳥蛋，則宿主鳥或拋棄這個蛋，或拋棄該鳥巢，并尋找新的位置重建鳥巢。該進化算法操作簡單，只需設置鳥巢數(shù)量n和宿主鳥發(fā)現(xiàn)外來鳥蛋概率pa兩個參數(shù)。

CSA的進化過程主要包括最優(yōu)鳥巢的選擇、局部隨機擾動、全局Lévy飛行隨機選擇3個過程[7]。

1) 最優(yōu)巢穴的選擇。在算法迭代過程中，保留當前代中性能最好的巢穴直接進入下一代種群中，以保證算法的迭代性能，類似于遺傳算法中的精英保留主義。

2) CSA的局部隨機擾動。算法進化過程中疊加隨機擾動，保證種群的多樣性。局部隨機擾動過程為

(1)

3) 采用Lévy飛行過程進行算法迭代。

算法的迭代進化過程采用全局Lévy飛行隨機游走策略進行，即

(2)

式中:

(3)

2.2 CSA的基本處理流程

CSA的基本處理流程如圖2所示。

圖2 CSA流程圖Fig.2 Flow chart of CSA

2.3 CSA的離散化方案

CSA在解決連續(xù)變量最優(yōu)化問題中顯示出良好性能，但是標準的CSA只能求解具有連續(xù)型變量的最優(yōu)化問題，無法求解離散型變量的最優(yōu)化問題[13-14]。在本文中采用一種基于Lévy隨機分布策略的插入、交換、倒置操作算子來進行算法的離散化，從而求解最優(yōu)偵察路徑規(guī)劃問題。離散布谷鳥搜索算法處理流程見圖3。

圖3 離散布谷鳥搜索算法流程圖Fig.3 Flow chart of discrete CSA

2.4 CSA的改進策略

基本型的CSA進化過程具有較大的隨機性、迭代過程難以控制，收斂速度難以保證[15]。因此，本文基于基本型的CSA和偵察決策問題的特點，給出對應的改進措施，提出一種改進型CSA(ICSA)，包括采用自適應步長的比例調(diào)節(jié)因子、進化過程中解向量的高斯擾動法則。

1) 自適應步長比例調(diào)節(jié)因子

(4)

2) 解向量的高斯擾動法則。

CSA的特點就是參數(shù)少、全局搜索能力較強、局部搜索能力較弱，因此在進化迭代過程中，采用對解向量進行小步長的擾動，使鳥巢進化位置進行微調(diào)以增加解向量的多樣性，不僅加快了收斂速度，而且有效提高了算法的局部搜索性能[16-17]。

引入解向量的高斯擾動，當CSA經(jīng)過Lévy飛行得到一組新的解向量后，通過增加一次高斯擾動，使得新的解向量在舊的解向量附近微調(diào)并保留較優(yōu)的解向量。該過程可表示為

xn*=xn+k⊕u

(5)

式中：x為鳥巢的位置向量；u為與解向量同階的隨機矩陣且滿足uij～N(0,1)；k為擾動調(diào)節(jié)因子，避免對解向量造成的影響過大而導致算法的進化效率下降。

3 UAV多任務區(qū)偵察決策問題的建模

為了敘述方便，定義：n為仿真任務場景中的待偵察任務區(qū)數(shù)量；M為UAV基地與待偵察任務區(qū)集合,M={1,2,3,…,n},節(jié)點{1}為基地，節(jié)點M{1}為待偵察任務區(qū)的集合；E表示待偵察任務區(qū)之間的任務路徑，E={i,j|i,j∈M,i≠j}；(xi,yi)為第i個任務區(qū)中心點的位置坐標，i∈M，(x1=0,y1=0)；Si為第i個任務區(qū)的待偵察面積，i∈M，設定任務區(qū)為長方形規(guī)則區(qū)域；dij為第i個任務區(qū)到第j個任務區(qū)的距離；Dmin為從基地起飛完成對所有任務區(qū)遍歷飛行的最短任務航路；ci為第i個任務區(qū)的偵察價值，i∈M；w為所攜帶偵察載荷的掃描寬度；v為UAV的飛行速度；T為UAV的總?cè)蝿湛娠w行時間；tij為UAV從任務區(qū)i到任務區(qū)j的飛行時間，tij=dij/v；tmin為UAV從基地起飛完成任務航路飛行所需的最小飛行時間；Gimin為第i個任務區(qū)需要達到的最小信息偵察收益，i∈M；Gi為對第i個任務區(qū)的偵察信息收益；Gmax為對全部任務區(qū)進行偵察所獲取的綜合化最大偵察信息收益；ti為第i個任務區(qū)分配的載荷工作時間，

3.1 多任務區(qū)偵察決策問題的解決方案

在多任務區(qū)的偵察決策問題中，需要解算的決策變量有Xij和ti兩類。為了使每個任務區(qū)都能獲取到比較滿意的偵察信息收益，首先需要保證UAV對全部待偵察任務區(qū)的偵察路徑是最優(yōu)的，從而保證有更多的有效任務工作時間分配給相應的任務區(qū)來執(zhí)行相應的偵察任務。在此將整個任務決策過程分為2個階段來求解:第1階段主要進行偵察路徑的規(guī)劃，求取UAV完成所有任務區(qū)飛行所需要的時間;第2階段進行任務區(qū)偵察時間的分配，將UAV剩余的可用任務飛行時間最優(yōu)化地分配給相應的任務區(qū)。兩階段的求解過程見圖4。

圖4 多任務區(qū)偵察決策問題求解流程Fig.4 Process of multi-task area reconnaissancedecision-making

3.2 UAV最短偵察路徑規(guī)劃模型

UAV對多任務區(qū)進行偵察的最短任務路徑問題可以歸結(jié)為經(jīng)典的TSP問題來進行求解，建立數(shù)學模型為

(6)

(7)

約束條件為

(8)

(9)

(10)

(11)

(12)

(13)

其中：約束方程式(8)、式(9)為任務區(qū)的偵察約束，確保每個任務區(qū)只能到達一次;約束方程式(10)為偵察遍歷約束，保證UAV能夠遍歷飛行到所有待偵察的任務區(qū)；約束方程式(11)為起點約束，保證UAV從基地起飛；約束方程式(12)為終點約束，保證UAV完成任務后能夠返回基地；約束方程式(13)為平衡約束。

3.3 UAV對任務區(qū)的偵察信息度量指標

UAV對任務區(qū)進行任務偵察的主要目的是獲取有用的情報信息，降低決策者對相應任務區(qū)的不確定性，一般而言，UAV對任務區(qū)進行偵察時都處于極其復雜的外部環(huán)境，難以保證對每個任務區(qū)都能夠進行完全信息偵察。UAV的偵察信息收益主要取決于其所攜帶的偵察載荷的工作能力，在特定偵察載荷(如機載CCD照相設備等)下，UAV在每個待偵察任務區(qū)內(nèi)的偵察信息收益主要與在該任務區(qū)內(nèi)的載荷工作時間成正比，載荷工作時間越長，偵察收益越大。因此，偵察信息的度量主要與UAV在該任務區(qū)內(nèi)的偵察時間長短、所攜帶偵察載荷的工作能力等因素相關，即

G(t)=G0+G1(1-e-βt)

(14)

式中：G0為偵察任務開始前UAV對該任務區(qū)域的已知信息，0≤G0<1，G1為UAV對任務區(qū)的信息不確定性部分，且G0+G1=1;β為偵察載荷對任務區(qū)的偵察能力指數(shù)。不同偵察載荷的工作能力指數(shù)對偵察收益的影響如圖5所示。

圖5 不同偵察載荷工作能力下的偵察收益曲線Fig.5 Reconnaissance revenue curve under different reconnaissance load capacity

為便于計算，假定UAV在對任務區(qū)進行偵察前沒有任何已知信息，即取G0=0。同時設定任務區(qū)為矩形區(qū)域，偵察載荷為機載CCD照相設備，則偵察能力指數(shù)主要由任務區(qū)的面積S，偵察載荷的有效掃描寬度w及UAV的任務飛行速度v所決定，表示為

(15)

則UAV偵察收益的信息確定性度量指標可以表示為

G(t)=1-e(-w·v/S)t。

(16)

3.4 UAV多任務區(qū)偵察信息收益模型

多任務區(qū)的偵察時間分配問題可以表示為如下的最優(yōu)化問題，即

(17)

式中，ci為任務區(qū)的價值系數(shù)。

該最優(yōu)化問題的約束條件為

(18)

tmin=Dmin/v

(19)

(20)

其中：約束方程式(18)為UAV對所有任務區(qū)的任務飛行時間約束；約束方程式(20)為每個任務區(qū)需要滿足的最小偵察收益約束。

4 仿真實驗

以某偵察UAV為參考，在Windows7操作系統(tǒng)和Matlab2012b 編程環(huán)境下進行仿真驗證。設定UAV的最大任務工作時間為30 h，任務飛行速度為v=220 km/h，所攜帶偵察載荷的有效掃描寬度為w=0.3 km，以UAV所在基地坐標為原點建立坐標系，場景中感興趣的任務區(qū)域共有24個，任務區(qū)域的有關參數(shù)如表1所示。

表1 待偵察任務區(qū)域的信息設置表

基于上述仿真任務想定，將問題劃分為任務航路規(guī)劃和任務區(qū)偵察時間分配兩個階段，分別采用離散型和連續(xù)型的ICSA進行求解。

仿真中設定ICSA的最大迭代次數(shù)為500，巢穴的數(shù)量為20，宿主鳥發(fā)現(xiàn)外來鳥蛋的概率為0.25，對每個待偵察任務區(qū)的偵察時間分配及相應的偵察信息收益及偵察任務航路規(guī)劃結(jié)果分別如圖6、圖7所示，其中,i為對應任務區(qū)序號，UAV完成全部任務區(qū)偵察的總偵察信息收益為6.12，從UAV所在基地起飛遍歷全部任務區(qū)的最小任務航路飛行時間為6.62 h，任務航路的飛行距離為1 456.33 km。

為了分析ICSA的收斂速度，針對以上仿真任務場景分別選用了基本CSA和GA進行了對比計算，3種算法的進化收斂曲線如圖8所示。

圖6 UAV多任務區(qū)偵察時間分配結(jié)果圖Fig.6 Time allocation result of multi-task area reconnaissance

圖7 UAV多任務區(qū)偵察收益圖Fig.7 Revenue of multi-task area reconnaissance

圖8 ICSA,CSA,GA算法下的進化收斂曲線Fig.8 Evolution curve of ICSA,CSA and GA

仿真結(jié)果顯示,GA運行時間為19.20 s，而ICSA運行時間僅為6.07 s，可見ICSA求解速度明顯快于GA。從ICSA,CSA和GA這3種的進化收斂曲線能夠看出，相比于標準CSA和GA，ICSA能夠克服GA早熟的缺點，收斂速度快，同時自適應的搜索步長能夠明顯提高基本CSA進化的速度，從而能夠在較小的迭代次數(shù)下快速收斂。仿真計算結(jié)果表明,ICSA能夠快速有效地給出多任務區(qū)偵察決策問題的最優(yōu)方案。

5 結(jié)論

本文針對UAV多任務區(qū)的偵察決策問題，將整個偵察決策過程分為任務路徑規(guī)劃與偵察時間分配2個階段，給出了偵察信息的度量指標。同時提出了一種改進的CSA為每個待偵察任務區(qū)分配最優(yōu)的任務偵察時間，從而使整個偵察任務過程的信息收益最大化。最后進行了相應的仿真分析，仿真結(jié)果表明，該算法可以在UAV任務飛行時間約束下獲得對多任務區(qū)的綜合偵察信息收益最大化決策方案。

參 考 文 獻

[1] LOH R,BIAN Y,ROE T.UAVs in civil airspace:safety requirements[J].IEEE Aerospace and Electronic Systems Magazine,2009,24(1):5-17.

[2] 許友平.無人機對地偵察/攻擊航路規(guī)劃軟件系統(tǒng)的研制與研發(fā)[D].南京：南京航空航天大學,2013.

[3] ERGEZER H,LEBLEBICIOLU M K.3D path planning for UAVs for maximum information collection[C]//International Conference on Unmanned Aircraft Systems(ICUAS),2013:79-88.

[4] MA J Y,ZHANG K H.Research on TSP solution based on genetic algorithm of logistic equation[C]//The 2nd International Conference on Computer Science and Network Technology,2010:738-742.

[5] YANG X S,DEB S.Cuckoo search via Lévy flights[C]// World Congress on Nature & Biologically Inspired Computing(NaBIC 2009),2010:210-214.

[6] YANG X S.Cuckoo search and firefly algorithm[M].Poland:Polish Academy of Sciences,2014:49-195.

[7] YANG X S,DEB S.Engineering optimization by cuckoo search[J].International Journal of Mathematical Modelling and Numerical Optimisation,2010,1(4):330-343.

[8] 張耀中,胡波，李寄瑋，等.不確定環(huán)境下無人機多任務區(qū)偵察決策研究[J].西北工業(yè)大學學報，2016，34(6)：1028-1034.

[9] BAXTER J,FINDLAY S,PAXTON M.Scheduling UAV surveillance tasks,lessons learnt from trials with users[C]//IEEE International Conference on Systems,Man and Cybernetics,2013:2606-2610.

[10] SHIN H S,LEBOUCHER C,TSOURDOS A.Resource allocation with cooperative path planning for multiple UAVs[C]//UKACC International Conference on Control, 2012:298-303.

[11] HABIB D,KHAN S A,JAMAL H. Collaborative path planning for multiple unmanned aerial vehicles in dynamic environment[C]//The Signal Processing, Communications and Computing (ICSPCC),2011:1-5.

[12] BERTUCCELLI L F,CHOI H L,CHO P,et al.Real-time multi-UAV task assignment in dynamic and uncertain environment[C]//AIAA Guidance,Navigation,and Control Conference,2009:10-13.

[13] YANG X S,DEB S.Cuckoo search:recent advances and applications[J].Neural Computing and Applications, 2014,24(1):169-174.

[14] OUAARAB A,AHIOD B,YANG X S.Discrete cuckoo search algorithm for the traveling salesman problem[J].Neural Computing and Applications,2014,24(7/8):1659-1669.

[15] OUAARAB A,AHIOD B,YANG X S,et al.Discrete cuckoo search algorithm for job shop scheduling problem[C]//IEEE International Symposium on Intelligence Control(ISIC),2014:1872-1876.

[16] MARICHELVAM M K,PRABAHARAH T,YANG X S.Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan[J].Applied Soft Computing,2014,19(1):93-101.

[17] YANG X S,DEB S.Multiobjective cuckoo search algorithm for design optimization[J].Computers & Operations Research,2013,40(6):1616-1624.