基于檢測算子經驗學習魚群算法的移動機器人路徑規劃

王 徽，黃宜慶*，劉曉峰

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

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

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

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

1 柵格環境化的魚群算法

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

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

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

(1)

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

(2)

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

(3)

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

2 經驗學習魚群算法及收斂性分析

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

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

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

(2)pb為次優解，其食物濃度為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 基于魚群算法的移動機器人路徑規劃 圖2 最優解和次優解路徑曲線

同理可證，從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)的下一個離目標點距離最小的點在障礙物區間內，所以導致pbest(r)和pb(rb)同時為最優解，因為存在隨機性，所以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)…}.

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

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

魚群經驗學習算法主體部分步驟如下：

Step 1:當前k時刻最優解的魚群編號是否與上一時刻相同，若是,則繼續跟蹤最優解魚群，執行Step 1；若否，則轉Step 2；

Step 2:將路徑集合中k～k-2的位置去除，所有魚群清除k～k-2時刻的位置數據，同時在柵格地圖上對應最優解魚群走過的柵格，賦予權值w，轉Step 3；

Step 3:更新實物濃度函數，轉Step 4;

Step 4:魚群從k-2時刻以新的實物濃度函數重新開始魚群基本行為跟蹤最優解魚群的編號，轉Step 1.

為了驗證基于經驗法的魚群算法對于解決魚群算法次優解干擾全局路徑規劃合理性問題的可行性，證明如下.魚群經驗學習后賦予權值如圖5所示，設編號為r的魚群在學習了圖3中的錯誤經驗之后，對pbest(r-1)，pbest(r)，pbest(r+1)位置區域，賦予權值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),…}.

由此可見，通過經驗學習后的魚群不會再因障礙物區域的阻攔，而出現次優解干擾全局路徑規劃合理性的問題.基于經驗學習的魚群算法的路徑規劃如圖6所示.柵格環境為20*20，障礙物柵格占全部柵格的35%.

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

3 具有檢測算子的經驗學習魚群算法

如圖6中的路徑曲線，在3個圓形區域的路徑，并不是最優的路徑，出現了路徑冗長的問題.為了解決路徑規劃中出現的路徑冗長問題，研究提出優化檢測算法.

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

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

(11)

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

(12)

(13)

式中，ki為已被優化檢測的解的個數.

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

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

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

圖5 魚群經驗學習后賦予權值 圖6 基于經驗學習的魚群算法的路徑規劃

4 算法仿真比較實驗

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

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

圖7 基于檢測算子優化算法后的路徑規劃 圖8 20*20柵格移動機器人路徑規劃

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柵格環境算法比較

表3 60*60柵格環境算法比較

5 結論

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