基于改進的蟻群算法的移動機器人路徑規(guī)劃

張?zhí)K英 趙國花 郭寶樑 于佳興 劉慧賢

摘 要：針對移動機器人路徑規(guī)劃中的傳統(tǒng)蟻群算法收斂精度低、易陷入局部最優(yōu)等問題，提出一種改進蟻群算法。首先，對算法的轉(zhuǎn)移概率進行改進，加入轉(zhuǎn)向代價，減少不必要的轉(zhuǎn)折，并針對啟發(fā)函數(shù)啟發(fā)性能不夠強，對路徑啟發(fā)信息進行改進;然后，提出一種自適應(yīng)的參數(shù)調(diào)整偽隨機狀態(tài)轉(zhuǎn)移策略，動態(tài)改變參數(shù)值，避免過早陷入搜索停滯，增強搜索的全面性，同時對信息素更新方式進行改進，調(diào)整信息素揮發(fā)系數(shù)，保持螞蟻發(fā)現(xiàn)最優(yōu)路徑的能力;最后，通過Matlab與其他算法進行對比分析。仿真結(jié)果表明，改進的蟻群算法收斂速度快，且路徑長度和算法迭代次數(shù)有明顯減少，能得到全局最優(yōu)路徑。改進蟻群算法具有可行性、有效性，在移動機器人路徑規(guī)劃中有一定的應(yīng)用價值。

關(guān)鍵詞：機器人控制;信息素;路徑規(guī)劃;改進的蟻群算法;自適應(yīng)參數(shù)調(diào)整

中圖分類號：TP242?文獻標(biāo)志碼：A

doi： 10.7535/hbgykj.2019yx06004

文章編號：1008-1534（2019）06-0390-06

Abstract：An improved ant colony algorithm is proposed for the traditional ant colony algorithm in mobile robot path planning with low convergence precision and easy to fall into local optimum.Firstly， the transition probability of the algorithm is improved， the steering cost is added， the unnecessary turning is reduced， and the heuristic performance of the heuristic function is not strong enough to improve the path heuristic information.Then an adaptive parameter adjustment pseudo-random state transition strategy is proposed to dynamically change the parameter values to avoid prematurely falling into search stagnation and enhance the comprehensiveness of the search. At the same time， the pheromone update method is improved， the pheromone volatilization coefficient is adjusted， and the ant is found to find the optimal path capability. Finally， through matlab and other algorithms， the simulation results show that the improved ant colony algorithm has a fast convergence speed， the path length?and algorithm iteration number are significantly reduced， and the global optimal path can be obtained， Proving the feasibility and effectiveness of the improved ant colony algorithm， which has certain application value in mobile robot path planning.

Keywords：robot control;pheromone; path planning; improved ant colony algorithm; adaptive parameter adjusting

隨著科學(xué)技術(shù)的迅猛發(fā)展，移動機器人被廣泛用于貨倉物流、農(nóng)業(yè)、工業(yè)、醫(yī)療等領(lǐng)域[1]。路徑規(guī)劃是移動機器人避障研究的重要技術(shù)之一，即在障礙物條件下能夠規(guī)劃出一條從起始點到終止點的最佳無撞擊路徑[2]。從過去到現(xiàn)在，無論國內(nèi)還是國外優(yōu)秀學(xué)者都對移動機器人的路徑規(guī)劃問題做了很多探究，不僅包括Dijkstra算法[3]等傳統(tǒng)算法，也包括遺傳算法[4]等智能優(yōu)化算法。這些算法在解決最短路徑問題上有了很大的提高，但是在復(fù)雜狀態(tài)下對機器人的要求就會增多，不單單要考慮路徑最短，因此，尋找一種最優(yōu)路徑算法成為研究重點。

蟻群算法是模仿自然界中螞蟻覓食過程發(fā)展起來的一種優(yōu)化方法[5]，具有適應(yīng)性強、易與其他算法相結(jié)合等特點。蟻群算法相比于其他算法是一種相對成熟的方法，但也有易于陷入局部最優(yōu)等缺陷[6]。面對這樣的缺陷，文獻[7]加入目標(biāo)點吸引機制和局部、全局相結(jié)合的策略進行信息素的更新;文獻[8]利用人工勢場法構(gòu)建勢場導(dǎo)向權(quán)改變狀態(tài)轉(zhuǎn)移概率，使算法收斂性變強，但是算法存在局限性，會出現(xiàn)停滯現(xiàn)象;文獻[9]將蟻群算法與遺傳算法進行結(jié)合，把每次迭代產(chǎn)生的可以行走的路徑作為父代種群，通過選擇交叉變異得到本次迭代最優(yōu)路徑。

為了更好地解決機器人的避障問題，本文針對蟻群算法的缺陷，引入轉(zhuǎn)向代價，提高路徑的平滑性;采用自適應(yīng)調(diào)整偽隨機狀態(tài)轉(zhuǎn)移策略，在算法的前期，參數(shù)q0對搜索干預(yù)大，從而減少陷入局部最優(yōu)的程度，隨著迭代的增強，在搜索的后期，參數(shù)q0對搜索的干預(yù)減小，算法使用輪盤賭法進行路徑選擇的幾率增大;對全局信息素的更新方式進行改進，加強最優(yōu)路徑的選擇。

1?路徑規(guī)劃問題的基本算法

1.1?柵格法建模

利用柵格法[10]將外部環(huán)境抽象離散化，建立機器人二維運動環(huán)境模型，使復(fù)雜問題簡單化，減少數(shù)據(jù)的計算量。柵格分為可行和不可行柵格，考慮到機器人自身長度、安全性、所占體積等，對環(huán)境中的阻隔物進行膨化處理，不足一個柵格的將其轉(zhuǎn)換為一個柵格，存在障礙物的柵格屬于不能夠行走的柵格[11]。機器人在能夠行走的柵格環(huán)境下，一共可以有8個行走方向[12]。以機器人所在柵格位置為中心的8個方向任由機器人選擇，如圖1所示。

1.2?傳統(tǒng)蟻群算法

DORIGO等提出了一種依賴于種群的啟發(fā)式隨機查找算法[13]。螞蟻在環(huán)境中覓食時會傾向于選擇信息素高的路徑行走，從而形成一種正反饋機制[14]。蟻群算法不可忽略以下2個重要方面：狀態(tài)轉(zhuǎn)移概率選擇以及局部、全局信息素更新[15]。

1.3?概率選擇

1.4?信息素更新

在螞蟻全部結(jié)束巡游后，不同軌道上的信息素按式（2）運行：

2?改進的蟻群算法

2.1?轉(zhuǎn)移概率的改進

考慮到在實際環(huán)境中，機器人大幅度轉(zhuǎn)彎會消耗時間和能量，在機器人路徑規(guī)劃中應(yīng)該減少不必要的轉(zhuǎn)折，提高路徑的平滑度。本文在計算路徑轉(zhuǎn)移概率時引入轉(zhuǎn)角啟發(fā)信息，轉(zhuǎn)角越小，選擇此路徑的概率越大。節(jié)點轉(zhuǎn)移概率公式為

傳統(tǒng)蟻群算法的啟發(fā)函數(shù)啟發(fā)性能不夠強，所以引入下一節(jié)點j到目標(biāo)節(jié)點z之間的距離。

改進后的啟發(fā)函數(shù)如式（7）所示。

2.2?自適應(yīng)參數(shù)調(diào)整策略

在傳統(tǒng)蟻群算法中，采用輪盤賭法進行路徑?jīng)Q擇。由于在算法早期存在差異不顯著的信息素濃度，造成蟻群算法早期收斂速度較慢，而且在環(huán)境規(guī)模很大的情況下，傳統(tǒng)蟻群容易出現(xiàn)停滯現(xiàn)象，減弱了算法對于最優(yōu)解的搜索，大大減弱了自適應(yīng)調(diào)整的作用。所以，本文添加狀態(tài)轉(zhuǎn)移規(guī)則可調(diào)控制參數(shù)q0，具體如式（8）、式（9）所示。

考慮到蟻群在迭代過程中搜索特性的需求，在算法的初期q0大概率大于q，使算法在前期路徑以偽隨機概率選擇方式為主，加快算法早期收斂，當(dāng)?shù)剿惴ǖ暮笃?，q0選取較小的數(shù)，從而使螞蟻隨機性進行尋優(yōu)。

2.3?全局信息素更新機制

每完成一次迭代后，按照式（10）進行更新。

螞蟻每次迭代完成后，如果La>Ln，那就意味著本次迭代的路徑更短，式（10）就應(yīng)該加強本次迭代信息素的強度，保存本次迭代的最優(yōu)路徑;反之，要是La

2.4?揮發(fā)系數(shù)ρ的改進

ρ的設(shè)置決定著螞蟻搜索的效果，也極大地影響著算法實現(xiàn)的性能，所以對揮發(fā)系數(shù)ρ做相應(yīng)的改進如式（11）所示。

3?算法詳細步驟

運行步驟如下。

步驟1：柵格環(huán)境地圖構(gòu)建;

步驟2：對涉及到的參數(shù)進行分配，包括機器人初始坐標(biāo)S，終止坐標(biāo)Z，螞蟻數(shù)量m，啟發(fā)因子α，β等參數(shù);

步驟3：螞蟻路徑選擇，根據(jù)式（4）、式（8）選擇下一節(jié)點;

步驟4：找出歷史迭代最優(yōu)La，本次迭代最優(yōu)路徑Ln，本次迭代最差路徑LA，對螞蟻應(yīng)用式（10）進行全局信息素更新;

步驟5：判斷是否達到最大迭代次數(shù)，條件成立得出最佳路徑，否則執(zhí)行步驟2。

算法實現(xiàn)流程圖如圖3所示。

4?仿真研究

為了使改進后的算法更具有說服力，在Matlab 2016a仿真平臺進行對比，設(shè)置算法初始參數(shù)，α=4，β=8，ρ=0.7，最大循環(huán)次數(shù)Nmax=50，螞蟻數(shù)量m=50，Q=1，為了驗證改進蟻群算法的優(yōu)越性，在不同環(huán)境下將其與傳統(tǒng)蟻群算法及文獻[7]算法進行比較。

4.1?20×20柵格地圖下仿真結(jié)果對比

由圖4—圖6可以直觀地看出，傳統(tǒng)蟻群算法陷入局部最優(yōu)，雖然最終也找到了一條最優(yōu)路徑，但路徑質(zhì)量不如改進后的蟻群算法。改進后的蟻群算法對啟發(fā)信息進行了改進，為蟻群提供了相對正確的初始啟發(fā)信息，從而使螞蟻找到了較好的路徑，并且改進的蟻群算法在轉(zhuǎn)彎次數(shù)上明顯少于傳統(tǒng)蟻群算法，對路徑進行了平滑處理，從而提高了算法的收斂速度。對比結(jié)果如表1所示，在簡單環(huán)境下，相比于傳統(tǒng)蟻群算法，本文算法有較高的收斂速度，運行時間也較短。

4.2?30×30柵格地圖下仿真結(jié)果對比

為了進一步了解本文算法在復(fù)雜環(huán)境下的全局

搜索能力，在復(fù)雜環(huán)境下對傳統(tǒng)蟻群、文獻[7]算法以及本文算法進行了對比，如圖7—圖10所示。

由圖7—圖10可以看出，為了對比明顯，在地圖尺寸和環(huán)境復(fù)雜度上進行了增強，故3種算法的迭代次數(shù)都有所增長，但是傳統(tǒng)蟻群算法依然陷入了局部最優(yōu)，文獻[7]對啟發(fā)信息進行了修改，引入了局部全局信息素更新機制，算法的收斂性能和全局尋優(yōu)能力得到了提升，在迭代15次后找到了最優(yōu)解，而本文引入了自適應(yīng)參數(shù)調(diào)整策略，在前期加速收斂，算法在迭代初期就取得了較小的初始值，通過引入轉(zhuǎn)彎角，本文算法轉(zhuǎn)彎次數(shù)的優(yōu)越性非常明顯，路徑更加平滑，僅用了9次就找到了最優(yōu)路徑。仿真結(jié)果對比見表2。

5?結(jié)?語

本文針對蟻群算法存在的不足，在柵格地圖中對蟻群算法進行了自適應(yīng)參數(shù)調(diào)整，在狀態(tài)轉(zhuǎn)移概率中引入轉(zhuǎn)角啟發(fā)信息，減少了運動過程中不必要的轉(zhuǎn)彎，實現(xiàn)路徑平滑，同時引入鄰域柵格和目標(biāo)點的距離因子構(gòu)建新的啟發(fā)函數(shù)，使得算法搜索路徑方向性更強;通過自適應(yīng)參數(shù)調(diào)整策略，動態(tài)地改變了參數(shù)值，提高了算法的收斂精度，保證螞蟻搜索的全局性;采用全局信息素更新方式進行信息素的更新，在規(guī)劃中對最短路徑進行信息素的加強，非最短路徑進行信息素的減弱，通過對揮發(fā)系數(shù)ρ的自適應(yīng)調(diào)整，防止路徑信息素軌跡量差異過大。本文改進算法相對于傳統(tǒng)蟻群算法和文獻[7]算法，尋找最優(yōu)路徑的能力更強，有很好的應(yīng)用價值。

本文只是在全局靜態(tài)環(huán)境下展開了研究，沒有考慮動態(tài)障礙物。在接下來的研究中將結(jié)合動態(tài)避障，進一步提高算法路徑規(guī)劃的能力。

參考文獻/References：

[1]歐青立，何克忠.室外智能移動機器人的發(fā)展及其關(guān)鍵技術(shù)研究[J].機器人，2000， 22（6）：519-526.

OU Qingli， HE Kezhong. Research on key techniques and development of outdoor intelligent autonomous mobile robot[J]. Robot， 2000， 22（6）： 519-526.

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

ZHANG Dianfu， LIU Fu. Research and development trend of path planning based on artificial potential field method[J]. Computer Engineering and Science， 2013， 35（6）： 88-95.

[3]田茹會.基于扇形優(yōu)化Dijkstra算法的艦船最佳導(dǎo)航路線分析[J].航艦電子工程，2019， 39（5）：41-45.

TIAN Ruhui. Research on shortest route of avoid disaster of mine roadway based on Dijkstra algorithm[J]. Ship Electronic Engineering， 2019， 39（5）： 41-45.

[4]FUKUSHIMA R， WANG H， TAMURA K， et al. Dominance relation-based genetic algorithm for superior solution set search problem[J]. IEEJ Transactions on Electrical and Electronic Engineering， 2019， 14（10）：959-960.

[5]陳曉，戴冉，陳昌源.基于Maklink 圖和蟻群算法的航線規(guī)劃[J].中國航海，2017， 40（3）：9-13.

CHEN Xiao， DAI Ran， CHEN Changyuan. Navigation route planning with Maklink graph and ant colony algorithm[J]. Navigation of China， 2017， 40（3）： 9-13.

[6]董曄，吳麗娟.基于混合人工勢場-蟻群算法的機器人避障[J].遼寧科技大學(xué)學(xué)報，2015， 38（3）：212-216.

DONG Ye， WU Lijuan. Research of robot obstacle avoidance based on hybrid artificial potential field-ant colony algorithm[J]. Journal of University of Science and Technology Liaoning， 2015， 38（3）：212-216.

[7]莊麗陽，陳樹林，朱龍彪，等.基于改進蟻群算法的農(nóng)用噴藥機器人路徑規(guī)劃[J].機床與液壓，2018， 46（21）：15-19.

ZHUANG Liyang， CHEN Shulin， ZHU Longbiao，et al. Path planning of agricultural spraying robot based on improved ant colony algorithm[J]. Machine Tool and Hydraulics， 2018， 46（21）： 15-19.

[8]王芳，李昆鵬，袁明新.一種人工勢場導(dǎo)向的蟻群路徑規(guī)劃算法[J].計算機科學(xué)，2014， 41（11A）：47-50.

WANG Fang， LI Kunpeng， YUAN Mingxin. Ant colony algorithm based on optimization of potential field method for path planning [J]. Computer Science， 2014， 41（11A）： 47-50.

[9]吳建，李康，龐宇，等.基于差分閾值與模板匹配的心電R波提取算法[J].重慶郵電大學(xué)學(xué)報（自然科學(xué)版），2015， 27（3）：372-376.

WU Jian， LI Kang， PANG Yu，et al. Algorithm of ECG R-wave extraction based on differential threshold and template matching[J]. Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition）， 2015， 27（3）： 372-376.

[10]周東健，張興國，馬海波，等.基于柵格地圖-蟻群算法的機器人最優(yōu)路徑規(guī)劃[J].制造業(yè)自動化，2013， 12（4）：91-94.

ZHOU Dongjian， ZHANG Xingguo， MA Haibo，et al. Optimal path planning for mobile robot based on grid map with ant colony algorithm[J]. Manufacturing Automation， 2013， 12（4）： 91-94.

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

LIANG Jiajun， ZENG Bi， HE Yuanlie. Research on path planning algorithm for cleaning robot based on improved potential field grid method[J]. Journal of Guangdong University of Technology， 2016， 33（4）： 30-36.

[12]李曉靜，余東滿.改進蟻群算法在果蔬采摘機器人路徑規(guī)劃中的應(yīng)用[J].江蘇農(nóng)業(yè)科學(xué)，2018， 46（23）：253-258.

LI Xiaojing， YU Dongman. Application of improved ant colony algorithm in path planning of fruit and vegetable picking robot[J]. Jiangsu Agricultural Science， 2018， 46（23）： 253-258.

[13]LU M， XU B， JIANG Z， et al. Automated tracking approach with ant colonies for different cell population density distribution[J]. Soft Computing， 2017， 21（14）：3977-3992.

[14]郭秀娟，張坤鵬.基于蟻群混合遺傳算法的組卷問題研究[J].吉林建筑大學(xué)學(xué)報，2017， 34（4）：79-83.

GUO Xiujuan， ZHANG Kunpeng. Research on application of ant colony algorithms hybrid genetic algorithms for test paper generation problems[J]. Journal of Jilin Jianzhu University， 2017， 34（4）： 79-83.

[15]李曉靜，余東滿.煤炭勘探及救援機器人最優(yōu)路徑規(guī)劃研究[J].工礦自動化，2017， 43（3）：24-29.

LI Xiaojing， YU Dongman. Research on the optimal path planning of coal exploration and rescue robot[J]. Industry and Mine Automation， 2017， 43（3）： 24-29.