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

（1.河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；2.河北工業(yè)大學(xué) 河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401；3.河北工業(yè)大學(xué) 河北工業(yè)大學(xué)學(xué)報(bào)編輯部，天津 300401）

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

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

（1.河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；2.河北工業(yè)大學(xué) 河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401；3.河北工業(yè)大學(xué) 河北工業(yè)大學(xué)學(xué)報(bào)編輯部，天津 300401）

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

多機(jī)器人；路徑規(guī)劃；改進(jìn)蟻群算法；多步長；拐點(diǎn)參數(shù)；協(xié)調(diào)避碰

0 引言

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

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

1 環(huán)境描述

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

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

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

設(shè)序號(hào)為i的柵格對應(yīng)的坐標(biāo)為(xi，yi)，則序號(hào)編碼與坐標(biāo)對應(yīng)關(guān)系如式 (1)所示．其中當(dāng)mod(i,20) ==0，即i為20的整數(shù)倍時(shí)，將xi設(shè)為19.5．

2 蟻群算法

2.1 基本蟻群算法

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

2.1.1 轉(zhuǎn)移概率

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

2.1.2 信息素更新

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

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

2.2 改進(jìn)的蟻群算法

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

2.2.1 多步長

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

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

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

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

2.2.2 概率公式

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

2.2.3 信息素更新

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

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

3.1 代價(jià)函數(shù)的設(shè)計(jì)

為機(jī)器人Ri規(guī)劃連接起點(diǎn)到終點(diǎn)的路徑，要求機(jī)器人同障礙物、其他機(jī)器人之間沒有碰撞，并且所有機(jī)器人完成路徑所付出的總代價(jià)最?。疚目紤]路徑長度、路徑平滑度和暫停時(shí)間3個(gè)優(yōu)化指標(biāo)，多機(jī)器人的代價(jià)函數(shù)如式 (12)～式 (15)所示

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

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

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

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

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

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

3）若Ri移動(dòng)到目標(biāo)點(diǎn)，輸出全局無碰最優(yōu)路徑，退出；

4）傳感器在視野域范圍內(nèi)是否探測到其他機(jī)器人Rj，否，轉(zhuǎn)至7）；

5）碰撞預(yù)測，判斷Ri和Rj之間是否會(huì)發(fā)生碰撞，否，轉(zhuǎn)至7）；

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

7）沿局部無碰路徑移動(dòng)；

8）返回3）．

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

3.3 碰撞預(yù)測

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

圖5 碰撞預(yù)測Fig.5 Collision prediction

3.4 路徑協(xié)調(diào)

由代價(jià)函數(shù)式 (12)可知，多機(jī)器人路徑規(guī)劃主要考慮路徑長度、路徑平滑度和暫停時(shí)間3個(gè)指標(biāo)，本文采用暫停策略進(jìn)行路徑協(xié)調(diào)．

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

比較2個(gè)機(jī)器人的坐標(biāo)值，x坐標(biāo)大的機(jī)器人暫停一步，如果x坐標(biāo)相等則比較y坐標(biāo)，y坐標(biāo)大的暫停一步．

4 仿真實(shí)驗(yàn)

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

4.2 仿真1

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

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

圖7 文獻(xiàn) [9]改進(jìn)蟻群算法收斂曲線Fig.7 Convergence curve of literature[9]improved ant colony algorithm

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

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

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

4.2 仿真2

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

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

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

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

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

5 結(jié)論

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

[1]朱慶保．全局未知環(huán)境下多機(jī)器人運(yùn)動(dòng)螞蟻導(dǎo)航算法 [J]．軟件學(xué)報(bào)，2006，17（9）：1890-1898．

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

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

[4]夏小云，周育人．蟻群優(yōu)化算法的理論研究進(jìn)展 [J]．智能系統(tǒng)學(xué)報(bào)，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，F(xiàn)ANG 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]柳長安，鄢小虎，劉春陽，等．基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法 [J]．電子學(xué)報(bào)，2011，39（5）：1220-1224．

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

[責(zé)任編輯 田 豐]

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

天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計(jì)劃（13JCQNJC00200，14JCYBJC18500）；河北省高等學(xué)?？茖W(xué)技術(shù)研究項(xiàng)目（ZD20131097）；河北省自然科學(xué)基金（F2015202311）

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