凌文通,倪建軍,陳 顏,唐廣翼
(河海大學物聯(lián)網(wǎng)工程學院,江蘇 常州 213000)
隨著計算機、傳感器和控制等技術(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é)作目標搜索任務。
在本文的任務中,目標位置信息未知,環(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之間的距離。
鴿群優(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)
鴿群優(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]為交叉概率,這種交叉概率可以保證差分進化后的個體包含其他個體的基因,保留種群多樣性。
無人機在搜索過程中不僅需要搜尋最大信息素,而且應該能夠避開障礙物,無人機兩兩之間互相不能相撞,通過設(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
在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
在這部分實驗中目標處于靜止狀態(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。
在這部分實驗中,目標能夠在路面上隨機運動,無人機的速度必須大于目標隨機運動的速度,否則無人機將無法搜索到目標。所有目標初始位置與靜態(tài)實驗中的相同,最終實驗結(jié)果如圖2所示。
從圖2結(jié)果可以看出,即使目標處于運動狀態(tài),本文所提出的方法仍然能夠避開障礙并最終完成目標搜索任務。實驗結(jié)果平均步長為69,平均時間為35.25 s。
實際環(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
為了更進一步探討所提算法的有效性,在復雜的實驗環(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
本文研究了三維未知環(huán)境中的多無人機目標搜索問題,使用鴿群優(yōu)化算法求解問題,由于鴿群優(yōu)化算法容易陷入局部最優(yōu),本文提出了基于差分進化策略的鴿群優(yōu)化算法。為了驗證所提出的基于改進鴿群優(yōu)化算法的多無人機目標搜索方法的有效性,設(shè)計并進行了多次仿真實驗,實驗結(jié)果表明該方法能夠有效完成搜索目標任務。在將來的工作中,將進一步優(yōu)化方法的性能,并開展實際多無人機協(xié)作目標搜索實驗,驗證方法的實際工作性能。