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

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

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

1 引言

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

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

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

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

2 問(wèn)題描述

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

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

(1)

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

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

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

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

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

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

Xi=[xi1,xi2,…,xiD]

(2)

Vi=[vi1,vi2,…,viD]

(3)

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

(4)

其中,R表示地圖和指南針因子，用來(lái)控制鴿子的速度；隨機(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時(shí)，算法第1階段完成。

(2)此時(shí)進(jìn)入算法第2階段，鴿子到達(dá)目標(biāo)附近時(shí)，PIO算法將切換到地標(biāo)算子，附近環(huán)境的地標(biāo)信息將提供精確的指導(dǎo)信息。在此階段，每次迭代時(shí)鴿子數(shù)量減半且速度不會(huì)改變，而位置會(huì)更新，如式(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)類似于遺傳算法，它能夠使個(gè)體在迭代時(shí)保留一些其他個(gè)體的特性。因此，本文將差分進(jìn)化算法的特點(diǎn)融入到鴿群優(yōu)化算法中，以便在快速搜索的過(guò)程中保持種群多樣性，防止陷入局部最優(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é)果。對(duì)Xi(t)進(jìn)行基因編碼操作，然后通過(guò)式(8)和式(9)計(jì)算Ui(t)：

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

(8)

(9)

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

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

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

f(Xi(t-1))=

(10)

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

(11)

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

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

(12)

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

(13)

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

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

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

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

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

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

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

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

(3)搜索過(guò)程：

fori=1..N

iff(Ui)==1

break;

else

Xi=rand(Xmin,Xmax);

Vi=rand(Vmin,Vmax);

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

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

endif

endfor

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

ifi≥NorItar==Star

f(Ui)=1;

endif

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

Figure 1 Experimental results of static targets

Figure 2 Experimental results of dynamic targets

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

在這部分實(shí)驗(yàn)中目標(biāo)處于靜止?fàn)顟B(tài)，基于改進(jìn)鴿群優(yōu)化算法的搜索過(guò)程如圖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為無(wú)人機(jī)搜索過(guò)程中的運(yùn)動(dòng)軌跡，從圖中可以看出，無(wú)人機(jī)可以避開障礙并朝著散發(fā)最大信息素的地方移動(dòng)，最終發(fā)現(xiàn)目標(biāo)。實(shí)驗(yàn)次數(shù)都為20次，根據(jù)實(shí)驗(yàn)結(jié)果對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了計(jì)算，靜態(tài)實(shí)驗(yàn)中無(wú)人機(jī)搜索到目標(biāo)的平均步長(zhǎng)為61，平均時(shí)間為25.13 s。

4.2 動(dòng)態(tài)目標(biāo)的實(shí)驗(yàn)結(jié)果

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

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

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

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

Figure 3 Experimental results in complex environment

Figure 4 Results of contrast experiment

4.4 對(duì)比實(shí)驗(yàn)結(jié)果鴿群優(yōu)化

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

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

Table 1 Comparison of experimental results

5 結(jié)束語(yǔ)

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