改進蟻群算法在移動機器人軌跡規(guī)劃中的應(yīng)用研究

李雪　金昕　鄭先鵬

摘 要：針對蟻群算法在移動機器人路徑規(guī)劃時會出現(xiàn)收斂速度慢、全局搜索空間大、時間長、效率低、易陷入局部最優(yōu)解和出現(xiàn)死鎖現(xiàn)象等問題，提出了一種改進的蟻群算法.在靜態(tài)已知環(huán)境的條件下利用柵格法建立模型，基于傳統(tǒng)蟻群算法的基礎(chǔ)上，采用精英選擇的方法加快收斂速度、自適應(yīng)改變揮發(fā)系數(shù)來使初始時刻的蟻群搜索能力加強、范圍擴大，避免陷入局部最優(yōu)解;針對U型障礙物，提出了丟棄陷入死鎖中的螞蟻.通過仿真結(jié)果可以得到改進后的蟻群算法能夠快速地搜索到最優(yōu)路徑，與傳統(tǒng)蟻群算法以及改進的蟻群算法相比較，具有良好的路徑尋優(yōu)的能力和避障性能.

關(guān)鍵詞：移動機器人;軌跡規(guī)劃;改進蟻群算法;精英選擇;自適應(yīng);U型障礙

中圖分類號：TP242? 文獻標識碼：A? 文章編號：1673-260X（2019）11-0103-04

1 引言

移動機器人的研究包括導航定位、運動控制、路徑跟蹤與路徑規(guī)劃等技術(shù)，其中路徑規(guī)劃是研究移動機器人的核心內(nèi)容之一.所謂機器人路徑規(guī)劃技術(shù)，就是指通過其他傳感器對環(huán)境采集的信息做出一個反饋，并且找出一條從起點到終點無碰撞運動路徑.國內(nèi)外學者將移動機器人的路徑規(guī)劃方法規(guī)劃為以下幾種類型，其中包括模塊匹配路徑規(guī)劃、人工勢場法、地圖構(gòu)建路徑規(guī)劃和人工智能路徑規(guī)劃等路徑規(guī)劃技術(shù)[1].地圖構(gòu)建路徑規(guī)劃中的柵格法在移動機器人全局路徑規(guī)劃中應(yīng)用較為廣泛，但是也存在著缺陷：儲存空間小以至于降低了搜索效率等問題.隨著遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、粒子群算法、免疫算法、PID模糊控制算法、蟻群算法等智能算法的提出[2-4]，許多學者利用人工智能算法來路徑規(guī)劃，其中蟻群算法被廣泛應(yīng)用于路徑規(guī)劃.蟻群算法是一種啟發(fā)式搜索算法，具有較強的魯棒性等特點[5].同時蟻群算法也具有許多缺陷：收斂速度慢、易陷入局部最優(yōu)解等問題.所以許多學者對蟻群算法進行了大量改進，其中有信息素更新方式的改進、路徑選擇策略方面的改進、與其他算法相結(jié)合的改進、多重蟻群算法的改進[6].比如文獻[7]中就提出了廣義信息素更新規(guī)則來解決螞蟻面對凹型障礙物會出現(xiàn)的死鎖現(xiàn)象來尋找最優(yōu)解，文獻[8]中就提出了使用不同的期望值，采用自適應(yīng)揮發(fā)系數(shù)來更新信息激素來找到最優(yōu)解，文獻[9]中就提出了通過動態(tài)調(diào)整自適應(yīng)蟻群算法的參數(shù)進而實現(xiàn)對信息素更新來找到最優(yōu)解，文獻[10]中就提出了對較優(yōu)螞蟻的路徑進行信息素更新，在面對U型障礙物時，提出了螞蟻回退策略，使算法的收斂速度加快，尋優(yōu)與避障能力加強.

針對以上提出的問題以及相關(guān)學者對這些問題所提出的解決辦法可以看出利用改進的蟻群算法來解決路徑規(guī)劃中收斂速度以及局部最優(yōu)解等問題還需要進一步的改進算法.本文中使用的改進算法主要是依據(jù)信息素更新方式的改進，首先自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ，因為當揮發(fā)系數(shù)ρ設(shè)置過大時，就會加大對之前搜索過的路徑的搜索，當揮發(fā)系數(shù)ρ設(shè)置過小時，即使會提高算法的全局搜素能力，但是算法的收斂速度會大幅降低，所以最終采取自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ來動態(tài)調(diào)整算法的整體性能，提高其魯棒性.最后是通過動態(tài)改變信息素τij（t），利用精英選擇在每次循環(huán)結(jié)束后對發(fā)現(xiàn)的最優(yōu)解給予額外的信息素增量，用來在下一次的循環(huán)中對螞蟻更具有吸引力，提高算法的收斂速度.以上改進的蟻群算法對不同時刻的信息素都有著全局掌控能力，為提高收斂速度和避免局部最優(yōu)解提供了保證.最后利用改進的蟻群算法來進行路徑規(guī)劃，并且完成了仿真實驗，相比較其他的改進蟻群算法的實驗結(jié)果可以證明本文的改進蟻群算法的可行性和優(yōu)越性.

2 環(huán)境建模及U型障礙物問題分析

2.1 環(huán)境建模

移動機器人工作環(huán)境建模主要分為以下幾種：特征地圖、柵格地圖等.其中柵格法普遍應(yīng)用于機器人環(huán)境建模，由于柵格法具有易于實現(xiàn)，分析等優(yōu)點，所以本文將采用柵格法對移動機器人進行環(huán)境建模.

首先定義一個有限二維平面作為機器人的移動區(qū)域，不妨設(shè)該區(qū)域為G，在該區(qū)域內(nèi)存在大小與位置不變的障礙物，其中白色柵格為機器人可移動區(qū)域，將白色柵格記為0，黑色柵格為固定的障礙物，將黑色柵格記為1.該區(qū)域按照從左到右，從上到下的順序來依次對柵格進行標記，記為1，2，3，4，…，n，其中每一個數(shù)字代表一個柵格;坐標原點定在柵格空間的左下方，從左到右定義為X軸正方向，從下到上定義為Y軸正方向.柵格的長度定義為單位長度，由此建立二維坐標平面XOY.以下是柵格序號和坐標的對應(yīng)關(guān)系：

x=mod（L，N）-0.5ifx=-0.5，x=19.5y=N+0.5-ceil（L，N）? （1）

式（1）中：mod為求余運算;L為柵格的序列號;N為柵格的行列數(shù).

為了避免機器人與障礙物發(fā)生碰撞，對障礙物的邊界進行膨化處理，于是機器人可以等效于一個質(zhì)點.

2.2 U型障礙物問題分析

蟻群算法在進行移動機器人路徑規(guī)劃時，當遇到復雜的環(huán)境有可能會陷入局部最優(yōu)解.在算法運行過程中，為了避免螞蟻重復訪問同一個節(jié)點，因此引入了禁忌表，已訪問的節(jié)點存儲在儲存器中，作為螞蟻在下一次選擇過程中的不需要訪問的節(jié)點.這樣就導致螞蟻在遇到U型障礙物時會陷入死鎖現(xiàn)象，圖2所示為U型障礙物1，從中可以清楚地看到螞蟻可以有以下路線：1→2→3、1→4→3、1→2→4→3，螞蟻在遇到U型障礙物1時可以順利通過，并且不會出現(xiàn)死鎖現(xiàn)象.雖然不會出現(xiàn)死鎖現(xiàn)象，但是會影響螞蟻在尋優(yōu)路徑所需要的時間.圖3所示為U型障礙物2，從中可以清楚地看到螞蟻可以有以下路線：1→2→3、1→4→3、1→2→4→3、1→2→4→5→6、1→4→5→6，螞蟻在路線1→2→4→5→6、1→4→5→6時就會出現(xiàn)死鎖現(xiàn)象，導致蟻群整體能量的損耗降低了收斂速度.

針對U型障礙物，有以下幾種處理辦法.

（1）將U型障礙進行凸型處理，以犧牲環(huán)境為代價，在實際環(huán)境中采取這種方法較為困難，因此不采用此方法.

（2）若螞蟻陷入死鎖，則將螞蟻視為死亡螞蟻，因此不再進行路徑搜索，并且清除死亡螞蟻在路徑上產(chǎn)生的信息素，停止更新.

（3）回退策略，當螞蟻無路徑搜索時，此時釋放禁忌表，目的是回退一步.如圖3所示，當螞蟻陷入死鎖狀態(tài)到達節(jié)點6，無路可走時，則通過釋放禁忌表選擇節(jié)點5，將節(jié)點6加入禁忌表，同時清除路徑節(jié)點5、節(jié)點6點的信息素，以此為循環(huán)直至“逃離”陷阱.

（4）更新信息素，當遇到U型障礙物并陷入死鎖狀態(tài)時，將該路徑的信息素清零，當遇到U型障礙物1時采取信息素漸滅方式[3].

本文采用（2）方式進行凹型障礙物避障，當遇到U型障礙物1和U型障礙物2時，采取丟棄陷入死鎖的螞蟻.遇到U型障礙物時采取本文改進的蟻群算法可以有效地提高蟻群搜索效率以及尋優(yōu)路徑.

3 改進蟻群算法設(shè)計

3.1 蟻群算法改進

傳統(tǒng)蟻群算法具有魯棒性強，易與其他算法相結(jié)合等優(yōu)點，缺點是收斂速度慢，易陷于局部最優(yōu)解，出現(xiàn)搜索停滯等.為了提高算法的有效性與實用性，本文主要針對螞蟻在避障時找到最優(yōu)路徑以及在陷入U型障礙時遇到的問題所做出的處理方法.首先采用自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ，最后是通過動態(tài)改變信息素τij（t），利用精英選擇在每次循環(huán)結(jié)束后對發(fā)現(xiàn)的最優(yōu)解給予額外的信息素增量，用來在下一次的循環(huán)中對螞蟻更具有吸引力，有效地提高了算法的收斂速度和全局搜索能力.

3.1.1 自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ

蟻群算法在運行過程中會受到許多因素的影響，本文所提到的動態(tài)調(diào)整參數(shù)ρ來解決算法在運行過程中收斂速度慢、易陷入局部最優(yōu)解等問題.當揮發(fā)系數(shù)ρ設(shè)置比較大時，之前螞蟻走過的路徑被再次選擇的機會就會加大，過小時會提高全局搜索能力導致收斂速度降低.于是初始時刻將參數(shù)ρ設(shè)置為最大值，雖然以前搜索路徑被再次選擇可能性加大，但是信息正反饋占主導作用.

本文對參數(shù)ρmin設(shè)置為0.1，ρ的自適應(yīng)調(diào)整公式如下：

3.1.2 精英選擇較優(yōu)路徑信息素更新

當全部螞蟻都完成一次路徑搜索以后，按每個螞蟻行走路徑的長短進行排序（L1≤L2≤L3≤…≤Lm），每只螞蟻對信息素更新的貢獻根據(jù)該螞蟻的排序進行加權(quán)，加權(quán)值記為φ.更新公式（3）（4）和（5）如下：

在每輪路徑搜索結(jié)束后對較優(yōu)螞蟻的路徑上的信息素進行更新，隨著參數(shù)ρ的逐漸降低，這將增大路徑上信息素的差異，增加了全局搜索能力，但此時算法的收斂速度降低.由于螞蟻在尋優(yōu)路徑的時候會傾向于信息素濃度大的路徑，所以通過精英選擇對較優(yōu)螞蟻路徑的信息素濃度的額外加權(quán)，增加了該路徑的信息素濃度也有助于縮短算法的求解時間，提高算法的運行效率.

3.2 改進蟻群算法流程

改進后蟻群算法流程如圖4所示.

4 實驗結(jié)果與分析

為了驗證本文改進的蟻群算法的可行性，將本文算法應(yīng)用在移動機器人路徑規(guī)劃中，同時和傳統(tǒng)的蟻群算法和其他學者改進的蟻群算法做一個比較來證明本文改進的蟻群算法的優(yōu)越性.實驗環(huán)境是在windows7操作平臺上運行MATLAB2016a軟件將這三種算法進行比較.設(shè)置螞蟻總數(shù)為M=100，初始ρ=0.8，C=0.8，參數(shù)α=1，β=5，信息素總量Q=1，最大迭代次數(shù)Nmax=100.圖5和圖6是本文改進的蟻群算法仿真實驗結(jié)果.表1是本文改進的蟻群算法與文獻[9]的比較.，通過表1對比可以發(fā)現(xiàn)，文獻[9]中的改進的算法經(jīng)過22次迭代達到穩(wěn)定，而本文中的實驗結(jié)果只需要經(jīng)過16次迭代就達到穩(wěn)定狀態(tài)，收斂速度得到了顯著的提高.

為了進一步驗證本文所提出的改進的蟻群算法的可行性，對20*20的環(huán)境模型進行研究，圖7、圖8是本文改進的蟻群算法的實驗結(jié)果，表2是與文獻[10]的對比結(jié)果.通過表2可以看出本文的實驗結(jié)果明顯優(yōu)于文獻[10]的實驗結(jié)果.雖然文獻[10]與本文在最優(yōu)路徑長度上一樣，但是本文在相同環(huán)境下，收斂速度更快，耗時不到文獻[10]所用的的二分之一.對比結(jié)果進一步證明本文提出的改進的蟻群算法的有效性和優(yōu)越性.

通過上述仿真實驗的對比分析，傳統(tǒng)蟻群算法具有收斂速度慢，易陷入局部最優(yōu)解等問題，本文提出的改進蟻群算法有效地解決了這些不足.在改進算法運行初始階段通過動態(tài)調(diào)整參數(shù)ρ來實現(xiàn)數(shù)據(jù)的更新，后期通過對信息素τij（t）的更新，能夠提高算法的尋優(yōu)能力，加快算法的收斂速度，快速找到最優(yōu)路徑.并且在遇到U型障礙物時，能夠快速避開且繼續(xù)尋找最優(yōu)路徑.

5 結(jié)論

本文針對移動機器人在路徑規(guī)劃中存在的收斂速度慢，易陷入局部最優(yōu)解等問題，提出了一種全新的改進蟻群算法，首先自適應(yīng)更新?lián)]發(fā)系數(shù)ρ，使算法前期對搜索到的較優(yōu)路徑加大了搜索力度，后期則提高了算法的全局搜索能力，但是算法的收斂速度會明顯降低.最后是通過動態(tài)改變信息素τij（t），利用精英選擇在每次循環(huán)結(jié)束后對發(fā)現(xiàn)的最優(yōu)解給予額外的信息素增量，用來在下一次的循環(huán)中對螞蟻更具有吸引力，提高算法的收斂速度.在處理U型障礙物時，提出了丟棄死鎖螞蟻.通過以上大量仿真實驗證明，改進后的蟻群算法在尋優(yōu)能力上得到了顯著的提高，有效地避免了出現(xiàn)死鎖的現(xiàn)象，在與其他算法的比較中可以發(fā)現(xiàn)本算法在移動機器人路徑規(guī)劃中具有優(yōu)越性和有效性.

參考文獻：

〔1〕朱大奇，顏明重.移動機器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010（7）：4-10.

〔2〕Azimirad V， Shorakaei H. Dual hierarchical genetic-optimal control： A new global optimal path planning method for robots [J]. Journal of Manufacturing Systems， 2014， 33（1）：139-148.

〔3〕張廣林，胡小梅，柴劍飛，趙磊，俞濤.路徑規(guī)劃算法及其應(yīng)用綜述[J].現(xiàn)代機械，2011（5）：85-90.

〔4〕王雷，李明，唐敦兵，等.基于改進遺傳算法的機器人動態(tài)路徑規(guī)劃[J].南京航空航天大學學報，2016，48（6）：841-846.

〔5〕吳慶洪，張穎，馬宗民.蟻群算法綜述[J].微計算機信息，2011，29（3）：1-2.

〔6〕黃摯雄，張登科，黎群輝.蟻群算法及其改進形式綜述[J].2006，25（3）：35-38.

〔7〕裴振兵，陳學波.改進蟻群算法及其在機器人在避障中應(yīng)用[J].智能系統(tǒng)學報，2015，10（1）：90-96.

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

〔9〕屈正庚，楊川.基于改進蟻群算法的移動機器人全局軌跡規(guī)劃研究[J].南京師大學報：自然科學版，2015，38（1）：81-85.

〔10〕侯欣磊，于蓮芝.基于改進蟻群算法的移動機器人路徑規(guī)劃[J].軟件導刊，2017，16（12）：162-164.