基于改進鴿群優化算法的多無人機目標搜索*

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

(河海大學物聯網工程學院，江蘇 常州 213000)

1 引言

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

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

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

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

2 問題描述

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

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

(1)

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

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

3.1 基本鴿群優化算法思想

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

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

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

Xi=[xi1,xi2,…,xiD]

(2)

Vi=[vi1,vi2,…,viD]

(3)

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

(4)

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

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

(5)

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

(6)

3.2 鴿群優化算法改進

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

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

(7)

其中，α1和α2為調節系數，且α1+α2=1;Ui(t-1)為第t-1次迭代中第i只鴿子的差分進化結果。對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]的隨機整數;F∈[0,1]為縮放因子，CR∈[0,1]為交叉概率，這種交叉概率可以保證差分進化后的個體包含其他個體的基因，保留種群多樣性。

3.3 多無人機目標搜索

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

f(Xi(t-1))=

(10)

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

(11)

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

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

(12)

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

(13)

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

步驟1UAV在環境中飛行，并檢測目標信息。

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

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

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

實現基于改進鴿群優化算法的多無人機目標搜索方法的偽代碼如下所示：

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

(2)計算：Itar,f(Ui),載入環境信息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)結束條件：

ifi≥NorItar==Star

f(Ui)=1;

endif

4 仿真實驗與結果分析

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

Figure 1 Experimental results of static targets

Figure 2 Experimental results of dynamic targets

4.1 靜態目標的實驗結果

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

4.2 動態目標的實驗結果

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

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

4.3 復雜環境實驗結果

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

Figure 3 Experimental results in complex environment

Figure 4 Results of contrast experiment

4.4 對比實驗結果鴿群優化

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

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

Table 1 Comparison of experimental results

5 結束語

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