基于人工蜂群算法的機器人路徑規劃研究

周國春，肖本賢

（1.合肥工業大學 工業與裝備技術研究院，合肥 230009；2.合肥工業大學 電氣與自動化工程學院，合肥 230009）

近年來，移動機器人系統已經成為人工智能和智能控制等領域的一個研究熱點，受到了越來越多研究者的重視[1-2]。移動機器人最重要的作用就是能移動，這種移動并不是漫無目的的移動，而是能夠自動從起點運動到終點的能力。在移動機器人移動之前，就已經生成一條從起點到終點的最佳路徑，并且這條路徑能夠躲避一切固定的障礙物，還能夠提前規避其他機器人[3]。移動機器人的路徑規劃問題經過幾十年的研究，我們得到很多關于這類問題的有效解決方法。傳統的路徑規劃方法有可視圖法、柵格法和人工勢場等，群智能算法有蟻群算法、粒子群算法和人工蜂群算法等。這些算法都能夠在一些環境中解決了路徑規劃問題，同樣也存在不足[4-6]。

當前對于機器人路徑規劃方法的研究，有時候會考慮到很多因素，不一定不需要移動機器人規劃出距離最短的路徑。所以在實際應用中，我們考慮路徑規劃的時候要結合當前環境以及實際要求來確定出最優路徑。通常評判路徑規劃的指標有路徑距離的大小、與障礙物保持安全距離以及路徑沒有過多曲折。在這類情況中，需要移動機器人路徑規劃的結果滿足上述要求多個指標的要求。目前，對于機器人路徑規劃實時性要求較高并且對可行路徑有多標準的任務中，通過將路徑規劃所要滿足的多個指標通過一定的方式轉化成一個綜合評價指標來規劃出最適合機器人的最優路徑。常用的轉化方式有約束法和權重系數變化法。本文采取設置權重系數，將多個路徑評價指標轉化成一個綜合評價指標，并且和優化后人工蜂群算法合并進行仿真試驗，試驗可知提出的方法可更快速地尋得更優的全局最優解。

1 人工蜂群算法

人工蜂群算法[7-10]從提出開始，由于其參數少，自適應強，受到很多研究者的追捧，廣泛應用于各大領域，其中就包括移動機器人的路徑規劃領域。

1.1 人工蜂群算法的數學模型

初始化會形成一個初始食物源。即初始解（x1，x2，…，xn，…，xN）：

式中：lbi為可行解的最小值；ubi是可行解的最大值；rand（0，1）生成（0，1）之間的隨機數；n∈｛1，2，3，…Fn｝，Fn為食物源數目。

食物源生成之后，評價函數會對生成的食物源進行評價，評價函數如式（2）所示：

式中：f（xn）為對應的解向量xn的目標函數值。

雇傭蜂在當前食物源附近搜索新食物源的方法如式（3）所示：

式中：xni′為新食物源；xni為當前食物源；ε為搜索系數，其值介于［-1，1］之間；xki是食物源中一個不同于 xni的食物源，k∈｛1，2，3，…Fn｝。

當搜索到新食物源，雇傭蜂會對這個新食物源進行評價，并與之前的食物源進行對比，來決定放棄哪個食物源。

觀察蜂參照雇傭蜂返回時所帶來的食物源信息進行選擇覓食。它們會利用食物源的評價函數來計算他們選擇某個食物源的可開采的概率probabilityn，計算方法如式（4）所示：

觀察蜂會因個體差異，存在各自對食物源的期望。然后將期望和可開采概率比較，來決定觀察蜂是否選擇此食物源進行開采。

偵察蜂的作用是搜索新的食物源，并不參照當前食物源，而是類似初始化一樣隨機生成。在此之前會對選擇次數超過限定值的食物源進行放棄，如式（5）所示：

式中：trial是當前蜜蜂對食物源優化的次數。

1.2 移動機器人的環境地圖

在移動機器人路徑仿真中，如果不考慮機器人的結構，通常將移動機器人當作一個質點。由于柵格法建立的地圖存在一些缺陷，我們采用坐標法來定位移動機器人的位置。在移動機器人路徑規劃中，由于一開始就知道移動機器人的位置，也知道它將要到達的地方。這樣根據移動機器人的起點和終點的坐標對應的X軸和Y軸上的數值最小值和最大值來生成一個長和寬均大一的矩形地圖。這樣機器人在地圖中的任何位置都可以由坐標值來表示。在這里我們規定移動機器人的移動步長Stepl，那么機器人的下一個位置就是以當前位置為圓心，半徑為Stepl的圓上。這樣如果我們可以得知下一個位置相對當前位置的角度，則可以準確得到下一個位置的準確值。公式如下所示：

式中：（xk＋1，yk＋1） 是移動機器人下一位置；（xk，yk）是移動機器人當前位置；θk是移動機器人下一位置相對當前位置的夾角。

通過這種表示方法，我們可以由移動機器人的起點坐標就可以直接得出移動機器人規劃出的路徑上任何一個點，如式（7）所示。

式中：（xk，yk）是移動機器人的任一路徑點坐標，k＝（1，2，…Fn）；（xs，ys）是移動機器人起點。

在工作環境地圖中，通常存在一些障礙物，對于已知的靜態環境來說，障礙物也是已知。我們采用一個比障礙物大一些的同心圓將障礙物包圍。這樣得出的移動機器人環境地圖如圖1所示。

圖1 機器人路徑規劃環境地圖Fig.1 Robot path planning environment map

在路徑仿真中，移動機器人要計算到障礙物的距離就可以通過已經得知障礙物同心圓的圓心和半徑來計算。

2 基于人工蜂群算法的路徑規劃

2.1 人工蜂群算法的改進

在人工蜂群算法中隨機搜索系數 ε=［-1，1］。隨機搜索系數是來確定蜜蜂對當前食物源附近的范圍進行搜索，在迭代早期需要進行范圍較大搜索，有利于得到全局最優解，但在迭代后期，目標解已經趨于穩定，這時候過大的搜索范圍不利于算法收斂，還會增加算法優化的時間。這里，我們對隨機搜索系數ε進行改進，設計了如式（8）所示的新隨機搜索因子。新的隨機搜索系數與迭代的次數成反比，在迭代初期仍在［-1，1］之間，但在迭代后期，隨機搜索系數只有早期的e-1，這樣符合我們的要求。

式中：Loop為當前迭代次數；MaxLoop為最大的迭代次數。

同時人工蜂群算法中雇傭蜂和觀察蜂搜索食物源時較大程度依賴當前所采蜜的食物源，雖然參考的其它蜜蜂的食物，但所占比重較小，這樣極易陷入局部最優，所以采用在食物源中隨機選擇3個食物源進行交叉產生新的食物源，公式如下：

式中：p，k，q均不等于n，將其與之前的隨機搜索相結合，搜索前產生一個隨機數P，隨機數P的大小和迭代次數成反比，這樣在算法的初期很好地進行全局搜索，在算法的后期只進行局部搜索，不會增加算法的運行時間。當隨機數P小于設定參數Pm時執行隨機搜索方式，反之執行新的搜索方式，如式（10）所示。通過將兩種搜索方式相結合，在蜜蜂搜索食物源的過程中，既能夠進行全局搜索，也能夠避免陷入局部最優。

人工蜂群算法應用于移動機器人路徑規劃中，就要對算法的目標函數提出新的要求。本文中，路徑規劃的評價指標存在3種，所以算法的目標函數也要包括這3項指標。三項指標分別是規劃出的路徑總長度；二是路徑是否安全，是根據移動機器人到障礙物的最小長度是否大于最小安全距離，最小長度的計算方法是移動機器人的位置點到障礙物同心圓邊界的最小長度；三是路徑的曲折性，通過計算各個位置點之間對應的夾角和。通過動態加權系數后得出評價任一條路徑的目標函數如式（11）所示。

式中：distgoali代表機器人的路徑點（xi，yi）到目標點（xgoal，ygoal）的距離；distobsi為機器人的路徑點（xi，yi）到障礙物（oxk，oky）的距離；rj為障礙物安全區半徑；obs為障礙物的數目；ω1、ω2、ω3為權重系數，其中 ω1+ω2+ω3=1。

為了使目標函數符合實際要求，一般設置ω3為定值，ω2隨著路徑點離障礙物的距離變化，如式（12）所示，而 ω1=1-ω2-ω3。

式中：ω2在［0.1，0.3］之間變化；distmax是絕對安全距離；distmin是最小安全距離。

2.2 改進后的人工蜂群算法在移動機器人路徑規劃的應用

為了使移動機器人能夠正確規劃出起點到終點的路徑。在環境地圖那章中，我們用規定的定步長，以及相對位置的夾角作為標記移動機器人的位置。因此，算法初始化生產一組關于初始角度大小的初始解，之后通過不斷優化得到最終最優角度解，最優解包含了移動機器人所有路徑點的信息。移動機器人在開始路徑規劃之前，就已經得知環境中的靜態障礙物的位置和大小，環境中存在的動態障礙物為同一工作空間中的其它移動機器人。一旦路徑點與所有障礙物的最小距離大于絕對安全距離，基本不用考慮安全性的問題。但是一旦低于最小安全距離，則該路徑的適應值變為0，重新規劃路徑。

在實際情況中，通常會存在多個移動機器人同時進行路徑規劃工作。在這種多機器人路徑規劃任務中，先給各移動機器人進行編號，編號小的機器人擁有較高優先級。這樣多移動機器人在進行路徑規劃時，首先會判斷該移動機器人是否與優先級較高的移動機器人存在交叉點。一旦發現存在交點，則會進一步判斷是否同時經過該點。在相同的步長中，通過步數來判斷是否同時經過交叉點。如果兩個機器人同時經過交叉點，則將優先級點的移動機器人在該路徑適應度值置為0，并重新規劃路徑。在規劃某一移動機器人路徑點時，會計算該移動機器人與當前所有優先級比它高的機器人所處的位置點之間的距離，如果有小于最小安全距離的，則將該移動機器人當前規劃的路徑適應值置為0，并重新規劃路徑。

3 仿真試驗及分析

3.1 仿真環境設置

為了驗證總評價標準的目標函數對路徑規劃的影響，同時也測試改進后的人工蜂群算法的優點，使用Matlab軟件進行仿真實驗。仿真實驗中設置編號為1、2、3的移動機器人和4個用同心圓包圍的障礙物。移動機器人路徑的起點和目標點坐標如表1所示，障礙物中心點的坐標及危險區半徑大小如表2所示。

表1 移動機器人起點和終點坐標Tab.1 Mobile robot start and end coordinates

表2 障礙物中心坐標及危險區半徑Tab.2 Center coordinates of obstacles and radius of danger zone

為了評估所提方法的有效性，仿真條件設置如下：

（1）分別采用標準人工蜂群算法（目標函數只考慮路徑距離）和改進后的人工蜂群算法（目標函數采用綜合評價指標）進行移動機器人路徑規劃。

（2）為了比較改進前和改進后的算法在移動機器人路徑規劃所得出總長度和規劃所需要的總時間，將兩種算法在相同的環境下各自運行10次。

3.2 仿真結果

我們設置循環次數為1500次，種群大小為40，即可行解的數量為 20，ω3=0.2、-45°≤θ≤45°。 仿真結果如圖2和圖3所示。

從圖2和圖3的仿真結果對比可知，采用綜合評價指標路徑是要優于只考慮路離指標的路徑，并且可以改進后的人工蜂群算法得到的路徑點的曲折性較標準人工蜂群算法的路徑要小，減小移動機器人的轉向負擔。

為了證明改進后的人工蜂群算法加快了收斂速度，減少了路徑規劃所花費的時間。將這兩種方法在同樣的實驗條件（同樣的綜合評價指標）下各自運行10次，其結果如表3所示。

圖2 標準人工蜂群算法的規劃結果Fig.2 Programming results of standard artificial bee colony algorithm

圖3 改進后的人工蜂群算法的規劃結果Fig.3 Programming results of optimized artificial bee colony algorithm

表3 路徑規劃的總長度和運行時間Tab.3 Total length and run time of path planning

由表3的數據可知，從規劃所得的路徑總長度上來看，兩種路徑規劃的基本一致。改進后的人工蜂群算法所得出路徑總長度比較穩定，標準的人工蜂群算法存在一點浮動。在移動機器人路徑規劃所花費的時間上，采用改進后的人工蜂群算法要明顯少于采用標準人工蜂群算法，這樣使得路徑規劃的效率得到提高。仿真結果證明人工蜂群算法可以用來解決移動機器人路徑規劃問題，改進的人工蜂群算法在路徑規劃方面更加穩定，并且節省路徑規劃所需要的時間。

4 結語

針對路徑規劃的特點，提出了評價路徑的綜合指標，利用綜合指標去考查移動機器人的路徑規劃，得出的路徑的綜合評價是最優的。對標準人工蜂群算法的食物源搜索方式進行改進，使算法在初期能夠進行全局搜索，而在后期又可以加快收斂速度。仿真結果表明，利用綜合評價標準得出的路徑滿足移動機器人的要求，并且通過對算法的改進較大的縮短了路徑規劃的時間，使得移動機器人工作的更加有效率。

[1]Lei Ulusoy，Alphan，Smith，et al.Optimal multi-robot path planning with temporal logic constraints[C]//International Conference on Intelligent Robots and Systems，IEEE，2011：3087-3092.

[2]Hou Y B，Wang W，et al.Mobile robot path planning and research in the improved artificial immune algorithm[J].Advanced Materials Research，2012，466-467.

[3]Jur P.van den Berg，Mark H.Roadmap-based motion planning in dynamic environments[J].IEEE Transactions on Robotics，2005，21（5）：885-897.

[4]陳超，唐堅，靳祖光.一種基于可視圖法導盲機器人路徑規劃的研究[J].機械科學與技術，2014，33（4）：490-495.

[5]柴寅，唐秋華，鄧明星.機器人路徑規劃的柵格模型構建與蟻群算法求解[J].機械設計與制造，2016（4）：178-181.

[6]蔡炯，汪小志.基于粗糙集與遺傳算法的采摘機器人路徑規劃[J].農機化研究，2016，38（8）：189-193.

[7]李彥蒼，彭揚.基于信息熵的改進人工蜂群算法[J].控制與決策，2015（6）：1121-1125.

[8]Mansury E，Nikoorar A，Salehi M E.Artificail Bee Colony optimization of ferguson splines for soccer robot path planning[C]//2013 First RSI/ISM International Conference on Robotics and Mechatronics（ICRoM)，2013：85-89

[9]張長勝.多目標人工蜂群算法及遺傳算法的研究與應用[M].沈陽：東北大學出版社，2013.

[10]竇連航.基于人工蜂群算法的多機器人路徑規劃研究[D].上海：上海大學，2015.