顧軍華，孟慧婕，夏紅梅，董永峰

（1.河北工業(yè)大學 計算機科學與軟件學院，天津 300401；2.河北工業(yè)大學 河北省大數據計算重點實驗室，天津 300401；3.河北工業(yè)大學 河北工業(yè)大學學報編輯部，天津 300401）

基于改進蟻群算法的多機器人路徑規(guī)劃研究

顧軍華1,2，孟慧婕1,2，夏紅梅2,3，董永峰1,2

（1.河北工業(yè)大學 計算機科學與軟件學院，天津 300401；2.河北工業(yè)大學 河北省大數據計算重點實驗室，天津 300401；3.河北工業(yè)大學 河北工業(yè)大學學報編輯部，天津 300401）

針對蟻群算法在機器人路徑規(guī)劃過程中存在的收斂速度慢、效率較低、容易陷入局部最優(yōu)等缺點，提出了一種多步長的改進蟻群算法．該算法實現了多步長路徑規(guī)劃；同時在概率公式中加入了拐點參數，使路徑更加平滑；并且提出了新的信息素獎勵懲罰機制．將改進的蟻群算法應用于具有3個優(yōu)化目標的多機器人路徑規(guī)劃中，采用碰撞預測策略和路徑協(xié)調策略完成多機器人間的協(xié)調避碰．仿真結果表明，改進的蟻群算法規(guī)劃的路徑更短、更平滑，效率更高，驗證了該算法在多機器人路徑規(guī)劃中的有效性和可行性．

多機器人；路徑規(guī)劃；改進蟻群算法；多步長；拐點參數；協(xié)調避碰

0 引言

多機器人路徑規(guī)劃問題是多移動機器人系統(tǒng)中最基本的問題之一，它的任務是為每個機器人規(guī)劃一條從起點到終點的最優(yōu)路徑，并且保證機器人和機器人之間、機器人和障礙物之間沒有碰撞．目前眾多學者已針對此問題展開了大量研究．文獻[1]將全局目標點映射到視野域附近作為局部子目標，再由兩組螞蟻相向搜索視野域內的局部最優(yōu)路徑，在此基礎上進行與其他機器人的碰撞預測與避碰規(guī)劃，但是在動態(tài)不確定環(huán)境中規(guī)劃路徑所需的時間較長．文獻[2]采用集中式和分布式相結合，融合免疫協(xié)同進化算法與人工勢場法進行全局和局部規(guī)劃．文獻[3]提出了基于雙層模糊邏輯的多機器人路徑規(guī)劃，考慮障礙物的距離和目標的角度，同時為了提高避碰的效率提出改變機器人的速度，但是機器人缺少對全局環(huán)境的了解，難以保證多機器人規(guī)劃出的路徑全局最優(yōu)．蟻群優(yōu)化算法因其并行性、魯棒性、易于與其他算法相結合的優(yōu)點[4]，廣泛應用于移動機器人路徑規(guī)劃問題[5-6]．許多學者針對路徑規(guī)劃問題對基本的蟻群算法進行了改進．文獻 [7]提出了蟻群算法和模糊控制相結合的方法，但該方法比較復雜，較難掌握．文獻 [8]提出根據目標點自適應調整啟發(fā)函數，信息素更新時參考狼群分配原則，同時引入粒子群算法改進蟻群算法的參數，優(yōu)化了蟻群算法的性能．文獻 [9]改進了期望值，更新信息素采用自適應方式，并在更新信息素時引入拐點，但是該方法由于步長的單一，對路徑長度的改進不是特別明顯．

本文提出一種多步長的改進蟻群算法．首先用柵格法進行建模，采用多步長縮短了路徑長度，在概率公式中加入了拐點參數使路徑更加平滑，提出了新的信息素獎勵懲罰機制避免陷入局部最優(yōu)．然后將改進的蟻群算法應用到3個機器人的路徑規(guī)劃中，主要分為2步：1）各個移動機器人采用改進的蟻群算法，獨自規(guī)劃一條初始路徑（忽略其他機器人）；2）如果在視野域范圍內發(fā)現其他機器人，進行局部避碰協(xié)調規(guī)劃．最后先在單機器人情況下將改進的蟻群算法和文獻[9]中提到的改進蟻群算法進行比較，然后把改進后的算法應用到多機器人中，完成仿真實驗．

1 環(huán)境描述

多個機器人的工作環(huán)境為二維靜態(tài)環(huán)境，有N個機器人Ri，i∈ (1,2,……,N)；機器人的起點和終點分別為Si和Gi，起點和終點各不相同；機器人之間能進行基本的通信；所有機器人的速度相同，狀態(tài)可以為勻速運動和暫停；機器人的大小相同．

采用柵格法進行建模，它能夠方便處理障礙物的邊界問題，柵格模型如圖1所示，左下方為原點，向右為x軸，向上為y軸，柵格的邊長為1．黑色部分表示有障礙物的柵格（障礙柵格），當障礙物小于一個柵格時，按照占一個柵格處理，白色部分為不存在障礙物的柵格（自由柵格）．把障礙物外擴一個機器人的最大直徑，移動機器人在柵格之間的移動可以近似成一個質點．

圖1 柵格法環(huán)境模型Fig.1 Grid environment model

設序號為i的柵格對應的坐標為(xi，yi)，則序號編碼與坐標對應關系如式 (1)所示．其中當mod(i,20) ==0，即i為20的整數倍時，將xi設為19.5．

2 蟻群算法

2.1 基本蟻群算法

蟻群算法是一種典型的路徑規(guī)劃算法．每只螞蟻在搜索路徑的過程中，基于其獲取的環(huán)境信息（主要是其它螞蟻在其走過路徑上留下的信息素濃度），按照若干簡單規(guī)則進行實時路徑規(guī)劃，找到1條從起點到終點的最優(yōu)無碰撞路徑．雖然每只螞蟻表現出簡單的行為，但是螞蟻群體中大量螞蟻通過與環(huán)境相互作用，就會呈現出復雜且靈活多樣的行為．

2.1.1 轉移概率

設螞蟻數量為M，假設第m(m=1,2,…,M)只螞蟻位于序號為i的柵格處，螞蟻m根據節(jié)點的信息素強度和啟發(fā)信息選擇下一節(jié)點j，轉移概率公式如式 (2)所示

2.1.2 信息素更新

蟻群經過某個柵格時會留下信息素，隨著時間的推移信息素會逐漸消逝，每一代的所有螞蟻完成尋徑以后，要對信息素進行更新，更新公式如式 (4)所示．

其中：Mij為經過路徑(i,j)的螞蟻集合；為第m只螞蟻留給節(jié)點i、j間的信息素增量，如式 (6)所示，Q為一適當常數，Lm為本次循環(huán)中螞蟻m走過的路徑長度．

2.2 改進的蟻群算法

針對基本的蟻群算法效率低和容易陷入局部最優(yōu)的缺點，本文提出了幾點改進：多步長、概率公式加入拐點參數以及信息素更新方式的改進等．

2.2.1 多步長

基本的蟻群算法路徑規(guī)劃時，螞蟻只能選擇相鄰的柵格作為下一節(jié)點，如圖2所示，螞蟻當前所處的柵格為34，基本蟻群算法只可以選擇周圍的8個柵格，可選集合為 {23,24,25,33,35,43,44,45}．改為多步長后可以選擇周圍的24個柵格作為下一節(jié)點，螞蟻可以從34柵格一步移動到26柵格．

如圖3所示螞蟻從柵格i到柵格j時，基本的蟻群算法選擇的最優(yōu)路徑可能為路徑1，改為多步長以后最優(yōu)路徑為路徑2，可見多步長縮短了路徑的長度．采用多步長時，需要將選擇的下一節(jié)點和路過的節(jié)點都加入到禁忌列表中．

圖2 多步長示意圖Fig.2 Multi step diagram

圖3 多步長蟻群和基本蟻群路徑長度比較Fig.3 Comparison of multi-step ant colony and basic ant colony path length

2.2.2 概率公式

為了使所尋路徑更加平滑，加入拐點參數gdij作為螞蟻選擇下一節(jié)點的一個依據．路徑中拐角分為銳角、直角和鈍角3種，假設螞蟻位于節(jié)點i，由節(jié)點i運動到下一可行節(jié)點j時拐角為A，拐點參數對應的值如式(7)所示，其中A的角度越大被選中的概率越大，改進后的概率公式如式(8)所示．為了避免陷入局部最優(yōu)，采用輪盤賭法選擇節(jié)點．

2.2.3 信息素更新

基本蟻群算法中，最差螞蟻釋放的信息素將導致算法的搜索陷入局部最優(yōu)，為了避免局部最優(yōu)和提高收斂速度，本文提出了新的信息素獎勵懲罰機制，對本次迭代的最優(yōu)路徑給予獎勵，增大其釋放的信息素量，對最差路徑進行懲罰，改進的信息素濃度更新公式如式 (9)～式 (11)所示，M_bij和M_wij分別為經過本次迭代最優(yōu)路徑和最差路徑的螞蟻，Lbest和Lworst分別為本次迭代的最優(yōu)路徑長度和最差路徑長度．

3 基于改進蟻群算法的多機器人路徑規(guī)劃

3.1 代價函數的設計

為機器人Ri規(guī)劃連接起點到終點的路徑，要求機器人同障礙物、其他機器人之間沒有碰撞，并且所有機器人完成路徑所付出的總代價最小．本文考慮路徑長度、路徑平滑度和暫停時間3個優(yōu)化指標，多機器人的代價函數如式 (12)～式 (15)所示

其中：函數f1x，f2x，f3x分別表示路徑長度、路徑平滑度和暫停時間；li表示機器人Ri規(guī)劃的路徑長度；turni為機器人Ri走過路徑的拐點余弦的平均值，為機器人Ri整條路徑的拐點個數；cos Aij為機器人Ri第j個拐角的余弦值，；Ti表示機器人Ri暫停的時間．為多個機器人規(guī)劃路徑時，要求式 (12)的代價盡可能小，即多個機器人的路徑盡可能短、行走的路徑盡可能平滑以及暫停時間盡可能短．

本文多機器人路徑規(guī)劃的主要思想是，首先，在不考慮其他機器人的情況下，根據上文提到的改進蟻群算法為每個機器人規(guī)劃1條無碰最優(yōu)路徑，然后，在安全距離內發(fā)現其他機器人時，利用通信和協(xié)調策略實現機器人之間的避碰．

3.2 多機器人路徑規(guī)劃的步驟

多機器人路徑規(guī)劃的流程如圖4所示，具體步驟如下：

1）初始化機器人的工作環(huán)境，多個機器人的起點Si，終點Gi，視野域半徑radius，機器人的半徑r，螞蟻個數M，迭代次數k等；

2）不考慮其他機器人，根據改進的蟻群算法為機器人Ri規(guī)劃1條全局無碰最優(yōu)路徑；

3）若Ri移動到目標點，輸出全局無碰最優(yōu)路徑，退出；

4）傳感器在視野域范圍內是否探測到其他機器人Rj，否，轉至7）；

5）碰撞預測，判斷Ri和Rj之間是否會發(fā)生碰撞，否，轉至7）；

6）路徑協(xié)調策略；

7）沿局部無碰路徑移動；

8）返回3）．

圖4 多機器人路徑規(guī)劃流程圖Fig.4 Flow chart of multi robot path planning

3.3 碰撞預測

機器人Ri在視野域范圍內檢測到機器人Rj，如圖5所示，2個機器人進行通信，互相交換路徑信息．如果路徑有交叉點，定義Ri到交叉點的距離為L_Ri，Rj到交叉點的距離為L_Rj，若L_RiL_Rj＞2r，則各機器人按照原路徑運動，否則執(zhí)行局部避碰操作．

圖5 碰撞預測Fig.5 Collision prediction

3.4 路徑協(xié)調

由代價函數式 (12)可知，多機器人路徑規(guī)劃主要考慮路徑長度、路徑平滑度和暫停時間3個指標，本文采用暫停策略進行路徑協(xié)調．

以機器人Ri為例，利用碰撞預測策略，探測到在某一時刻t機器人Ri和Rj發(fā)生碰撞，t 1時刻的協(xié)調避碰策略具體如下：

比較2個機器人的坐標值，x坐標大的機器人暫停一步，如果x坐標相等則比較y坐標，y坐標大的暫停一步．

4 仿真實驗

為了驗證改進蟻群算法的有效性，用Matlab進行了仿真，并將基本蟻群算法、文獻 [9]中改進的蟻群算法和本文改進的蟻群算法進行了比較．設螞蟻數量M=50，迭代次數．

4.2 仿真1

對單個機器人進行仿真，在環(huán)境和參數完全相同的情況下，對基本蟻群算法、文獻 [9]中改進的蟻群算法和本文改進的蟻群算法進行比較，分別運行20次，得出平均結果．機器人的起點為S=1，終點G=400．圖6、圖7和圖8分別各自的收斂曲線．

圖6 基本蟻群算法收斂曲線Fig.6 Convergence curve of basic ant colony algorithm

圖7 文獻 [9]改進蟻群算法收斂曲線Fig.7 Convergence curve of literature[9]improved ant colony algorithm

圖8 本文改進蟻群算法收斂曲線Fig.8 Convergence curve of this paper improved ant colony algorithm

表1為3種算法之間的比較，經過分析可以得出，改進后的蟻群算法路徑更短、更平滑，且收斂速度較快，改進的蟻群算法優(yōu)于基本蟻群算法和文獻 [9]中的改進蟻群算法．

表1 3種算法性能比較Tab.1 Performance comparison of the three algorithms

4.2 仿真2

對3個機器人進行仿真，采用改進的蟻群算法分別為機器人規(guī)劃路徑，機器人Ri的起點柵格序號分別為（1,381,201），終點柵格序號分別為（400,20,115），圖9、圖10分別為文獻 [9]中的改進蟻群算法和本文的改進蟻群算法為3個機器人規(guī)劃出的路徑．其中R1和R3，R2和R3的路徑雖然有交點，但是經過計算不會在同一時刻到達交點，2種方法規(guī)劃的路徑中，R1和R2的交點坐標分別為（7.5,10.5）、（7.833 3,10.833 3），會發(fā)生碰撞，機器人R1在交點的前一節(jié)點暫停一步．

表2是3個機器人在環(huán)境和參數完全相同時，采用本文的改進蟻群算法和文獻 [9]中的算法進行50次仿真實驗的平均數據．可以看出，本文改進蟻群算法規(guī)劃出的路徑更短更平滑．

表2 本文算法和文獻 [9]算法性能比較Tab.2 Performance comparison between algorithm in this paper and literature[9]algorithm

圖9 文獻 [9]算法多機器人規(guī)劃路徑示意圖Fig.9 Multi-robotplanning path diagram of document[9]algorithm

圖10 本文算法多機器人規(guī)劃路徑示意圖Fig.10 Multi-robotplanning path diagram in this paper

5 結論

本文針對蟻群算法的缺點，對算法進行了改進．步長選擇不再局限于1個柵格，從而縮短了路徑的長度；在概率公式中加入拐點參數，改善了路徑的平滑度；信息素更新時加入獎勵懲罰機制，避免陷入局部最優(yōu)．然后將改進的蟻群算法應用到3個機器人的路徑規(guī)劃問題中，成功避免了機器人之間的碰撞，到達最終目的地．仿真結果表明改進的蟻群算法的收斂性、路徑長度和平滑度得到了較好的改善．

[1]朱慶保．全局未知環(huán)境下多機器人運動螞蟻導航算法 [J]．軟件學報，2006，17（9）：1890-1898．

[2]肖國寶，嚴宣輝．一種新型協(xié)作多機器人路徑規(guī)劃算法 [J]．計算機科學，2013，40（4）：217-220．

[3]高翔，蘇青．基于雙層模糊邏輯的多機器人路徑規(guī)劃與避碰 [J]．計算機技術與發(fā)展，2014，24（11）：79-82．

[4]夏小云，周育人．蟻群優(yōu)化算法的理論研究進展 [J]．智能系統(tǒng)學報，2016，11（1）：27-36．

[5]DENG X，ZHANG L，LUO L．An improved ant colony optimization applied in robot path planning problem[J]．Journal of Computers，2013，8 （3）：585-593．

[6]TANG B W，ZHU Z X，FANG Q，et al．Path planning and replanning for intelligent robot based on improved ant colony algorithm[J]．Applied Mechanicsand Materials，2013，390：495-499．

[7]Wenbin C，Qingbao Z，Jun H．Path planning based on biphasic ant colony algorithm and fuzzy control in dynamic environment[C]//Intelligent Human-Machine Systems and Cybernetics（IHMSC），2010 2nd International Conference on．IEEE，2010，1：333-336．

[8]柳長安，鄢小虎，劉春陽，等．基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法 [J]．電子學報，2011，39（5）：1220-1224．

[9]萬曉鳳，胡偉，方武義，等．基于改進蟻群算法的機器人路徑規(guī)劃研究 [J]．計算機工程與應用，2014，50（18）：63-66．

[責任編輯 田 豐]

Research on multi-robots path planning of robot based on improved ant colony algorithm

GU Junhua1,2，MENG Huijie1,2，XIA Hongmei2,3，DONG Yongfeng1,2

(1.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;2.Hebei Province Key Laboratory of Big Data Calculation,Tianjin 300401,China;3.Editorial Department of Journal of Hebei University of Technology, Hebei University of Technology,Tianjin 300401,China)

The basic ant colony algorithm has problems of slow convergence speed,inefficiency and easy to fall into local optimization in the process of robot path planning.Aiming at these problems,an improved ant colony algorithm is proposed. Multi-step path planning is realized by this proposed algorithm.In order to make the path smoother,the inflection point is added in the probability formula.This article proposed anew pheromone reward punishment mechanism.The improved ant colony algorithm is applied to the multi-robot path planning with three optimization goals.Collision prediction strategy and path coordination strategy is applied to solve the problem of coordination and obstacle avoidance between mobile robots.The simulation results show that the path planned by improved ant colony algorithm is shorter,smoother and more efficient,which verifies the effectiveness and feasibility of the proposed algorithm in multi robot path planning.

multi-robot;path planning;improved ant colony algorithm;multi-step;inflection point parameter; coordinated collision avoidance

TP242

A

1007-2373(2016)05-0028-07

10.14081/j.cnki.hgdxb.2016.05.005

2016-10-11

天津市應用基礎與前沿技術研究計劃（13JCQNJC00200，14JCYBJC18500）；河北省高等學?？茖W技術研究項目（ZD20131097）；河北省自然科學基金（F2015202311）

顧軍華（1968-），男（漢族），教授．通訊作者：董永峰（1977-），男（漢族），副教授．