基于蟻群改進(jìn)與尖峰平滑的移動(dòng)機(jī)器人路徑規(guī)劃

王嬌嬌　毛劍琳

摘要：

近年來(lái)，移動(dòng)機(jī)器人路徑規(guī)劃作為機(jī)器人自主導(dǎo)航領(lǐng)域的一個(gè)重要問(wèn)題而備受關(guān)注，針對(duì)傳統(tǒng)ACA有易陷入局部最優(yōu)，以及現(xiàn)階段在很多機(jī)器人路徑規(guī)劃中易被忽略的出現(xiàn)過(guò)于尖銳拐點(diǎn)的問(wèn)題，提出一種改進(jìn)蟻群算法（ACA-ES）應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃。首先，針對(duì)ACA易陷入早熟的問(wèn)題，引入精英策略，目的是給每次循環(huán)結(jié)束后找出的最優(yōu)解增加額外信息素，提高算法收斂速度；其次，為了不使機(jī)器人在路徑尖峰處失去平衡，引入基于中心點(diǎn)的平滑方法，提高路徑平滑性。在柵格環(huán)境下進(jìn)行仿真，得到一條平滑路徑，且路徑長(zhǎng)度比原來(lái)縮短了5.90%，證明了該改進(jìn)算法的有效性和可行性。

關(guān)鍵詞：

移動(dòng)機(jī)器人；路徑規(guī)劃；蟻群算法；精英策略；尖峰平滑

DOIDOI：10.11907/rjdk.181005

中圖分類(lèi)號(hào)：TP303

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2018）009003604

英文標(biāo)題Mobile Robot Path Planning Based on Ant Colony Improvement and Spike Smoothing

——副標(biāo)題

英文作者WANG Jiaojiao， MAO Jianlin

英文作者單位（Institute of Information Engineering and Automation， Kunming University of Science and Technology，Kunming 650000，China）

英文摘要Abstract：In recent years， Mobile robot path planning has drawn much attention as an important issue in robot autonomous navigation. An improved ACA （ACA-ES）is proposed for mobile robot path planning. First of all， in view of the ACA is easy to fall premature， Introducing Elitist Strategyelitist strategy is employed to aim at the fact that ACA is easy to fall premature， The purpose is to add extra pheromones to the optimal solution found at the end of each cycle， amd improve the convergence speed of the algorithm. Secondly， in order not to make the robot lose balance at the peak of the path， a smoothing method based on the center point is introduced to improve the smoothness of the path. Simulation in the grid environment A smooth path is obtained in grid environment， and the path length is reduced by 5.90%. The effectiveness and feasibility of the improved algorithm are proved.

英文關(guān)鍵詞Key Words：mobile robot； path planning； ant colony algorithm；elite strategy； spike smoothing

0引言

移動(dòng)機(jī)器人路徑規(guī)劃是移動(dòng)機(jī)器人研究領(lǐng)域的核心技術(shù)之一，主要目的是從已知起始點(diǎn)到要求達(dá)到的終止點(diǎn)，并且在有障礙物的情況下完成避障和路徑規(guī)劃。

遺傳算法的全局搜索能力較強(qiáng)[1]，文獻(xiàn)[2]通過(guò)設(shè)計(jì)自適應(yīng)變異概率，提高了遺傳個(gè)體評(píng)價(jià)精度和其應(yīng)用于路徑規(guī)劃時(shí)的求解質(zhì)量；文獻(xiàn)[3]采用染色體變長(zhǎng)遺傳算法（Messy GA），提高了路徑規(guī)劃的可靠性，但A*算法收斂速度慢，并且在搜索過(guò)程中會(huì)陷入“死循環(huán)”；文獻(xiàn)[4]采用頭尾雙向搜索法提高了A*算法的執(zhí)行效率和穩(wěn)定性，但粒子群算法（PSO）缺乏時(shí)間的動(dòng)態(tài)調(diào)節(jié)，使得局部尋優(yōu)能力相對(duì)較差；文獻(xiàn)[5]引入一種非線性動(dòng)態(tài)調(diào)整慣性權(quán)重的改進(jìn)PSO；文獻(xiàn)[6]引入一種更新函數(shù)，提高了PSO的局部路徑搜索能力，但蟻群算法（Ant Colony Algorithn，ACA）有易陷入局部最優(yōu)，且會(huì)導(dǎo)致收斂速度變慢的缺點(diǎn)[7]；文獻(xiàn)[8]分析了ACA主要參數(shù)對(duì)路徑規(guī)劃的影響，得到了最佳匹配參數(shù)；文獻(xiàn)[9]通過(guò)引入最大、最小蟻群系統(tǒng)對(duì)更新的信息素濃度進(jìn)行限制，解決了ACA因信息素差異過(guò)大而陷入“早熟”的問(wèn)題。

盡管上述算法都在一定程度上解決了路徑規(guī)劃中遇到的問(wèn)題，但多數(shù)算法都忽略了路徑規(guī)劃過(guò)程中的實(shí)際應(yīng)用問(wèn)題，比如得到了一條相對(duì)較短的路徑，但忽略了實(shí)際應(yīng)用中對(duì)路徑平滑性的要求，使得機(jī)器人實(shí)體平衡性差，且會(huì)在路徑尖峰處產(chǎn)生不必要的能量損耗。本文利用平滑方法增加路徑轉(zhuǎn)角的平滑性，消除路徑尖峰，以保障機(jī)器人實(shí)體的平衡性，并且能夠減少不必要的能量消耗。該改進(jìn)后的蟻群算法（ACA-ES）能獲得最短并且適合機(jī)器人行進(jìn)的平滑路徑。

1基于蟻群改進(jìn)與尖峰平滑（ACA-ES）的移動(dòng)機(jī)器人路徑規(guī)劃

1.1問(wèn)題描述

移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題是移動(dòng)機(jī)器人研究中最基本的問(wèn)題，目的是在起始點(diǎn)和目標(biāo)點(diǎn)已知的情況下找到一條最優(yōu)無(wú)碰路徑。根據(jù)機(jī)器人對(duì)運(yùn)行環(huán)境的掌握程度，可將其分為全局路徑規(guī)劃與局部路徑規(guī)劃[10]。本文研究的基于蟻群改進(jìn)與尖峰平滑（ACA-ES）的移動(dòng)機(jī)器人路徑規(guī)劃是環(huán)境信息已知的全局路徑規(guī)劃，主要包括環(huán)境建模、路徑規(guī)劃與路徑平滑。采用柵格法對(duì)環(huán)境進(jìn)行劃分，將環(huán)境信息存儲(chǔ)于（0，1）矩陣中，矩陣中1表示黑色不可通過(guò)的障礙柵格，0表示白色可通過(guò)柵格。

1.2基于中心點(diǎn)的平滑方法

平滑方法（Smooth Method）對(duì)規(guī)劃好的路徑中出現(xiàn)的尖峰有修正作用，可使路徑拐角更為平滑，機(jī)器人實(shí)體能在拐彎過(guò)程中平穩(wěn)前進(jìn)，同時(shí)減少在路徑尖峰處不必要的能量損耗。

文獻(xiàn)[11]設(shè)計(jì)了動(dòng)態(tài)搜索模型，以加快ACA的收斂速度，優(yōu)化解的質(zhì)量；文獻(xiàn)[12]采用簡(jiǎn)化A*算法對(duì)初始信息素進(jìn)行優(yōu)化設(shè)置，反饋優(yōu)化目標(biāo)以實(shí)現(xiàn)自適應(yīng)調(diào)節(jié)，提高ACA的全局搜索能力。但文獻(xiàn)中的改進(jìn)方法都忽略了機(jī)器人實(shí)體對(duì)路徑平滑性的要求。

本文基于中心點(diǎn)平滑方法改進(jìn)的蟻群算法（ACA-S）是通過(guò)在路徑拐點(diǎn)處增加新節(jié)點(diǎn)實(shí)現(xiàn)的，用新節(jié)點(diǎn)代替舊節(jié)點(diǎn)完成路徑平滑處理[13]。新節(jié)點(diǎn)的選擇及添加對(duì)路徑平滑性的改善和整體路徑規(guī)劃效率有著直接影響。圖1是基于中心點(diǎn)的平滑方法操作示意圖，原路徑線段夾角稱(chēng)為α2，選擇及添加新節(jié)點(diǎn)并去除舊節(jié)點(diǎn)，與設(shè)置的兩條路徑拐角的角度期望值α1有關(guān)，角度期望值α1定為155°。若兩條相鄰直線的實(shí)際拐角α2≤α1，則在兩條線段的可行域之間取中點(diǎn)（x-new1，y-new1）和（x-new2，y-new2），再判斷新節(jié)點(diǎn)與兩邊構(gòu)成的拐角角度是否滿(mǎn)足大于角度期望值α。若不滿(mǎn)足，繼續(xù)進(jìn)行上述變換，尋找新拐點(diǎn)（x-new1，y-new1）和（x-new2，y-new2）；滿(mǎn)足角度條件后，刪除舊拐點(diǎn)，以新拐點(diǎn)代替。再以此判斷路徑內(nèi)的其它拐點(diǎn)是否滿(mǎn)足條件，不斷重復(fù)，使整條路徑的拐角都大于角度期望值。

1.3基于精英策略的改進(jìn)蟻群算法

精英策略（Elitist Strategy）[14]是指當(dāng)每只螞蟻經(jīng)過(guò)一次循環(huán)后，利用傳統(tǒng)ACA即可找出最優(yōu)解。精英策略是對(duì)其信息素給予額外補(bǔ)償，蟻群之間主要靠信息素傳遞信息，找出的最優(yōu)解對(duì)應(yīng)的信息素增強(qiáng)，目的是這次循環(huán)中找到的最優(yōu)解在螞蟻的下次循環(huán)中，經(jīng)過(guò)信息素的增強(qiáng)操作后，對(duì)后面經(jīng)過(guò)的螞蟻吸引力更大，解決了蟻群算法在迭代過(guò)程中易陷入局部最優(yōu)從而使路徑中出現(xiàn)不必要尖峰的缺點(diǎn)。信息素更新公式如下：

τij（t+l）=ρ.τij（t）+Δτij+Δτ+*ij（1）

式中：

Δτ+*ij=QL+*，若邊（i，j）是所找最優(yōu)解的一部分0，否則（2）

式中，△τij表示精英螞蟻在路徑（i，j）上信息素的增加，σ表示精英螞蟻及數(shù)量，L*表示循環(huán)結(jié)束后所找出的最優(yōu)解對(duì)應(yīng)的路徑總長(zhǎng)度。

仿真結(jié)果表明，精英策略解決了蟻群算法在路徑規(guī)劃時(shí)遇到的易陷入“早熟”的缺點(diǎn)，加入精英策略的蟻群算法比傳統(tǒng)ACA的迭代次數(shù)明顯減少，并能獲得相對(duì)滿(mǎn)意的最優(yōu)路徑。

1.4ACA-ES 算法步驟

基于中心點(diǎn)的平滑方法改進(jìn)后的蟻群算法（ACA-ES）步驟如下：

Step1：初始化參數(shù)，對(duì)螞蟻個(gè)數(shù)M、迭代次數(shù)K、柵格、螞蟻起始點(diǎn)和終止點(diǎn)、表征信息素重要程度的參數(shù)α、表征啟發(fā)式因子重要程度的參數(shù)β、信息素?fù)]發(fā)系數(shù)ρ、信息素增加強(qiáng)度系數(shù)Q以及期望偏轉(zhuǎn)角度α1、禁忌表初始化。

Step2：將M只螞蟻分布到各節(jié)點(diǎn)。

Step3：for k=1， 2， …， M

while 下步可行點(diǎn)≥1&&未到達(dá)終止點(diǎn)

end

計(jì)算各路徑長(zhǎng)度并保存

K=k+1

end

Step4：根據(jù)公式（1）精英策略更新信息素。

Step5：判斷是否達(dá)到最大迭代次數(shù)：

if N=Nmax

Step 6

跳轉(zhuǎn)到Step 2

Step6：利用基于中心點(diǎn)的平滑方法對(duì)路徑進(jìn)行平滑操作。

Step7：判斷路徑上相鄰的3個(gè)點(diǎn)是否在一條直線上：

if 3個(gè)相鄰點(diǎn)不在一條直線上

Step 6

else

跳轉(zhuǎn)到下一個(gè)點(diǎn) Step 6

Step8：輸出優(yōu)化后的路徑。

2仿真實(shí)驗(yàn)及分析

為驗(yàn)證引入精英策略和基于中心點(diǎn)平滑方法的改進(jìn)后蟻群算法（ACA-ES）應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃效果，在MATLAB2012a環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。利用柵格法對(duì)環(huán)境進(jìn)行劃分，圖中黑色格子表示不能通過(guò)的柵格即為障礙物柵格，白色格子表示道路為可通過(guò)柵格。分別在障礙物覆蓋率為19%的20*20簡(jiǎn)單柵格和障礙物覆蓋率為77%的17*17復(fù)雜柵格環(huán)境下進(jìn)行仿真。

2.1簡(jiǎn)單障礙物柵格環(huán)境仿真

為了驗(yàn)證本文提出的基于中心點(diǎn)的平滑方法（ACA-S）應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃的可行性，劃分機(jī)器人的工作環(huán)境為20*20簡(jiǎn)單障礙物柵格，仿真參數(shù)設(shè)置為：螞蟻個(gè)數(shù)M為50，迭代次數(shù)N為200，啟發(fā)因子α為1，期望啟發(fā)因子β為7，信息素蒸發(fā)系數(shù)ρ為0.7，信息素增加強(qiáng)度系數(shù)為1，機(jī)器人起始點(diǎn)坐標(biāo)為（0.5，19.5），終止點(diǎn)坐標(biāo)為（19.5，0.5），期望偏轉(zhuǎn)角度α1為155°。路徑規(guī)劃仿真如圖3所示。

由圖3可看出，本文提出的路徑平滑方法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃過(guò)程中，不僅能夠規(guī)劃出令人滿(mǎn)意的避障路徑，而且在機(jī)器人拐彎處的路線有了明顯的平滑改善。路徑由原來(lái)的30.384 8縮短為29.799 0，迭代次數(shù)由32減少到29，證明了該平滑方法可為實(shí)體機(jī)器人規(guī)劃出一條更加適合自主移動(dòng)的平滑路線。

2.2復(fù)雜障礙物柵格環(huán)境仿真

為驗(yàn)證該改進(jìn)算法（ACA-ES）應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃時(shí)的可行性和有效性，在17*17柵格環(huán)境下進(jìn)行路徑規(guī)劃仿真，參數(shù)設(shè)置與20*20柵格一致，機(jī)器人的起始點(diǎn)坐標(biāo)為（0.5，16.5），終止點(diǎn)坐標(biāo)為（16.5，0.5）。

分別采用傳統(tǒng)蟻群算法（ACA）、基于精英策略的改進(jìn)蟻群算法（ACA-E）、在精英策略基礎(chǔ)上加入平滑方法的改進(jìn)蟻群算法（ACA-ES）在17*17的復(fù)雜障礙物柵格環(huán)境下進(jìn)行路徑規(guī)劃仿真研究，圖4給出了采用各類(lèi)算法的機(jī)器人路徑規(guī)劃仿真結(jié)果，表1對(duì)其路徑長(zhǎng)度和仿真耗時(shí)進(jìn)行匯總對(duì)比。

由圖4（a）可知，傳統(tǒng)蟻群算法（ACA）雖然能有效避開(kāi)障礙物并規(guī)劃出一條可行路線，但由于蟻群算法本身有易陷入局部最優(yōu)的缺點(diǎn)，使得規(guī)劃好的路徑中出現(xiàn)了不必要的冗余節(jié)點(diǎn)。為了去除路徑中的這些節(jié)點(diǎn)，達(dá)到縮短路徑長(zhǎng)度的目的，引入精英策略；如圖4（b）所示為ACA-E路徑規(guī)劃圖，精英策略提高了ACA的全局搜索能力，消除了路徑中的多余節(jié)點(diǎn)。由表1可知，路徑長(zhǎng)度由原來(lái)的33.899 5縮短為32.727 9，迭代次數(shù)由70下降到35，減少了一半。在此基礎(chǔ)上引入基于中心點(diǎn)的平滑方法進(jìn)一步對(duì)拐點(diǎn)進(jìn)行優(yōu)化，使得路徑更加圓滑，符合實(shí)體機(jī)器人的運(yùn)動(dòng)特性，同時(shí)路徑長(zhǎng)度縮短為31.899 5，迭代次數(shù)減少為25；如圖4（c）所示，與傳統(tǒng)ACA路徑規(guī)劃相比，ACA-ES應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃，不僅縮短了得到的最優(yōu)路徑長(zhǎng)度，而且相對(duì)于傳統(tǒng)ACA減少了迭代次數(shù)，并結(jié)合實(shí)體機(jī)器人對(duì)路徑規(guī)劃的特殊要求，得到一條適合機(jī)器人行進(jìn)的平滑路線。

表1數(shù)據(jù)顯示路徑規(guī)劃在引入精英策略（ACA-E）和基于中心點(diǎn)的平滑方法（ACA-ES）后，所得規(guī)劃路徑長(zhǎng)度明顯優(yōu)于傳統(tǒng)ACA，分別減少了3.46%和5.90%，說(shuō)明精英策略和基于中心點(diǎn)的平滑方法有效發(fā)揮了作用。但是路徑的縮短以消耗時(shí)間為代價(jià)，改進(jìn)后的ACA-E和ACA-ES所需的規(guī)劃時(shí)間分別增加了5.48%和4.51%。

3結(jié)語(yǔ)

本文提出一種引入精英策略和路徑尖峰平滑方法的改進(jìn)蟻群算法 （ACA-ES）應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃，其中，精英策略的加入解決了傳統(tǒng)蟻群算法易陷入局部最優(yōu)而導(dǎo)致算法搜索停滯的弊端，提高了解的全局性。在引入精英策略的基礎(chǔ)上加入基于中心點(diǎn)的平滑方法，該方法使路徑中的較小轉(zhuǎn)角更為平滑，降低了機(jī)器人在路徑轉(zhuǎn)彎處的能量損耗，機(jī)器人實(shí)體在行進(jìn)中的穩(wěn)定性也得到了保障。仿真實(shí)驗(yàn)表明，采用ACA-ES算法明顯提高了路徑平滑度，所獲得的路徑長(zhǎng)度也更短，但這是以消耗計(jì)算機(jī)的運(yùn)行時(shí)間為代價(jià)的，在實(shí)際要求較高的情況下需要進(jìn)一步改進(jìn)。

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

[1]ZHANG X， TANG L. A new hybrid ant colony optimization algorithm for the vehicle routing problem [J]. Pattern Recognition Letters， 2009，30（9）：848855.

[2]王雷，李明，唐敦兵，等.基于改進(jìn)遺傳算法的機(jī)器人動(dòng)態(tài)路徑規(guī)劃[J].南京航空航天大學(xué)學(xué)報(bào)，2016，48（6）：841846.

[3]盧瑾，楊東勇.基于雙重遺傳算法機(jī)制的路徑規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào)，2008，20（8）：20482051.

[4]劉鈺，陸建峰，蔡海舟.基于改進(jìn)A*算法的機(jī)器人路徑規(guī)劃方法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012（12）：108111.

[5]張萬(wàn)緒，張向蘭，李瑩.基于改進(jìn)粒子群算法的智能機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用，2014，34（2）：510513.

[6]顏雪松，胡成玉，姚宏，等.精英粒子群優(yōu)化算法及其在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].光學(xué)精密工程，2013，21（12）：31603168.

[7]XIONG W Q， WEI P. A kind of ant colony algorithm for function optimization[C].International Conference on Machine Learning and Cybernetics， Proceedings， 2002：552555.

[8]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014，45（6）：5357.

[9]趙開(kāi)新，魏勇，王東署.改進(jìn)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的研究[J].計(jì)算機(jī)測(cè)量與控制，2014，22（11）：6770.

[10]GE S S， CUI Y J. New potential functions for mobile robot path planning [J]. IEEE Transactions on Robotics & Automation， 2000，16（5）：615620.

[11]游曉明，劉升，呂金秋.一種動(dòng)態(tài)搜索策略的蟻群算法及其在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].控制與決策，2017，32（3）：552556.

[12]黃辰，費(fèi)繼友，劉洋，等.基于動(dòng)態(tài)反饋A*蟻群算法的平滑路徑規(guī)劃方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)， 2017，48（4）：3440.

[13]王雪松，高陽(yáng)，程玉虎，等.知識(shí)引導(dǎo)遺傳算法實(shí)現(xiàn)機(jī)器人路徑規(guī)劃[J].控制與決策，2009，24（7）：10431049.

[14]張家善，王志宏，陳應(yīng)顯.一種基于精英策略的改進(jìn)蟻群算法及應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21（10）：105108.

責(zé)任編輯（責(zé)任編輯：黃?。?/p>