顏杰 秦飛舟 翟帥華

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

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

DOI：10. 11907/rjdk. 182031

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：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 引言

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

1 環(huán)境建模

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

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

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

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

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

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

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

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

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

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

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

其中，Nj為下一節(jié)點j的可選行走節(jié)點數(shù)，其值越大，表明該節(jié)點的路徑選擇越多，算法的搜索多樣性越高，因此相應(yīng)的估計代價值越小;[djg]為下一可選節(jié)點j到目標(biāo)節(jié)點g的歐式距離，其值越小，表明下一節(jié)點到目標(biāo)節(jié)點的朝向性越好，估計代價值也越小。但考慮到實際環(huán)境中由于障礙物的存在，當(dāng)可選節(jié)點離目標(biāo)節(jié)點較遠(yuǎn)時，實際路徑長度遠(yuǎn)大于估計值，此時估計路徑長度應(yīng)適當(dāng)擴(kuò)大，當(dāng)距離較近時，實際值接近甚至等于估計值。因此對其進(jìn)行加權(quán)處理，引入加權(quán)系數(shù)[μdjg（μ>1）]，當(dāng)[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ā)因子直接影響蟻群算法的性能。當(dāng)信息素?fù)]發(fā)因子的值過小時，各條路徑的信息素濃度差別較小，使得蟻群對每只螞蟻的引導(dǎo)性降低，從而降低算法搜索速度。當(dāng)信息素?fù)]發(fā)因子過大時，使得蟻群對螞蟻的引導(dǎo)作用過強，導(dǎo)致螞蟻搜索更多路徑的可能性變小，更易陷入局部最優(yōu)解。因此，引入Logistic增長函數(shù)對揮發(fā)因子進(jìn)行自適應(yīng)調(diào)整。Logistic增長函數(shù)是一種常見的S形函數(shù)，如圖2所示。

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

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

4 算法仿真測試

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

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

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

[3] 王殿君. 基于改進(jìn)A*算法的室內(nèi)移動機(jī)器人路徑規(guī)劃[J]. 清華大學(xué)學(xué)報：自然科學(xué)版，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] 周文卷. 復(fù)雜環(huán)境下自主移動機(jī)器人路徑規(guī)劃方法的研究[D]. 長春：吉林大學(xué)，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] 施磊磊，施化吉，束長波，等. 改進(jìn)的模糊控制算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 軟件導(dǎo)刊，2014，13（11）：46-48.

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

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

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

[11] 史恩秀，陳敏敏，李俊，等. 基于蟻群算法的移動機(jī)器人全局路徑規(guī)劃方法研究[J]. 農(nóng)業(yè)機(jī)械學(xué)報，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ìn)展[J]. 智能系統(tǒng)學(xué)報，2016，11（1）：27-36.

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

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

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

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

[18] 侯欣蕾，于蓮芝. 基于改進(jìn)蟻群算法的移動機(jī)器人路徑規(guī)劃[J]. 軟件導(dǎo)刊，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] 王沛棟. 改進(jìn)蟻群算法及在路徑規(guī)劃問題的應(yīng)用研究[D]. 青島：中國海洋大學(xué)，2012.

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

（責(zé)任編輯：何 麗）