李全勇，李 波，張 瑞，姜 濤

(1.內(nèi)蒙古一機(jī)集團(tuán)力克橡塑制品有限公司 技術(shù)中心，內(nèi)蒙古 包頭 014000；2.湖北文理學(xué)院 機(jī)械工程學(xué)院，湖北 襄陽(yáng) 441053；3.武漢科技大學(xué) 機(jī)械自動(dòng)化學(xué)院，湖北 武漢 430081；4.北京星航機(jī)電裝備有限公司 技術(shù)中心，北京 100071)

0 引言

自動(dòng)導(dǎo)航運(yùn)輸車(AGV)作為智能物流的核心設(shè)備，廣泛應(yīng)用于汽車、食品、煙草、醫(yī)療、服裝等行業(yè)。路徑規(guī)劃是AGV應(yīng)用的核心技術(shù)之一，對(duì)其進(jìn)行研究具有極高的工程價(jià)值。文獻(xiàn)[1]提出了一種基于時(shí)間最短的無碰撞路徑算法；文獻(xiàn)[2]在AGV調(diào)度算法中計(jì)入空閑時(shí)間，基于遺傳算法進(jìn)行調(diào)度規(guī)劃；文獻(xiàn)[3]將改進(jìn)遺傳算法應(yīng)用于AGV避障路徑規(guī)劃；文獻(xiàn)[4]研究了細(xì)菌勢(shì)場(chǎng)算法，求解移動(dòng)機(jī)器人靜態(tài)和動(dòng)態(tài)路徑規(guī)劃；文獻(xiàn)[5]在車間調(diào)度中引入了灰狼優(yōu)化算法，預(yù)測(cè)工件到達(dá)時(shí)間；文獻(xiàn)[6]提出了改進(jìn)重力搜索算法，仿真實(shí)現(xiàn)了在靜態(tài)障礙物下的路徑規(guī)劃；文獻(xiàn)[7]采用Dijkstra算法求解單臺(tái)AGV最短路徑，實(shí)現(xiàn)AGV的智能無線控制；文獻(xiàn)[8]提出一種改進(jìn)型蟻群路徑規(guī)劃算法，加入全局信息素更新機(jī)制,提高了算法的搜索效率；文獻(xiàn)[9]以最小化最大搬運(yùn)完成時(shí)間為目標(biāo)，研究了一種生成無路徑?jīng)_突的路徑規(guī)劃算法；文獻(xiàn)[10]采用遺傳算法對(duì)改進(jìn)蟻群算法進(jìn)行參數(shù)優(yōu)化，以提高收斂速度，避免局部最優(yōu)。

針對(duì)磁導(dǎo)AGV運(yùn)行特點(diǎn)，本文進(jìn)行了基于柵格法的拓?fù)涞貓D建模，分析了A*、蟻群、遺傳、Dijkstra算法的AGV路徑規(guī)劃問題，引入路徑平滑度，并以時(shí)間權(quán)重為優(yōu)化目標(biāo)求解最優(yōu)路徑，提出了改進(jìn)Dijkstra算法，開發(fā)了路徑規(guī)劃仿真系統(tǒng)，進(jìn)行了多種算法AGV路徑規(guī)劃對(duì)比分析。

1 AGV地圖模型構(gòu)建

地圖模型構(gòu)建是AGV路徑規(guī)劃的基礎(chǔ)，直接影響路徑規(guī)劃算法的設(shè)計(jì)。本文基于柵格法的無向有權(quán)拓?fù)涞貓D方法，開展AGV運(yùn)行環(huán)境的建模，如圖1所示。

圖1 地圖建模

以柵格圖為基礎(chǔ)，每個(gè)網(wǎng)格中心為節(jié)點(diǎn)，連接相關(guān)節(jié)點(diǎn)作為邊，其代表路徑規(guī)劃中的磁導(dǎo)線。保留圖中節(jié)點(diǎn)和邊，去除網(wǎng)格，剩下部分為拓?fù)涞貓D的地圖模型。

2 基于改進(jìn)Dijkstra算法的AGV路徑規(guī)劃

針對(duì)拓?fù)鋱D下的AGV路徑規(guī)劃問題，A*算法求解最短路徑，但由于受到估計(jì)代價(jià)值的影響，算法出現(xiàn)局部最優(yōu)，穩(wěn)定性不佳；蟻群算法雖能得到強(qiáng)魯棒性的優(yōu)化路徑，但對(duì)全局搜索能力較低，收斂速度較慢，容易在搜索過程中陷入局部最優(yōu)；遺傳算法具有良好的搜索能力，不易陷入局部最優(yōu)，但局部搜索能力較差，進(jìn)化后期搜索效率較低，需對(duì)算法本身參數(shù)進(jìn)行優(yōu)化，避免過早收斂。

Dijkstra算法[11]作為一種貪心算法，以起始點(diǎn)為中心源點(diǎn)層層向外擴(kuò)散直至搜索到所有節(jié)點(diǎn)的最短路徑。其根據(jù)路徑總權(quán)重來獲得最短路徑，兩節(jié)點(diǎn)之間權(quán)重使用一般直線距離公式求解：

(1)

傳統(tǒng)Dijkstra算法作為典型的最短路徑算法，可準(zhǔn)確獲取全局最優(yōu)路徑，通常將路徑長(zhǎng)度作為權(quán)重因子搜索最短路徑，但無法考慮到路徑平滑度對(duì)AGV實(shí)際運(yùn)行中的影響。

本文提出以時(shí)間權(quán)重作為最優(yōu)路徑的考慮因素，通過模擬AGV從起點(diǎn)至終點(diǎn)運(yùn)行花費(fèi)的總時(shí)長(zhǎng)，對(duì)比AGV在各個(gè)可行路徑中的運(yùn)行最短時(shí)長(zhǎng)，篩選出最優(yōu)路徑。時(shí)間權(quán)重T函數(shù)表達(dá)式為：

(2)

其中：Dij為節(jié)點(diǎn)i、j之間的距離；U為AGV在路徑直線部分的平均速度；TΦ為彎道總權(quán)重，表示AGV經(jīng)過所有彎道時(shí)間權(quán)重；Tij為時(shí)間總權(quán)重，表示AGV從節(jié)點(diǎn)i到節(jié)點(diǎn)j總權(quán)重。彎道總權(quán)重函數(shù)表達(dá)式為：

(3)

其中：S(i,i+1)為首尾分別為節(jié)點(diǎn)i與節(jié)點(diǎn)i+1的邊；tΦ為兩條相鄰邊夾角的權(quán)重。

AGV在巡線過程中面對(duì)不同角度彎道做出不同動(dòng)作，其中夾角權(quán)重如式(4)所示：

(4)

其中：R為拐彎類型標(biāo)識(shí)符，R=0表示角度彎，R=1表示為弧度彎；r為拐彎半徑；c為轉(zhuǎn)彎因子，根據(jù)不同AGV拐彎?rùn)C(jī)制設(shè)定，值為常量，用U·c表示AGV拐彎角速度；wβ為減速因子，用于弧度彎道中，表示AGV過彎時(shí)減速程度；W為旋轉(zhuǎn)精度懲罰因子；Φ為轉(zhuǎn)角角度；tw為減速損耗權(quán)重，用于表示減速帶來的時(shí)間損耗，表達(dá)函數(shù)為：

(5)

其中：dw為減速緩沖距離(減速節(jié)點(diǎn)與轉(zhuǎn)彎節(jié)點(diǎn)的距離)；wα為減速因子，表示AGV進(jìn)入彎道前的減速程度，wα≤1。

AGV經(jīng)過不同角度彎道時(shí)會(huì)產(chǎn)生不同層次時(shí)間損耗，根據(jù)這一特性，依據(jù)角度Φ的不同，將夾角權(quán)重tΦ分為三個(gè)階段分析求解：

第一階段(0≤Φ≤Φ1)：轉(zhuǎn)彎夾角很小，此類彎道所產(chǎn)生時(shí)間損耗為0。

第二階段(Φ1<Φ≤Φ2)：彎道夾角適中，AGV無法通過自動(dòng)巡線功能通過此類彎道，可在彎道夾角放置拐角節(jié)點(diǎn)，根據(jù)信號(hào)依次完成急停、準(zhǔn)確地旋轉(zhuǎn)相應(yīng)角度、恢復(fù)巡線速度等動(dòng)作。

第三階段(Φ2<Φ≤Φ3)：當(dāng)彎道夾角過大，AGV無法旋轉(zhuǎn)至相應(yīng)角度，會(huì)產(chǎn)生或多或少的旋轉(zhuǎn)角度誤差。此時(shí)，AGV會(huì)通過自身巡線功能，以拐角節(jié)點(diǎn)為中心左右旋轉(zhuǎn)尋找磁導(dǎo)線。隨著拐彎夾角的增大，產(chǎn)生的誤差角度也會(huì)增大，隨之帶來的巡線損耗時(shí)間也會(huì)增加。為此提出W旋轉(zhuǎn)精度懲罰因子，可根據(jù)不同AGV自身的性能設(shè)值。

通過對(duì)兩夾角的權(quán)重分析，最優(yōu)路徑權(quán)重可由式(6)表示：

(6)

3 仿真驗(yàn)證

采用C#語(yǔ)言開發(fā)了Winform應(yīng)用程序，進(jìn)行了多算法仿真實(shí)驗(yàn)。圖2為AGV仿真平臺(tái)界面截圖，采用柵格法拓?fù)鋱D進(jìn)行車間地圖布局。

圖2 仿真界面

根據(jù)圖1地圖模型，將41個(gè)節(jié)點(diǎn)與53條邊信息錄入系統(tǒng)，完成實(shí)驗(yàn)數(shù)據(jù)初始化。地圖拐角信息主要采用角度彎道，U=5(以模型比例設(shè)置)，wα=2，wβ=0，Φ1=0°，Φ2=90°，Φ3=180°，c=3°，dw=10，W=0。通過選擇不同任務(wù)起點(diǎn)與終點(diǎn)進(jìn)行實(shí)驗(yàn)，結(jié)果如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)表

通過多次實(shí)驗(yàn)，選擇三組特征值最明顯的數(shù)組進(jìn)行對(duì)比，主要結(jié)論如下：

(1) 蟻群算法與遺傳算法在求取最優(yōu)路徑時(shí)具有不穩(wěn)定性，在多次求解過程中會(huì)出現(xiàn)多個(gè)長(zhǎng)度相同、但是拐彎次數(shù)不同的路徑，在迭代次數(shù)不足的情況下，蟻群算法更是無法獲取路徑長(zhǎng)度最短的解。

(2) A*算法、遺傳算法、改進(jìn)Dijkstra算法的穩(wěn)定性更好。

(3) 改進(jìn)Dijkstra算法每次獲取路徑都為最優(yōu)解(理論用時(shí)最短)，求得路徑長(zhǎng)度雖大于其他路徑算法，但理論用時(shí)依然是最少。

為進(jìn)一步驗(yàn)證算法的可靠度，開展了120個(gè)節(jié)點(diǎn)車間環(huán)境的仿真實(shí)驗(yàn)，布局如圖3所示。

圖3 地圖模型

120個(gè)節(jié)點(diǎn)使用了無規(guī)律的連接來降低實(shí)驗(yàn)環(huán)境的平滑度，總共有173條連接線。仿真實(shí)驗(yàn)以1號(hào)節(jié)點(diǎn)為起點(diǎn)，選擇圖中一系列坐標(biāo)點(diǎn)作為實(shí)驗(yàn)終點(diǎn)進(jìn)行多次驗(yàn)證。

采用蟻群算法與遺傳算法分別對(duì)每組數(shù)據(jù)進(jìn)行100次實(shí)驗(yàn)并提取平均值，進(jìn)行實(shí)驗(yàn)數(shù)據(jù)對(duì)比。其中蟻群算法參數(shù)設(shè)置為：蟻群數(shù)量40，最大迭代次數(shù)40,alpha=3，beta=0.5；遺傳算法參數(shù)為：染色體數(shù)量50，最大迭代次數(shù)20，最大變異次數(shù)20，交叉率0.8，變異率0.2。實(shí)驗(yàn)數(shù)據(jù)對(duì)比如圖4所示。

圖4 仿真數(shù)據(jù)對(duì)比

4 結(jié)語(yǔ)

本文基于柵格的無向有權(quán)拓?fù)浞椒ǎ⒘薃GV系統(tǒng)仿真地圖模型；分析了A*、蟻群、遺傳和Dijkstra算法，針對(duì)上述算法在拓?fù)鋱D中的適用性問題，提出了改進(jìn)的Dijkstra算法，引入路徑平滑度，以時(shí)間權(quán)重為優(yōu)化目標(biāo)求解最優(yōu)路徑；基于仿真平臺(tái)，開展了上述算法在拓?fù)涞貓D模型的實(shí)驗(yàn)對(duì)比，測(cè)試結(jié)果表明：改進(jìn)Dijkstra算法在路徑拐彎次數(shù)、模擬運(yùn)行時(shí)間等方面具有良好表現(xiàn)。