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

孫 瑞，張文勝

?

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

孫 瑞，張文勝

(石家莊鐵道大學(xué)交通運(yùn)輸學(xué)院，河北 石家莊 050043)

針對(duì)移動(dòng)機(jī)器人提出了基于改進(jìn)蟻群算法的平滑路徑規(guī)劃方法。為了克服蟻群算法解決路徑規(guī)劃問題時(shí)存在的收斂速度慢的缺點(diǎn)，對(duì)啟發(fā)因子的矩陣初始值及更新方式進(jìn)行了改進(jìn)，啟發(fā)因子改進(jìn)后的結(jié)果與之前相比，平均路徑長(zhǎng)度減少了17.6%，平均收斂代數(shù)減少了93.1%；對(duì)于柵格環(huán)境下存在障礙物時(shí)機(jī)器人累計(jì)轉(zhuǎn)彎角度大的問題，提出了控制點(diǎn)轉(zhuǎn)移策略，在上一步改進(jìn)的基礎(chǔ)上，通過對(duì)控制路徑走向的柵格中心點(diǎn)向柵格角頂點(diǎn)的轉(zhuǎn)移，實(shí)現(xiàn)了路徑規(guī)劃的平滑改進(jìn)。路徑規(guī)劃仿真結(jié)果表明，與平滑改進(jìn)前相比，平滑改進(jìn)后機(jī)器人的平均路徑長(zhǎng)度減少了4.28%，累計(jì)轉(zhuǎn)彎角度減少了52.58%。

蟻群算法；移動(dòng)機(jī)器人；路徑規(guī)劃；控制點(diǎn)轉(zhuǎn)移策略

隨著人工智能的發(fā)展，機(jī)器人在人類社會(huì)發(fā)揮著越來越重要的作用[1]。移動(dòng)機(jī)器人的路徑規(guī)劃是機(jī)器人執(zhí)行任務(wù)的首要條件[2]，可要求機(jī)器人在躲避障礙物的前提下，找到從出發(fā)點(diǎn)到目的地的最優(yōu)路徑。

蟻群算法是模仿自然界中螞蟻覓食過程發(fā)展起來的一種優(yōu)化方法[3-4]，具有較強(qiáng)的魯棒性，在解決優(yōu)化問題方面顯示出巨大優(yōu)勢(shì)和發(fā)展?jié)摿5-7]，廣泛應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃問題。目前眾多學(xué)者對(duì)其進(jìn)行研究，徐勝華等[8]在解決機(jī)器人路徑規(guī)劃問題時(shí)對(duì)蟻群算法進(jìn)行改進(jìn)，使其能根據(jù)環(huán)境特征進(jìn)行優(yōu)化；張文強(qiáng)和張彥[9]提出一種改進(jìn)蟻群算法，將引力系數(shù)和避障系數(shù)引入啟發(fā)因子中，提高了解的質(zhì)量和搜索效率；朱艷等[10]將方向信息加到啟發(fā)因子中，且動(dòng)態(tài)調(diào)整權(quán)重系數(shù)使算法搜索效率更高；王輝等[11]通過更改啟發(fā)因子及信息素更新規(guī)則，使改進(jìn)后的算法收斂更快；王志中[12]提出了螞蟻相遇策略及螞蟻回退策略，設(shè)置了信息素感應(yīng)閾值，對(duì)信息素殘留方法進(jìn)行了改進(jìn)，使改進(jìn)后的蟻群算法具有更快的收斂速度以及更優(yōu)的規(guī)劃結(jié)果；張瑋等[13]采用改進(jìn)煙花-蟻群混合算法進(jìn)行最優(yōu)路徑的求解，將改進(jìn)煙花算法得到的最短路徑作為參照路徑，將其換算成蟻群算法的初始信息素分布，結(jié)果表明該算法具有良好的性能；王紅君等[14]提出了一種平滑蟻群算法，將路徑上當(dāng)前節(jié)點(diǎn)與其他不在同一條直線上的節(jié)點(diǎn)依次連線，如果新的連接線不穿越障礙物，則將當(dāng)前連接線作為新路徑代替原來路徑，降低了路徑長(zhǎng)度。

以上研究大多是對(duì)蟻群算法進(jìn)行改進(jìn)，對(duì)于改進(jìn)后的路徑進(jìn)行平滑的方法較少。本文不但通過改進(jìn)啟發(fā)因子實(shí)現(xiàn)了對(duì)蟻群算法的改進(jìn)，而且提出了控制點(diǎn)轉(zhuǎn)移策略，通過對(duì)控制路徑走向的柵格中心點(diǎn)向柵格角頂點(diǎn)的轉(zhuǎn)移，實(shí)現(xiàn)了對(duì)蟻群算法改進(jìn)后的路徑平滑操作，為蟻群算法的改進(jìn)及路徑平滑操作提供了一種新思路。

1 環(huán)境建模

柵格法可使機(jī)器人感知的柵格信息與環(huán)境相對(duì)應(yīng)，且柵格法地圖易于創(chuàng)建和維護(hù)，因此采用柵格法建立移動(dòng)機(jī)器人二維空間環(huán)境模型。柵格法模型如圖1所示，劃分柵格區(qū)域的指標(biāo)為機(jī)器人單位運(yùn)動(dòng)步長(zhǎng)。左上角柵格為起始柵格，柵格序號(hào)按自左向右，從上至下的順序依次增大，右下角柵格為終點(diǎn)柵格。障礙物柵格表現(xiàn)為黑色，自由柵格為白色[15]。設(shè)為柵格序號(hào)；為柵格的邊長(zhǎng)。柵格序號(hào)與柵格中心點(diǎn)坐標(biāo)對(duì)應(yīng)關(guān)系如下

2 基本蟻群算法

在覓食過程中，螞蟻根據(jù)信息素濃度選擇新的路徑，并賦予路徑一定概率。信息素具有揮發(fā)性，隨著時(shí)間的推移，揮發(fā)留下的信息素能引導(dǎo)螞蟻找到最優(yōu)路徑[16-17]。

在尋找新的食物源時(shí)，螞蟻沒有信息素指引，因此進(jìn)行完全隨機(jī)搜索，此時(shí)所有路徑均被賦予相同的概率。螞蟻將更多的信息素留在較短的路徑上，較長(zhǎng)的路徑逐漸被放棄[18]。之后會(huì)有更多的螞蟻選擇信息素較多的路徑，這就形成了正反饋機(jī)制，通過該機(jī)制，蟻群中螞蟻能沿著最佳路徑找到食物。該過程如圖2所示。

圖2 螞蟻覓食示意圖

設(shè)為食物來源；為蟻巢所在地；為時(shí)間；和為單位距離；和為0.5單位距離。設(shè)和中有30只螞蟻，當(dāng)＝1時(shí)，上沒有信息素，因此螞蟻以相同的概率選擇路徑。經(jīng)過1單位時(shí)間后，路徑上信息素量是的2倍；當(dāng)＝2時(shí)，和中的30只螞蟻根據(jù)先前迭代中不同路徑上的信息素濃度再次選擇路徑：從點(diǎn)出發(fā)的螞蟻有20只選擇，10只選擇；從點(diǎn)出發(fā)的螞蟻有20只選擇，10只選擇，因此，較短路徑上積累了更多的信息素。隨著時(shí)間的推移，會(huì)有更多螞蟻選擇()路徑，直到最后一組螞蟻均找到蟻巢和食物之間的最短路徑。螞蟻覓食是一個(gè)正反饋過程。某刻，螞蟻從節(jié)點(diǎn)轉(zhuǎn)向節(jié)點(diǎn)的概率為[19]

3 改進(jìn)蟻群算法

3.1 啟發(fā)因子的改進(jìn)

對(duì)于啟發(fā)因子的改進(jìn)分為啟發(fā)因子矩陣初始值和啟發(fā)因子更新方式2部分。

3.1.1 啟發(fā)因子矩陣初始值的改進(jìn)

在基本蟻群算法中，啟發(fā)因子矩陣初始值為該節(jié)點(diǎn)與下一節(jié)點(diǎn)距離的倒數(shù)。經(jīng)驗(yàn)證其收斂性能較弱、全局搜索能力較差。為加強(qiáng)蟻群算法收斂性能，減少收斂代數(shù)，提高全局搜索能力，對(duì)啟發(fā)因子矩陣初始值進(jìn)行改進(jìn)，即

(x,y)為該節(jié)點(diǎn)處坐標(biāo)值，(x,y)為下一節(jié)點(diǎn)處坐標(biāo)值，引入常數(shù)a、b，使啟發(fā)因子矩陣初始值為任意兩節(jié)點(diǎn)距離進(jìn)行初等變換后的倒數(shù)。在第4節(jié)中進(jìn)行路徑規(guī)劃統(tǒng)計(jì)結(jié)果分析，找到移動(dòng)機(jī)器人路徑規(guī)劃最短且收斂代數(shù)最少的a、b值。

3.1.2 啟發(fā)因子更新方式的改進(jìn)

在基本蟻群算法中，啟發(fā)因子為該節(jié)點(diǎn)與下一節(jié)點(diǎn)距離的倒數(shù)，使螞蟻具有一定的盲目性，易陷入局部最優(yōu)而錯(cuò)失全局最優(yōu)路徑[20]。為減少這種情況的發(fā)生，提高蟻群算法全局搜索能力，引入下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的距離，對(duì)啟發(fā)因子更新方式進(jìn)行改進(jìn)，即

其中，為下一節(jié)點(diǎn)；為目標(biāo)節(jié)點(diǎn)；d為節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的距離。

將改進(jìn)后啟發(fā)因子帶入狀態(tài)轉(zhuǎn)移公式，得到改進(jìn)后的狀態(tài)轉(zhuǎn)移公式為

分析可知，當(dāng)下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的距離越大時(shí)，啟發(fā)因子越小，螞蟻選擇該節(jié)點(diǎn)的概率隨之越小。也就是說，當(dāng)搜索到的距離越短時(shí)，螞蟻選擇的概率越大，因此移動(dòng)機(jī)器人路徑規(guī)劃更優(yōu)。

3.2 路徑規(guī)劃的平滑改進(jìn)

在柵格環(huán)境下，移動(dòng)機(jī)器人的路徑規(guī)劃是該路徑上各個(gè)柵格中心點(diǎn)連成的直線段，將這些柵格中心點(diǎn)稱為控制點(diǎn)，其控制著移動(dòng)機(jī)器人的路徑規(guī)劃。由于移動(dòng)機(jī)器人的路徑是從中心點(diǎn)到中心點(diǎn)的直線段，從一定程度上增加了路徑長(zhǎng)度，且增大了移動(dòng)機(jī)器人累計(jì)轉(zhuǎn)彎角度。對(duì)路徑規(guī)劃進(jìn)行平滑改進(jìn)，不僅能減少移動(dòng)機(jī)器人運(yùn)行距離，還能降低其由于轉(zhuǎn)彎帶來的能耗[21]。

圖3實(shí)線為基于蟻群算法搜索到的路徑，從點(diǎn)到點(diǎn)的路徑由3段折線組成。若將路徑上的點(diǎn)與點(diǎn)相連，能減小移動(dòng)機(jī)器人路徑規(guī)劃累計(jì)轉(zhuǎn)彎角度，且根據(jù)三角形兩邊之和大于第三邊的定理，線段的長(zhǎng)度小于原路徑長(zhǎng)度。

圖3 從A到B的路徑規(guī)劃改進(jìn)

因此引入控制點(diǎn)轉(zhuǎn)移策略，將圖3中第35個(gè)柵格的控制點(diǎn)由柵格中心點(diǎn)轉(zhuǎn)移到該柵格上離起點(diǎn)最近的點(diǎn)，將第55個(gè)柵格的控制點(diǎn)由柵格中心點(diǎn)轉(zhuǎn)移到該柵格上離終點(diǎn)最近的點(diǎn)，刪除原路徑上第45個(gè)柵格的中心點(diǎn)，并將點(diǎn)與點(diǎn)連接成一條直線段。因此，縮短了路徑規(guī)劃的距離，減少了路徑規(guī)劃的累計(jì)轉(zhuǎn)彎角度，實(shí)現(xiàn)了路徑的平滑操作。

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

步驟1.運(yùn)用經(jīng)過啟發(fā)因子改進(jìn)后的蟻群算法生成一條機(jī)器人最優(yōu)路徑。

步驟2. 引入控制點(diǎn)轉(zhuǎn)移策略，即通過對(duì)控制路徑走向的柵格中心點(diǎn)向柵格角頂點(diǎn)的轉(zhuǎn)移，進(jìn)行路徑簡(jiǎn)化與平滑操作。

設(shè)置路徑起點(diǎn)為，終點(diǎn)為。控制點(diǎn)轉(zhuǎn)移策略主要針對(duì)除起點(diǎn)與終點(diǎn)之外的路徑上的其他柵格中心點(diǎn)。當(dāng)路徑上存在豎直線段時(shí)，將最上方柵格中心點(diǎn)記為(X,Y)，分別判斷所在柵格的4個(gè)角頂點(diǎn)：U(X–0.5,Y+0.5)，U(X+0.5,Y+0.5)，U(X+0.5,Y–0.5)，U(X–0.5,Y–0.5)與起點(diǎn)的距離，選擇與起點(diǎn)的距離最小的點(diǎn)作為轉(zhuǎn)移的目標(biāo)角頂點(diǎn)(記為U)，將轉(zhuǎn)移至U。將最下方柵格中心點(diǎn)記為(X,Y)，分別判斷所在柵格的4個(gè)角頂點(diǎn)：D，D，D，D與終點(diǎn)的距離，選擇與終點(diǎn)距離最小的點(diǎn)作為轉(zhuǎn)移的目標(biāo)角頂點(diǎn)(記為D)，將轉(zhuǎn)移至D。刪除與之間的中心柵格點(diǎn)，并將點(diǎn)U與點(diǎn)D相連。

判斷當(dāng)路徑上存在水平線段時(shí)，將最左側(cè)柵格中心點(diǎn)記為，分別判斷所在柵格的4個(gè)角頂點(diǎn)：，L，L，L與起點(diǎn)的距離，將轉(zhuǎn)移到該柵格距起點(diǎn)最近的角頂點(diǎn)(記為L)上。將最右側(cè)柵格中心點(diǎn)記為，分別判斷所在柵格的4個(gè)角頂點(diǎn)：R，R，R，R與終點(diǎn)的距離，將轉(zhuǎn)移到該柵格距終點(diǎn)最近的角頂點(diǎn)(記為R)上。刪除與之間的中心柵格點(diǎn)，并將點(diǎn)L與點(diǎn)R相連。

步驟3.生成新路徑取代原有路徑。判斷路徑上是否仍存在水平線段或豎直線段，若仍存在則重新執(zhí)行步驟2和步驟3，否則輸出機(jī)器人最終路徑。

路徑規(guī)劃的平滑改進(jìn)能有效減小移動(dòng)機(jī)器人的路徑長(zhǎng)度及累計(jì)轉(zhuǎn)彎角度，使得機(jī)器人的能量消耗得以降低，更符合移動(dòng)機(jī)器人的路徑規(guī)劃要求。路徑規(guī)劃平滑改進(jìn)流程圖如圖4所示。

圖4 路徑規(guī)劃平滑改進(jìn)流程圖

4 改進(jìn)蟻群算法及路徑平滑操作的仿真驗(yàn)證

4.1 仿真1

為驗(yàn)證經(jīng)過啟發(fā)因子改進(jìn)的蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃的正確性與有效性，對(duì)算法進(jìn)行仿真。仿真環(huán)境為MATLAB R2016a，采用柵格法建模，柵格邊長(zhǎng)為10。螞蟻個(gè)數(shù)=30，信息素重要程度參數(shù)=1，啟發(fā)因子重要程度參數(shù)=6，信息素蒸發(fā)系數(shù)=0.1，信息素增加強(qiáng)度系數(shù)=14。

在和均為默認(rèn)值1的情況下，對(duì)基本蟻群算法及經(jīng)過啟發(fā)因子更新方式、狀態(tài)轉(zhuǎn)移公式改進(jìn)的蟻群算法進(jìn)行仿真，路徑規(guī)劃仿真結(jié)果如圖5所示。

蟻群算法在搜索過程中進(jìn)行下一節(jié)點(diǎn)選擇時(shí)存在著隨機(jī)性因素，僅根據(jù)一次實(shí)驗(yàn)結(jié)果難以準(zhǔn)確判斷兩種算法的優(yōu)劣，因此需進(jìn)行多次實(shí)驗(yàn)來得到更準(zhǔn)確的結(jié)果。為此，分別用MATLAB運(yùn)行20次和50次，并對(duì)兩者的運(yùn)行結(jié)果進(jìn)行對(duì)比。

用MATLAB運(yùn)行20次得到的路徑規(guī)劃統(tǒng)計(jì)結(jié)果見表1。

用MATLAB運(yùn)行50次得到的路徑規(guī)劃統(tǒng)計(jì)結(jié)果見表2。

圖5 啟發(fā)因子更新方式、狀態(tài)轉(zhuǎn)移公式改進(jìn)前后路徑規(guī)劃仿真結(jié)果

表1 a和b均為1時(shí)，運(yùn)行20次的路徑規(guī)劃統(tǒng)計(jì)結(jié)果

表2 a和b均為1時(shí)，運(yùn)行50次的路徑規(guī)劃統(tǒng)計(jì)結(jié)果

由表1和表2比較分析可知，運(yùn)行50次時(shí)，基本蟻群算法的平均路徑長(zhǎng)度、平均收斂代數(shù)、最小收斂代數(shù)均發(fā)生變化。運(yùn)行50次比20次包含更多的路徑搜索情況，以最小收斂代數(shù)為例，運(yùn)行50次時(shí)為147，而運(yùn)行20次時(shí)未出現(xiàn)此情況。因此，選擇用MATLAB進(jìn)行50次獨(dú)立實(shí)驗(yàn)，分析時(shí)采用MATLAB運(yùn)行50次得到的路徑規(guī)劃統(tǒng)計(jì)數(shù)據(jù)。

由表2可知，啟發(fā)因子更新方式改進(jìn)后的蟻群算法仿真出的平均路徑長(zhǎng)度比基本蟻群算法減少了17.6%，最短路徑長(zhǎng)度減少了16.8%。在平均收斂代數(shù)方面，改進(jìn)蟻群算法比基本蟻群算法減少了87.3%。在最小收斂代數(shù)方面，改進(jìn)蟻群算法比基本蟻群算法減少了91.8%。因此，在路徑長(zhǎng)度及收斂速度上，經(jīng)過啟發(fā)因子更新方式改進(jìn)后的算法優(yōu)于基本蟻群算法。

當(dāng)和取不同值時(shí)，在10×10柵格環(huán)境下，對(duì)經(jīng)過啟發(fā)因子更新方式改進(jìn)的蟻群算法執(zhí)行50次，路徑規(guī)劃統(tǒng)計(jì)結(jié)果見表3。

表3 當(dāng)a和b取不同值時(shí)，改進(jìn)蟻群算法路徑規(guī)劃統(tǒng)計(jì)結(jié)果

由表3分析可知，當(dāng)=1；=1，2，3時(shí)，對(duì)經(jīng)過啟發(fā)因子更新方式改進(jìn)的蟻群算法執(zhí)行50次得到的平均路徑長(zhǎng)度均為最短，在保證具有最短路徑的前提下，當(dāng)=3，=1時(shí)平均收斂代數(shù)及最小收斂代數(shù)最小，此時(shí)蟻群算法具有較好的收斂性能。與基本蟻群算法路徑統(tǒng)計(jì)結(jié)果相比，=3且=1時(shí)平均路徑長(zhǎng)度減少了17.6%，平均收斂代數(shù)減少了93.1%。

4.2 仿真2

運(yùn)用控制點(diǎn)轉(zhuǎn)移策略，對(duì)路徑規(guī)劃進(jìn)行平滑改進(jìn)，仿真結(jié)果如圖6和圖7所示。由圖6分析可知，在10×10柵格環(huán)境下，路徑規(guī)劃平滑改進(jìn)后最優(yōu)路徑長(zhǎng)度為13.677 3，比原有路徑長(zhǎng)度14.485 3減少了5.58%。改進(jìn)前累計(jì)轉(zhuǎn)彎角度為315.000 0°，改進(jìn)后累計(jì)轉(zhuǎn)彎角度為169.695 2°，減少了46.13%。

圖7在20×20柵格環(huán)境下，經(jīng)過路徑規(guī)劃平滑改進(jìn)后的路徑長(zhǎng)度為27.329 0，比原有路徑長(zhǎng)度28.041 6減少了2.54%。改進(jìn)前轉(zhuǎn)彎角度為360.000 0°，改進(jìn)后轉(zhuǎn)彎角度為147.479 3°，減少了59.03%。

采用控制點(diǎn)轉(zhuǎn)移策略后，平均路徑長(zhǎng)度減少量為4.28%，平均轉(zhuǎn)彎角度減少量為52.58%。平滑改進(jìn)前后數(shù)據(jù)對(duì)比見表4。

圖7 20×20柵格環(huán)境下平滑改進(jìn)前后的路徑規(guī)劃

表4 路徑平滑前后對(duì)比

5 結(jié)束語(yǔ)

針對(duì)蟻群算法解決路徑規(guī)劃問題時(shí)存在的收斂速度慢的缺點(diǎn)，對(duì)啟發(fā)因子矩陣初始值及更新方式進(jìn)行了改進(jìn)，與基本蟻群算法相比，改進(jìn)后平均路徑長(zhǎng)度減少了17.6%，平均收斂代數(shù)減少了93.1%；對(duì)于在柵格環(huán)境下機(jī)器人累計(jì)轉(zhuǎn)彎角度大的問題，提出了控制點(diǎn)轉(zhuǎn)移策略，通過對(duì)控制路徑走向的柵格中心點(diǎn)向柵格角頂點(diǎn)的轉(zhuǎn)移，進(jìn)一步縮短了路徑長(zhǎng)度，實(shí)現(xiàn)了路徑規(guī)劃的平滑改進(jìn)，平滑改進(jìn)后機(jī)器人的平均路徑長(zhǎng)度減少了4.28%，累計(jì)轉(zhuǎn)彎角度減少了52.58%。

[1] 栗紅生, 劉瑩. 復(fù)雜路徑下機(jī)器人路徑規(guī)劃優(yōu)化方法仿真[J]. 計(jì)算機(jī)仿真, 2014, 31(1): 407-411.

[2] 趙開新, 孫新領(lǐng), 王東署, 等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J]. 科技通報(bào), 2017, 33(9): 76-79.

[3] GONG Y J, CHEN E, ZHANG X L, et al. AntMapper: An ant colony-based map matching approach for trajectory-based applications [J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(2): 390-401.

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

[5] 張琦. 移動(dòng)機(jī)器人的路徑規(guī)劃與定位技術(shù)研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2014.

[6] DENG X Y, ZHANG L, LUO L. An improved ant colony optimization applied in robot path planning problem [J]. Journal of Computers, 2013, 8(3): 585-593.

[7] TANG B W, ZHU Z X, FANG Q, et al. Path planning and replanning for intelligent robot based on improved ant colony algorithm [J]. Applied Mechanics and Materials, 2013, 390: 495-499.

[8] 徐勝華, 宋樹祥, 佘果. 一種掃地機(jī)器人路徑規(guī)劃的改進(jìn)算法[J]. 測(cè)控技術(shù), 2017, 36(2): 120-123, 127.

[9] 張文強(qiáng), 張彥. 基于改進(jìn)蟻群算法的機(jī)器人三維空間路徑規(guī)劃[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2018(4): 73-75.

[10] 朱艷, 游曉明, 劉升, 等. 基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃問題研究[J/OL].計(jì)算機(jī)工程與應(yīng)用. [2018-05-22]. http://kns.cnki.net/kcms/detail/11.2127.TP. 20180313.0951.014.html.

[11] 王輝, 王景良, 朱龍彪, 等. 基于改進(jìn)蟻群算法的泊車系統(tǒng)路徑規(guī)劃[J]. 控制工程, 2018, 25(2): 253-258.

[12] 王志中. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J]. 機(jī)械設(shè)計(jì)與制造, 2018(1): 242-244.

[13] 張瑋, 馬焱, 趙捍東, 等. 基于改進(jìn)煙花-蟻群混合算法的智能移動(dòng)體避障路徑規(guī)劃[J/OL]. 控制與決策. [2018-07-03]. https://doi.org/10.13195/j.kzyjc.2017.0870.

[14] 王紅君, 徐軍, 趙輝, 等. 基于平滑蟻群算法的機(jī)器人路徑規(guī)劃[J]. 燕山大學(xué)學(xué)報(bào), 2017, 41(3): 278-282.

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

[16] 龔星宇, 常心坦, 賈澎濤, 等. 基于蟻群算法的井下救援路徑優(yōu)化方法[J]. 工礦自動(dòng)化, 2018, 44(3): 76-81.

[17] 顧軍華, 孟慧婕, 夏紅梅, 等. 基于改進(jìn)蟻群算法的多機(jī)器人路徑規(guī)劃研究[J]. 河北工業(yè)大學(xué)學(xué)報(bào), 2016, 45(5): 28-34.

[18] SHU J, WU L, HAN B, et al. Enhanced multi‐dimensional power network planning based on ant colony optimization [J]. International Transactions on Electrical Energy Systems, 2015, 25(7): 1204-1222.

[19] ZHANG W B, GONG X P, HAN G J, et al. An improved ant colony algorithm for path planning in one scenic area with many spots [J]. IEEE Access, 2017, 5: 13260-13269.

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

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

Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm

SUN Rui, ZHANG Wen-sheng

(School of Traffic and Transportation, Shijiazhuang Tiedao University, Shijiazhuang Hebei 050043, China)

A smooth path planning method based on improved ant colony algorithm is proposed for mobile robot in this paper.In order to overcome the disadvantage of slow convergence rate of ant colony algorithm in solving path planning problem,the initial value and updating method of the matrix of heuristic factors are improved. Compared with the results that the heuristic factor has not been improved, the average path length is reduced by 17.6%, and the average convergence algebra is decreased by 93.1%.The control point transfer strategy is proposed to solve the problem of large cumulative turning angle of the robot when obstacles exist in the grid environment.Based on the previous improvement,a smooth improvement of path planning is achieved by transferring the central point of grid to the vertex of grid. The path planning simulation results show that the average path length of the robot is decreased by 4.28% and the cumulative turning angle is reduced by 52.58%, compared with the non-smooth improvement.

ant colony algorithm; mobile robot; path planning; control point transfer strategy

TP 391

10.11996/JG.j.2095-302X.2019020344

A

2095-302X(2019)02-0344-07

2018-07-07；

2018-09-19

河北省重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(18390324D)；石家莊市科學(xué)技術(shù)研究與發(fā)展計(jì)劃項(xiàng)目(181130034A，191260411A)；石家莊鐵道大學(xué)研究生創(chuàng)新項(xiàng)目(YC2019044)

孫 瑞(1995-)，女，河北衡水人，碩士研究生。主要研究方向?yàn)橹悄軆?yōu)化算法。E-mail：sunr3617@163.com

張文勝(1971-)，男，寧夏隆德人，教授，博士。主要研究方向?yàn)榻煌ㄐ畔ⅰ-mail：zws@stdu.edu.cn