凌文通,倪建軍,陳 顏，唐廣翼

(河海大學物聯(lián)網(wǎng)工程學院，江蘇 常州 213000)

1 引言

隨著計算機、傳感器和控制等技術(shù)的發(fā)展，無人機UAV(Unmanned Aerial Vehicle)在各個領(lǐng)域的應用也更加廣泛，例如預防森林火災、邊境偵查和物資運輸?shù)?。與單無人機相比，多無人機協(xié)作[1-3]可以更加高效、快速地完成任務，因此對多無人機協(xié)作進行研究具有重要的現(xiàn)實意義。

在多無人機協(xié)作中，目標搜索是非常基本和重要的任務之一，為此，已經(jīng)有許多學者進行了大量的研究工作，如：文獻[4]建立了搜索概率環(huán)境信息模型，提出了一種新的基于蟻群理論的多UAV協(xié)同區(qū)域搜索方法。文獻[5]建立了多旅行商問題MTSP(Multiple Traveling Salesman Problem)模型，提出了一種聚類算法和遺傳算法進行分步組合的優(yōu)化算法來進行搜索。文獻[6]針對動態(tài)時敏目標的運動特性，建立了動態(tài)時敏目標的運動預測模型，以優(yōu)化無人機的搜索性能。文獻[7]設(shè)計了一種基于預測控制思想的多無人機協(xié)同區(qū)域搜索算法,使多無人機在執(zhí)行區(qū)域搜索任務時同時考慮當前搜索代價和長期搜索代價,提高了多無人機的協(xié)同搜索效能。

上述這些研究，大部分是在二維環(huán)境中進行的，而無人機工作在三維環(huán)境中，這種情況下的協(xié)作搜索任務明顯復雜很多。因此，近年來很多學者開始針對三維環(huán)境中的多無人機協(xié)作搜索問題開展研究，如：文獻[8]提出了一種基于混沌理論的人工勢場算法來解決三維無人機航路規(guī)劃問題。文獻[9]提出了一種基于改進蟻群算法的優(yōu)化算法用于三維航跡規(guī)劃。文獻[10,11]將鴿群優(yōu)化算法用于二維環(huán)境無人機搜索之中。這些對無人機協(xié)作搜索的研究具有重要的理論和實際價值，但是依然存在一些問題需要深入研究，如蟻群算法存在搜索效率低、收斂速度慢等缺點；有的研究只適合單無人機搜索問題等。

針對上述問題，本文研究了在未知三維環(huán)境中的多無人機目標搜索問題，并提出一種基于差分進化策略改進的鴿群優(yōu)化算法來求解多無人機協(xié)作目標搜索任務。

2 問題描述

在本文的任務中，目標位置信息未知，環(huán)境信息未知，無人機需要在避開障礙的同時搜索到目標。本文將所有的無人機視為質(zhì)點，忽略大小、形狀及通信問題，UAV被標記為Ui，i=1,2,…,N，其中N表示無人機的數(shù)量。

假設(shè)無人機相互之間通信始終保持良好狀況，且通信沒有延時，因此無人機之間信息可以相互共享，同時假設(shè)目標可以釋放信息素[12]，無人機可以檢測搜索到目標的信息素，并且可以識別信息素的強弱，定義目標的信息素在環(huán)境中的強度如式(1)所示：

(1)

其中,Star表示最大的信息素強度，Rtar表示目標的信息素能夠傳播的最遠距離，ptar和pi分別表示目標ptar和點pi的位置，L(x,y)表示x和y之間的距離。

3 基于改進鴿群優(yōu)化算法的多無人機目標搜索方法

3.1 基本鴿群優(yōu)化算法思想

鴿群優(yōu)化PIO(Pigeon-Inspired Optimization)算法[13,14]相比于人工勢場算法、蟻群算法等傳統(tǒng)優(yōu)化算法，具有收斂速度快、搜索效率高等特點，因此，本文使用鴿群優(yōu)化算法來完成搜索任務。

基本鴿群優(yōu)化算法是受到鴿子群自主歸巢行為啟發(fā)的新型群體智能算法，鴿群優(yōu)化算法主要包括2個階段：

(1)在給定的求解空間內(nèi)初始化鴿子的位置和速度，分別如式(2)和式(3)所示：

Xi=[xi1,xi2,…,xiD]

(2)

Vi=[vi1,vi2,…,viD]

(3)

其中,i∈{1,2,…,N}表示鴿子編號，N表示鴿子總數(shù)，D表示求解問題的維度。鴿子的速度和位置的更新方程如式(4)所示：

(4)

其中,R表示地圖和指南針因子，用來控制鴿子的速度；隨機數(shù)rand∈[0,1];t=1,2,…,Nc1表示當前迭代次數(shù)；Xgbest(t-1)是t-1次迭代所搜索到的全局最優(yōu)位置，當?shù)螖?shù)t達到Nc1時，算法第1階段完成。

(2)此時進入算法第2階段，鴿子到達目標附近時，PIO算法將切換到地標算子，附近環(huán)境的地標信息將提供精確的指導信息。在此階段，每次迭代時鴿子數(shù)量減半且速度不會改變，而位置會更新，如式(5)所示：

(5)

其中,Np表示t-1次迭代減半的鴿子數(shù)量；Xc(t)是剩余鴿子的中心位置(作為地標信息)；fitness(·)是每只鴿子的適應度函數(shù)，根據(jù)求解的最值不同，其定義也不同,如式(6)所示：

(6)

3.2 鴿群優(yōu)化算法改進

鴿群優(yōu)化算法雖然搜索效率高、收斂速度快，但是極容易陷入局部最優(yōu)。差分進化算法[15，16]是一種基于群體差異性的算法，其整體結(jié)構(gòu)類似于遺傳算法，它能夠使個體在迭代時保留一些其他個體的特性。因此，本文將差分進化算法的特點融入到鴿群優(yōu)化算法中，以便在快速搜索的過程中保持種群多樣性，防止陷入局部最優(yōu)，提高全局搜索能力。即將式(4)中位置更新公式變更為式(7)：

Xi(t)=Xi(t-1)+α1Vi(t)+α2Ui(t-1)

(7)

其中，α1和α2為調(diào)節(jié)系數(shù)，且α1+α2=1;Ui(t-1)為第t-1次迭代中第i只鴿子的差分進化結(jié)果。對Xi(t)進行基因編碼操作，然后通過式(8)和式(9)計算Ui(t)：

Vi(t)=Xi(t)+F(Xm(t)-Xn(t))

(8)

(9)

其中，Vi(t)為差分向量;Xij(t)為Xi(t)的第j號基因;Vij(t)為Vi(t)的第j號基因;Uij(t)為Ui(t)的第j號基因;m≠n≠i且m，n都為[1,N]的隨機整數(shù);F∈[0,1]為縮放因子，CR∈[0,1]為交叉概率，這種交叉概率可以保證差分進化后的個體包含其他個體的基因，保留種群多樣性。

3.3 多無人機目標搜索

無人機在搜索過程中不僅需要搜尋最大信息素，而且應該能夠避開障礙物，無人機兩兩之間互相不能相撞，通過設(shè)定安全距離Dsafe，當無人機之間距離大于Dsafe時，令d=0,表示無人機之間互不影響；當無人機之間距離小于Dsafe時，令d=1，從而實現(xiàn)無人機避碰的效果。因此，適應度函數(shù)的設(shè)計如式(10)所示：

f(Xi(t-1))=

(10)

其中，w1和w2是調(diào)節(jié)系數(shù)，o為障礙物總數(shù)，ok為第k個障礙物的位置。無人機利用機載傳感器可以進行障礙物探測，這里用函數(shù)O(ok,pr)來判斷無人機搜索的下一位置pr是否存在障礙，具體定義如式(11)所示：

(11)

由于無人機之間可以共享信息，對于無人機已經(jīng)搜索過的區(qū)域應盡量避免重復搜索，從而可以提高搜索效率，縮短搜索到目標的時間。本文通過將已搜索過的區(qū)域進行標記并存儲，減小重復搜索的概率。因此，將式(10)進一步改進為式(12)：

f(Xi(t-1))=Itar(Xi(t-1))-

(12)

其中,w3是調(diào)節(jié)系數(shù)，函數(shù)G(pr)通過和已標記的區(qū)域進行比較，判斷無人機搜索的下一位置pr是否已經(jīng)被其他無人機搜索過,如式(13)所示：

(13)

基于改進鴿群優(yōu)化算法的多無人機目標搜索方法具體步驟如下所示：

步驟1UAV在環(huán)境中飛行，并檢測目標信息。

步驟2當UAV檢測到目標信息時，使用改進后的鴿群優(yōu)化算法進行搜索。

步驟3遵循滾動優(yōu)化的原則，采取算法迭代中選取的最優(yōu)個體，進行UAV位置的更新。

步驟4判斷是否滿足最大迭代次數(shù)或者UAV找到目標，滿足則停止運行，否則返回步驟1。

實現(xiàn)基于改進鴿群優(yōu)化算法的多無人機目標搜索方法的偽代碼如下所示：

(1)初始化：Ui,i=1,2,…,N;Tj,j=1,2,…,M;//初始化無人機和目標位置

(2)計算：Itar,f(Ui),載入環(huán)境信息O;/*Itar為信息素強度，f(Ui)為標志位*/

(3)搜索過程：

fori=1..N

iff(Ui)==1

break;

else

Xi=rand(Xmin,Xmax);

Vi=rand(Vmin,Vmax);

location=g(Xi,Vi);//使用改進后的算法計算

Ui=Ui+location;//無人機進行位置更新

endif

endfor

(4)結(jié)束條件：

ifi≥NorItar==Star

f(Ui)=1;

endif

4 仿真實驗與結(jié)果分析

在UAV搜索過程中，目標狀態(tài)可能出現(xiàn)2種不同情況：第1種目標是靜止的，第2種目標是隨機運動的。針對2種不同情況本文分別進行了多次實驗。為了簡化實驗，本文中不考慮噪聲的影響，將所有UAV和目標視為質(zhì)點，與此同時適當擴大了障礙，以抵消忽略UAV實際形狀和尺寸所帶來的影響。

Figure 1 Experimental results of static targets

Figure 2 Experimental results of dynamic targets

4.1 靜態(tài)目標的實驗結(jié)果

在這部分實驗中目標處于靜止狀態(tài)，基于改進鴿群優(yōu)化算法的搜索過程如圖1所示。圖1a顯示了UAV的初始位置分別為(65,10,60)，(10,10,60)，(40,90,60)和(90,80,60)，目標的位置分別為(10,40,5)和(90,80,5)，圖1b和圖1c為無人機搜索過程中的運動軌跡，從圖中可以看出，無人機可以避開障礙并朝著散發(fā)最大信息素的地方移動，最終發(fā)現(xiàn)目標。實驗次數(shù)都為20次，根據(jù)實驗結(jié)果對實驗數(shù)據(jù)進行了計算，靜態(tài)實驗中無人機搜索到目標的平均步長為61，平均時間為25.13 s。

4.2 動態(tài)目標的實驗結(jié)果

在這部分實驗中，目標能夠在路面上隨機運動，無人機的速度必須大于目標隨機運動的速度，否則無人機將無法搜索到目標。所有目標初始位置與靜態(tài)實驗中的相同，最終實驗結(jié)果如圖2所示。

從圖2結(jié)果可以看出，即使目標處于運動狀態(tài)，本文所提出的方法仍然能夠避開障礙并最終完成目標搜索任務。實驗結(jié)果平均步長為69，平均時間為35.25 s。

4.3 復雜環(huán)境實驗結(jié)果

實際環(huán)境中，情況可能更加復雜(如山地環(huán)境等)，因此為了更進一步驗證本文所提方法的有效性，設(shè)計了復雜環(huán)境實驗。如圖3a所示，在這部分實驗中除了地面存在山脈等復雜地形，空中還分布著靜態(tài)障礙物(如其他飛行器等)。圖3顯示了無人機的整個搜索過程。實驗結(jié)果表明，本文方法是有效可行的，在較為復雜的實驗環(huán)境中，無人機仍然可以安全且平穩(wěn)地搜索到目標。實驗平均步長78.8，平均時間為42.15 s。

Figure 3 Experimental results in complex environment

Figure 4 Results of contrast experiment

4.4 對比實驗結(jié)果鴿群優(yōu)化

為了更進一步探討所提算法的有效性，在復雜的實驗環(huán)境中，將改進后的鴿群優(yōu)化算法與未改進的鴿群優(yōu)化算法以及蟻群算法進行比較，實驗結(jié)果對比圖如圖4所示。

為了防止一次實驗帶來的偶然性，所有算法均運行了20次，實驗結(jié)果如表1所示。從表1中可以看出，鴿群優(yōu)化算法比蟻群算法搜索效果要好，改進后的鴿群優(yōu)化算法在3種算法中表現(xiàn)最優(yōu)。

Table 1 Comparison of experimental results

5 結(jié)束語

本文研究了三維未知環(huán)境中的多無人機目標搜索問題，使用鴿群優(yōu)化算法求解問題，由于鴿群優(yōu)化算法容易陷入局部最優(yōu)，本文提出了基于差分進化策略的鴿群優(yōu)化算法。為了驗證所提出的基于改進鴿群優(yōu)化算法的多無人機目標搜索方法的有效性，設(shè)計并進行了多次仿真實驗，實驗結(jié)果表明該方法能夠有效完成搜索目標任務。在將來的工作中，將進一步優(yōu)化方法的性能，并開展實際多無人機協(xié)作目標搜索實驗，驗證方法的實際工作性能。