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

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

1 引言

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

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

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

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

2 問題描述

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

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

(1)

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

3 基于改進(jìn)鴿群優(yōu)化算法的多無人機(jī)目標(biāo)搜索方法

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

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

基本鴿群優(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表示地圖和指南針因子，用來控制鴿子的速度；隨機(jī)數(shù)rand∈[0,1];t=1,2,…,Nc1表示當(dāng)前迭代次數(shù)；Xgbest(t-1)是t-1次迭代所搜索到的全局最優(yōu)位置，當(dāng)?shù)螖?shù)t達(dá)到Nc1時，算法第1階段完成。

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

(5)

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

(6)

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

鴿群優(yōu)化算法雖然搜索效率高、收斂速度快，但是極容易陷入局部最優(yōu)。差分進(jìn)化算法[15，16]是一種基于群體差異性的算法，其整體結(jié)構(gòu)類似于遺傳算法，它能夠使個體在迭代時保留一些其他個體的特性。因此，本文將差分進(jìn)化算法的特點融入到鴿群優(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只鴿子的差分進(jìn)化結(jié)果。對Xi(t)進(jìn)行基因編碼操作，然后通過式(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]的隨機(jī)整數(shù);F∈[0,1]為縮放因子，CR∈[0,1]為交叉概率，這種交叉概率可以保證差分進(jìn)化后的個體包含其他個體的基因，保留種群多樣性。

3.3 多無人機(jī)目標(biāo)搜索

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

f(Xi(t-1))=

(10)

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

(11)

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

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

(12)

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

(13)

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

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

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

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

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

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

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

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

(3)搜索過程：

fori=1..N

iff(Ui)==1

break;

else

Xi=rand(Xmin,Xmax);

Vi=rand(Vmin,Vmax);

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

Ui=Ui+location;//無人機(jī)進(jìn)行位置更新

endif

endfor

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

ifi≥NorItar==Star

f(Ui)=1;

endif

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

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

Figure 1 Experimental results of static targets

Figure 2 Experimental results of dynamic targets

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

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

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

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

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

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

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

Figure 3 Experimental results in complex environment

Figure 4 Results of contrast experiment

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

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

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

Table 1 Comparison of experimental results

5 結(jié)束語

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