一種改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃

顏杰 秦飛舟 翟帥華

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

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

DOI：10. 11907/rjdk. 182031

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

1 環(huán)境建模

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算法仿真測(cè)試

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

[18] 侯欣蕾，于蓮芝. 基于改進(jìn)蟻群算法的移動(dòng)機(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ī)劃問(wèn)題的應(yīng)用研究[D]. 青島：中國(guó)海洋大學(xué)，2012.

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

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