王 徽，黃宜慶*，劉曉峰

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

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

(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的路徑曲線.在魚群到達pbest(r)和pb(rb)位置之前，編號為r的魚群和編號為rb的魚群到目標點的歐氏距離為：

(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 基于魚群算法的移動機器人路徑規(guī)劃 圖2 最優(yōu)解和次優(yōu)解路徑曲線

同理可證，從k+1時刻到最終到達目標點，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)的下一個離目標點距離最小的點在障礙物區(qū)間內(nèi)，所以導致pbest(r)和pb(rb)同時為最優(yōu)解，因為存在隨機性，所以pbest(r)和pb(rb)都有50%概率被存到road集合中.所以，

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

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

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

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

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

Step 2:將路徑集合中k～k-2的位置去除，所有魚群清除k～k-2時刻的位置數(shù)據(jù)，同時在柵格地圖上對應最優(yōu)解魚群走過的柵格，賦予權值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)驗學習后賦予權值如圖5所示，設編號為r的魚群在學習了圖3中的錯誤經(jīng)驗之后，對pbest(r-1)，pbest(r)，pbest(r+1)位置區(qū)域，賦予權值w1,w2,w3；同時在road集合中刪除這些路徑位置.

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

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

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

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

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

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

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

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

(11)

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

(12)

(13)

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

在圖6中，設第一個圓的圓心所在位置為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)驗學習后賦予權值 圖6 基于經(jīng)驗學習的魚群算法的路徑規(guī)劃

4 算法仿真比較實驗

將研究算法與蟻群算法和模糊邏輯算法進行仿真實驗，并對數(shù)據(jù)進行比較.在對比實驗中，以下參數(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)境的復雜化，算法的評價函數(shù)值波動小，算法穩(wěn)定性能優(yōu)于WAS,AFSA和FL3種算法.

圖7 基于檢測算子優(yōu)化算法后的路徑規(guī)劃 圖8 20*20柵格移動機器人路徑規(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é)論

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