李任江，滕智鵬

（長(zhǎng)春工業(yè)大學(xué) 機(jī)電工程學(xué)院，吉林 長(zhǎng)春 130012）

0 引言

自動(dòng)引導(dǎo)小車AGV作為調(diào)節(jié)和聯(lián)系離散型物流系統(tǒng)，被廣泛運(yùn)用于自動(dòng)化立體倉(cāng)庫(kù)中，常用的路徑規(guī)劃方法有柵格法［1］、A＊算法［2］、Dijkstra算法［3］、遺傳算法［4］、蟻 群 算 法［5］、粒 子 群 算 法［6］等。 在 這 些 方 法中，遺傳算法有著較強(qiáng)的搜索能力，通過(guò)引入自適應(yīng)的參數(shù)，能夠找到全局最優(yōu)解［7］，但是局部尋優(yōu)能力差；粒子群算法參數(shù)少，能夠快速收斂，但易于陷入局部最優(yōu)解；蟻群算法具有很強(qiáng)的魯棒性和適應(yīng)性，但是還存在一些問(wèn)題，如不具備自主避障能力、信息素的更新機(jī)制不完善等，有待進(jìn)一步研究。

本文基于改進(jìn)蟻群算法進(jìn)行AGV路徑規(guī)劃，首先引入方向系數(shù)，并采用局部、全局結(jié)合的信息素更新方式，達(dá)到快速尋優(yōu)的目的；其次引入安全距離判斷策略，提高AGV運(yùn)行路徑的安全性。仿真結(jié)果表明，改進(jìn)算法具有較好的避障能力，收斂速度快，能夠運(yùn)用于復(fù)雜運(yùn)輸環(huán)境。

1 構(gòu)造AGV運(yùn)行環(huán)境

為規(guī)劃AGV運(yùn)行路徑，首先要建立能夠使AGV識(shí)別的運(yùn)行環(huán)境，通常情況下，AGV的運(yùn)行環(huán)境為二維有界空間，為了便于研究，進(jìn)行如下假設(shè)：①將行駛的AGV看作質(zhì)點(diǎn)；②AGV行駛過(guò)程中主方向?yàn)閤軸，且行駛速度v不變；③黑色方格為障礙物柵格；④每一條路徑節(jié)點(diǎn)之間的連續(xù)不能穿過(guò)障礙物。

用M表示AGV的運(yùn)動(dòng)空間，建立笛卡爾坐標(biāo)系xoy，以橫向?yàn)樽鴺?biāo)軸x，縱向?yàn)樽鴺?biāo)軸y，原點(diǎn)位于M區(qū)域左下角，起點(diǎn)S位于原點(diǎn)，終點(diǎn)E位于M 區(qū)域右上角。x、y軸上的最大值分別為Xmax、Ymax，基于行駛速度v完成x、y對(duì)柵格的劃分，每行的柵格數(shù)為Nx＝個(gè)柵格的序列號(hào)滿足如下關(guān)系式：

其中：i為序列號(hào)；n為每一行柵格數(shù)；int為取整運(yùn)算；mod為求余運(yùn)算。

基于以上描述及設(shè)定，本文建立20×20的AGV運(yùn)行環(huán)境，如圖1所示。

2 傳統(tǒng)蟻群算法

蟻群算法是一種模擬螞蟻覓食的仿生算法，螞蟻根據(jù)轉(zhuǎn)移概率選擇一條路徑留下信息素，積累的信息素濃度越大，路徑被選擇的概率越大，螞蟻會(huì)根據(jù)留下的信息素找到最優(yōu)路徑。根據(jù)傳統(tǒng)蟻群算法設(shè)定，某時(shí)刻t螞蟻k從節(jié)點(diǎn)i移動(dòng)到節(jié)點(diǎn)j的概率為：

其中：pij（k）（t）為轉(zhuǎn)移概率；τij（t）為t時(shí)刻節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的信息素強(qiáng)度；α為信息素重要度因子；ηij（t）為節(jié)點(diǎn)i到節(jié)點(diǎn)j的期望啟發(fā)函數(shù)，ηij（t）＝，dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的歐幾里得距離；β為期望程度因子。

螞蟻完成一次循環(huán)后更新每條路徑上的信息素：

其中：τij（t＋1）為更新后節(jié)點(diǎn)i和j之間的信息素強(qiáng)度；ρ為信息素?fù)]發(fā)系數(shù)；Δτij（t）為路徑節(jié)點(diǎn)i到節(jié)點(diǎn)j上的信息素增加量，設(shè)初始時(shí)刻Δτij（0）＝0；m為蟻群的數(shù)量；Q為信息素加強(qiáng)系數(shù)；Lk為螞蟻k所走過(guò)路徑的總長(zhǎng)度。

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

3.1 啟發(fā)函數(shù)改進(jìn)

傳統(tǒng)蟻群算法中，由于初始時(shí)刻各條路徑上的信息素含量較少，為了使路徑規(guī)劃初期AGV的路徑選擇具有一定的指向性，本文引入方向系數(shù)（即方向啟發(fā)因子）μ來(lái)判斷AGV運(yùn)行過(guò)程中當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)的角度，避免角度過(guò)大而造成路徑搜索時(shí)間的浪費(fèi)。某時(shí)刻AGV運(yùn)行引導(dǎo)原理如圖2所示。

圖1 AGV運(yùn)行環(huán)境

圖2 AGV運(yùn)行引導(dǎo)原理

AGV連續(xù)經(jīng)過(guò)節(jié)點(diǎn)i、j、a、b，當(dāng)前 AGV運(yùn)行路徑為節(jié)點(diǎn)i到節(jié)點(diǎn)j，節(jié)點(diǎn)a和節(jié)點(diǎn)b為下一步的出發(fā)點(diǎn)和到達(dá)點(diǎn)，θ1、θ2分別為AGV處于節(jié)點(diǎn)a和節(jié)點(diǎn)j時(shí)與運(yùn)動(dòng)邊界形成的角度。Δθ越小，AGV運(yùn)行方向越靠近終點(diǎn)b，從而縮短運(yùn)行距離。設(shè)ηij＊為改進(jìn)后的期望啟發(fā)函數(shù)，Δθ和ηij＊的計(jì)算公式如下：

其中：dij為i與j之間的距離；μ為方向啟發(fā)因子，且μ＞0。

由式（7）可知，若角度過(guò)大則會(huì)使η＊ij的值減少，可以減少角度較大的柵格被選擇的概率。結(jié)合式（7）和式（2）可得到改進(jìn)后的蟻群算法轉(zhuǎn)移概率計(jì)算公式：

3.2 信息素更新機(jī)制改進(jìn)

傳統(tǒng)蟻群算法對(duì)信息素的更新方式較為單一，當(dāng)算法進(jìn)入下一循環(huán)時(shí)并沒(méi)有充分利用上一循環(huán)中最短路徑上的信息素。本文采用的信息素更新方式如下：當(dāng)螞蟻進(jìn)行一次循環(huán)時(shí)，對(duì)所到達(dá)的每個(gè)節(jié)點(diǎn)上的信息素根據(jù)式（4）進(jìn)行局部更新；經(jīng)過(guò)n個(gè)時(shí)刻螞蟻完成一次循環(huán)后，對(duì)最優(yōu)、最差路徑上的信息素根據(jù)式（9）進(jìn)行全局更新：

其中：Lgb為當(dāng)前最優(yōu)路徑長(zhǎng)度；Tu為當(dāng)前最優(yōu)路徑上所有節(jié)點(diǎn)的集合；Lgw為當(dāng)前最差路徑長(zhǎng)度；Tv為當(dāng)前最差路徑上所有節(jié)點(diǎn)的集合。

采用上述更新方式，可以使每個(gè)循環(huán)中的信息素充分利用，提高較好路徑被選擇的概率，從而提高算法的性能，避免陷入局部最優(yōu)解。

3.3 路徑安全距離判斷策略

算法對(duì)AGV進(jìn)行路徑規(guī)劃的過(guò)程中，會(huì)出現(xiàn)與障礙物邊緣碰撞的路徑，這樣會(huì)影響AGV運(yùn)行的安全性。本文在對(duì)AGV路徑規(guī)劃過(guò)程中引入安全距離，以提高AGV運(yùn)行路徑的安全性。圖3為引入安全距離前、后的AGV運(yùn)行路徑，路徑uv、ij分別為引入安全距離前、后的規(guī)劃路徑。

圖3 引入路徑安全距離

根據(jù)本文的設(shè)定，AGV運(yùn)動(dòng)方向?yàn)閤軸，假設(shè)障礙物右上尖角點(diǎn)e的坐標(biāo)為（x，y），取ce為250mm，點(diǎn)c的坐標(biāo)為（x，y＋250）。某時(shí)刻AGV運(yùn)行到點(diǎn)c，點(diǎn)c與障礙物尖角e以及路徑終點(diǎn)j產(chǎn)生一個(gè)角度θ，由此可以計(jì)算出線段lde的長(zhǎng)度，并將線段lde的長(zhǎng)度稱為安全距離：

其中：lce為線段ce的長(zhǎng)度；θ為ce與cd的夾角，且θ∈（0，90°］。

路徑規(guī)劃過(guò)程中，AGV經(jīng)過(guò)障礙物時(shí)路徑節(jié)點(diǎn)的選擇與點(diǎn)c一致，可以滿足安全距離且安全距離∈（0，250］。若AGV經(jīng)過(guò)障礙時(shí)主運(yùn)動(dòng)方向?yàn)閥軸，則判斷障礙物右下尖角與AGV的安全距離。

4 仿真實(shí)驗(yàn)及結(jié)果分析

在圖1環(huán)境下，對(duì)傳統(tǒng)蟻群算法和改進(jìn)蟻群算法進(jìn)行仿真實(shí)驗(yàn)，并對(duì)兩種算法規(guī)劃出的結(jié)果進(jìn)行對(duì)比分析。仿真中各項(xiàng)參數(shù)的設(shè)定為：螞蟻數(shù)量m＝50；信息素重要度因子α＝1；期望程度因子β＝8；信息素?fù)]發(fā)系數(shù)ρ＝0.1；信息素加強(qiáng)系數(shù)Q＝15；最大迭代次數(shù)N＝100。圖4為傳統(tǒng)蟻群算法和改進(jìn)后的蟻群算法的收斂曲線。從圖4中可以看出，改進(jìn)蟻群算法比傳統(tǒng)蟻群算法更快達(dá)到收斂。

圖5為傳統(tǒng)蟻群算法、改進(jìn)蟻群算法和改進(jìn)蟻群算法引入安全距離（取安全距離為250mm）后進(jìn)行路徑規(guī)劃的結(jié)果。通過(guò)比較圖5（a）和圖5（b）可以看出，改進(jìn)蟻群算法得到的最優(yōu)路徑更短。再比較圖5（b）和圖5（c）可以看出，引入安全距離后AGV在靠近障礙物時(shí)會(huì)控制與障礙物的距離為設(shè)定的安全距離。傳統(tǒng)蟻群算法在路徑規(guī)劃初始時(shí)刻路徑的選擇具有隨機(jī)性，而改進(jìn)后的蟻群算法在引入方向啟發(fā)因子之后在路徑選擇上避免了平移的出現(xiàn)，同時(shí)也能夠根據(jù)安全距離自主避碰。

對(duì)以上仿真得到的最優(yōu)路徑長(zhǎng)度、平均收斂代數(shù)和平均收斂時(shí)間以及拐點(diǎn)數(shù)進(jìn)行比較分析，見表1。由表1可以看出：引入方向啟發(fā)因子和安全距離后，AGV的運(yùn)動(dòng)更具有指向性，產(chǎn)生的路徑上的拐點(diǎn)數(shù)比傳統(tǒng)蟻群算法更少，從而產(chǎn)生的路徑長(zhǎng)度更短且搜索耗時(shí)也明顯減少；AGV會(huì)在障礙物附近判斷當(dāng)前安全距離同時(shí)保證路徑最短，使直行路徑變成拐角，所以路徑長(zhǎng)度也會(huì)有所增加，更符合實(shí)際情形。

圖5 算法路徑仿真結(jié)果

表1 算法性能對(duì)比

5 結(jié)語(yǔ)

本文提出一種適用于復(fù)雜運(yùn)輸環(huán)境下AGV路徑規(guī)劃的改進(jìn)蟻群算法。采用柵格法建立運(yùn)行地圖，通過(guò)引入方向系數(shù)、安全距離判斷策略和改進(jìn)信息素更新機(jī)制，提高算法運(yùn)行效率和收斂速度，避免陷入死鎖，保證了AGV運(yùn)輸路徑的安全性。實(shí)驗(yàn)結(jié)果表明，本文提出的算法比傳統(tǒng)蟻群算法更快達(dá)到收斂，且規(guī)劃的最優(yōu)路徑距離更短，引入安全距離之后AGV的運(yùn)行路徑與引入前相比更安全。