一種基于改進人工蜂群算法的機器人實時路徑規(guī)劃方法

殷霞紅，倪建軍，吳榴迎

(河海大學物聯(lián)網(wǎng)工程學院，江蘇 常州 213022)

0 引言

在移動機器人自主導航中，路徑規(guī)劃是核心研究問題之一。所謂機器人路徑規(guī)劃，就是在有障礙物的環(huán)境下，根據(jù)一些準則為機器人找到一條從起始位置到目標位置的最優(yōu)無碰撞的路徑［1］。機器人路徑規(guī)劃的研究始于20 世紀70 年代，總的來說，路徑規(guī)劃方法可以分成2 種:經(jīng)典方法和啟發(fā)式方法。經(jīng)典的路徑規(guī)劃方法主要包括:勢場法［2］、網(wǎng)格法和可視圖法［3］。

勢場方法擁有簡單的結構，但是這種方法有一些固有的局限性，包括容易陷入局部最小值，在鄰近障礙物之間找不到通道等［2］。在網(wǎng)格法中，存在的主要問題是如何確定網(wǎng)格的大小?？梢晥D法的缺點是搜索效率較低。

由于經(jīng)典方法存在許多不足，學者們開始研究基于啟發(fā)式方法的機器人路徑規(guī)劃，主要包括模糊邏輯、神經(jīng)網(wǎng)絡、遺傳算法等［4-6］，并取得了不少成果。近年來，越來越多的群體智能算法開始應用于路徑規(guī)劃，例如蟻群算法、粒子群算法、蛙跳算法等［7-9］。這些群體智能算法也有一定的局限性，例如容易陷入局部最優(yōu)等。針對這些問題，研究人員提出了一些改進方法，如康冰等人［10］提出了一種改進的蟻群算法，通過采用折返螞蟻等策略，提高了算法的收斂速度和機器人搜索最優(yōu)路徑的能力。Shakiba 等人［11］使用費格森樣條函數(shù)和粒子群算法完成仿人足球機器人的路徑規(guī)劃。

人工蜂群算法［12］是由Karaboga 于2005 年提出來的一種新型仿生群體智能算法，由于其搜索速度快、參數(shù)少、易于實現(xiàn)等優(yōu)點，已經(jīng)成功應用于求解TSP 問題［13］、任務調(diào)度、圖像處理［14］等許多領域。近年來，人工蜂群算法被嘗試用于求解路徑規(guī)劃問題，但是傳統(tǒng)的人工蜂群算法存在容易陷入局部最優(yōu)，且搜索效率低下等不足。針對這些問題，本文提出一種基于改進人工蜂群算法的路徑規(guī)劃方法，并進行了仿真實驗，仿真結果證明了該方法的可行性與有效性。

1 基于改進人工蜂群算法的機器人路徑規(guī)劃方法

機器人路徑規(guī)劃包括如下幾個方面的問題需要解決，一是環(huán)境建模問題，另一方面是對路徑的評價問題。本文采用一種改進人工蜂群算法實現(xiàn)機器人路徑規(guī)劃，具體介紹如下。

1.1 環(huán)境建模

采用柵格法建立移動機器人的環(huán)境模型，首先作如下假設:1)機器人工作在二維環(huán)境中，機器人的起始位置和終點位置已知，且忽略環(huán)境中障礙物的高度信息;2)假設機器人為一個質點，忽略機器人的實際尺寸;3)環(huán)境中障礙物所在的柵格用黑色表示，沒有障礙物的柵格用白色表示，機器人可以在白色柵格中進行運動。在此基礎上，建立環(huán)境柵格模型:假設機器人的移動步長為R(一般設R=1)，以R 為單位對直角坐標系的橫軸和縱軸進行劃分，從而將整個環(huán)境劃分為柵格地圖，則每行的柵格數(shù)為;每列的柵格數(shù)為。柵格的位置可以由坐標或者序列號表示，圖1 表示坐標與序列號之間的關系。

圖1 柵格序列號與坐標關系示意圖

1.2 適應度函數(shù)

機器人路徑規(guī)劃的目標是找到一條盡可能短的路徑，且要避開障礙物，因此，設計適應度函數(shù)如下:

其中，k 是權值，這里取k=0.5，Dn表示路徑長度的代價，Pn表示與障礙物碰撞的代價。設機器人的路徑由D 個路徑節(jié)點構成，則Dn和Pn的計算如下:

公式(3)中，Dsafe表示機器人的安全距離，dmin為路徑到障礙物的最短距離。fitness 的值越小，對應的解越優(yōu)，即規(guī)劃出來的路徑越短。

1.3 基于改進人工蜂群算法的路徑規(guī)劃

由于蜜蜂尋找最優(yōu)食物源的過程和路徑規(guī)劃很相似，所以人工蜂群算法很適合用于解決機器人路徑規(guī)劃問題。在人工蜂群算法中，蜜蜂分為3 種角色:引領蜂、跟隨蜂和偵察蜂，基于人工蜂群的路徑規(guī)劃方法如下:

首先，隨機生成N 個可行解(X1，X2，…，XN)作為初始路徑，每條路徑Xi可表示為Xi=(xi1，xi2，…，xiD)，其中Xi中的每個元素對應于環(huán)境模型中的柵格序列號，D 為路徑節(jié)點數(shù)。然后，引領蜂對初始路徑進行一次鄰域搜索，如果新搜索到的路徑的適應度函數(shù)值優(yōu)于之前的路徑，則用新路徑替換舊路徑，否則保持原路徑不變。當全部引領蜂完成搜索后，回到蜂巢把路徑的信息傳達給跟隨蜂，跟隨蜂通過精英保留選擇策略進行路徑選擇，一旦選中后，也進行一次鄰域搜索，并保留較優(yōu)的解，人工蜂群算法就是通過不斷重復搜索，最終找到最優(yōu)的解［15］。

引領蜂和跟隨蜂通過自適應的搜索方式對路徑位置進行更新，本文采用的更新公式如下:

傳統(tǒng)的人工蜂群算法中，跟隨蜂是通過輪盤賭選擇路徑的，很有可能具有高適應度值的路徑通過輪盤賭而被忽略了。為了解決這個問題，提高算法的性能，本文采用基于精英保留的選擇策略，即讓最好的路徑不需要通過輪盤賭機制而直接進入下一個步驟，防止較短路徑被遺漏。

在本文改進的人工蜂群算法中，利用參數(shù)Times記錄某條路徑被更新的次數(shù)，如果某條路徑連續(xù)循環(huán)的次數(shù)Times 達到一定閾值ε，卻沒有得到改善，表示這條路徑陷入局部最優(yōu)，則舍棄該路徑，重新隨機產(chǎn)生一條新的路徑代替原來的路徑進入循環(huán)。

基于改進人工蜂群算法的路徑規(guī)劃方法的基本步驟歸納如下:

1)初始化參數(shù)。主要包括可行路徑的數(shù)目N，路徑節(jié)點數(shù)D，最大迭代次數(shù)Gmax，最大限制次數(shù)ε。

2)將機器人的運動環(huán)境根據(jù)柵格法進行建模，并在該環(huán)境下，隨機生成N 條可行路徑。

3)每只引領蜂按照公式(4)對初始路徑進行鄰域搜索，如果新產(chǎn)生的路徑的適應度函數(shù)值優(yōu)于當前的，則替代當前路徑，否則保持不變。

4)跟隨蜂按照精英保留選擇策略，把最好的路徑選擇出來直接進行搜索，然后其余的跟隨蜂按照輪盤賭機制選擇一條路徑進行搜索，記錄較優(yōu)解。

5)如果某條路徑循環(huán)ε 次后，仍得不到更新，則在解空間中，重新初始化一條路徑取代它。

6)如果搜索次數(shù)達到Gmax，則記錄最優(yōu)路徑，并跳轉到步驟7)，否則跳轉到步驟3)開始重新搜索。

7)將路徑中的各個節(jié)點連接起來，就得到機器人的規(guī)劃路徑。

2 仿真實驗和結果分析

圖2 初始環(huán)境圖

為了驗證基于改進人工蜂群算法的機器人路徑規(guī)劃方法的準確性與可行性，本文在Intel Core2 CPU，2.1 GHz，Matlab 環(huán)境下進行了仿真實驗。將機器人運動環(huán)境劃分成15 ×15 個柵格，人工蜂群算法中，參數(shù)設置為:路徑數(shù)目N=10，路徑節(jié)點數(shù)D=10，最大迭代次數(shù)Gmax=200，ε=5，Dsafe=1。機器人和目標分別由一個小圓和三角形表示，初始環(huán)境圖如圖2 所示，黑色部分表示障礙物。在相同參數(shù)設置下，用傳統(tǒng)的人工蜂群算法(ABC)和本文改進的人工蜂群算法(IABC)進行對比實驗。2 種算法分別進行10 次實驗，其中一次的仿真實驗結果如圖3 所示，相關數(shù)據(jù)見表1 所示。圖4 給出了2 種算法的進化曲線，其中橫坐標為迭代次數(shù)，縱坐標為路徑長度值。

表1 2 種算法下的實驗結果

圖3 仿真結果圖

圖4 2 種算法下的進化曲線圖

由表1 中的數(shù)據(jù)和圖3 的路徑規(guī)劃曲線可以看出，改進算法所得到的路徑長度優(yōu)于傳統(tǒng)算法，且10次實驗的方差也遠小于傳統(tǒng)的人工蜂群算法，說明本文改進算法的穩(wěn)定性較好。除此之外，本文算法的運行時間也大大縮短了，有利于提高機器人運行的效率。從圖4 中可以看出，本文算法當?shù)螖?shù)達到45 次左右以后，就能找到最優(yōu)路徑，而傳統(tǒng)的人工蜂群算法要到120 次左右才能發(fā)現(xiàn)最優(yōu)路徑，可見本文算法具有更好的尋優(yōu)能力以及更好的全局收斂速度。

3 結束語

本文提出了一種改進的人工蜂群算法用來解決機器人路徑規(guī)劃問題;提出了一種自適應的搜索方式來提高算法的收斂速度，并且采用基于精英保留的選擇策略避免路徑陷入局部最優(yōu);最后，通過仿真實驗驗證了本文改進的算法比傳統(tǒng)人工蜂群算法更有效。本文提出的路徑規(guī)劃方法在移動機器人控制領域具有廣泛的應用，例如，危險環(huán)境下的機器人搜捕和火災探測等［16-17］。

［1］馬千知，雷秀娟.改進粒子群算法在機器人路徑規(guī)劃中的應用［J］.計算機工程與應用，2011，47(25):241-244.

［2］石為人，黃興華，周偉.基于改進人工勢場法的移動機器人路徑規(guī)劃［J］.計算機應用，2010，30(8):2021-2023.

［3］楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規(guī)劃算法［J］.沈陽工業(yè)大學學報，2009，31(2):225-229.

［4］陳衛(wèi)東，朱奇光.基于模糊算法的移動機器人路徑規(guī)劃［J］.電子學報，2011，39(4):971-974.

［5］Li H，Yang S X，Seto M L.Neural-network-based path planning for a multirobot system with moving obstacles［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part C:Applications and Reviews，2009，39(4):410-419.

［6］Tsai C C，Huang H C，Chan C K.Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation［J］.IEEE Transactions on Industrial Electronics，2011，58(10):4813-4821.

［7］劉廣瑞，劉軍，孔令云.移動機器人路徑規(guī)劃蟻群算法及其收斂性分析［J］.鄭州大學學報(工學版)，2012，33(2):24-27.

［8］靳其兵，趙振興，蘇曉靜，等.基于粒子健康度的快速收斂粒子群優(yōu)化算法［J］.化工學報，2011，62(8):2328-2333.

［9］趙鵬軍，劉三陽.求解復雜函數(shù)優(yōu)化問題的混合蛙跳算法［J］.計算機應用研究，2009，26(7):2435-2437.

［10］康冰，王曦輝，劉富.基于改進蟻群算法的搜索機器人路徑規(guī)劃［J］.吉林大學學報(工學版)，2014，44(4):1062-1068.

［11］Shakiba R，Najafipour M，Salehi M E.An improved PSObased path planning algorithm for humanoid soccer playing robots［C］// 2013 3rd Joint Conference of AI ＆ Robotics and 5th RoboCup Iran Open International Symposium(RIOS).2013:1-6.

［12］胡珂，李迅波，王振林.改進的人工蜂群算法性能［J］.計算機應用，2011，31(4):1107-1110.

［13］胡中華，趙敏.基于人工蜂群算法的TSP 仿真［J］.北京理工大學學報，2009，29(11):978-982.

［14］溫長吉，王生生，于合龍，等.基于改進蜂群算法優(yōu)化神經(jīng)網(wǎng)絡的玉米病害圖像分割［J］.農(nóng)業(yè)工程學報，2013，29(13):142-149.

［15］王慧穎，劉建軍，王全洲.改進的人工蜂群算法在函數(shù)優(yōu)化問題中的應用［J］.計算機工程與應用，2012，48(19):36-39.

［16］Ni Jianjun，Yang S X.Bioinspired neural network for realtime cooperative hunting by multirobots in unknown environments［J］.IEEE Transactions on Neural Networks，2011，22(12):2062-2077.

［17］Tian Yan-tao，Yang Mao，Qi Xin-yue，et al.Multi-robot task allocation for fire-disaster response based on reinforcement learning［C］// 2009 International Conference on Machine Learning and Cybernetics.2009，4:2312-2317.