基于檢測算子經(jīng)驗學(xué)習(xí)魚群算法的移動機(jī)器人路徑規(guī)劃

王 徽，黃宜慶*，劉曉峰

(1.安徽工程大學(xué) 電氣工程學(xué)院，安徽 蕪湖 241000；2.蕪湖發(fā)電有限責(zé)任公司，安徽 蕪湖 241000)

移動機(jī)器人路徑規(guī)劃問題在現(xiàn)實生活中具有重要的研究價值.路徑規(guī)劃問題一般分為全局路徑規(guī)劃和局部路徑規(guī)劃問題，前者為環(huán)境參數(shù)全部已知，后者為部分環(huán)境參數(shù)已知.在自動駕駛、無人機(jī)自主飛行等領(lǐng)域有重要的應(yīng)用價值和研究意義.

目前，移動機(jī)器人路徑規(guī)劃的熱點方法主要有群智能算法的路徑規(guī)劃方法[1]，包括人工魚群算法、深度強(qiáng)化學(xué)習(xí)算法[2]、蟻群算法[3]等；文獻(xiàn)[4]中在移動機(jī)器人路徑的起始點和目標(biāo)點之間輸入角度值的模糊推理系統(tǒng).算法在完成路徑規(guī)劃中耗時短，但是對于靜態(tài)環(huán)境的要求較高，需要建立完善的知識庫，因而耗費較多的存儲空間和時間；文獻(xiàn)[5]中提出將基因算法和自適應(yīng)模糊邏輯算法應(yīng)用到移動機(jī)器人路徑規(guī)劃問題上，通過遺傳算法生成一條從起始點到目標(biāo)點的可行路徑，再利用Hermite插值多項式使路徑平滑，最后通過自適應(yīng)模糊邏輯控制器讓移動小車跟隨該路徑.算法在應(yīng)用過程中小車行走路徑表現(xiàn)效果較好，但是路徑規(guī)劃結(jié)果存在早熟現(xiàn)象，且不能有效地擺脫路徑中的陷阱，會出現(xiàn)陷入局部極值的問題；文獻(xiàn)[6]中提出將粒子群優(yōu)化算法用來解決路徑規(guī)劃問題，通過設(shè)定必要的中間目標(biāo)來提高算法執(zhí)行效率.算法在復(fù)雜地圖環(huán)境中的表現(xiàn)效果較好，但是中間目標(biāo)點的選取方式導(dǎo)致路徑規(guī)劃存在路徑冗長問題；文獻(xiàn)[7]中提出使用簡化群體優(yōu)化算法解決移動機(jī)器人路徑規(guī)劃問題.算法對于機(jī)器人路徑規(guī)劃的效果較好，但是該算法應(yīng)用的環(huán)境模型較為簡單，在較為復(fù)雜的環(huán)境中效果不再突出，并且對于機(jī)器人可通行的區(qū)域限制條件不足；文獻(xiàn)[8]中提出使用混合策略改進(jìn)傳統(tǒng)人工魚群算法固定不變的步長和視野范圍來解決移動機(jī)器人路徑問題.算法在移動機(jī)器人路徑規(guī)劃上效果較好.但是在較為復(fù)雜的地圖環(huán)境中時，會出現(xiàn)次優(yōu)解干擾全局路徑和理性的問題；文獻(xiàn)[9]提出動態(tài)分級的蟻群算法，在原始蟻群算法中加入了狼群算法的分級機(jī)制.算法提高了傳統(tǒng)蟻群算法的執(zhí)行效率，但是對于較復(fù)雜地圖環(huán)境中存在的較多陷阱，不具備逃逸能力，最終無法完成路徑規(guī)劃任務(wù)；文獻(xiàn)[10-11]提出了蟻群算法的優(yōu)化改進(jìn)策略，針對傳統(tǒng)蟻群算法易于陷入局部最優(yōu)解的問題做出改進(jìn).算法在二維地圖環(huán)境中表現(xiàn)出具備逃逸陷阱的能力，但是存在路徑冗長的問題.

傳統(tǒng)人工魚群算法是目前仿生算法中收斂速度和尋優(yōu)效果較好的算法[12]，而模糊邏輯算法在建立好靜態(tài)環(huán)境模型后，完成路徑規(guī)劃也具有較好的收斂速度.基于魚群算法主要解決次優(yōu)解干擾全局路徑合理性問題和路徑冗長問題，使得算法具備在復(fù)雜多陷阱地圖環(huán)境中具備逃逸能力，同時規(guī)劃的路徑曲線長度最優(yōu).研究設(shè)計了經(jīng)驗學(xué)習(xí)的方法，使得原來不具備學(xué)習(xí)能力的魚群擁有了學(xué)習(xí)錯誤經(jīng)驗的能力，解決了次優(yōu)解干擾全局路徑和理性的問題，同時具有較好的擺脫陷阱的能力；針對路徑冗長問題，研究設(shè)計了優(yōu)化檢測算子，基于檢測算子設(shè)計的優(yōu)化算法，極大地減少了路徑的長度.通過仿真與其他算法的比較說明了算法的優(yōu)越性、可靠性和穩(wěn)定性.

1 柵格環(huán)境化的魚群算法

選擇柵格法搭建移動機(jī)器人的行走環(huán)境.以xoy平面建立坐標(biāo)系，在以單位1作為機(jī)器人移動步長，建立柵格環(huán)境.其中黑色柵格代表障礙物，白色格子代表機(jī)器人可以移動的區(qū)域.為了適應(yīng)柵格環(huán)境下的機(jī)器人路徑規(guī)劃問題，需要對于傳統(tǒng)人工魚群算法做如下定義.設(shè)每個柵格為1*1的正方形格子.

定義2：用Allow表示移動機(jī)器人的可行域，用Barrier表示障礙物區(qū)域.整個區(qū)域，用s表示，滿足Allow∪Barrier=S,(Allow)c∩S=Barrier,(Barrier)c∩S=Allow.

定義5：魚群覓食行為，設(shè)pi為當(dāng)前魚群的位置，Hi為當(dāng)前人工魚pi處的食物濃度，pk為pi可行域中的任意一個位置，由魚群的隨機(jī)行為決定，Hk為pk處的食物濃度，則覓食行為函數(shù)可描述如下：

(1)

式中,pnest為人工魚下一時刻的位置;prand為在pi可行域中隨機(jī)選取一個柵格作為下一時刻位置.若可行域中找到下一位置pk，食物濃度Hk，滿足Hk

(2)

定義7：魚群追尾行為，設(shè)pi為當(dāng)前人工魚位置，其附近伙伴的中食物濃度最低的人工魚群位置為plow，物濃度為Hlow.追尾行為可描述為：

(3)

傳統(tǒng)人工魚群算法通過循環(huán)不斷地執(zhí)行群聚和追尾行為，不斷將每一時刻中的最優(yōu)解更新到公告板上，最終最優(yōu)解附近會聚集較多的人工魚，然后得出最優(yōu)解.

2 經(jīng)驗學(xué)習(xí)魚群算法及收斂性分析

這種尋優(yōu)方式在應(yīng)用到柵格環(huán)境的機(jī)器人路徑規(guī)劃問題上，會出現(xiàn)嚴(yán)重的次優(yōu)解干擾路徑規(guī)劃的合理性問題.基于魚群算法的移動機(jī)器人路徑規(guī)劃如圖1所示.

針對此問題做如下證明.最優(yōu)解和次優(yōu)解路徑曲線如圖2所示.設(shè)：

(1)1～k時刻，全局最優(yōu)解為pbest，其食物濃度為Hbest，該處魚群編號為r.

(2)pb為次優(yōu)解，其食物濃度為Hb，該處魚群編號記為rb.

(3)pbest(r)和pb(rb)表示編號為r和rb的人工魚群行走的路徑.

如圖2所示，上方pbest路徑為魚群r的路徑曲線，下方pb曲線為魚群rb的路徑曲線.在魚群到達(dá)pbest(r)和pb(rb)位置之前，編號為r的魚群和編號為rb的魚群到目標(biāo)點的歐氏距離為：

(dr)2=‖pbest(r)-GOAL‖2=(xr-xg)2+(yr-yg)2,

(4)

(drb)2=‖pb(rb)-GOAL‖2=(xrb-xg)2+(yrb-yg)2,

(5)

式中,Pbest(r)=pbest(xr,yr)為編號r魚群的位置;pb(rb)=pb(xrb,yrb)為編號rb魚群的位置.由圖2可知，總有xr

(6)

因為xr

圖1 基于魚群算法的移動機(jī)器人路徑規(guī)劃 圖2 最優(yōu)解和次優(yōu)解路徑曲線

同理可證，從k+1時刻到最終到達(dá)目標(biāo)點，pb(rb)之后的點會存放到road集合中，即road={…,pbest(r-3),pbest(r-2),pbest(r-1),pb(rb+1),pb(rb+2),pb(rb+3),…}.

特別地，在k時刻，因為pbest(r-1)的下一個離目標(biāo)點距離最小的點在障礙物區(qū)間內(nèi)，所以導(dǎo)致pbest(r)和pb(rb)同時為最優(yōu)解，因為存在隨機(jī)性，所以pbest(r)和pb(rb)都有50%概率被存到road集合中.所以，

(Ⅰ)當(dāng)pbest(r)被存到road中后，road1={…,pbest(r-3),pbest(r-2),pbest(r-1),pbest(r),pb(rb+1),pb(rb+2),pb(rb+3),…}.

(Ⅱ)當(dāng)pb(rb)被存到road中后，road2={…,pbest(r-3),pbest(r-2),pbest(r-1),pb(rb+1),pb(rb+2),pb(rb+3)…}.

為了解決魚群算法的次優(yōu)解干擾全局路徑規(guī)劃的問題.設(shè)計了基于經(jīng)驗學(xué)習(xí)的魚群算法.經(jīng)驗學(xué)習(xí)方法在于學(xué)習(xí)規(guī)劃失敗的經(jīng)驗.算法一直跟蹤最優(yōu)解魚群的位置，若該魚群k時刻的位置不再是全局最優(yōu)，那么就將時刻從k～k-2的路徑值從road集合中刪除，同時在柵格地圖上賦予權(quán)值w∈[1,1.5)，權(quán)值w從k～k-2時刻走過的柵格依次遞減，同時重新設(shè)計食物濃度函數(shù)為：

圖3 road1路徑曲線 圖4 road2路徑曲線

魚群經(jīng)驗學(xué)習(xí)算法主體部分步驟如下：

Step 1:當(dāng)前k時刻最優(yōu)解的魚群編號是否與上一時刻相同，若是,則繼續(xù)跟蹤最優(yōu)解魚群，執(zhí)行Step 1；若否，則轉(zhuǎn)Step 2；

Step 2:將路徑集合中k～k-2的位置去除，所有魚群清除k～k-2時刻的位置數(shù)據(jù)，同時在柵格地圖上對應(yīng)最優(yōu)解魚群走過的柵格，賦予權(quán)值w，轉(zhuǎn)Step 3；

Step 3:更新實物濃度函數(shù)，轉(zhuǎn)Step 4;

Step 4:魚群從k-2時刻以新的實物濃度函數(shù)重新開始魚群基本行為跟蹤最優(yōu)解魚群的編號，轉(zhuǎn)Step 1.

為了驗證基于經(jīng)驗法的魚群算法對于解決魚群算法次優(yōu)解干擾全局路徑規(guī)劃合理性問題的可行性，證明如下.魚群經(jīng)驗學(xué)習(xí)后賦予權(quán)值如圖5所示，設(shè)編號為r的魚群在學(xué)習(xí)了圖3中的錯誤經(jīng)驗之后，對pbest(r-1)，pbest(r)，pbest(r+1)位置區(qū)域，賦予權(quán)值w1,w2,w3；同時在road集合中刪除這些路徑位置.

于是魚群從k-2時刻重新開始.已知w3=1,w2

因為w3=1，所以當(dāng)魚群再次到達(dá)此位置時，其可行域中下一時刻的候選位置為pbest(r)和pb(rb)，記到目標(biāo)點的歐式距離分別為：

(7)

(8)

(9)

由圖5可知，總有w2∈(1,1.5),xrb>xr,yrb>yr,|xg-xrb|=|yg-yr|,|xg-xr|=|yg-yrb|,則

(10)

同理可證，pb(rb+1)以后的位置也都被記錄到road集合中，即road={…,pbest(r-1),pb(rb),pb(rb+1),pb(rb+2),…}.

由此可見，通過經(jīng)驗學(xué)習(xí)后的魚群不會再因障礙物區(qū)域的阻攔，而出現(xiàn)次優(yōu)解干擾全局路徑規(guī)劃合理性的問題.基于經(jīng)驗學(xué)習(xí)的魚群算法的路徑規(guī)劃如圖6所示.柵格環(huán)境為20*20，障礙物柵格占全部柵格的35%.

基于經(jīng)驗學(xué)習(xí)的魚群算法，在學(xué)習(xí)了圖1中錯誤的經(jīng)驗后，給了圖6所示的合理的全局路徑規(guī)劃結(jié)果，使得魚群成功地避開了{(lán)211，210，230，270，269}等柵格號的陷阱誘惑，解決了魚群算法次優(yōu)解干擾全局路徑規(guī)劃合理性問題.

3 具有檢測算子的經(jīng)驗學(xué)習(xí)魚群算法

如圖6中的路徑曲線，在3個圓形區(qū)域的路徑，并不是最優(yōu)的路徑，出現(xiàn)了路徑冗長的問題.為了解決路徑規(guī)劃中出現(xiàn)的路徑冗長問題，研究提出優(yōu)化檢測算法.

在前期魚群距離目標(biāo)點距離較遠(yuǎn)，產(chǎn)生的最優(yōu)解缺乏目標(biāo)位置的影響，存在路徑冗長的問題，如圖6中3塊圓形區(qū)域所示，R(t)在前期的取值會適當(dāng)?shù)拇?，使得魚群移動方向能夠受到目標(biāo)點的影響，而不是僅僅參考當(dāng)前魚群最優(yōu)解；隨著魚群不斷接近目標(biāo)點，R(t)的取值逐漸減小.由此可見，需要被優(yōu)化檢測的解t越小，說明路徑處于前期或者中期，R(t)的值較大；而當(dāng)t越大，說明路徑進(jìn)入后期，R(t)的值變小.

不妨假設(shè)，劃分路徑前75%為魚群尋優(yōu)的前期和中期，后25%為魚群尋優(yōu)后期.給出優(yōu)化檢測算子R(t)的表達(dá)式如下：

(11)

式中，p(kx,ky)為k時刻解的最優(yōu)魚群的位置坐標(biāo)；goal(x,y)為目標(biāo)位置的坐標(biāo)；D(k)表示p(kx,ky)到goal(x,y)的整數(shù)倍距離.

(12)

(13)

式中，ki為已被優(yōu)化檢測的解的個數(shù).

在圖6中，設(shè)第一個圓的圓心所在位置為k時刻全局最優(yōu)解，上一個點的位置記為k-1時刻的全局最優(yōu)解，下一點的位置記為k+1時刻的全局最優(yōu)解，以此類推，分別為…,k-1,k,k+1,…時刻最優(yōu)解的位置.優(yōu)化檢測算法滿足以下條件：

(1)在優(yōu)化檢測第一個圓后，k+1,k+2,k+3路徑位置被優(yōu)化后，不會再加入到待優(yōu)化檢測的序列；

(2)下一時刻直接從k+4時刻的路徑位置開始優(yōu)化檢測.

圖5 魚群經(jīng)驗學(xué)習(xí)后賦予權(quán)值 圖6 基于經(jīng)驗學(xué)習(xí)的魚群算法的路徑規(guī)劃

4 算法仿真比較實驗

將研究算法與蟻群算法和模糊邏輯算法進(jìn)行仿真實驗，并對數(shù)據(jù)進(jìn)行比較.在對比實驗中，以下參數(shù)始終不變：N=50，visual=10,δ=0.618,Nant=50柵格中障礙物區(qū)域占整個柵格數(shù)的35%.其中，N為魚群數(shù)，visual為魚群的視野，δ為擁擠度，Nant為螞蟻的個數(shù).

20*20柵格環(huán)境下WAS,AFSA,FL和ELDO-AFSA算法仿真得出的路徑規(guī)劃結(jié)果如圖8所示.從仿真結(jié)果不難看出研究提出的ELDO-AFSA算法在路徑規(guī)劃上表現(xiàn)效果優(yōu)于其他3種算法.在20*20，40*40，60*60柵格環(huán)境下的AFSA,WAS,FL和ELDO-AFSA算法的路徑長度、算法耗時和評價函數(shù)值分別如表1、表2、表3所示.通過對比可以看出，研究提出的ELDO-AFSA算法全程路徑短，而且隨著環(huán)境的復(fù)雜化，算法的評價函數(shù)值波動小，算法穩(wěn)定性能優(yōu)于WAS,AFSA和FL3種算法.

圖7 基于檢測算子優(yōu)化算法后的路徑規(guī)劃 圖8 20*20柵格移動機(jī)器人路徑規(guī)劃

dist_min=28.2843AFSAWASFLELDO-AFSA最長路徑37.455830.799034.384830.3848最短路徑32.142129.293229.799029.2132平均路徑值34.799030.046132.091929.7990耗時/s9.293215.894712.23049.3102E(k)1.23031.06231.13461.0536

表2 40*40柵格環(huán)境算法比較

表3 60*60柵格環(huán)境算法比較

5 結(jié)論

針對魚群算法在解決移動機(jī)器人路徑規(guī)劃中出現(xiàn)的次優(yōu)解干擾路徑合理性問題，設(shè)計了具有檢測算子的經(jīng)驗學(xué)習(xí)魚群算法(ELDO-AFSA)，使每條魚都具有學(xué)習(xí)錯誤經(jīng)驗的能力，在解決次優(yōu)解干擾路徑規(guī)劃合理性問題上效果顯著.同時針對路徑冗長的情況，引入了優(yōu)化檢測算子，在不改變路徑合理性的前提下，使路徑不斷接近全局最優(yōu)路徑.最后將ELDO-AFSA算法與AFSA,WAS,FL算法進(jìn)行比較，對比仿真實驗體現(xiàn)了ELDO-AFSA算法具有更強(qiáng)的收斂性、穩(wěn)定性和可靠性.但是，對于柵格環(huán)境龐大且地圖中的“陷阱”區(qū)域較多時，魚群會耗費較多的時間在學(xué)習(xí)經(jīng)驗上.因此，接下來的工作方向會更加注重提高魚群在大量“陷阱”區(qū)域環(huán)境下的學(xué)習(xí)效率問題，使得算法的收斂速度更快.