基于優(yōu)化的元胞蟻群算法的無人飛行器 動態(tài)路徑規(guī)劃方法

,

(貴州民族大學(xué)數(shù)據(jù)科學(xué)與信息工程學(xué)院,貴州 貴陽 550025)

0 引言

路徑規(guī)劃是無人飛行器(UAV)研究的重要方向，已經(jīng)引起了諸多學(xué)者的興趣[1-2]。路徑規(guī)劃是依靠環(huán)境感知程度并在某些約束條件下，找出從出發(fā)點到目標(biāo)節(jié)點的最佳飛行路線。

概率路線圖法是一種常見的路徑規(guī)劃方法，采取隨機抽樣的方法選取無人飛行器的下一步的移動目標(biāo)，并通過反復(fù)的隨機抽樣完成無人飛行器到目標(biāo)節(jié)點的路徑規(guī)劃。目前有關(guān)概率路線圖方法的研究已有許多文獻(xiàn)，文獻(xiàn)[1]針對未知環(huán)境中無人飛行器的路徑規(guī)劃問題，提出了一種適用于靜態(tài)環(huán)境的路徑規(guī)劃方案，有效地改進(jìn)了無人飛行器模擬路線的尖角問題和折返運動問題。文獻(xiàn)[2-3]解決了傳統(tǒng)概率路線圖法在窄通道環(huán)境方面的不足，引入了人工勢場方法，縮短了無人飛行器路徑規(guī)劃的時間。

蟻群算法是概率路線圖方法的延伸。近些年來有關(guān)蟻群算法的無人飛行器的路徑規(guī)劃問題也引起了學(xué)者的注意。文獻(xiàn)[4]為了克服路徑搜索的盲目性，在蟻群算法的基礎(chǔ)上引入了人工勢場方法，將人工勢場加入單蟻的信息素，有效降低了路徑規(guī)劃初期反饋不明顯的影響。文獻(xiàn)[5-6]用障礙物權(quán)重替代灰度矩陣，并引入一種新的啟發(fā)因子影響路徑抽樣概率，既提高了無人飛行器的避障能力，又縮短了無人飛行器路徑規(guī)劃時間。

因此，在無人飛行器蟻群算法的基礎(chǔ)上，提出了一種新的方案，每次采用多架次無人飛行器進(jìn)行模擬，使用最優(yōu)飛行路徑進(jìn)行信息素更新。同時，引入路徑尖角優(yōu)化策略對無人飛行器的飛行特征進(jìn)行刻畫。

1 傳統(tǒng)PRM方法

傳統(tǒng)的PRM算法依據(jù)飛行區(qū)域內(nèi)的最小代價進(jìn)行路徑規(guī)劃，并將其作為未知環(huán)境中路徑移動的參考。遺憾的是，傳統(tǒng)的PRM算法是借助隨機抽樣的原理，所規(guī)劃出的路徑并不一定符合無人飛行器的飛行特征?？紤]圖1中的無人飛行器路徑規(guī)劃問題，其中各節(jié)點的坐標(biāo)如表1所示。進(jìn)一步將地圖離散化，節(jié)點之間可行區(qū)域用1表示，不可行區(qū)域用0表示，形成的矩陣被稱為環(huán)境地圖的灰度矩陣，如圖2的映射被稱為灰度映射。

圖1 無人飛行器移動的環(huán)境地圖

圖2 環(huán)境地圖的灰度映射

根據(jù)傳統(tǒng)的PRM算法進(jìn)行100架次的無人飛行器飛行模擬，模擬的最佳軌跡如圖3所示?？梢钥闯?00架次無人飛行器的最佳模擬軌跡不僅存在折返跑的現(xiàn)象，而且其移動軌跡存在尖角，這些都不符合無人飛行器的飛行特征。

圖3 基于傳統(tǒng)PRM算法的無人飛行器移動軌跡

在實際飛行過程中，既不希望無人飛行器出現(xiàn)折返跑的現(xiàn)象，同時也不希望無人飛行器進(jìn)行過大角度的轉(zhuǎn)彎?；诖?，利用無人飛行器的局部動態(tài)感知能力，對無人飛行器進(jìn)行動態(tài)重規(guī)劃，提出了一種基于元胞蟻群算法的局部動態(tài)PRM方法。

2 基于元胞蟻群算法和尖點優(yōu)化的局部動態(tài)PRM方法

元胞蟻群算法是一種適用于并行計算的離散型算法。相比傳統(tǒng)PRM算法，元胞蟻群算法不采用等概率進(jìn)行路徑選擇，取而代之的是依據(jù)節(jié)點上的信息素濃度來確定抽樣概率。

但是元胞蟻群算法在模擬初期容易出現(xiàn)搜索的盲目性和“螞蟻迷失”現(xiàn)象。為此，本文全局上采用元胞蟻群算法和圈形軌跡優(yōu)化相結(jié)合的方法進(jìn)行路徑規(guī)劃，局部上采用尖點優(yōu)化算法模擬無人飛行器的飛行特征，計算過程分為以下幾個方面。

2.1 元胞蟻群算法構(gòu)建

首先，對環(huán)境進(jìn)行離散化建模，將地理環(huán)境進(jìn)行網(wǎng)格化，依據(jù)無人飛行器的飛行特征(主要考察巡航高度)，確定出無人飛行器的可行飛行路線和可行區(qū)域，真實地理環(huán)境下的路線見圖1，網(wǎng)格化以后的結(jié)果被稱為灰度矩陣，矩陣上的每一點都和環(huán)境地圖一一對應(yīng)，可行用1表示，不可行用0表示，結(jié)果見圖2。

其次，建立單蟻的元胞模型，其模型(用Model表示)簡述為：

Model=(S,L,N,F)

(1)

S為元胞狀態(tài)，Sn(i,j)=1表示經(jīng)過n次移動單蟻處于節(jié)點(i,j)；L表示單蟻所有可能到達(dá)的位置節(jié)點即元胞空間；N為元胞鄰居，通常用N(Sn)表示，它表示結(jié)合無人飛行器的飛行特征，篩選出的無人飛行器n+1次移動后可能到達(dá)的位置節(jié)點，如圖4所示。N(Sn)={si|i=1,2,…,8}，i為方向序號，s3=1則表示在進(jìn)行n+1移動時，單蟻選擇3號方向，反之，若s3=0，則表示不選3號方向。

圖4 Moore元胞鄰居模型

為了方便論述，用Φ(n)表示經(jīng)過n次移動后無人飛行器所處的位置(i,j)，通常記為Φ(n)=(i,j)。元胞蟻群算法就是確定一個轉(zhuǎn)換函數(shù)F，依據(jù)轉(zhuǎn)換函數(shù)F并結(jié)合尖角優(yōu)化策略，在元胞鄰居中選擇下一個坐標(biāo)Φ(n+1)，即

Φ(n+1)=F(Φ(n))

(2)

最后，利用優(yōu)化后的最優(yōu)路徑進(jìn)行無人飛行器的信息素更新，這樣可以最大限度地使得蟻群算法在最優(yōu)路徑上富集更多的信息素。若無人飛行器在優(yōu)化后的軌跡上按照概率pk選擇了元胞鄰居N0(Sn+1)的第k個節(jié)點，那么第k個節(jié)點的信息素采用的局部更新規(guī)則為：

τk←(1-r)τk+rΔτk

(3)

這里r為常數(shù)，表示信息的揮發(fā)系數(shù)。假定元胞鄰居N0(Sn+1)的第k個節(jié)點為Φ(n+1)，則有：

(4)

d(Φ(n),Φ(n+1))為節(jié)點Φ(n)和節(jié)點Φ(n+1)之間的距離。

2.2 尖點優(yōu)化以及圈型軌跡的消除

在式(2)中，引入尖點優(yōu)化最大限度地消除蟻群算法引起的無人飛行器折返跑現(xiàn)象。在尖點優(yōu)化規(guī)則下，確定狀態(tài)轉(zhuǎn)移規(guī)則F和信息素更新規(guī)則。假定已經(jīng)經(jīng)歷n次轉(zhuǎn)移處于節(jié)點Φ(n)，并假定下次轉(zhuǎn)移處于節(jié)點Φ(n+1)，并假定Φ(n-1)、Φ(n)和Φ(n+1)之間的夾角為Angle(n)。則尖點優(yōu)化規(guī)則如下所述。

a.對Moore元胞鄰居中的任意節(jié)點Φ(n+1)∈N(Sn)，若

Angle(n)>100°

(5)

則認(rèn)為Φ(n+1)∈N0(Sn)。

b.若不存在任何節(jié)點Φ(n+1)∈N(Sn)使得Angle(n)>100°，則認(rèn)為：

N0(Sn)=N(Sn)

(6)

利用元胞蟻群算法，將在新的元胞鄰居N0(Sn+1)中進(jìn)行隨機抽樣作為下一次移動的目標(biāo)節(jié)點，抽樣的概率為：

(7)

τk為元胞鄰居N0(Sn+1)中第k個節(jié)點的信息素。

接下來進(jìn)行單輪無人飛行器模擬的最優(yōu)路徑的選擇。選擇的結(jié)果將用于信息素的更新。除路徑最短方案之外,本文做了另一方面的改進(jìn)：在更新之前進(jìn)行圈形軌跡的識別和剔除，保證以后的飛行模擬最大限度地避免無人飛行器折返跑問題。在圈形軌跡的識別方法中，假定根據(jù)最短路徑確定出來的移動路徑為：

S0,S1,…,Si,Si+1,…,Sj,Sj+1,…,Sn

(8)

S0為起點,Sn為目標(biāo)點。若檢測發(fā)現(xiàn)Si=Sj,則將路徑優(yōu)化為：

S0,S1,…,Si,Sj+1,…,Sn

(9)

當(dāng)確保最優(yōu)路徑?jīng)]有重復(fù)節(jié)點之后,說明優(yōu)化后的最優(yōu)路徑已不存在圈型軌跡。

2.3 實驗算法設(shè)計

在不引起混淆的前提下，將圈形軌跡優(yōu)化和尖點優(yōu)化統(tǒng)稱為路徑優(yōu)化。將路徑優(yōu)化策略融入元胞蟻群算法，那么基于路徑優(yōu)化的蟻群系統(tǒng)算法步驟如下：

a.建立灰度矩陣H，將地圖離散化。

b.設(shè)置飛行模擬次數(shù)n和每次模擬的無人飛行器數(shù)量m。

c.設(shè)置信息素矩陣IM，維數(shù)和灰度矩陣H相同，所有元素取值為1。

d.飛行次數(shù)的循環(huán)開始for(i= 1:n)。

e.飛行器數(shù)量的循環(huán)開始for(j= 1:m)。

f.while循環(huán)(或者repeat)開始，直至尋找到目標(biāo)節(jié)點停止。

g.假定第i次循環(huán)的第j個無人飛行器所處的位置為Poisition(i,j)，依據(jù)灰度矩陣確定其元胞鄰居中的可行區(qū)域。

h.進(jìn)行尖點優(yōu)化，將可行區(qū)域內(nèi)不符合飛行角度的節(jié)點剔除。

i.按照信息素確定的抽樣概率，在可行區(qū)域內(nèi)進(jìn)行隨機抽樣確定下一節(jié)點。

j.while循環(huán)結(jié)束。

k.飛行器數(shù)量的循環(huán)結(jié)束，確定了m條路徑，按照距離最短選擇本次模擬的最優(yōu)路徑。

l.對最優(yōu)路徑進(jìn)行圈形軌跡的識別，剔除圈形軌跡。

m.按照優(yōu)化后的最優(yōu)軌跡進(jìn)行信息素更新，選擇Q=m，r=0.05。

n.飛行次數(shù)的循環(huán)結(jié)束，綜合n次飛行模擬的結(jié)果選取最優(yōu)的路徑。

在設(shè)計好實驗算法之后，將尖點優(yōu)化的蟻群系統(tǒng)算法進(jìn)行數(shù)值模擬，與此同時也將尖點優(yōu)化方案用于常規(guī)的PRM算法，并將2種方案所得結(jié)果進(jìn)行比對。

3 仿真驗證

為了驗證本文所提出方法的正確性和有效性，采用30架無人飛行器進(jìn)行運算(運算10次的結(jié)果如圖5所示，運算20次的結(jié)果如圖6所示)。在和圖3相同的環(huán)境下，設(shè)置初始位置為(2,8)、目標(biāo)節(jié)點為(24,11)，采用尖角優(yōu)化的蟻群系統(tǒng)算法進(jìn)行規(guī)劃，并選取30架無人飛行器的最優(yōu)路徑進(jìn)行信息素的更新，每次更新的信息濃度為30，模擬結(jié)果如圖5和圖6所示。

對比圖6和圖3可以看出，基于尖角優(yōu)化的蟻群系統(tǒng)算法經(jīng)過了最少的節(jié)點，路徑距離也是最短。值得讀者注意的是圖5規(guī)劃的路徑?jīng)]有直接經(jīng)過節(jié)點F和節(jié)點G，這是因為在灰度映射中網(wǎng)格剖分不夠細(xì)致所致，見圖2。再對比圖5和圖6還可以看出隨著運算次數(shù)的增多，結(jié)果更加精確。

圖5 基于尖角優(yōu)化的蟻群系統(tǒng)算法(運算10次)

圖6 基于尖角優(yōu)化的蟻群系統(tǒng)算法(運算20次)

4 結(jié)束語

引入尖點優(yōu)化策略和圈型軌跡檢索算法之后，模擬結(jié)果更加符合無人飛行器的動力特征,也有利于操控的穩(wěn)定性。對比傳統(tǒng)元胞蟻群算法，進(jìn)行尖角優(yōu)化策略和圈型軌跡算法優(yōu)化之后，無人飛行器的最優(yōu)路徑更加平滑。