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

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

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

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

doi： 10.7535/hbgykj.2019yx06004

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

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

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

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

1.1?柵格法建模

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

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

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

1.3?概率選擇

1.4?信息素更新

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

2?改進(jìn)的蟻群算法

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

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

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

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

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

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

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

2.3?全局信息素更新機(jī)制

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

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

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

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

3?算法詳細(xì)步驟

運(yùn)行步驟如下。

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

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

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

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

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

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

4?仿真研究

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

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

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

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

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

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

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

5?結(jié)?語

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

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

參考文獻(xiàn)/References：

[1]歐青立，何克忠.室外智能移動(dòng)機(jī)器人的發(fā)展及其關(guān)鍵技術(shù)研究[J].機(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]張殿富，劉福.基于人工勢(shì)場(chǎng)法路徑規(guī)劃方法研究及展望[J].計(jì)算機(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]田茹會(huì).基于扇形優(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]董曄，吳麗娟.基于混合人工勢(shì)場(chǎng)-蟻群算法的機(jī)器人避障[J].遼寧科技大學(xué)學(xué)報(bào)，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]莊麗陽，陳樹林，朱龍彪，等.基于改進(jìn)蟻群算法的農(nóng)用噴藥機(jī)器人路徑規(guī)劃[J].機(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]王芳，李昆鵬，袁明新.一種人工勢(shì)場(chǎng)導(dǎo)向的蟻群路徑規(guī)劃算法[J].計(jì)算機(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é)報(bào)（自然科學(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]周東健，張興國，馬海波，等.基于柵格地圖-蟻群算法的機(jī)器人最優(yōu)路徑規(guī)劃[J].制造業(yè)自動(dòng)化，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]梁嘉俊，曾碧，何元烈.基于改進(jìn)勢(shì)場(chǎng)柵格法的清潔機(jī)器人路徑規(guī)劃算法研究[J].廣東工業(yè)大學(xué)學(xué)報(bào)，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]李曉靜，余東滿.改進(jìn)蟻群算法在果蔬采摘機(jī)器人路徑規(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é)報(bào)，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]李曉靜，余東滿.煤炭勘探及救援機(jī)器人最優(yōu)路徑規(guī)劃研究[J].工礦自動(dòng)化，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.