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

王嬌嬌　毛劍琳

摘要：

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

關(guān)鍵詞：

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

DOIDOI：10.11907/rjdk.181005

中圖分類號：TP303

文獻標(biāo)識碼：A文章編號文章編號：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引言

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

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

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

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

1.1問題描述

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

1.2基于中心點的平滑方法

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

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

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

1.3基于精英策略的改進蟻群算法

精英策略（Elitist Strategy）[14]是指當(dāng)每只螞蟻經(jīng)過一次循環(huán)后，利用傳統(tǒng)ACA即可找出最優(yōu)解。精英策略是對其信息素給予額外補償，蟻群之間主要靠信息素傳遞信息，找出的最優(yōu)解對應(yīng)的信息素增強，目的是這次循環(huán)中找到的最優(yōu)解在螞蟻的下次循環(huán)中，經(jīng)過信息素的增強操作后，對后面經(jīng)過的螞蟻吸引力更大，解決了蟻群算法在迭代過程中易陷入局部最優(yōu)從而使路徑中出現(xià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)解對應(yīng)的路徑總長度。

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

1.4ACA-ES 算法步驟

基于中心點的平滑方法改進后的蟻群算法（ACA-ES）步驟如下：

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

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

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

while 下步可行點≥1&&未到達終止點

end

計算各路徑長度并保存

K=k+1

end

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

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

if N=Nmax

Step 6

跳轉(zhuǎn)到Step 2

Step6：利用基于中心點的平滑方法對路徑進行平滑操作。

Step7：判斷路徑上相鄰的3個點是否在一條直線上：

if 3個相鄰點不在一條直線上

Step 6

else

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

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

2仿真實驗及分析

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

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

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

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

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

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

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

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

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

3結(jié)語

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

參考文獻參考文獻：

[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]王雷，李明，唐敦兵，等.基于改進遺傳算法的機器人動態(tài)路徑規(guī)劃[J].南京航空航天大學(xué)學(xué)報，2016，48（6）：841846.

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

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

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

[6]顏雪松，胡成玉，姚宏，等.精英粒子群優(yōu)化算法及其在機器人路徑規(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]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機械學(xué)報，2014，45（6）：5357.

[9]趙開新，魏勇，王東署.改進蟻群算法在移動機器人路徑規(guī)劃中的研究[J].計算機測量與控制，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]游曉明，劉升，呂金秋.一種動態(tài)搜索策略的蟻群算法及其在機器人路徑規(guī)劃中的應(yīng)用[J].控制與決策，2017，32（3）：552556.

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

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

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

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