基于改進(jìn)蟻群與動(dòng)態(tài)窗口法的AGV動(dòng)態(tài)路徑規(guī)劃

楊 周，劉海濱

北京工業(yè)大學(xué) 材料與制造學(xué)部，北京 100124

路徑規(guī)劃是自動(dòng)導(dǎo)引車（automatic guided vehicle，AGV）研究領(lǐng)域的一個(gè)重要課題，其目的是在有障礙物約束的環(huán)境下，根據(jù)已知的起點(diǎn)與終點(diǎn)，以最短路徑、最短時(shí)間等為目標(biāo)尋找一條最優(yōu)或接近最優(yōu)的安全、無(wú)障礙路徑[1-2]。根據(jù)應(yīng)用場(chǎng)景的不同，可將路徑規(guī)劃算法分為全局靜態(tài)路徑規(guī)劃算法和局部動(dòng)態(tài)路徑規(guī)劃算法。全局靜態(tài)路徑規(guī)劃算法主要應(yīng)用于全局信息已知的靜態(tài)環(huán)境，常用的算法有Dijkstra算法[3]、A*算法[4]、蟻群算法[5]等；局部動(dòng)態(tài)路徑規(guī)劃算法主要應(yīng)用于全局信息未知或部分已知的動(dòng)態(tài)環(huán)境，常用的算法有動(dòng)態(tài)窗口法[6]、強(qiáng)化學(xué)習(xí)[7]等。

蟻群算法因具有良好的搜索能力、正反饋特性、并行計(jì)算、易與其他算法融合等特性，在全局靜態(tài)路徑規(guī)劃中得到大量應(yīng)用。但傳統(tǒng)蟻群算法也存在搜索時(shí)間長(zhǎng)、易陷于局部最優(yōu)、前期盲目搜索導(dǎo)致收斂性差等缺陷。葛志遠(yuǎn)等[8]針對(duì)傳統(tǒng)蟻群算法搜索效率低，耗時(shí)長(zhǎng)等問(wèn)題，通過(guò)改進(jìn)啟發(fā)函數(shù)確定搜索方向并利用優(yōu)勝劣汰機(jī)制更新全局信息素，保證算法多樣性的同時(shí)提高算法收斂速度；王曉燕等[9]針對(duì)傳統(tǒng)蟻群算法各節(jié)點(diǎn)初始信息素均勻分布導(dǎo)致算法初期搜索范圍大，收斂性差等問(wèn)題，提出初始信息素不均衡分配策略，降低了初期搜索盲目性，提高了算法搜索效率。

動(dòng)態(tài)窗口法是常用的局部動(dòng)態(tài)路徑規(guī)劃算法，具有很好的躲避動(dòng)態(tài)障礙物能力，可以實(shí)時(shí)在線路徑規(guī)劃，且路徑較為平滑，符合AGV運(yùn)動(dòng)特征。但由于缺少全局信息的指導(dǎo)，規(guī)劃路徑質(zhì)量較差，且經(jīng)常無(wú)法到達(dá)目標(biāo)點(diǎn)。殷紹偉等[10]利用改進(jìn)的A*算法改進(jìn)蟻群算法，然后融合滾動(dòng)窗口法進(jìn)行局部實(shí)時(shí)路徑規(guī)劃，最后使用貝塞爾曲線對(duì)路徑進(jìn)行平滑度處理，使路徑更加接近AGV實(shí)際運(yùn)動(dòng)特征；槐創(chuàng)鋒等[11]將傳統(tǒng)A*算法的3×3搜索領(lǐng)域擴(kuò)展到7×7，解決了傳統(tǒng)A*算法折點(diǎn)多，路徑不平滑的問(wèn)題，然后根據(jù)全局最優(yōu)路徑設(shè)計(jì)動(dòng)態(tài)窗口評(píng)價(jià)函數(shù)，實(shí)現(xiàn)了機(jī)器人在復(fù)雜環(huán)境下的實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃。

由上述文獻(xiàn)可知：全局靜態(tài)路徑規(guī)劃算法可以有效利用全局信息規(guī)劃出全局最優(yōu)路徑，但無(wú)法躲避動(dòng)態(tài)障礙物；局部動(dòng)態(tài)路徑規(guī)劃算法可以實(shí)時(shí)在線規(guī)劃路徑，有效躲避動(dòng)態(tài)障礙物，但由于缺少全局信息，易陷入局部最優(yōu)解，經(jīng)常出現(xiàn)無(wú)法到達(dá)目標(biāo)點(diǎn)的現(xiàn)象。針對(duì)這兩類算法的缺陷，許多學(xué)者將兩類算法融合，并在實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃方面取得了較好的效果。為在動(dòng)態(tài)環(huán)境中實(shí)時(shí)規(guī)劃全局最優(yōu)路徑，本文參考融合思想提出了一種結(jié)合改進(jìn)蟻群算法和動(dòng)態(tài)窗口法的全局動(dòng)態(tài)路徑規(guī)劃算法。首先，對(duì)蟻群算法提出改進(jìn)：初始信息素不均勻、雙向分布，為蟻群算法雙向搜索提供大體方向；引入放大系數(shù)A增大相鄰柵格啟發(fā)信息差異，增大螞蟻選擇更優(yōu)節(jié)點(diǎn)的概率；更新信息素選擇最優(yōu)路徑時(shí)考慮轉(zhuǎn)彎次數(shù)的影響，得到更平滑的路徑，提升AGV運(yùn)行效率。然后，設(shè)計(jì)新的動(dòng)態(tài)窗口法距離評(píng)價(jià)子函數(shù)并動(dòng)態(tài)設(shè)置AGV初始航向角。最后，提取改進(jìn)蟻群算法規(guī)劃的全局最優(yōu)路徑上的轉(zhuǎn)折點(diǎn)作為改進(jìn)動(dòng)態(tài)窗口法的子目標(biāo)點(diǎn)，引導(dǎo)動(dòng)態(tài)窗口法沿著全局最優(yōu)路徑方向進(jìn)行實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃，最終實(shí)現(xiàn)有效躲避動(dòng)態(tài)障礙物的同時(shí)規(guī)劃全局最優(yōu)路徑。

1 蟻群算法及改進(jìn)

1.1 蟻群算法工作原理

蟻群算法是一種來(lái)源于自然界的智能隨機(jī)搜索算法，有很強(qiáng)發(fā)現(xiàn)較優(yōu)解的能力[12]。其工作原理為螞蟻在覓食過(guò)程中通過(guò)釋放信息素進(jìn)行群體間信息傳遞，信息素濃度與路徑長(zhǎng)度成反比，濃度越高表示路徑越短，該路徑被其他螞蟻選擇的概率就越高，通過(guò)這種正反饋機(jī)制能夠很快搜索出到達(dá)目標(biāo)位置的無(wú)碰撞最優(yōu)路徑。

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

1.2.1 初始信息素不均勻、雙向分布

傳統(tǒng)蟻群算法初始信息素采用均勻分布的方法，簡(jiǎn)單易行，但各柵格信息素濃度相同導(dǎo)致算法初期存在盲目搜索，收斂性差等問(wèn)題[13]。由于雙向搜索策略能大大提高算法全局搜索能力、加快前期搜索效率、增大前期有效解，因此本文在基于雙向搜索策略下提出初始信息素不均勻、雙向分布，為蟻群雙向搜索提供大體方向，避免算法初期盲目搜索、收斂性差等問(wèn)題，并滿足任意起點(diǎn)與終點(diǎn)的應(yīng)用場(chǎng)景。

假設(shè)AGV的起點(diǎn)坐標(biāo)為( xS,yS)，終點(diǎn)坐標(biāo)為( xE,yE)，則過(guò)起點(diǎn)與終點(diǎn)的直線可以用方程L表示：

式中，k為連接起點(diǎn)與終點(diǎn)的直線斜率；q為初始信息素均勻分布時(shí)的初始值；i為柵格點(diǎn)數(shù)；qi為改進(jìn)后各柵格信息素初始值，d為節(jié)點(diǎn)i到方程L的距離。

1.2.2 改進(jìn)啟發(fā)信息函數(shù)

傳統(tǒng)蟻群算法的啟發(fā)信息函數(shù)ηij與柵格i和柵格j之間的距離成反比，但相鄰柵格之間的距離差異很小，對(duì)路徑搜索的引導(dǎo)作用不大。目前，對(duì)有效的改進(jìn)是將螞蟻下一可選柵格到終點(diǎn)的距離與當(dāng)前柵格到下一可選柵格的距離的加權(quán)和倒數(shù)作為啟發(fā)信息函數(shù)[14]。該方法雖然考慮當(dāng)前柵格轉(zhuǎn)移到下一柵格所付出的代價(jià)，但相鄰柵格距離差異較小，對(duì)整體的啟發(fā)信息影響也不大。為此，本文引入放大系數(shù)A來(lái)增大相鄰柵格的啟發(fā)信息差異，從而增大螞蟻選擇更短節(jié)點(diǎn)的概率。

式中，ηij為啟發(fā)信息函數(shù)，表示螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度；dij為節(jié)點(diǎn)i到下一節(jié)點(diǎn)j的歐氏距離；djE為下一節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)E的歐式距離；A為放大系數(shù)；μ為常數(shù)。

1.2.3 改進(jìn)信息素更新規(guī)則

傳統(tǒng)蟻群算法采用全局信息素更新方式，只有最短路徑上信息素被更新，雖然可以很好地利用最優(yōu)解信息，但蟻群會(huì)過(guò)早集中在同一條路徑上，降低算法的全局搜索能力，易陷入局部最優(yōu)解。另外，在更新最短路徑上的信息素時(shí)，很少有人考慮到最短路徑可能并非只有一條，大多只更新其中一條最短路徑上信息素，可能會(huì)丟失最優(yōu)解（本文定義的最優(yōu)解為路徑長(zhǎng)度最短，轉(zhuǎn)彎次數(shù)最少的路徑）。針對(duì)上述問(wèn)題，本文提出所有到達(dá)終點(diǎn)的路徑都進(jìn)行信息素更新，并找到所有的最短路徑，然后在額外獎(jiǎng)勵(lì)最優(yōu)路徑時(shí)首次引入轉(zhuǎn)彎次數(shù)影響因素（轉(zhuǎn)彎次數(shù)的增加會(huì)大大降低AGV運(yùn)行時(shí)的工作效率，過(guò)于頻繁地轉(zhuǎn)向還會(huì)加速AGV的損耗，縮短使用壽命），選擇轉(zhuǎn)彎次數(shù)最少的最短路徑作為最優(yōu)路徑更新信息素，從而得到平滑度更高，更符合AGV運(yùn)行特征的路徑。改進(jìn)后的信息素更新公式為：

式中，ρ為信息素?fù)]發(fā)系數(shù)，0＜ρ≤1；τij表示t時(shí)刻信息素；Δτij為信息素增量，初始時(shí)刻Δτij=0；Q為信息素總量；Δτbestij為最優(yōu)路徑上的信息素增量；Lm為到達(dá)終點(diǎn)的路徑長(zhǎng)度；Lbest為最優(yōu)路徑長(zhǎng)度。

2 動(dòng)態(tài)窗口法及改進(jìn)

2.1 動(dòng)態(tài)窗口法基本原理

動(dòng)態(tài)窗口法[15]是在充分考慮到AGV自身機(jī)械特性限制以及環(huán)境對(duì)速度的約束下，在速度二維空間中采樣多組速度對(duì)（線速度、角速度），在一定時(shí)間間隔內(nèi)同時(shí)模擬AGV在這些速度對(duì)下的軌跡。獲取多組可行模擬軌跡后，根據(jù)設(shè)計(jì)的評(píng)價(jià)函數(shù)，AGV以最優(yōu)模擬軌跡所對(duì)應(yīng)的速度對(duì)，完成局部路徑規(guī)劃。

2.1.1 速度組采樣

在速度空間中存在無(wú)窮多組速度對(duì)(v,ω)，根據(jù)AGV自身限制及環(huán)境因素，對(duì)采樣速度范圍進(jìn)行約束：

（1）速度約束

設(shè)AGV初始狀態(tài)下的速度為Vs，則：

式中，v、w分別表示速度和角速度；vmin、vmax和wmin、wmax分別表示速度和加速度最小值與最大值。

（2）最大加速度約束

由于電機(jī)力矩有限，存在最大加速度限制，因此使得AGV軌跡的前向模擬周期內(nèi)，存在一個(gè)動(dòng)態(tài)窗口vd，該窗口的速度集合是AGV在下一個(gè)時(shí)間間隔內(nèi)實(shí)際能夠達(dá)到的速度，則：

式中，vn、wn分別表示AGV當(dāng)前狀態(tài)下的速度與角速度；a、b分別表示AGV的加速度與角加速度。

（3）制動(dòng)距離約束

為保證AGV的運(yùn)行安全，在最大減速度下，當(dāng)前速度應(yīng)能在撞到障礙物前減速為0，即：

式中，d為速度(v,w)對(duì)應(yīng)軌跡終點(diǎn)到障礙物最近的距離。

2.1.2 設(shè)計(jì)評(píng)價(jià)函數(shù)

動(dòng)態(tài)窗口法評(píng)價(jià)函數(shù)設(shè)計(jì)準(zhǔn)則是AGV盡量避開(kāi)障礙物，朝向目標(biāo)快速前進(jìn)。設(shè)計(jì)的評(píng)價(jià)函數(shù)為：

式中，head( v,w)為方向角評(píng)價(jià)子函數(shù)，表示在當(dāng)前速度下，模擬軌跡終點(diǎn)方向與目標(biāo)點(diǎn)之間的方向角偏差；dist( v,w)為距離評(píng)價(jià)子函數(shù)，表示在當(dāng)前速度下，模擬軌跡終點(diǎn)到障礙物最近的距離；vel( v,w)為當(dāng)前速度大小評(píng)價(jià)子函數(shù)；σ為平滑函數(shù)；γ、ε、φ為各評(píng)價(jià)子函數(shù)加權(quán)系數(shù)。

2.2 改進(jìn)動(dòng)態(tài)窗口法

2.2.1 改進(jìn)距離評(píng)價(jià)子函數(shù)dist( v,w)

傳統(tǒng)距離評(píng)價(jià)子函數(shù)dist(v,w)，并未考慮模擬軌跡其余點(diǎn)到障礙物的距離，這可能會(huì)出現(xiàn)模擬軌跡終點(diǎn)繞開(kāi)了移動(dòng)障礙物，但軌跡上的其余點(diǎn)與移動(dòng)障礙物發(fā)生了碰撞的情況，如圖1所示。針對(duì)這種情況，本文提出了改進(jìn)的距離評(píng)價(jià)子函數(shù)，以模擬軌跡上所有點(diǎn)到障礙物的最小距離為評(píng)價(jià)距離，di st越大，表示AGV離障礙物越遠(yuǎn)。

圖1 距離評(píng)價(jià)子函數(shù)的影響Fig.1 Influence of distance evaluation sub-function

2.2.2 動(dòng)態(tài)設(shè)定AGV初始狀態(tài)航向角

AGV初始航向角是隨機(jī)設(shè)定的固定角，當(dāng)與目標(biāo)點(diǎn)角度偏差較大時(shí)，會(huì)出現(xiàn)初期搜索路線繞行的現(xiàn)象，增加AGV運(yùn)行路徑的冗余，如圖2所示。因此，本文提出了以起點(diǎn)與第一個(gè)子目標(biāo)點(diǎn)的連線與水平方向的夾角來(lái)動(dòng)態(tài)設(shè)定AGV初始航向角，明確搜索路徑的前進(jìn)方向，避免繞行。

圖2 初始航向角的影響Fig.2 Influence of initial heading angle

設(shè)起點(diǎn)坐標(biāo)為(XS,YS)，第一個(gè)子目標(biāo)點(diǎn)的坐標(biāo)為(X1,Y1)，則AGV的初始航向角φ為：

式中，c為初始航向角的正弦值；d為起點(diǎn)與第一個(gè)子目標(biāo)點(diǎn)的歐式距離。

2.3 全局動(dòng)態(tài)路徑規(guī)劃算法

動(dòng)態(tài)窗口法根據(jù)AGV檢測(cè)到的局部環(huán)境信息，實(shí)時(shí)動(dòng)態(tài)規(guī)劃路徑，具有良好的避障能力，但由于無(wú)法有效利用全局環(huán)境信息，存在易陷入局部最優(yōu)、無(wú)法到達(dá)目標(biāo)點(diǎn)等致命問(wèn)題。因此，本文提出利用改進(jìn)蟻群算法進(jìn)行全局靜態(tài)路徑規(guī)劃，然后將規(guī)劃的最優(yōu)路徑上各轉(zhuǎn)折點(diǎn)依次作為改進(jìn)動(dòng)態(tài)窗口法的子目標(biāo)點(diǎn)，終點(diǎn)為總目標(biāo)點(diǎn)，分步指引動(dòng)態(tài)窗口法沿全局最優(yōu)路徑方向進(jìn)行實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃，以保證動(dòng)態(tài)規(guī)劃路徑的全局最優(yōu)性。若在行程后期出現(xiàn)目標(biāo)位置轉(zhuǎn)移的情況，可以根據(jù)目標(biāo)點(diǎn)轉(zhuǎn)移狀態(tài)分為兩種情況：（1）若目標(biāo)點(diǎn)一直移動(dòng)，則可以利用改進(jìn)的動(dòng)態(tài)窗口法動(dòng)態(tài)追蹤移動(dòng)目標(biāo)點(diǎn)，但路徑質(zhì)量可能較差；（2）若目標(biāo)點(diǎn)轉(zhuǎn)移后靜止不動(dòng)，則可以將當(dāng)前位置設(shè)為起點(diǎn)，轉(zhuǎn)移后的目標(biāo)位置設(shè)為終點(diǎn)，重新調(diào)用全局動(dòng)態(tài)路徑規(guī)劃算法進(jìn)行實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃。這里僅簡(jiǎn)單討論兩種目標(biāo)轉(zhuǎn)移情況的解決方法，在下文實(shí)驗(yàn)中并不考慮目標(biāo)轉(zhuǎn)移的情況，因此全局動(dòng)態(tài)路徑規(guī)劃算法的具體流程如圖3所示。

圖3 全局動(dòng)態(tài)路徑規(guī)劃算法流程圖Fig.3 Flow chart of global dynamic path planning algorithm

3 仿真實(shí)驗(yàn)

3.1 基于改進(jìn)蟻群算法的全局靜態(tài)路徑規(guī)劃

為了驗(yàn)證改進(jìn)蟻群算法的可行性和有效性，本文利用編碼簡(jiǎn)單、易于實(shí)現(xiàn)的柵格地圖法建立模擬環(huán)境[10]，在不同模擬環(huán)境下，通過(guò)Matlab進(jìn)行傳統(tǒng)蟻群算法和本文改進(jìn)蟻群算法的仿真實(shí)驗(yàn)對(duì)比。相關(guān)實(shí)驗(yàn)數(shù)據(jù)如下：迭代次數(shù)K=100，螞蟻數(shù)量M=50，信息素啟發(fā)因子α=1，期望啟發(fā)因子β=8，信息素?fù)]發(fā)系數(shù)ρ=0.4，信息素增量Q=10。

（1）仿真實(shí)驗(yàn)環(huán)境一（圖4～圖6）

圖4 傳統(tǒng)與改進(jìn)蟻群算法的路徑長(zhǎng)度收斂對(duì)比（實(shí)驗(yàn)1）Fig.4 Comparison of path length convergence between traditional and improved ant colony algorithms（E1）

圖6 改進(jìn)蟻群算法路徑軌跡（實(shí)驗(yàn)1）Fig.6 Path trajectory of improved ant colony algorithm（E1）

仿真實(shí)驗(yàn)環(huán)境一是規(guī)模為20×20的二維平面，可移動(dòng)?xùn)鸥衽c障礙物柵格比為7∶3，障礙物隨機(jī)分布。

（b）仿真實(shí)驗(yàn)環(huán)境二（圖7～圖9）

仿真實(shí)驗(yàn)環(huán)境二是規(guī)模為30×30的二維平面，可移動(dòng)?xùn)鸥衽c障礙物柵格比為7∶3，障礙物隨機(jī)分布。

圖4～圖9是分別是不同環(huán)境下傳統(tǒng)蟻群算法和本文改進(jìn)蟻群算法運(yùn)行10次中規(guī)劃效果最好的結(jié)果，表1是不同實(shí)驗(yàn)環(huán)境下兩種算法搜索結(jié)果對(duì)比。圖4、圖7中藍(lán)線表示傳統(tǒng)蟻群算法的路徑長(zhǎng)度收斂曲線，紅線表示本文改進(jìn)蟻群算法的路徑長(zhǎng)度收斂曲線；圖5、圖6、圖8、圖9分別是傳統(tǒng)蟻群算法和本文改進(jìn)蟻群算法在不同仿真實(shí)驗(yàn)環(huán)境中搜索的所有最短路徑和最優(yōu)路徑（即路徑最短，轉(zhuǎn)彎次數(shù)最少）。由表1可知，在仿真實(shí)驗(yàn)環(huán)境一中，本文改進(jìn)蟻群算法與傳統(tǒng)蟻群算法相比：最優(yōu)路徑長(zhǎng)度減少2.8%，轉(zhuǎn)彎次數(shù)減少25%，迭代次數(shù)減少47.5%；在仿真實(shí)驗(yàn)環(huán)境二中，本文改進(jìn)蟻群算法與傳統(tǒng)蟻群算法相比：最優(yōu)路徑長(zhǎng)度減少4.9%，轉(zhuǎn)彎次數(shù)減少38.5%，迭代次數(shù)減少55%。

圖5 傳統(tǒng)蟻群算法路徑軌跡（實(shí)驗(yàn)1）Fig.5 Path trajectory of traditional ant colony algorithm（E1）

圖7 傳統(tǒng)與改進(jìn)蟻群算法的路徑長(zhǎng)度收斂對(duì)比（實(shí)驗(yàn)2）Fig.7 Comparison of path length convergence between traditional and improved ant colony algorithms（E2）

圖8 傳統(tǒng)蟻群算法路徑軌跡（實(shí)驗(yàn)2）Fig.8 Path trajectory of traditional ant colony algorithm（E2）

圖9 改進(jìn)蟻群算法路徑軌跡（實(shí)驗(yàn)2）Fig.9 Path trajectory of improved ant colony algorithm（E2）

表1 不同實(shí)驗(yàn)環(huán)境下兩種算法搜索結(jié)果對(duì)比Table 1 Comparison of search results of two algorithms in different experimental environments

通過(guò)不同環(huán)境下的仿真實(shí)驗(yàn)可知，本文提出的改進(jìn)蟻群算法收斂性更好，規(guī)劃的全局最優(yōu)路徑質(zhì)量更優(yōu)、平滑度更高，證明了本文改進(jìn)蟻群算法的可行性和有效性。

3.2 基于全局動(dòng)態(tài)路徑規(guī)劃算法的實(shí)時(shí)路徑規(guī)劃

為了驗(yàn)證全局動(dòng)態(tài)路徑規(guī)劃算法的可行性和有效性，本文在不同模擬環(huán)境下，通過(guò)Matlab進(jìn)行傳統(tǒng)動(dòng)態(tài)窗口法和本文提出的全局動(dòng)態(tài)路徑規(guī)劃算法仿真實(shí)驗(yàn)對(duì)比。改進(jìn)蟻群算法的相關(guān)數(shù)據(jù)參考3.1節(jié)；改進(jìn)動(dòng)態(tài)窗口法的相關(guān)數(shù)據(jù)如下：AGV最高線速度1.0 m/s，最高角速度30.0（°）/s，加速度0.2 m/s，旋轉(zhuǎn)加速度60.0（°）/s，線速度分辨率0.01 m/s，角速度分辨率1.0（°）/s，航向得分的比重0.4、距離得分的比重0.4、速度得分的比重0.2、向前模擬軌跡的時(shí)間3 s，距離目標(biāo)點(diǎn)的距離小于0.5 m時(shí)，則認(rèn)為AGV到達(dá)目標(biāo)點(diǎn)。

（1）仿真實(shí)驗(yàn)環(huán)境一

仿真實(shí)驗(yàn)環(huán)境一是規(guī)模為10×10的二維平面，可移動(dòng)?xùn)鸥衽c障礙物柵格比為8∶2，障礙物隨機(jī)分布。本文在柵格地圖中設(shè)置了兩個(gè)移動(dòng)障礙物：紅色柵格設(shè)為動(dòng)態(tài)障礙物A，藍(lán)色柵格為動(dòng)態(tài)障礙物B。

（2）仿真實(shí)驗(yàn)環(huán)境二

仿真實(shí)驗(yàn)環(huán)境二是規(guī)模為20×20的二維平面，可移動(dòng)?xùn)鸥衽c障礙物柵格比為8∶2，障礙物隨機(jī)分布。由仿真實(shí)驗(yàn)環(huán)境一可知傳統(tǒng)動(dòng)態(tài)窗口法在相對(duì)簡(jiǎn)單環(huán)境下無(wú)法找到目標(biāo)點(diǎn)，所以本次實(shí)驗(yàn)僅做了全局動(dòng)態(tài)路徑規(guī)劃算法。

圖10分別表示AGV從遇到動(dòng)態(tài)障礙物B到有效避開(kāi)動(dòng)態(tài)障礙物B的全過(guò)程。圖11、圖12、圖13分別表示傳統(tǒng)動(dòng)態(tài)窗口法和本文改進(jìn)的全局路徑規(guī)劃算法的路徑軌跡，其中，圖12（a）、圖13（a）為全局動(dòng)態(tài)路徑規(guī)劃算法動(dòng)態(tài)路徑規(guī)劃軌跡，圖12（b）、圖13（b）為改進(jìn)蟻群算法規(guī)劃的全局最優(yōu)路徑（紅線）與全局動(dòng)態(tài)路徑規(guī)劃算法規(guī)劃的全局最優(yōu)路徑（藍(lán)線）的對(duì)比。由圖11可知，傳統(tǒng)動(dòng)態(tài)窗口法雖然可以有效躲避移動(dòng)障礙物，但由于缺少全局信息的指導(dǎo)，陷入死鎖，無(wú)法成功到達(dá)目標(biāo)點(diǎn)。由圖12（a）、圖13（a）可知，在全局信息的指導(dǎo)下，本文提出的全局動(dòng)態(tài)路徑規(guī)劃算法可以有效躲避動(dòng)態(tài)障礙物的同時(shí)規(guī)劃出全局最優(yōu)路徑；由圖12（b）、圖13（b）可知，與改進(jìn)蟻群算法相比，全局動(dòng)態(tài)路徑規(guī)劃算法規(guī)劃的路徑曲率連續(xù)，平滑度更高，更適合AGV的高效運(yùn)行。

圖10 動(dòng)態(tài)躲避障礙物過(guò)程Fig.10 Dynamic avoidance of obstacles process

圖11 傳統(tǒng)動(dòng)態(tài)窗口法Fig.11 Traditional dynamic window approach

圖12 改進(jìn)的全局動(dòng)態(tài)路徑規(guī)劃算法（實(shí)驗(yàn)1）Fig.12 Improved global dynamic path planning algorithm（E1）

圖13 改進(jìn)的全局動(dòng)態(tài)路徑規(guī)劃算法（實(shí)驗(yàn)2）Fig.13 Improved global dynamic path planning algorithm（E2）

通過(guò)不同環(huán)境下仿真實(shí)驗(yàn)可知，在全局信息的指導(dǎo)下，本文提出的全局動(dòng)態(tài)路徑規(guī)劃算法在不同環(huán)境下都可以通過(guò)實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃躲避動(dòng)態(tài)障礙物，規(guī)劃出全局最優(yōu)路徑，證明了本文提出的全局動(dòng)態(tài)路徑規(guī)劃算法的可行性和有效性。

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

針對(duì)全局靜態(tài)路徑規(guī)劃算法無(wú)法有效躲避動(dòng)態(tài)障礙物、局部動(dòng)態(tài)路徑規(guī)劃算法缺少全局環(huán)境信息而易陷入局部最優(yōu)或無(wú)法到達(dá)目標(biāo)點(diǎn)等問(wèn)題，本文提出了一種結(jié)合改進(jìn)蟻群算法和動(dòng)態(tài)窗口法的AGV全局動(dòng)態(tài)路徑規(guī)劃算法。首先，對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)：（1）基于雙向搜索策略提出初始信息素不均勻、雙向分布，為蟻群算法雙向搜索提供大體方向，避免算法初期存在盲目搜索、收斂性差等問(wèn)題；（2）針對(duì)相鄰柵格距離差異較小，本文引入放大系數(shù)A來(lái)增大相鄰柵格的啟發(fā)信息差異，增大螞蟻選擇更優(yōu)節(jié)點(diǎn)的概率；（3）更新信息素時(shí)引入轉(zhuǎn)彎次數(shù)影響因素，在所有最短路徑中選擇轉(zhuǎn)彎次數(shù)最少的路徑作為最優(yōu)路徑更新信息素，從而得到更平滑的路徑，提升AGV運(yùn)行效率。然后，對(duì)動(dòng)態(tài)窗口法進(jìn)行改進(jìn)：（1）改進(jìn)距離評(píng)價(jià)子函數(shù)，以模擬軌跡上各點(diǎn)到障礙物最小距離為評(píng)價(jià)距離，評(píng)價(jià)距離越大，表示AGV離障礙物越遠(yuǎn)，避障效果越好；（2）提出以起點(diǎn)與第一個(gè)子目標(biāo)點(diǎn)的連線與水平方向的夾角動(dòng)態(tài)設(shè)置AGV的初始航向角，明確搜索路徑的前進(jìn)方向，避免初始航向角設(shè)置不當(dāng)造成繞行。最后，結(jié)合改進(jìn)的蟻群算法和動(dòng)態(tài)窗口法構(gòu)建全局動(dòng)態(tài)路徑規(guī)劃算法，以改進(jìn)蟻群算法規(guī)劃的全局最優(yōu)路徑上各轉(zhuǎn)折點(diǎn)為動(dòng)態(tài)窗口法子目標(biāo)點(diǎn)，引導(dǎo)動(dòng)態(tài)窗口法沿著全局最優(yōu)路徑方向進(jìn)行實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃，最終實(shí)現(xiàn)AGV在動(dòng)態(tài)環(huán)境下沿著全局最優(yōu)路徑躲避動(dòng)態(tài)障礙物。通過(guò)不同環(huán)境下的仿真實(shí)驗(yàn)結(jié)果，證明了本文提出的改進(jìn)蟻群算法和全局動(dòng)態(tài)路徑規(guī)劃算法均可行和有效。