基于貝葉斯決策風(fēng)險(xiǎn)的元胞蟻群算法路徑規(guī)劃

王秀芬， 楊盛毅， 田茂祥， 胡馨丹

(1.貴州民族大學(xué) 機(jī)械電子工程學(xué)院， 貴州 貴陽(yáng) 550025；2.貴州民族大學(xué) 貴州省模式識(shí)別與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室， 貴州 貴陽(yáng) 550025)

0 引言

無(wú)人飛行器(Unmanned Air Vehicle，UAV)作為移動(dòng)機(jī)器人的一種，其路徑規(guī)劃的任務(wù)是在一定性能指標(biāo)要求下，在其運(yùn)動(dòng)環(huán)境中尋找出一條從起始位置到目標(biāo)位置的最優(yōu)或次優(yōu)無(wú)碰撞路徑[1-2]. 其主要研究?jī)?nèi)容包括：路徑長(zhǎng)度的選擇、收斂速度、避障以及路徑平滑度等. 目前主要路徑規(guī)劃方法有A*算法[3]、人工勢(shì)場(chǎng)法[4]、拓?fù)浞╗5]、可視圖法[6]、蟻群算法[7]、神經(jīng)網(wǎng)絡(luò)算法[8]、遺傳算法[9]、粒子群算法等[10]. 蟻群算法是路徑規(guī)劃的重要研究方法，關(guān)于蟻群算法在路徑規(guī)劃方面的已有大量研究[11，12]. 蟻群算法利用信息素濃度影響后續(xù)單蟻的選擇概率，一定程度上改變了單純概率路線(xiàn)圖法搜索的盲目性[13，14]. 但是初始階段的單蟻可能在錯(cuò)誤的路線(xiàn)上累積信息濃度，造成后續(xù)單蟻路徑規(guī)劃失敗. 為了克服蟻群算法在初始階段的盲目性，同時(shí)提高路徑規(guī)劃的速度，學(xué)者們?cè)趥鹘y(tǒng)蟻群算法的基礎(chǔ)之上引入了人工勢(shì)場(chǎng)[15]. 人工勢(shì)場(chǎng)分為目標(biāo)節(jié)點(diǎn)的引力場(chǎng)和障礙等信息的斥力場(chǎng)，將信息素、引力場(chǎng)和斥力場(chǎng)綜合考量決定單蟻移動(dòng)的概率選擇，緩解了蟻群算法在初始階段的盲目性，減少了螞蟻迷失. 融合貝葉斯統(tǒng)計(jì)學(xué)的蟻群算法也是近些年來(lái)的一個(gè)改進(jìn)方向[16，17]. 基于貝葉斯的蟻群算法在路徑節(jié)點(diǎn)選擇方式上采用貝葉斯后驗(yàn)概率代替?zhèn)鹘y(tǒng)蟻群算法中由信息濃度確定的概率，一定程度上解決了用傳統(tǒng)螞蟻算法進(jìn)行路徑規(guī)劃時(shí)容易造成螞蟻迷失的問(wèn)題.

基于以上分析，本文提出了一種新的貝葉斯統(tǒng)計(jì)學(xué)和蟻群算法的融合方案，將蟻群算法中單蟻的節(jié)點(diǎn)選擇視為貝葉斯決策，將由蟻群算法獲取的抽樣概率為先驗(yàn)概率，并將目標(biāo)節(jié)點(diǎn)的啟發(fā)信息融入條件概率、將障礙物的斥力信息融入風(fēng)險(xiǎn)函數(shù)，依據(jù)平均風(fēng)險(xiǎn)的大小進(jìn)行決策分析，從而構(gòu)造了一種新的貝葉斯元胞蟻群算法.

1 傳統(tǒng)蟻群算法的避障缺陷

蟻群算法是一種仿生算法，在移動(dòng)過(guò)程中允許單蟻觸及障礙之后再轉(zhuǎn)向移動(dòng)，這顯然不符合無(wú)人飛行器(UAV)的飛行特征.本文在環(huán)境地圖的基礎(chǔ)之上考察蟻群算法在避障方面的缺陷,如圖1所示.

圖1 環(huán)境地圖

為了說(shuō)明蟻群算法在避障方面的不足，以圖1所示的兩幅靜態(tài)環(huán)境地圖為例，進(jìn)行蟻群算法模擬. 其中陰影部分為障礙區(qū)域，Start表示出發(fā)點(diǎn)，End表示目標(biāo)節(jié)點(diǎn). 對(duì)于環(huán)境地圖按照20×20進(jìn)行離散，空白區(qū)域?yàn)榭尚袇^(qū)域，灰色點(diǎn)在灰度矩陣中表示障礙區(qū)域，并將其網(wǎng)格化以后的結(jié)果稱(chēng)為灰度矩陣. 矩陣上的每一點(diǎn)都和環(huán)境地圖一一對(duì)應(yīng)，可行用1表示，不可行用0表示，結(jié)果如圖2所示.

圖2 環(huán)境地圖的灰度矩陣

在模擬過(guò)程中，分10批次設(shè)置了500只螞蟻，其最優(yōu)路徑見(jiàn)圖3. 在環(huán)境地圖1(a)中經(jīng)過(guò)53次移動(dòng)到達(dá)目標(biāo)節(jié)點(diǎn)，在環(huán)境地圖1(b)中經(jīng)過(guò)30次移動(dòng)到達(dá)目標(biāo)節(jié)點(diǎn). 模擬結(jié)果表明：傳統(tǒng)的蟻群算法在避障過(guò)程中使得UAV多次發(fā)生大角度轉(zhuǎn)彎.

圖3 傳統(tǒng)蟻群算法的最優(yōu)路徑

此外，在環(huán)境地圖1(a)中設(shè)置了凹形障礙，這使得蟻群算法極易陷于局部最優(yōu)解. 選取部分單蟻的運(yùn)動(dòng)軌跡，見(jiàn)圖4. 由圖4可以看出單蟻在凹形區(qū)域逗留了很長(zhǎng)時(shí)間. 利用“螞蟻迷失”來(lái)衡量這種無(wú)效路徑，若單蟻在1000次移動(dòng)不能到達(dá)目標(biāo)節(jié)點(diǎn)或者多次移動(dòng)之后返回了出發(fā)點(diǎn)，記為“螞蟻迷失”. 圖5中的單蟻在進(jìn)行了658次移動(dòng)之后返回了出發(fā)點(diǎn)，路徑規(guī)劃失敗.

圖4 傳統(tǒng)蟻群算法下部分單蟻的移動(dòng)軌跡

最后進(jìn)行螞蟻迷失的比例分析，結(jié)果見(jiàn)圖6，可以看出凹形區(qū)域造成了許多“螞蟻迷失”，在真實(shí)的UAV路徑規(guī)劃中，這意味著大量的UAV不能到達(dá)目標(biāo)節(jié)點(diǎn)，既浪費(fèi)設(shè)備(UAV不能到達(dá)目標(biāo)節(jié)點(diǎn)意味著設(shè)備丟失)，又使得路徑規(guī)劃失敗.

2 基于貝葉斯決策風(fēng)險(xiǎn)的元胞蟻群算法路徑規(guī)劃

考慮蟻群算法路徑規(guī)劃在避障方面的不足，本文在傳統(tǒng)蟻群算法的基礎(chǔ)之上、將信息濃度確定的采樣概率視為先驗(yàn)概率、整合目標(biāo)啟發(fā)因素構(gòu)造條件概率，并計(jì)算貝葉斯后驗(yàn)概率，再融合障礙信息構(gòu)造決策風(fēng)險(xiǎn)函數(shù)，利用后驗(yàn)分布獲取的平均風(fēng)險(xiǎn)來(lái)確定蟻群算法的節(jié)點(diǎn)轉(zhuǎn)移.

2.1 單蟻的元胞模型

為便于描述單蟻運(yùn)行軌跡，其元胞模型(用Model表示)簡(jiǎn)述為

Model=(S,L,N,F)

(1)

S為元胞狀態(tài)，Sn(i,j)=1表示經(jīng)過(guò)n次移動(dòng)單蟻處于節(jié)點(diǎn)(i,j)，L表示單蟻所有可能到達(dá)的位置節(jié)點(diǎn)即元胞空間.N為元胞鄰居，通常用N(Sn)表示，N(Sn)={si|i=1,2,…,8}，它表示結(jié)合UAV的飛行特征，篩選出的UAVn+1次移動(dòng)后可能到達(dá)的位置節(jié)點(diǎn)，見(jiàn)圖7.

圖7 Moore元胞鄰居模型

i為方向序號(hào)，s3=1則表示在進(jìn)行n+1次移動(dòng)時(shí)，單蟻選擇方向ω3，反之，若s3=0，則表示不選方向ω3. 為了方便論述，用φ(n)表示經(jīng)過(guò)n移動(dòng)后UAV所處的位置(i,j)，通常記為φ(n)=(i,j). 元胞蟻群算法就是確定一個(gè)轉(zhuǎn)換函數(shù)F，在元胞鄰居中選擇下一個(gè)坐標(biāo)φ(n+1)，即，

φ(n+1)=F(φ(n))

(2)

2.2 可行區(qū)域

依據(jù)UAV的飛行特征，確定出障礙區(qū)域和可行區(qū)域. 結(jié)合尖角優(yōu)化策略確定元胞鄰居N(Sn)中的可行區(qū)域. 為了方便論述將元胞鄰居N(Sn)分為兩個(gè)部分：可行區(qū)域N1(Sn)和禁忌區(qū)域N0(Sn)，同時(shí)設(shè)φ(n-1)、φ(n)和A之間的夾角為Angle(n)，其中A∈N(Sn)，則為了避免UAV進(jìn)行大角度轉(zhuǎn)彎設(shè)定尖角優(yōu)化規(guī)則如下:

1) 對(duì)Moore元胞鄰居中的任意節(jié)點(diǎn)A∈N(Sn)，若，

Angle(n)>100°

(3)

則認(rèn)為A∈N1(Sn)，否則A∈N0(Sn)；

2) 若元胞鄰居N(Sn)沒(méi)有備選節(jié)點(diǎn)滿(mǎn)足Angle(n)>100°，則，

N1(Sn)=N(Sn)

(4)

2.3 貝葉斯后驗(yàn)概率

首先，在新的元胞鄰居的可行區(qū)域N1(Sn)內(nèi)，根據(jù)信息素矩陣計(jì)算備選節(jié)點(diǎn)的概率，并將其視為路徑選擇的先驗(yàn)概率，具體做法如下：

(5)

其中，τWi是可行區(qū)域N1(Sn)中第Wi個(gè)節(jié)點(diǎn)的信息素.

其次，確定元胞鄰居可行區(qū)域N1(Sn)中備選節(jié)點(diǎn)的條件概率. 針對(duì)目標(biāo)節(jié)點(diǎn)的引力場(chǎng)構(gòu)造啟發(fā)函數(shù)，

(6)

其中Wi∈N1(Sn)，Wi距離目標(biāo)節(jié)點(diǎn)的距離越近，f1(Wi)越大. 進(jìn)行歸一化處理即可得到備選節(jié)點(diǎn)的條件概率，

(7)

最后，根據(jù)貝葉斯公式計(jì)算后驗(yàn)概率，

2.4 備選節(jié)點(diǎn)的決策風(fēng)險(xiǎn)

設(shè){αi,i=1,2,…,n}表示貝葉斯決策選出的狀態(tài)，若最終選擇了狀態(tài)Wj，則有可能給UAV帶來(lái)風(fēng)險(xiǎn). 假設(shè)將本來(lái)應(yīng)該選擇轉(zhuǎn)移方向αi錯(cuò)誤選擇了轉(zhuǎn)移方向Wj時(shí)造成的風(fēng)險(xiǎn)為Ci,j，i,j=1,2,…,n，n≤8，顯然Ci,i=0(i=j)，見(jiàn)表1.

表1 基于風(fēng)險(xiǎn)的貝葉斯決策

接下來(lái)，計(jì)算各個(gè)決策的后驗(yàn)平均風(fēng)險(xiǎn)，

(9)

從而可以在后驗(yàn)平均風(fēng)險(xiǎn)R(α1|G)，R(α2|G)，…，R(αn|G)中找出風(fēng)險(xiǎn)最小的決策αk，即，

(10)

則αk即為UAV下一目標(biāo)節(jié)點(diǎn)的最佳策略.

2.5 備選節(jié)點(diǎn)的風(fēng)險(xiǎn)函數(shù)構(gòu)造

首先，設(shè)預(yù)測(cè)半徑為R，構(gòu)造預(yù)測(cè)區(qū)域RD，對(duì)于元胞鄰居可行區(qū)域N1(Sn)內(nèi)的任意一個(gè)備選節(jié)點(diǎn)Wi，

RD(Wi)={dot|dist(Wi,dot)100°,dot∈L}

(11)

圖8 備選節(jié)點(diǎn)Wi的預(yù)測(cè)區(qū)域

其次，針對(duì)UAV固定區(qū)域(預(yù)測(cè)區(qū)域)內(nèi)障礙節(jié)點(diǎn)的數(shù)量構(gòu)造下面的風(fēng)險(xiǎn)函數(shù)，

(12)

其中Wj∈N1(Sn)，Wj為N1(Sn)內(nèi)的任意一個(gè)備選節(jié)點(diǎn)，Num(Wj)表示預(yù)測(cè)區(qū)域內(nèi)障礙節(jié)點(diǎn)的數(shù)量，Num(Wj)越多，風(fēng)險(xiǎn)R1(Wj)越大；通常情況下，為了防止避障失敗，UAV需要一定的飛行安全距離，這里設(shè)定為D0，針對(duì)UAV和障礙節(jié)點(diǎn)的距離，定義另一個(gè)風(fēng)險(xiǎn)函數(shù)

(13)

節(jié)點(diǎn)Wj和障礙物的最小距離mindist(Wj,obstacle)越小，潛在的風(fēng)險(xiǎn)R2(Wj)越大. 用λ1表示障礙物分布情況(預(yù)測(cè)區(qū)域內(nèi)障礙物數(shù)量)形成的風(fēng)險(xiǎn)函數(shù)，1-λ1表示UAV和障礙節(jié)點(diǎn)的最小距離帶來(lái)的風(fēng)險(xiǎn)，則綜合風(fēng)險(xiǎn)函數(shù)為，

R(Wj)=λ1R1(Wj)+(1-λ1)R2(Wj)

(14)

最后，計(jì)算平均風(fēng)險(xiǎn). 令R(Wj)=Cij，代入式(9)，即可計(jì)算平均風(fēng)險(xiǎn)，完成單蟻的一次移動(dòng).

2.6 節(jié)點(diǎn)信息素更新

接下來(lái)進(jìn)行UAV的信息素更新. 若UAV在優(yōu)化后的軌跡上按照概率pk選擇了元胞鄰居N1(Sn)的第k個(gè)節(jié)點(diǎn)φ(n+1)，那么第k個(gè)節(jié)點(diǎn)的信息素采用下面的局部更新規(guī)則，

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

(15)

這里r為常數(shù)，表示信息的揮發(fā)系數(shù).

(16)

其中d(φ(n),φ(n+1))表示節(jié)點(diǎn)φ(n)和節(jié)點(diǎn)φ(n+1)之間的距離，Q為常數(shù).

基于以上分析，基于決策風(fēng)險(xiǎn)的貝葉斯元胞蟻群算法步驟如下:

1) 設(shè)定矩形地圖區(qū)域，并將其網(wǎng)格離散，同時(shí)設(shè)定相應(yīng)的灰度矩陣H和信息素矩陣IM；

2) 設(shè)定蟻群算法中模擬UAV批次m和同批次UAV的數(shù)量m0；

3) 批次循環(huán)開(kāi)始for(i=1:m)；

4) 同批次內(nèi)UAV的循環(huán)開(kāi)始for(j=1:m0)；

5) 開(kāi)始repeat循環(huán)；

6) 執(zhí)行尖角優(yōu)化策略，確定當(dāng)前元胞鄰居的可行區(qū)域；

7) 按照蟻群算法的信息濃度確定可行區(qū)域內(nèi)每個(gè)節(jié)點(diǎn)Wi的先驗(yàn)概率并計(jì)算條件概率和后驗(yàn)概率；

8) 識(shí)別節(jié)點(diǎn)Wi的預(yù)測(cè)區(qū)域，確定其風(fēng)險(xiǎn)函數(shù)，并依據(jù)后驗(yàn)概率計(jì)算平均風(fēng)險(xiǎn)；

9) 按照平均風(fēng)險(xiǎn)最小從可行區(qū)域內(nèi)采點(diǎn)，完成螞蟻的本次移動(dòng)；

10) 直至UAV到達(dá)目標(biāo)節(jié)點(diǎn)，repeat循環(huán)結(jié)束；

11) 同批次UAV的循環(huán)結(jié)束，確定m0條路徑并按照距離最短選擇局部最優(yōu)路徑；

12) 設(shè)定Q=m0，r=0.05，按照優(yōu)化后的局部最優(yōu)路徑進(jìn)行信息素更新，新的信息素矩陣用于下一批次UAV模擬；

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

3 數(shù)值模擬

為了驗(yàn)證本文構(gòu)造算法的有效性，在PC上進(jìn)行了仿真模擬，處理器為Intel(R) Core(TM) i7-6700K，主頻為4.00 GHz，安裝內(nèi)存16 GB，仿真軟件為R3.5.2.

進(jìn)行10個(gè)批次的模擬計(jì)算，每批次30架UAV，同批次間用相同的信息濃度，本批次模擬結(jié)束后的局部最優(yōu)路徑對(duì)下一批次UAV的信息濃度進(jìn)行更新.

圖9 基于貝葉斯決策風(fēng)險(xiǎn)蟻群算法的模擬效果

在圖1環(huán)境下，圖1(a)設(shè)置初始位置為(1，21)、目標(biāo)節(jié)點(diǎn)為(21，1)，圖1(b)設(shè)置初始位置為(1，21)、目標(biāo)節(jié)點(diǎn)為(21，21). 選擇揮發(fā)系數(shù)r=0.05，采用基于貝葉斯風(fēng)險(xiǎn)決策的元胞蟻群算法，選擇

(17)

注意環(huán)境地圖按照20×20進(jìn)行離散，這里選擇預(yù)測(cè)區(qū)域的半徑為R=3.

在相同的實(shí)驗(yàn)環(huán)境下，考慮最優(yōu)規(guī)劃路徑問(wèn)題，將傳統(tǒng)蟻群算法和基于決策風(fēng)險(xiǎn)的貝葉斯蟻群算法模擬效果進(jìn)行比對(duì)分析，模擬結(jié)果見(jiàn)圖3、圖9. 由圖可以看出蟻群算法融入貝葉斯風(fēng)險(xiǎn)策略之后，UAV的避障能力增強(qiáng)，同時(shí)陷于凹形區(qū)域的不足得到了改善.

蟻群算法的螞蟻“迷失”意味著UAV路徑規(guī)劃失敗，接下來(lái)模擬兩種算法下的螞蟻迷失現(xiàn)象. 連續(xù)模擬10個(gè)批次，傳統(tǒng)蟻群算法下UAV的迷失數(shù)量見(jiàn)圖6，基于決策風(fēng)險(xiǎn)的貝葉斯蟻群算法下UAV的迷失數(shù)量見(jiàn)圖10. 進(jìn)行交叉比對(duì)之后可以看出，引入貝葉斯決策之后，螞蟻迷失的現(xiàn)象明顯減少.

圖10 基于貝葉斯決策風(fēng)險(xiǎn)蟻群算法的螞蟻迷失數(shù)量

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)蟻群算法在避障時(shí)容易使得UAV頻繁大角度轉(zhuǎn)彎、易于陷于局部最優(yōu)解的問(wèn)題，本章提出了一種基于決策風(fēng)險(xiǎn)的貝葉斯元胞蟻群算法，提高了UAV的避障能力、緩解了路徑規(guī)劃易陷于凹形區(qū)域的不足.