混合改進人工蜂群算法的機器人路徑規劃研究

陳信華，孟冠軍，張 偉，張 磊

（合肥工業大學機械工程學院，安徽 合肥 230009）

1 引言

路徑規劃是機器人研究領域中的核心內容之一，針對路徑規劃的算法研究也是該領域的熱點和難點。根據路徑規劃的不同目的其可以劃分為兩種形式，分別為點到點的路徑規劃和完全遍歷路徑規劃[1]。

這里主要研究點到點的路徑規劃，根據一定準則尋找一條從起點到終點的最優路徑。經典的機器人路徑規劃方法主要包括：多邊形擬合（Polygonal Approximation，PA）法[2]、可視圖（Visibility Graph，VG）法[3]、人工勢場（Artificial Potential Field，APF）法等[4]。雖然這些算法在路徑規劃方面取得了不錯的效果，但都存在著一定的局限性，如易于陷入局部最小值、搜索效率較低等問題。為了改進經典算法在路徑規劃運用中存在的不足，智能算法得到研究人員的關注。包括蟻群算法（Ant Colony Optimization，ACO）[5]、混合蛙跳算法（Shufled Frog Leaping Algorithm，SFLA）[6]、遺傳算法（Genetic Algorithm）[7]在內的各種群體智能算法在路徑規劃的運用中越來越普遍，也能獲得較理想的結果。但同樣需要進一步提高算法的收斂速度，避免早熟現象。

人工蜂群（Artificial Bee Colony，ABC）算法是一種基于蜜蜂的覓食行為而啟發的算法，在2005年由Karaboga小組為優化代數問題而提出[8]。

該算法具有結構相對簡單且易于實現、控制參數較少，無需梯度信息等優點，已經成功應用于任務調度、求解TSP問題、圖像處理等眾多領域。近年來，人工蜂群算法也被嘗試運用于機器人路徑規劃的研究上，但是標準ABC算法存在易于陷入局部最優，進化后期收斂速度慢等不足，限制了ABC算法在實際中的引用。

為了提高ABC算法在求解路徑規劃時獲取最優解的能力，包括克服早熟、提高收斂速度和尋優精度，使用了新的搜索機制。利用APF算法能在目標點附近產生引力以及在障礙物附近產生斥力的特點，將APF 與ABC 算法相結合以提高算法求解速度。但APF算法和ABC算法存在易于陷入局部最優的缺點，因此針對ABC算法做出改進，將Levy分布與柯西分布分別引入食物源更新公式和隨機搜索公式中，增強了ABC算法局部和全局搜索能力。

最后提出一種混合改進人工蜂群算法（Hybrid Improved Artificial Bee Colony，HIABC），通過實驗證明了算法能夠提高在求解機器人路徑規劃時解的質量。

2 人工蜂群算法

蜜蜂是一種群居昆蟲，自然環境中的蜜蜂能夠在任何復雜環境下找到食物源進而采蜜。蜂群所產生的群體智慧的最小搜索模型包括三個要素：食物源、被雇傭的蜜蜂、未被雇傭的蜜蜂[9]。食物源的評價標準由多個因素來確定，包括：離蜂巢的距離、蜜源量的大小以及采蜜難易程度等[10]。

根據蜜蜂的采蜜機制將人工蜂群分為三類：偵察蜂、觀察蜂和采蜜蜂。

其中每個采蜜蜂分別對應一個確定的蜜源，并在迭代過程中對蜜源的領域進行搜索同時更新蜜源信息和確定蜜源的花蜜量；

然后觀察蜂根據蜜源的豐富程度采用輪盤賭選擇策略來選擇相應蜜源，并更新蜜源信息和確定蜜源量的大小；當搜索空間被采蜜蜂和觀察蜂全部搜索完后，如果在限定的循環次數后蜜源的適應值仍沒有改進，則放棄該蜜源，采蜜蜂轉為偵查蜂并根據隨機搜索策略搜索新蜜源。

ABC算法可簡要描述為：蜂群搜索蜜源過程中，首先在搜索空間中隨機生成SN個蜜源，每個蜜源代表一個初始解Xi(i=1，2，L，SN)，該解為一個D維向量［11］。

采蜜蜂和觀察蜂根據下式進行搜索更新蜜源信息：

式中：vij—新的食物源位置；φij—[ -1 1 ]范圍內的隨機數，控制著xij領域的生成范圍；k、j—k∈{1，2，L，SN}，并且k≠i，j∈{1，2，…，D}，兩者下標隨機選取。

觀察蜂所采用的輪盤賭選擇公式為：

式中：SN—解的個數；fiti—第i個解的適應度函數值。適應度函數是影響蜂群算法收斂和穩定的重要因素[12]，fiti值越大則對應的解越優，適應度函數評判標準，如式（3）所示。

式中：n—機器人運動路徑等分點數。偵查蜂所采用的隨機搜索公式為：

3 混合改進人工蜂群算法

3.1 食物源更新公式的改進

在標準ABC算法中，采蜜蜂與觀察蜂根據式（1）在蜜源附近來搜索并更新蜜源。但這種更新只是基于當前蜜源i在附近隨機選取其它蜜源，會導致個體間的信息未能被充分利用，使得算法在局部搜索能力較弱且種群淘汰效果不佳。因此考慮在食物源更新公式中引入當前最優蜜源位置xbestj，使歷史最優位置對當前位置產生影響，提高算法在局部的搜索能力。

同時標準ABC算法更新種群時采用隨機步長，步長太大或太小會導致新解遠離當前最優解和新解變化小，搜索效率低。針對以上存在的問題，考慮引入變異算子來調整步長。

由線性組合分布理論知Levy 分布[13]滿足重尾的穩定分布，其兼具正態分布與柯西分布的特性，可產生合適步長，在進化陷入局部最優時，服從Levy分布的隨機數可引導個體快速跳出，使算法具有較好的全局搜索能力。引入Levy分布后的食物源更新公式可表示為：

式中：xbestj—當前最優蜜源位置；Levy(β)—對應于xij服從指數為β的Levy分布，即為：

其中，通常設置λ=1。由于Levy分布生成的步長相對復雜，可由Mantegna 算法來實現對稱Levy 穩定分布。采用式（7）來計算步長：

式中：β取值范圍同上，通常β=1.5；u、ν—服從正態分布。

σμ和συ表達式如下：

式中：Γ—標準的Gamma函數[14]。食物源更新公式為：

3.2 隨機搜索策略的改進

偵查蜂根據隨機搜索策略的公式隨機產生一個新解來代替xi。由于公式產生的解隨機性太強導致算法在尋優過程中容易陷入局部極值。為克服該缺陷，引入柯西分布［15］，將隨機變換rand( 0，1)換成柯西變異算子C(0，1)。

柯西變異算子使得公式能充分利用當前搜索到的信息，增加了算法的抗擾動能力，改進后的隨機搜索公式為：

3.3 HIABC算法中的勢場力法

根據人工勢場法的特點，人工勢場包括引力勢場和斥力勢場，路徑規劃環境中在目標點附近形成一個引力勢場，而在障礙物附近一定范圍形成斥力勢場。

設在環境中某處為Q，則該處引力勢場可表示為：

式中：ξ—引力尺度因子，非負數；d(q，q goal)—機器人當前位置與目標的距離。

故機器人所受目標引力即為引力場對距離的導數：

當機器人越接近目標時所受到的引力就會越小，直到為零。Q處的斥力勢場為：

式中：η—是斥力尺度因子；ρ(q,qobs)—機器人當前位置與障礙物的距離；ρ0—障礙物斥力范圍。

同理機器人所受障礙物斥力即為斥力場對距離的導數：

綜上所述，機器人在運動環境中所受的總的勢力場即為引力場和斥力場的疊加，所受力即為來自目標點的引力和來自障礙物的斥力的合力，該合力決定了機器人的運動方向。

3.4 路徑規劃的HIABC算法執行步驟

綜合上述描述，HIABC算法執行可以分為以下步驟：

（1）種群參數初始化。主要包括種群的規模，如初始解xi的個數SN及其維數D，計算評價各個解的適應度函數值；算法的最大限制次數Limit值和最大迭代次數。

（2）每只采蜜蜂根據表達式（10）在搜索空間中對蜜源進行鄰域搜索，找出新的蜜源并計算其適應值。如果該適應值優于當前蜜源，則取代該蜜源，反之則不變。

（3）基于上步得到的各適應值，觀察蜂通過式（2）采用輪盤賭選擇策略來選擇蜜源，并在蜜源領域進行再搜索，采用式（10），更新蜜源位置。記錄最優解。

（4）若到達算法的限制次數Limit后，蜜源仍舊沒有更新，則該蜜源被放棄。采蜜蜂變為偵查蜂，且根據式（11）產生隨機解，用于替換被放棄的蜜源位置。否則轉到（5）。

（5）完成一次迭代，記下該次迭代中的最優蜜源位置。

（6）判斷循環迭代次數是否達到終止條件，若達到，則停止循環轉到（7）；若未達到，則跳到（2）。

（7）連接每次迭代中的最優蜜源節點，進而得到一條從起始點到目標點的最優路徑，即為機器人的規劃路徑。

4 路徑規劃仿真試驗及分析

4.1 機器人運動環境模型

設機器人的工作任務空間為二維空間，空間中存在著若干靜止且大小不變的障礙物，機器人需在空間中繞過障礙物從起點到達指定目標點。

采用柵格法來建立路徑規劃的運動環境模型，通過柵格將環境空間分割成多個大小相同的單元格，處于障礙物范圍的單元格作為障礙柵格，反之即為自由柵格。

設機器人工作任務空間由（20×20）的柵格組成，環境中共有20個不同大小障礙物，對柵格依次進行編號，黑色柵格表示障礙物，白色柵格表示自由可行柵格，如圖1所示。

圖1 機器人運動環境模型圖Fig.1 Robot Motion Environment Model Diagram

為了簡化分析，假設機器人每次只行進一個格子包括斜對角線，那么機器人在運動過程中就存在以下兩種情況：

（1）當機器人運動至環境中間處（非邊界處），則機器人周圍存在8個可以選擇的路徑，如圖2所示。

圖2 機器人運動位置圖Fig.2 Robot Motion Location Map

假設當前機器人坐標為(x0,y0)，那么機器人8種路線的坐標變化分別為：

（2）當機器人運動至邊界則存在8個特殊位置（A-H），這8種地方的位置坐標條件以及可走的路線分別為：

其中A處可走路線2、3、5；B處可走路線1、2、3、4、5；C處可走路線1、2、4；D處可走路線1、2、4、6、7；E處可走路線4、6、7；F處可走路線4、5、6、7、8；G處可走路線5、7、8；H處可走路線2、3、5、7、8。

4.2 仿真環境及參數設置

仿真環境：利用MATLAB R13a，在Intel（R）Core（TM）i5-3210M CPU@2.50GHZ、4.00GB內存、Window 7操作系統下進行仿真驗算。

首先在MATLAB中建立圖1所示的環境模型圖，根據具體環境模型將HIABC 算法的參數設置為：種群規模SN=20；蜜源個體維度D=10；最大限制次數Limit=20；最大循環次數Gmax=100；路徑長度權值1；起始點坐標（0.5，19.5）；終點坐標（19.5，0.5）。

4.3 仿真結果及分析

在同一變量參數下，采用標準ABC算法和HIABC算法對圖1環境模型進行求解，求解結果，如圖3、圖4所示。

圖3 兩種算法的最優路徑規劃Fig.3 Optimal Path Planning for Two Algorithms

從圖中可以看出，兩種算法下選擇的最優路線不同，可以看到基于HIABC算法下的機器人路徑規劃結果明顯更優。兩種算法下所得到的迭代曲線圖，如圖4所示。

圖4 兩種算法的迭代曲線圖Fig.4 Iterative Graph of Two Algorithms

兩種算法的路徑搜索模型在整體上都呈收斂趨勢。在搜索之初雖然出現了一定的波動，但隨著波動的持續變化，搜索的路徑越來越短。

在搜索中后期，隨機搜索的數量越來越少，最優路徑趨于平緩。HIABC 算法下的路徑規劃在迭代約20 次后收斂到最短路徑，路徑長度約為30.000。

而標準ABC算法的路徑規劃是在迭代約40次后收斂到最短路徑，路徑長度約為32.300。

為了更好的比較ABC和HIABC算法的性能，將兩種算法在同樣的實驗條件下運行10次，如表1所示。

由表1數據可知，ABC算法在求解路徑規劃時得到的路徑長度存在一定的波動，且很難獲取最優值。

表1 路徑規劃長度和運行時間Tab.1 Total Length and Run Time of Path Planning

而HIABC算法獲得的路徑長度值則相對穩定一些，由于人工勢場法的結合，使得獲取解的效率也得到大大提高。實驗結果表明基于HIABC算法在路徑規劃的研究中能夠更高效的找到機器人運動的最短路徑。

5 結束語

提出了一種基于混合改進人工蜂群算法的機器人路徑規劃研究方法。

在標準ABC算法的基礎上，對算法中的食物源更新公式和隨機搜索策略進行改進，彌補了標準ABC算法收斂速度慢且易陷入局部最優導致算法停滯的不足。

同時利用人工勢場法簡單高效的優點將其與ABC算法相結合提高了算法的收斂速度。基于此方法在MATLAB 軟件中進行了仿真實驗，實驗結果證明了HIABC算法的可行性和有效性，為研究機器人路徑規劃提供了重要的參考價值。

不足之處是在算法的參數設置上仍有待進一步優化，簡化了環境中的約束條件導致與實際情況有一定的差距。

進一步研究工作展望：

（1）在算法中引入更加有效的約束條件，進一步提高算法的收斂速度和尋優精度。

（2）設計機器人動態環境模型，將算法運用到實時避障路徑規劃系統以及更多的實際應用當中。