基于動(dòng)態(tài)反饋A*蟻群算法的平滑路徑規(guī)劃方法

黃 辰 費(fèi)繼友, 劉 洋 李 花 劉曉東

(1.大連交通大學(xué)機(jī)械工程學(xué)院， 大連 116028； 2.大連交通大學(xué)動(dòng)車運(yùn)用與維護(hù)工程學(xué)院， 大連 116028；3.釜慶國(guó)立大學(xué)工程學(xué)院， 釜山 608737)

基于動(dòng)態(tài)反饋A*蟻群算法的平滑路徑規(guī)劃方法

黃 辰1費(fèi)繼友1,2劉 洋3李 花2劉曉東2

(1.大連交通大學(xué)機(jī)械工程學(xué)院， 大連 116028； 2.大連交通大學(xué)動(dòng)車運(yùn)用與維護(hù)工程學(xué)院， 大連 116028；3.釜慶國(guó)立大學(xué)工程學(xué)院， 釜山 608737)

針對(duì)移動(dòng)機(jī)器人提出了一種基于動(dòng)態(tài)反饋A*蟻群算法的平滑路徑規(guī)劃方法。首先，為了克服蟻群算法收斂速度慢的缺點(diǎn)，提出了簡(jiǎn)化A*算法來(lái)優(yōu)化初始信息素設(shè)置以解決初次搜索的盲目性，并借鑒多策略進(jìn)化機(jī)制加強(qiáng)算法的全局搜索能力。其次，為了進(jìn)一步提高算法在路徑規(guī)劃中的適應(yīng)能力，解決陷入局部極小和停滯問(wèn)題，引入閉環(huán)反饋思想來(lái)實(shí)現(xiàn)參數(shù)的動(dòng)態(tài)自適應(yīng)調(diào)節(jié)。最后，結(jié)合三次B樣條曲線對(duì)所規(guī)劃的路徑進(jìn)行平滑處理，以滿足移動(dòng)機(jī)器人實(shí)際運(yùn)動(dòng)路徑的要求。通過(guò)仿真表明：與原蟻群算法相比，動(dòng)態(tài)反饋A*蟻群算法平均可減少10.4%的路徑成本和65.8%的計(jì)算時(shí)長(zhǎng)。同時(shí)，該算法在動(dòng)態(tài)和靜態(tài)環(huán)境中，均能快速規(guī)劃出一條光滑優(yōu)質(zhì)路徑。

路徑規(guī)劃； 蟻群算法； 動(dòng)態(tài)反饋； A*算法； B樣條曲線

引言

目前，路徑規(guī)劃成為移動(dòng)機(jī)器人控制領(lǐng)域的熱點(diǎn)之一[1-2]。除傳統(tǒng)的規(guī)劃方法，如人工勢(shì)場(chǎng)法[3]、柵格法等，啟發(fā)式智能方法由于其良好的學(xué)習(xí)能力也開(kāi)始應(yīng)用到移動(dòng)機(jī)器人的路徑規(guī)劃領(lǐng)域[4-8]。其中，蟻群算法(AC)由于具有并行性、強(qiáng)魯棒性等優(yōu)點(diǎn)在移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題的解決中得到廣泛應(yīng)用，但存在收斂速度慢，易陷入局部最優(yōu)以及初期信息素匱乏等現(xiàn)象，使得搜索比較盲目，導(dǎo)致收斂速度慢等問(wèn)題。近年來(lái)，大部分學(xué)者開(kāi)始研究對(duì)蟻群信息素更新和搜索策略的改進(jìn)[9-14]。但是，對(duì)于信息素初始化，大多采取平均分配原則，導(dǎo)致搜索時(shí)間加長(zhǎng)。同時(shí)，蟻群參數(shù)對(duì)規(guī)劃路徑的性能產(chǎn)生較大影響，目前大部分改進(jìn)的蟻群算法在迭代過(guò)程中使用固定的參數(shù)或采用預(yù)先設(shè)計(jì)好的分段算法參數(shù)，這種參數(shù)是開(kāi)環(huán)的，并不能動(dòng)態(tài)地反饋搜索過(guò)程，不能很好地適應(yīng)搜索空間中的不確定性。因此，解決參數(shù)優(yōu)化問(wèn)題的有效途徑之一是閉環(huán)反饋優(yōu)化。

本文提出一種基于動(dòng)態(tài)反饋A*蟻群算法的平滑動(dòng)態(tài)路徑規(guī)劃方法。首先，為提高算法搜索效率，以 A*算法的估價(jià)函數(shù)為評(píng)價(jià)標(biāo)準(zhǔn)，得到一條估價(jià)函數(shù)值相對(duì)最小的規(guī)劃路徑，增加此路徑上的初始信息素，從而優(yōu)化信息素初值。其次，采用多進(jìn)化策略加大搜索空間，防止局部最優(yōu)。同時(shí)，引入閉環(huán)反饋動(dòng)態(tài)自適應(yīng)調(diào)節(jié)算法參數(shù)，提高算法在動(dòng)態(tài)路徑規(guī)劃中的適應(yīng)能力，并解決算法的停滯問(wèn)題。最后，引入三次B樣條曲線對(duì)規(guī)劃路徑進(jìn)行平滑處理。

1 A*蟻群算法與多進(jìn)化機(jī)制

1.1 A*蟻群算法

蟻群算法在首次搜索時(shí)，由于地圖信息的匱乏，大多采用信息素均勻分布法，將各條路徑上的信息素初始化為1個(gè)常量C，從而造成算法在搜索初期由于環(huán)境未知而降低收斂速度，增加算法的搜索時(shí)間。為對(duì)初始信息素進(jìn)行優(yōu)化，提出利用簡(jiǎn)化的A*算法和地圖信息來(lái)設(shè)置初始信息素以加快算法初期的收斂速度，減少迭代次數(shù)，提高算法的實(shí)時(shí)性。

A*算法是一種經(jīng)典的啟發(fā)式搜索算法[15]，是靜態(tài)環(huán)境中求解最短路徑較為有效的直接搜索方法[16]。A*算法的估價(jià)函數(shù)為[17]

f(n)=g(n)+h(n)

(1)

其中

(2)

(3)

式中f(n)——節(jié)點(diǎn)n的估價(jià)函數(shù)g(n)——當(dāng)前節(jié)點(diǎn)n到起點(diǎn)s的實(shí)際代價(jià)h(n)——當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的預(yù)估代價(jià)

據(jù)此，簡(jiǎn)化A*算法的主要原理為借用A*算法的估價(jià)函數(shù)作為評(píng)價(jià)指標(biāo)，從起點(diǎn)出發(fā)，將以起點(diǎn)為中心的相鄰節(jié)點(diǎn)中的無(wú)障礙節(jié)點(diǎn)組成OPEN表，取估價(jià)函數(shù)值最小的節(jié)點(diǎn)放入CLOSE表中，再以此節(jié)點(diǎn)為中心，選估價(jià)函數(shù)值最小的節(jié)點(diǎn)放入CLOSE表中，從而迅速搜索到1條從起點(diǎn)到目標(biāo)點(diǎn)估價(jià)函數(shù)相對(duì)最小的路徑，即CLOSE表中節(jié)點(diǎn)所連接的路徑。簡(jiǎn)化A*算法中不需要考慮既在父節(jié)點(diǎn)又在新子節(jié)點(diǎn)鄰域內(nèi)的待選節(jié)點(diǎn)實(shí)際估價(jià)值g(n)的再檢查過(guò)程，即省略待選節(jié)點(diǎn)直接到父節(jié)點(diǎn)與通過(guò)新的子節(jié)點(diǎn)再到父節(jié)點(diǎn)的實(shí)際代價(jià)的比較過(guò)程。將f(n)作為評(píng)價(jià)函數(shù)得到的優(yōu)化路徑記為Rfbest，將這條路徑的初始信息素設(shè)為

τ(Rfbest)=kC(k>1)

(4)

其余路徑的初始信息素仍為常數(shù)C。本文將用簡(jiǎn)化A*算法來(lái)優(yōu)化初始信息素，稱為A*蟻群算法。

1.2 多策略進(jìn)化機(jī)制

為增加蟻群搜索空間，加大算法的隨機(jī)性以獲得全局最優(yōu)解，引入多策略進(jìn)化機(jī)制。

(5)

式中α——信息素啟發(fā)因子β——能見(jiàn)度啟發(fā)因子τ——信息素η——能見(jiàn)度或啟發(fā)信息Jk(r)——下一步允許選擇的柵格集

2 參數(shù)分析及動(dòng)態(tài)閉環(huán)調(diào)節(jié)

2.1 參數(shù)影響分析

蟻群算法的參數(shù)配置將會(huì)直接影響其處理實(shí)際問(wèn)題的能力[18-19]。在多策略A*蟻群算法中，有4個(gè)主要參數(shù)：q0為進(jìn)化選擇概率，即開(kāi)發(fā)(廣度)與探索(深度)間的調(diào)節(jié)概率，0

采用的2種環(huán)境地圖如圖1所示，其中，圖1a為較大整塊障礙物圖，圖1b為小塊分散障礙物圖，起點(diǎn)均為第1個(gè)柵格，終點(diǎn)均為第400 個(gè)柵格，螞蟻數(shù)量m為30。停止條件為連續(xù)3次循環(huán)搜索中最優(yōu)解的差異小于停止閾值。每組數(shù)據(jù)為5次試驗(yàn)數(shù)據(jù)的平均值。參數(shù)變化對(duì)路徑的影響結(jié)果如圖2和表1所示。

圖1 環(huán)境地圖Fig.1 Environmental maps

圖2 參數(shù)對(duì)路徑長(zhǎng)度的影響Fig.2 Influence of parameters on path length

參數(shù)環(huán)境1環(huán)境2最短路徑長(zhǎng)度最長(zhǎng)路徑長(zhǎng)度差值最短路徑長(zhǎng)度最長(zhǎng)路徑長(zhǎng)度差值測(cè)試范圍β28.627530.04171.414230.384930.97070.58581～15ρ28.627529.48110.853630.677831.36710.68930.1～0.9q028.627586.911858.284330.384994.254963.87000.1～1.0

參數(shù)選擇是耗費(fèi)時(shí)間的過(guò)程，因此希望能夠降低任務(wù)的復(fù)雜性，選擇能夠?qū)φ{(diào)節(jié)路線長(zhǎng)度產(chǎn)生最大影響的主要參數(shù)。從表1中可以看出，參數(shù)q0的變化對(duì)產(chǎn)生路徑長(zhǎng)度影響最大。分析表明，q0是主要影響因子。因此，在閉環(huán)調(diào)節(jié)中只需選擇參數(shù)q0進(jìn)行調(diào)節(jié)。

2.2 參數(shù)的動(dòng)態(tài)閉環(huán)調(diào)節(jié)

為提高蟻群算法在動(dòng)態(tài)及復(fù)雜環(huán)境中的適應(yīng)性，將改進(jìn)的蟻群算法與經(jīng)典閉環(huán)控制系統(tǒng)相結(jié)合，利用閉環(huán)反饋來(lái)動(dòng)態(tài)調(diào)節(jié)改進(jìn)蟻群算法中的參數(shù)q0，給出算法閉環(huán)控制框圖如圖3所示。

圖3 算法閉環(huán)控制框圖Fig.3 Algorithm framework of closed loop control

控制框架的核心在于反饋量的選取以及參數(shù)的調(diào)整策略。將本次迭代搜尋到的最短路徑長(zhǎng)度與前代最短路徑長(zhǎng)度差和前代長(zhǎng)度的比值作為反饋量。當(dāng)比值大于0時(shí)，說(shuō)明本次搜索的路徑區(qū)域解質(zhì)量較差，需要加大搜索，應(yīng)減小q0值，加大開(kāi)發(fā)力度；相反，當(dāng)比值小于0時(shí)，說(shuō)明找到了更優(yōu)路徑，此區(qū)域具有探索價(jià)值，應(yīng)加大探索力度，此時(shí)應(yīng)增加q0值。而當(dāng)比值為0時(shí)，需要對(duì)初次比值連續(xù)為1的次數(shù)進(jìn)行計(jì)數(shù)并設(shè)定一個(gè)停滯門限，當(dāng)累加計(jì)數(shù)超過(guò)此門限時(shí)，極有可能陷入局部極小。此時(shí)，應(yīng)減小q0值，通過(guò)q0的調(diào)整而跳出極小區(qū)。具體的調(diào)整策略為

(6)

式中Nmax——停滯門限 num——種群出現(xiàn)連續(xù)停滯的代數(shù)累加ε——調(diào)整因子，0<ε<1

為得到全局最優(yōu)解，q0不應(yīng)超出其取值范圍，應(yīng)對(duì)q0的取值范圍進(jìn)行約束，0

3 三次B樣條曲線平滑路徑

路徑規(guī)劃是創(chuàng)建一個(gè)機(jī)器人從出發(fā)點(diǎn)到達(dá)目標(biāo)點(diǎn)的免于碰撞的最優(yōu)有序序列，為軌跡跟蹤提供路線支持。因此，所規(guī)劃的路徑應(yīng)滿足平滑性的要求，盡量保證規(guī)劃出的路徑與實(shí)際運(yùn)動(dòng)路線相同。由于蟻群算法采用柵格表示環(huán)境地圖，因此會(huì)在轉(zhuǎn)彎處產(chǎn)生尖峰。

B樣條曲線具有參數(shù)表達(dá)式簡(jiǎn)單、局部修改性、凸包性等優(yōu)點(diǎn)，因此， B 樣條曲線在工程設(shè)計(jì)中得到廣泛應(yīng)用[20]。由于三次B樣條曲線在連接處二階連續(xù)，將其用于路徑規(guī)劃時(shí)，速度和加速度都是連續(xù)的。因此，采用三次B樣條來(lái)平滑蟻群已規(guī)劃出的路徑。

3.1 三次B樣條曲線方程

一般，n次均勻B樣條曲線的數(shù)學(xué)表達(dá)式為[17]

(7)

其中

(8)

式中Pi——給定n+1個(gè)控制點(diǎn)Pi的坐標(biāo)Fi,n(t)——n次B樣條基函數(shù)

當(dāng)n=3時(shí)，則有三次B樣條曲線的基函數(shù)為

(9)

因此，三次B樣條曲線方程為

(10)

用三次B樣條曲線對(duì)尖峰路徑進(jìn)行光滑處理，圖4為由9個(gè)控制點(diǎn)生成的光滑曲線。

圖4 B樣條曲線平滑結(jié)果Fig.4 Smooth result of B spline curve

3.2 三次B樣條曲線平滑路徑

三次B樣條曲線對(duì)路徑的平滑是在動(dòng)態(tài)反饋A*蟻群算法得到最優(yōu)路徑后進(jìn)行，也可稱為路徑的后處理環(huán)節(jié)，其流程如圖5所示。

圖5 B樣條曲線的平滑流程Fig.5 Smoothing process of B spline curve

4 仿真

從4方面對(duì)本文算法的性能進(jìn)行仿真分析：①A*蟻群與原蟻群算法仿真比較。②動(dòng)態(tài)反饋A*蟻群算法整體性能與原蟻群算法、蟻群系統(tǒng)(ACS)[12]比較。③算法迭代過(guò)程中出現(xiàn)靜態(tài)障礙物干擾的路徑規(guī)劃。④動(dòng)態(tài)障礙物的路徑規(guī)劃。借助Matlab 2014a軟件進(jìn)行仿真，在2.3 GHz處理器、4 GB內(nèi)存的Windows 10計(jì)算機(jī)上進(jìn)行。

4.1 A*蟻群算法與原蟻群算法比較

對(duì)初始信息素優(yōu)化的A*蟻群算法與原蟻群算法進(jìn)行對(duì)比仿真。仿真初始條件設(shè)置如下：蟻群大小m=30，最大迭代次數(shù)NC-max=40，α=1，ρ=0.1，β=6，信息量常數(shù)Q=14；地圖采用3.1節(jié)中的環(huán)境1。圖6為原蟻群算法和A*蟻群算法路徑圖的對(duì)比結(jié)果。20次仿真的平均最短路線長(zhǎng)度與迭代次數(shù)的關(guān)系的比較結(jié)果如圖7所示。路徑規(guī)劃仿真20次比較的平均結(jié)果如表2所示。

圖6 A*蟻群算法與原蟻群算法路徑圖Fig.6 Path planning of A* ant colony and original ant colony algorithms

圖7 路徑長(zhǎng)度與迭代次數(shù)的關(guān)系Fig.7 Relationship between path length and number of iterations

由表2可以得出， A*蟻群算法通過(guò)優(yōu)化初始信息素，從而加快原蟻群算法的收斂速度，減少迭代次數(shù)，規(guī)劃出的最優(yōu)路徑質(zhì)量要高于原蟻群算法，因此，提出的A*蟻群算法提高了原蟻群算法的實(shí)時(shí)性和規(guī)劃效率。

4.2 動(dòng)態(tài)反饋的A*蟻群算法與原蟻群算法、蟻群系統(tǒng)的比較

仿真初始條件如下：m=45，NC-max=50，α=1，ρ=0.1，β=6，q0=0.8，k=5，Q=14，在30×30的

表2 信息素初始化優(yōu)化對(duì)比結(jié)果

柵格地圖環(huán)境中進(jìn)行測(cè)試，利用3種方法進(jìn)行從起點(diǎn)到終點(diǎn)的路徑規(guī)劃，圖8為本文提出的動(dòng)態(tài)反饋的A*蟻群算法規(guī)劃出的路徑和采用B曲線平滑后的路徑(采用三次B樣條曲線)。圖9為在迭代過(guò)程中主要控制參數(shù)q0的變化情況。

圖8 動(dòng)態(tài)反饋A*蟻群算法的平滑路徑圖Fig.8 Smooth path planning of A* ant colony algorithms optimization based on dynamic feedback

圖9 q0變化曲線Fig.9 Variation curve of parameter q0

進(jìn)行20次路徑規(guī)劃的仿真測(cè)試，得到3種算法的平均結(jié)果見(jiàn)圖10和表3。

圖10 路徑長(zhǎng)度與迭代次數(shù)的關(guān)系Fig.10 Relationship between path length and number of iterations

算法平均最短路徑長(zhǎng)度平均耗時(shí)/s原蟻群算法50.355445.1蟻群系統(tǒng)算法47.941232.5本文算法45.112815.4

從表3中可以看出，動(dòng)態(tài)反饋的A*蟻群算法所規(guī)劃出的路徑長(zhǎng)度平均值要優(yōu)于原蟻群算法和蟻群系統(tǒng)算法所得的最優(yōu)解，表明算法具有較好的穩(wěn)定性且收斂速度較快，運(yùn)行時(shí)間短。因此，本文算法具有較好的尋優(yōu)能力和更快的收斂速度。該算法與原蟻群算法相比，平均可減少10.4%的路徑成本和65.8%的計(jì)算時(shí)長(zhǎng)。另外，與蟻群系統(tǒng)算法相比，平均可減少5.9%的路徑成本和52.6%的計(jì)算時(shí)長(zhǎng)。

4.3 靜態(tài)障礙物干擾下的路徑規(guī)劃

圖11 靜態(tài)干擾下的路徑規(guī)劃圖Fig.11 Path planning under static interference

在柵格地圖中，初始條件設(shè)置如下：m=30，ρ=0.1，α=1，β=6，NC-max=40，q0=0.7。如圖11所示，在第10次進(jìn)化迭代后加入障礙物(在圖11中用其它顏色標(biāo)記)，在第10代前規(guī)劃得到路徑1，在10代后加入靜態(tài)障礙物得到路徑2，紅色曲線為B曲線平滑后的路徑，采用三次B樣條曲線。另外，路徑長(zhǎng)度與迭代次數(shù)的關(guān)系如圖12所示。從圖12可以看出，由于A*蟻群算法優(yōu)化了初始信息素的設(shè)置，使路徑初次搜索速度較快。在10次迭代后加入了靜態(tài)障礙物，最優(yōu)路徑的長(zhǎng)度也相應(yīng)發(fā)生了波動(dòng)，但由于閉環(huán)反饋參數(shù)調(diào)節(jié)參數(shù)q0，使算法快速收斂。由此可知，在路徑搜索過(guò)程中，加入靜態(tài)障礙物，能快速找到最優(yōu)路徑，具有較強(qiáng)的魯棒性。

圖12 路徑長(zhǎng)度變化曲線Fig.12 Path length variation curve

4.4 存在動(dòng)態(tài)障礙物的路徑規(guī)劃

仿真初始條件設(shè)置如下：m=30，ρ=0.1，α=1，β=6，NC-max=40，q0=0.8。動(dòng)態(tài)障礙物是矩形障礙物，沿y軸正向做速度為1柵格/s的勻速運(yùn)動(dòng)。圖13a為未發(fā)生碰撞時(shí)的路徑圖，圖13b為碰撞時(shí)躲避動(dòng)態(tài)障礙物的路徑圖。可以看出，本文算法能躲避動(dòng)態(tài)障礙物。

圖13 存在動(dòng)態(tài)障礙物的路徑規(guī)劃圖Fig.13 Path planning under dynamic obstacles

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

蟻群算法作為一種基于生物習(xí)性的啟發(fā)式進(jìn)化方法，在移動(dòng)機(jī)器人路徑規(guī)劃中的適用性和自進(jìn)化能力需要得到進(jìn)一步改善。因此，提出了一種基于動(dòng)態(tài)反饋的A*蟻群算法。為進(jìn)一步提升算法在搜索過(guò)程中的動(dòng)態(tài)特性，將蟻群算法的優(yōu)化目標(biāo)作為反饋信息引入到蟻群算法中，將反饋信息經(jīng)過(guò)處理后動(dòng)態(tài)調(diào)節(jié)算法參數(shù)q0，通過(guò)q0的變化來(lái)控制3種策略進(jìn)化的比例，以此來(lái)平衡算法的局部和全局搜索能力。同時(shí)，為加快運(yùn)行效率，引入簡(jiǎn)化的A*算法來(lái)對(duì)初始信息素進(jìn)行優(yōu)化設(shè)置。其次，借助B樣條曲線對(duì)已規(guī)劃路徑進(jìn)行進(jìn)一步平滑優(yōu)化，以滿足實(shí)際中移動(dòng)機(jī)器人軌跡跟蹤的要求。仿真結(jié)果表明，提出的規(guī)劃算法與原蟻群算法和蟻群系統(tǒng)算法相比，具有更高的收斂速度和收斂質(zhì)量。同時(shí)，在搜索過(guò)程中存在靜態(tài)障礙物干擾和動(dòng)態(tài)環(huán)境時(shí)，能夠快速地規(guī)劃出一條較優(yōu)且平滑的路徑，具有較好的適應(yīng)性和魯棒性。

1 朱大奇，顏明重. 移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J]. 控制與決策，2010, 25(7): 961-967. ZHU Daqi， YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7): 961-967. (in Chinese)

2 ZHU Q, HU J, CAI W, et al. A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm[J]. Applied Soft Computing, 2011, 11(8): 4667-4676.

3 韓永，劉國(guó)棟. 動(dòng)態(tài)環(huán)境下基于人工勢(shì)場(chǎng)的移動(dòng)機(jī)器人運(yùn)動(dòng)規(guī)劃[J]. 機(jī)器人，2006, 28(1): 45-49. HAN Yong, LIU Guodong. Mobile robot motion planning based on potential field in dynamic environment[J]. Robot, 2006, 28(1): 45-49. (in Chinese)

4 MANIKAS W, ASHENVVI K, WAINWRIGHT R. Genetic algorithms for autonomous robot navigation[J]. IEEE Instrumentation & Measurement Magazine, 2008, 10(6): 26-31.

5 NI B, CHEN X. New approach of neural network for robot path planning[C]∥2004 IEEE International Conference on Systems, Man and Cybernetics, 2004: 735-739.

6 吳憲祥，郭寶龍，王娟. 基于粒子群三次樣條優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃算法[J]. 機(jī)器人，2009, 31(6): 556-560. WU Xianxiang, GUO Baolong, WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. Robot, 2009, 31(6): 556-560. (in Chinese)

7 GARRO B A, SOSSA H, VAZQUEZ R A. Evolving ant colony system for optimizing path planning in mobile robots[C]∥ IEEE Electronics, Robotics and Automotive Mechanics Conference, 2007: 444-449.

8 WANG Y, YANG Y, YUAN X, et al. Autonomous mobile robot navigation system designed in dynamic environment based on transferable belief model[J]. Measurement, 2011, 44(8): 1389-1405.

9 劉建華，楊建國(guó)，劉華平，等. 基于勢(shì)場(chǎng)蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015, 46(9): 18-27. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20150903&flag=1.DOI:10.6041/j.issn.1000-1298.2015.09.003. LIU Jianhua, YANG Jianguo, LIU Huaping, et al. Robot global path planning based on ant colony optimization with artificial potential field[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(9): 18-27. (in Chinese)

10 王沛棟，馮祖洪，黃新. 一種改進(jìn)的機(jī)器人路徑規(guī)劃蟻群算法[J]. 機(jī)器人，2008, 30(6): 554-560. WANG Peidong, FENG Zuhong, HUANG Xin. An improved ant colony algorithm for mobile robot path planning[J]. Robot, 2008, 30(6): 554-560. (in Chinese)

11 趙娟平，高憲文，符秀輝，等. 移動(dòng)機(jī)器人路徑規(guī)劃的改進(jìn)蟻群優(yōu)化算法[J]. 控制理論與應(yīng)用，2011, 28(4): 457-461. ZHAO Juanping, GAO Xianwen, FU Xiuhui, et al. Improved ant colony algorithm of path planning for mobile robot[J]. Control Theory & Application, 2011, 28(4): 457-461. (in Chinese)

12 DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.

13 郭宗環(huán), 謝志江, 宋代平,等. 基于改進(jìn)蟻群算法的風(fēng)洞試驗(yàn)俯仰機(jī)構(gòu)運(yùn)動(dòng)誤差優(yōu)化[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 2016, 47(7):375-381. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160751&journal_id=jcsam.DOI:10.6041/j.issn.1000-1298.2016.07.051. GUO Zonghuan, XIE Zhijiang, SONG Daiping, et al. Error optimization of pitching mechanism motion in wind tunnel test based on improved ant colony algorithm[J/OL].Transactions of the Chinese Society for Agricultural Machinery,2016,47(7):375-381. (in Chinese)

14 吳小勇, 謝志江, 宋代平,等. 基于改進(jìn)蟻群算法的3-PPR并聯(lián)機(jī)構(gòu)位置正解研究[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 2015, 46(7):339-344. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20150748&flag=1.DOI:10.6041/j.issn.1000-1298.2015.07.048. WU Xiaoyong, XIE Zhijiang, SONG Daiping, et al. Forward kinematics of 3-PPR parallel mechanism based on improved ant colony algorithm[J/OL].Transactions of the Chinese Society for Agricultural Machinery, 2015,46(7): 339-344. (in Chinese)

15 王殿君. 基于改進(jìn)A*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J]. 清華大學(xué)學(xué)報(bào):自然科學(xué)版，2012, 52(8): 1085-1089. WANG Dianjun. Indoor mobile-robot path planning based on an improved A*algorithm[J]. Journal of Tsinghua University: Science and Technology, 2012, 52(8): 1085-1089. (in Chinese)16 顧青，豆風(fēng)鉛，馬飛. 基于改進(jìn)A*算法的電動(dòng)車能耗最優(yōu)路徑規(guī)劃[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015, 46(12): 316-322.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20151243&flag=1.DOI:10.6041/j.issn.1000- 1298.2015.12.043. GU Qing, DOU Fengqian, MA Fei. Energy optimal path planning of electric vehicle based on improved A*algorithm[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(12): 316-322. (in Chinese)

17 馬飛, 楊皞屾, 顧青,等. 基于改進(jìn)A*算法的地下無(wú)人鏟運(yùn)機(jī)導(dǎo)航路徑規(guī)劃[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 2015, 46(7):303-309. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20150743&flag=1.DOI:10.6041/jissn.1000-1298.2015.07.043. MA Fei, YANG Haoshen, GU Qing, et al. Navigation path planning of unmanned underground LHD based on improved A*algorithm[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(7): 303-309. (in Chinese)

18 杜鵬楨，唐振民，孫研. 一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問(wèn)題求解[J]. 控制與決策，2014(10): 1729-1736. DU Pengzhen, TANG Zhenmin, SUN Yan. An object-oriented multi-role ant colony optimization algorithm for solving TSP problem[J]. Control and Decision, 2014(10): 1729-1736. (in Chinese)

19 史恩秀，陳敏敏，李俊，等. 基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014, 45(6):53-57. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20140609&flag=1.DOI:10.6041/j.issn.1000-1298.2014.06.009. SHI Enxiu, CHEN Minmin, LI Jun, et al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6): 53-57. (in Chinese)

20 趙彤，呂強(qiáng)，張輝，等. 三次均勻B樣條曲線高速實(shí)時(shí)插補(bǔ)研究[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2008, 14(9): 1830-1836. ZHAO Tong, Lü Qiang, ZHANG Hui, et al. High-speed real-time interpolation of cubic uniform B-spline curve[J]. Computer Integrated Manufacturing Systems, 2008, 14(9): 1830-1836. (in Chinese)

Smooth Path Planning Method Based on Dynamic Feedback A*Ant Colony Algorithm

HUANG Chen1FEI Jiyou1,2LIU Yang3LI Hua2LIU Xiaodong2

(1.CollegeofMechanicalEngineering,DalianJiaotongUniversity,Dalian116028,China2.CollegeofBulletTrainApplicationandMaintenanceEngineering,DalianJiaotongUniversity,Dalian116028,China3.CollegeofEngineering,PukyongNationalUniversity,Pusan608737,Korea)

A smooth path planning method for mobile robot with A*ant colony optimization was proposed based on dynamic feedback for mobile robot. First of all, in order to overcome the disadvantage about slow convergence speed of ant colony algorithm, simplified A*algorithm was presented to optimize the initial pheromone settings, which was able to solve the blindness of the first search. In this step, the planning path with the minimum value of the valuation function was obtained by the evaluation function of A*algorithm. And the presented multi-evolutionary strategy mechanism which could increase search space was used to strengthen the global search ability of the algorithm. Secondly, in order to further improve the adaptability of algorithm about the problem of local minimum and stagnation in the path planning, the key parameters of the algorithm were systematically analyzed and the closed-loop feedback idea was adopted to adjust the parameters of ant colony optimization algorithm dynamically. Finally, combining with the cubic B spline curve method, the planning path was smoothed to meet the practical movement route of mobile robot. The simulation experiment results showed that compared with traditional ant colony (AC), A*ant colony optimization based on dynamic feedback could reduce 10.4% of the average path cost and shorten 65.8% of the computing time in average. In addition, compared with ant colony system (ACS), the average path cost could be reduced by 5.9%, the calculation time could be shortened by 52.6%. The improved ant colony optimization algorithm could plan a smooth and high quality path in both the dynamic and static environments.

path planning; ant colony algorithm; dynamic feedback; A*algorithm; B spline curve

10.6041/j.issn.1000-1298.2017.04.004

2016-07-19

2016-08-30

國(guó)家自然科學(xué)基金項(xiàng)目(51376028)和“十二五”國(guó)家科技支撐計(jì)劃項(xiàng)目(2015BAF20B02)

黃辰(1982—)，女，工程師，博士生，主要從事運(yùn)動(dòng)控制研究，E-mail： huangchen054@163.com

費(fèi)繼友(1964—)，男，教授，博士生導(dǎo)師，主要從事現(xiàn)代測(cè)試技術(shù)研究，E-mail： fjy@djtu.edu.cn

TP391.41

A

1000-1298(2017)04-0034-07