顏杰 秦飛舟 翟帥華

摘 要：路徑規(guī)劃是移動機器人運動控制中的關(guān)鍵問題。針對傳統(tǒng)蟻群算法在機器人全局路徑規(guī)劃中存在收斂速度慢、易陷入局部最優(yōu)等缺點，提出一種改進型蟻群路徑規(guī)劃算法。首先，通過柵格法建立機器人運動環(huán)境模型，然后在傳統(tǒng)蟻群算法基礎(chǔ)上引入A*搜索算法的估價函數(shù)思想，改進蟻群算法的啟發(fā)函數(shù)，增加目標節(jié)點與可選行進節(jié)點數(shù)對啟發(fā)函數(shù)的影響。其次，在信息素更新公式中，通過引入Logistic增長函數(shù)對信息素揮發(fā)因子作自適應(yīng)調(diào)整，提高算法速度與精度。最后，通過Matlab仿真實驗證明，改進蟻群算法比傳統(tǒng)算法在路徑搜索速度和精度上都有較大提升。

關(guān)鍵詞：移動機器人;路徑規(guī)劃;改進蟻群算法

DOI：10. 11907/rjdk. 182031

中圖分類號：TP301文獻標識碼：A文章編號：1672-7800（2019）002-0005-04

Abstract： Path planning is a key problem in motion control of mobile robot. An improved ant colony path planning algorithm is proposed to solve the problems of slow convergence rate and getting stuck in the local optimum easily. First robot movement environment model is established by the grid method， and then on the basis of traditional ant colony algorithm， the evaluation function of A* search algorithm is produced to improve ant colony algorithm function， increase the target node and optional node number's influence on the heuristic function. Secondly， in the update formula of pheromones， the speed and accuracy of the algorithm are improved by introducing logistic growth function to adjust the volatility factor of pheromones. Finally， through the Matlab simulation experiment， it is verified that the improved ant colony algorithm has greatly improved the speed and precision of the path search compared with the traditional algorithm.

Key Words： mobile robot; path planning; improved ant colony algorithm

0 引言

智能機器人是當下研究的熱門，其中路徑規(guī)劃是智能機器人研究領(lǐng)域的核心內(nèi)容之一。機器人路徑規(guī)劃是指在有障礙物的環(huán)境下，按照一定評價標準，找出一條從起點到終點的最優(yōu)無碰路徑[1-3]。機器人路徑規(guī)劃方法可以分為全部環(huán)境信息已知的全局路徑規(guī)劃和信息未知的局部路徑規(guī)劃[4-5]。常見的局部路徑規(guī)劃方法有模糊控制法[6-8]、人工勢場法[9-10]等。常見的全局路徑規(guī)劃方法有蟻群算法[11-13]、拓撲圖法[14]、可視圖法[15]等。其中，蟻群算法是由學者Marco Dorigo[16]在20世紀90年代首次提出的，因其具有良好的魯棒性且易與其它算法相結(jié)合，被廣泛用于機器人全局路徑規(guī)劃中。針對傳統(tǒng)蟻群算法存在收斂速度慢、易陷入局部最優(yōu)等問題，國內(nèi)外學者通過引入方向角參數(shù)[17]、制定螞蟻回退策略[18]、更改信息素更新策略[19-20]等方法對蟻群算法進行改進并取得了不錯效果。本文在已有蟻群算法基礎(chǔ)上，利用A*算法的估價函數(shù)思想改進蟻群算法的啟發(fā)函數(shù)，同時引入Logistic函數(shù)自適應(yīng)調(diào)整信息素揮發(fā)因子，進一步提高蟻群算法在全局路徑規(guī)劃中的搜索速度和精度。

1 環(huán)境建模

基于蟻群算法的機器人路徑規(guī)劃是一種在已知環(huán)境信息下的路徑規(guī)劃方法。因此，首先需要對環(huán)境進行建模處理，將環(huán)境信息轉(zhuǎn)化為機器人可識別的數(shù)學模型。本文采用柵格法[21]建立機器人工作的二維環(huán)境模型，直接在機器人工作環(huán)境中建立二維直角坐標系，以大小固定的柵格對環(huán)境進行割分。每個柵格按序號法表示，取每個柵格中心點坐標為柵格坐標，并將其作為機器人行進點，柵格序號與坐標之間可以相互轉(zhuǎn)化。劃分后的柵格分為障礙柵格和可行柵格，考慮到機器人自身尺寸影響，把障礙物的邊界按機器人本體在長或?qū)挿较蛏献畲蟪叨鹊腫12]長度進行擴展，則可將機器人看作質(zhì)點忽略不計，柵格法建立的環(huán)境模型如圖1所示。圖中黑色柵格為障礙柵格，白色柵格為可行柵格，除邊界柵格外，每個柵格與8個柵格相連，除去障礙柵格，其它相連柵格為該柵格的可選行進柵格節(jié)點。

2 傳統(tǒng)蟻群算法路徑規(guī)劃

蟻群算法是一種通過隨機搜索空間尋找目標最優(yōu)解的算法，主要利用蟻群之間的信息傳遞，通過正反饋尋求問題的最優(yōu)解。蟻群算法是一種新型的啟發(fā)式智能優(yōu)化算法，蟻群在尋找食物過程中，各螞蟻可以通過遺留在當前節(jié)點路徑上的信息素濃度以及啟發(fā)信息確定當前節(jié)點到下一節(jié)點的路徑轉(zhuǎn)移概率，再根據(jù)路徑轉(zhuǎn)移概率選擇行走路徑。路徑轉(zhuǎn)移概率的數(shù)學模型可以用式（1）描述。

式（1）中，[pkij（t）]為t時刻螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的轉(zhuǎn)移概率;[Sk]為螞蟻k在當前節(jié)點行進到下一個可選節(jié)點的集合，其中不包括螞蟻k已經(jīng)行進過的節(jié)點與障礙節(jié)點;[τij（t）]表示t時刻節(jié)點i到節(jié)點j之間路徑的信息素濃度，初始時刻各路徑的信息素濃度相同，即[τij（0）]=C，C為某一常數(shù);[ηij（t）]為表示節(jié)點i到節(jié)點j的啟發(fā)函數(shù)，也叫能見度，其表達式為[ηij（t）=1/dij]，其中[dij]為節(jié)點i到節(jié)點j的歐式距離;[α]為信息素濃度啟發(fā)因子，代表信息素濃度的相對重要程度，該因子越大，螞蟻越傾向于選擇其它螞蟻走過的路程;[β]為能見度啟發(fā)因子，表示能見度相對重要程度。

按照上述規(guī)則，螞蟻可以確定當前節(jié)點到每個可選節(jié)點的路徑轉(zhuǎn)移概率，再根據(jù)轉(zhuǎn)輪賭法確定下一個行進節(jié)點。當所有螞蟻從起點到達終點完成一輪路徑搜索后，需要計算每只螞蟻所經(jīng)過的路徑長度，并保存最小路徑長度，然后更新每條路徑的信息素濃度，信息素濃度的更新規(guī)則為揮發(fā)一部分、增加一部分，如式（2）、式（3）所示。

其中，[τij（t+1）]為更新后的節(jié)點i到節(jié)點j路徑上的信息素濃度;[τij（t）]為該路徑上當前信息素濃度;[ρ]為信息素揮發(fā)因子，其取值為[0，1]，其值越大信息素濃度揮發(fā)得越快;[Δτij（t）]為搜索過程中經(jīng)過該路徑的所有螞蟻留下的信息素濃度之和。

每只經(jīng)過該路徑的螞蟻遺留的信息濃度計算公式為式（4），其中LK為螞蟻k完成路徑搜索后行走的總路徑長度，Q為螞蟻攜帶的信息素濃度因子。從式（4）中可以看到，螞蟻走的總路徑越短，遺留在路徑上的信息素濃度越高。蟻群正是通過以上路徑選擇規(guī)則和信息素更新規(guī)則，使得較優(yōu)路徑上的信息素越來越多，而較差路徑上的信息素越來越少，從而尋找出一條最優(yōu)行進路徑。

3 改進蟻群算法路徑規(guī)劃

3.1 啟發(fā)函數(shù)改進

在傳統(tǒng)蟻群算法中，啟發(fā)函數(shù)[ηij（t）]僅僅考慮了當前節(jié)點到下一節(jié)點的距離大小，這樣會使得算法初期搜索具有很大的盲目性，降低算法的搜索精度與速度。因此，在傳統(tǒng)蟻群算法基礎(chǔ)上，引入A*算法的估價函數(shù)思想，增加算法搜索的指向性，提高算法的搜索速度與精度。估價函數(shù)的表達式如式（5）。

其中，[f（n）]為當前節(jié)點的估價函數(shù);[g（n）]為當前節(jié)點到可選節(jié)點的實際代價，取值為當前節(jié)點i到可選節(jié)點j之間的歐式距離[dij]，即[g（n）=dij];[h（n）]為下一可選節(jié)點j到目標節(jié)點g之間的最小路徑估計代價。[h（n）]的值主要考慮兩點因素：下一可選節(jié)點j到目標節(jié)點g的歐式距離[djg];下一節(jié)點j的可選行走節(jié)點數(shù)Nj。表達式如式（6）。

其中，Nj為下一節(jié)點j的可選行走節(jié)點數(shù)，其值越大，表明該節(jié)點的路徑選擇越多，算法的搜索多樣性越高，因此相應(yīng)的估計代價值越小;[djg]為下一可選節(jié)點j到目標節(jié)點g的歐式距離，其值越小，表明下一節(jié)點到目標節(jié)點的朝向性越好，估計代價值也越小。但考慮到實際環(huán)境中由于障礙物的存在，當可選節(jié)點離目標節(jié)點較遠時，實際路徑長度遠大于估計值，此時估計路徑長度應(yīng)適當擴大，當距離較近時，實際值接近甚至等于估計值。因此對其進行加權(quán)處理，引入加權(quán)系數(shù)[μdjg（μ>1）]，當[djg]較大時，加權(quán)系數(shù)大，估計路徑值也更大。加權(quán)系數(shù)會隨著[djg]的減小而減小，直至減到1，估計值等于實際值。最終得到新啟發(fā)函數(shù)[ηij（t）]式（7）。

3.2 揮發(fā)因子自適應(yīng)調(diào)整

在蟻群算法搜索最優(yōu)解過程中，信息素濃度的更新規(guī)則起極其重要作用，信息素濃度更新公式中的揮發(fā)因子直接影響蟻群算法的性能。當信息素揮發(fā)因子的值過小時，各條路徑的信息素濃度差別較小，使得蟻群對每只螞蟻的引導性降低，從而降低算法搜索速度。當信息素揮發(fā)因子過大時，使得蟻群對螞蟻的引導作用過強，導致螞蟻搜索更多路徑的可能性變小，更易陷入局部最優(yōu)解。因此，引入Logistic增長函數(shù)對揮發(fā)因子進行自適應(yīng)調(diào)整。Logistic增長函數(shù)是一種常見的S形函數(shù)，如圖2所示。

由圖2可以看到，Logistic增長函數(shù)最初因變量Y從某一最小值開始隨著X增加而緩慢增長;當X值到達一定量后，Y值隨X值的增加速度陡然加快;當X繼續(xù)增加到一定量時，Y值隨X值的增加速度開始急速變慢，且Y值隨X值的增加不斷趨近于某一極限值。Logistic函數(shù)表達式為：

式（8）中，參數(shù)Theta1為y值的上邊界，Theta2為y值的下邊界，Theta3為增長線中心點的x值，Theta4的值可以控制增長線的增長速度。本文將該函數(shù)用于揮發(fā)系數(shù)自適應(yīng)調(diào)整，將迭代次數(shù)t作為自變量，揮發(fā)因子[ρ]作為因變量。在算法前期，使揮發(fā)因子較小，減小蟻群的引導作用，增加螞蟻的搜索解范圍，提高算法精度。隨著算法進行，揮發(fā)因子快速增加，增大蟻群引導作用，提高蟻群搜索速度，使算法快速收斂。同時針對不同環(huán)境，可以通過設(shè)定Theta1、Theta2、Theta3、Theta4的值，確定揮發(fā)因子最大值、最小值以及揮發(fā)因子的增長速度。改進后算法表達式為：

4 算法仿真測試

為了驗證改進蟻群算法在機器人路徑規(guī)劃中的有效性與優(yōu)越性，通過Matlab 2014a軟件對算法進行仿真測試。首先搭建兩個機器人運動環(huán)境柵格模型：較復雜環(huán)境模型與簡單環(huán)境模型。復雜環(huán)境模型下設(shè)置初始蟻群螞蟻數(shù)量60，最大迭代次數(shù)200次;簡單環(huán)境模型下設(shè)置初始蟻群螞蟻數(shù)量50，最大迭代次數(shù)150。在簡單環(huán)境下，改進蟻群算法與傳統(tǒng)算法規(guī)劃路徑及收斂速度如圖3、圖4、圖5所示。

從圖3可以看到，在較簡單環(huán)境下，兩種算法都能夠有效規(guī)劃最優(yōu)行駛路徑，但對比兩種算法的收斂速度，可以看出傳統(tǒng)算法經(jīng)歷53次迭代才最終收斂，而改進算法迭代40次后就進入收斂狀態(tài)，改進算法的搜索速度有明顯提升。

復雜環(huán)境下的路徑規(guī)劃仿真結(jié)果如圖6、圖7、圖8所示。通過對比圖6、圖7可以看出，在較復雜環(huán)境下，改進算法規(guī)劃的路徑更短，轉(zhuǎn)折點更少，路徑規(guī)劃效果更好。圖8為兩種算法的最優(yōu)路徑長度與收斂速度對比，其中上方曲線為傳統(tǒng)算法的收斂曲線，下方曲線為改進算法的收斂曲線。傳統(tǒng)算法經(jīng)過105次迭代后達到最小路徑，最小路徑長度為38，而改進算法僅經(jīng)過76次迭代收斂到最小路徑，且最小路徑長度為35。改進后的算法在搜索精度和速度上都有了很大提升。

5 結(jié)語

本文針對傳統(tǒng)蟻群路徑規(guī)劃算法在搜索速度和精度上的不足，對蟻群算法進行了改進。通過在啟發(fā)函數(shù)中引入估價函數(shù)，加入目標節(jié)點和可選行進節(jié)點數(shù)對路徑選擇概率的影響，降低了算法前期搜索的盲目性。同時，通過引入Logistic函數(shù)自適應(yīng)調(diào)整信息素揮發(fā)因子，既保證了算法前期能夠大范圍搜索，又使得算法后期能夠快速收斂，提高了算法搜索的速度和精度。仿真實驗結(jié)果表明，改進算法相比傳統(tǒng)算法在搜索次數(shù)、最優(yōu)路徑長度上都有所改進，具有更好的路徑規(guī)劃效果。

參考文獻：

[1] 任玉潔，付麗霞，張勇，等. 基于平滑A*人工勢場法的機器人動態(tài)路徑規(guī)劃[J]. 軟件導刊，2018，17（1）：8-10.

[2] 高涵，高柏軍. 移動機器人路徑規(guī)劃方法研究[J]. 現(xiàn)代儀器與醫(yī)療，2015，21（5）：14-17.

[3] 王殿君. 基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃[J]. 清華大學學報：自然科學版，2012，52（8）：1085-1089.

[4] FAKOOR M，KOSARI A，JAFARZADEH M. Humanoid robot path planning with fuzzy Markov decision processes[J]. Journal of Applied Research & Technology，2016，14（5）：300-310.

[5] 周文卷. 復雜環(huán)境下自主移動機器人路徑規(guī)劃方法的研究[D]. 長春：吉林大學，2014.

[6] MEHD I，F(xiàn)ATEH M，F(xiàn)ATEH S. A precise robust fuzzy control of robots using voltage control strategy[J]. International Journal of Automation and Computing，2013，10（1）：64-72.

[7] 施磊磊，施化吉，束長波，等. 改進的模糊控制算法在機器人路徑規(guī)劃中的應(yīng)用[J]. 軟件導刊，2014，13（11）：46-48.

[8] 彭玉青，李木，張媛媛. 基于改進模糊算法的移動機器人避障[J]. 計算機應(yīng)用，2015，35（8）：2256-2260.

[9] 李奕銘. 基于人工勢場法的移動機器人避障研究[D]. 合肥：合肥工業(yè)大學，2013.

[10] 張殿富，劉福. 基于人工勢場法的路徑規(guī)劃方法研究及展望[J]. 計算機工程與科學，2013，35（6）：88-95.

[11] 史恩秀，陳敏敏，李俊，等. 基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J]. 農(nóng)業(yè)機械學報，2014，45（6）：53-57.

[12] ZHANG K，YUAN C M，GAO X S. A greedy algorithm for feedrate planning of CNC machines along curved tool paths with confined jerk[J].? Robotics and Computer Integrated Manufacturing，2012，28（4）：472-483.

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

[14] 李明磊，趙杰，李戈. 面向方形節(jié)點拓撲地圖下的移動機器人路徑規(guī)劃算法研究[J]. 機械與電子，2015（10）：67-70.

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

[16] 李士勇，陳勇強，李研. 蟻群算法及其應(yīng)用[M]. 哈爾濱：哈爾濱出版社，2004.

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

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

[19] MOHAMMAD S M，SAEED D A，F(xiàn)ARSHID E，et al.An ant colony algorithm （ACA） for solving the new integrated model of job shop scheduling and conflictfree routing of AGVs[J]. Computers and Industrial Engineering，2015，86（C）： 2-13.

[20] 王沛棟. 改進蟻群算法及在路徑規(guī)劃問題的應(yīng)用研究[D]. 青島：中國海洋大學，2012.

[21] 梁嘉俊，曾碧，何元烈. 基于改進勢場柵格法的清潔機器人路徑規(guī)劃算法研究[J]. 廣東工業(yè)大學學報，2016，33（4）：30-36.

（責任編輯：何 麗）