韓 強(qiáng)，何利力

（浙江理工大學(xué) 信息學(xué)院，杭州 310018）

0 引 言

近年來隨著快消品制造業(yè)智能化及無人化的快速發(fā)展，在倉儲(chǔ)和制造設(shè)施內(nèi)的自動(dòng)負(fù)載運(yùn)輸方式在提高生產(chǎn)效率的同時(shí)已然成為顯著降低運(yùn)營成本的實(shí)用手段，許多物流和制造過程都依賴于使用多個(gè)自動(dòng)導(dǎo)引車（multi-AGV）系統(tǒng)。多AGV系統(tǒng)的任務(wù)是為系統(tǒng)中的每輛AGV（Automated Guided Vehicle）分配執(zhí)行運(yùn)輸任務(wù)，對于每臺(tái)AGV，給出了唯一的開始狀態(tài)和唯一的目標(biāo)狀態(tài)，在AGV移動(dòng)過程中不能發(fā)生碰撞的約束下，找到所有AGV從其開始狀態(tài)到目標(biāo)狀態(tài)的路徑。實(shí)現(xiàn)制造車間智能生產(chǎn)的關(guān)鍵是實(shí)現(xiàn)多AGV的路徑軌跡最優(yōu)或接近最優(yōu)的無障礙路徑。

從初始位置到目標(biāo)位置檢測并避開障礙物，實(shí)現(xiàn)物料的安全運(yùn)輸是AGV在無人倉庫中的最重要功能。迄今為止，針對智能倉儲(chǔ)車間中AGV路徑求解較為常用的求解方法多以智能優(yōu)化算法為主，如遺傳算法、A算法、人工勢場法、蟻群算法等。蟻群算法是通過模擬自然界螞蟻覓食規(guī)律的概率型算法，相比于其他智能算法具有更強(qiáng)的魯棒性和正反饋性，同時(shí)存在收斂速度慢，易陷入局部最優(yōu)解等缺點(diǎn)，對此占偉等人改進(jìn)啟發(fā)因子給定初步引導(dǎo)方向減少算法收斂時(shí)間。李燕等人針對后期信息素濃度過高易陷入局部最優(yōu)解問題提出了對信息素總量進(jìn)行自適應(yīng)調(diào)整的機(jī)制，大大降低了陷入局部最優(yōu)解的概率。同時(shí)，人工勢場法本身具有計(jì)算量小、反應(yīng)速度快、路徑無碰撞等優(yōu)點(diǎn)，為此Liu等人利用人工勢場法重新計(jì)算啟發(fā)信息，提出改進(jìn)的勢場蟻群算法。王曉燕等人提出一種全局靜態(tài)環(huán)境下移動(dòng)AGV路徑規(guī)劃的改進(jìn)勢場蟻群算法，具有較高的全局搜索能力，但未解決原始人工勢場法存在局部最優(yōu)陷阱、目標(biāo)不可達(dá)等問題。

針對智能倉儲(chǔ)車間中多AGV路徑規(guī)劃問題，本文提出了一種改進(jìn)人工勢場蟻群融合算法。首先針對人工勢場法改進(jìn)斥力場函數(shù)，然后將人工勢場法生成路徑距離引入蟻群算法啟發(fā)信息中，并改進(jìn)蟻群算法信息素更新方式，提高算法的收斂速度和防止陷入局部最優(yōu)解陷阱，最后針對多AGV路徑規(guī)劃加入沖突解決策略來解決AGV路徑之間的沖突。仿真結(jié)果表明本文研究使改進(jìn)人工勢場蟻群融合算法在路徑規(guī)劃中耗時(shí)少，且能夠針對多AGV規(guī)劃出最優(yōu)路徑。

1 問題描述和環(huán)境建模

1.1 問題描述

在智能倉儲(chǔ)車間內(nèi)，為使多AGV運(yùn)輸系統(tǒng)完成運(yùn)輸任務(wù)，要求每臺(tái)AGV從起點(diǎn)出發(fā)，避開靜態(tài)障礙物，同時(shí)根據(jù)任務(wù)屬性賦予的優(yōu)先級信息，完成沖突路徑的避讓，最終到達(dá)目標(biāo)位置完成運(yùn)輸任務(wù)。每臺(tái)AGV所歸劃的行駛路徑都應(yīng)當(dāng)是當(dāng)前AGV從起點(diǎn)出發(fā)到達(dá)目標(biāo)點(diǎn)的最優(yōu)或次優(yōu)路徑（無碰撞、無沖突）。在進(jìn)行多AGV路徑規(guī)劃則需考慮如下約束條件：

（1）倉庫障礙物分布、可行路徑已知。

（2）每臺(tái)AGV的起點(diǎn)和目標(biāo)點(diǎn)已知。

（3）所有AGV逐步進(jìn)行路徑規(guī)劃直至到達(dá)目標(biāo)點(diǎn)。

（4）AGV行駛過程中每一步都要考慮障礙物避撞和沖突路徑的避讓。

因此本文提出人工勢場法蟻群混合算法，結(jié)合人工勢場法收斂速度快和蟻群算法全局規(guī)劃能力較強(qiáng)的優(yōu)點(diǎn)，通過引入人工勢場法先導(dǎo)路徑到蟻群算法啟發(fā)信息中，提高蟻群算法收斂速度，結(jié)合多AGV沖突避讓策略確定了每臺(tái)AGV從起點(diǎn)到目標(biāo)點(diǎn)的最佳路徑。

1.2 環(huán)境建模

AGV路徑規(guī)劃的首要條件是建立工作環(huán)境模型，通過標(biāo)注環(huán)境信息產(chǎn)生AGV能理解的環(huán)境地圖，使機(jī)器人可以在環(huán)境地圖中模擬實(shí)際運(yùn)輸路徑。常用的環(huán)境建模方法有拓?fù)鋱D法、可視圖法和柵格法等，其中柵格法具有易于實(shí)現(xiàn)、原理簡單等優(yōu)點(diǎn)，故本文中采用柵格法建立環(huán)境地圖，地圖中陰影部分代表障礙物，白色柵格為AGV可選柵格，如圖1所示。

圖1 柵格環(huán)境Fig.1 Grid environment

為柵格賦于序號(hào)的目的是方便表示路徑，而在計(jì)算柵格之間距離時(shí)需使用坐標(biāo)計(jì)算，兩者之間的轉(zhuǎn)換關(guān)系為：

其中，（x，y）表示序號(hào)為的坐標(biāo)；表示取余函數(shù)；表示橫坐標(biāo)的最大值；表示橫坐標(biāo)的最小值；表示縱坐標(biāo)的最大值；表示縱坐標(biāo)的最小值。

本文在序號(hào)法下，若路徑表示為｛X，，，，…，X，X｝，則表示從序號(hào)X為起點(diǎn)，行駛到目標(biāo)點(diǎn)X路徑經(jīng)過序號(hào)為X的柵格，則全局路徑長度函數(shù)為：

2 人工勢場法蟻群融合算法

2.1 人工勢場法優(yōu)化

2.1.1 人工勢場法原理

人工勢場法是由Khatib提出的一種虛擬力法。該法的基本思想是將機(jī)器人在環(huán)境中的運(yùn)動(dòng)抽象成在人造引力場中的運(yùn)動(dòng)，其中目標(biāo)點(diǎn)對于機(jī)器人產(chǎn)生“引力”，障礙物對于機(jī)器人產(chǎn)生“斥力”，最后通過合力來引導(dǎo)機(jī)器人的移動(dòng)方向。研究可知，機(jī)器人所受引力大小與目標(biāo)距離成正比，即目標(biāo)距離越遠(yuǎn)時(shí)、引力越大，目標(biāo)距離越近時(shí)、引力越小，到達(dá)目標(biāo)位置時(shí)、引力為0；機(jī)器人所受斥力大小與障礙物距離成反比，障礙物距離越遠(yuǎn)時(shí)、斥力越小，障礙物距離越近時(shí)、斥力越大。

在二維空間中機(jī)器人當(dāng)前位置為（，），目標(biāo)位置為X（x，y），障礙物位置為X（x，y），則有合力勢場函數(shù)為：

其中，U()為目標(biāo)點(diǎn)對機(jī)器人的引力勢場函數(shù)，具體計(jì)算公式為：

式（3）中，U()為機(jī)器人與障礙物之間的斥力勢場函數(shù)，具體計(jì)算公式為：

機(jī)器人所受到的引力為引力勢場函數(shù)的負(fù)梯度，其值可由如下公式計(jì)算得到：

機(jī)器人所受到的斥力為斥力勢場函數(shù)的負(fù)梯度，其值可由如下公式計(jì)算得到：

當(dāng)機(jī)器人處于障礙物的最大影響距離內(nèi)時(shí)，機(jī)器人所受到的合力為：

傳統(tǒng)人工勢場法相比其他路徑規(guī)劃方法具有計(jì)算量小、反應(yīng)速度較快及實(shí)時(shí)性較強(qiáng)的優(yōu)點(diǎn)，但是仍存在一定的局限性，如目標(biāo)不可達(dá)問題。

2.1.2 斥力場優(yōu)化

傳統(tǒng)人工勢場法中，機(jī)器人在空間中運(yùn)行時(shí)同時(shí)受到來自目標(biāo)點(diǎn)的引力和來自障礙物的斥力作用。當(dāng)目標(biāo)點(diǎn)周圍存在障礙物時(shí)，隨著機(jī)器人越來越接近目標(biāo)點(diǎn)，目標(biāo)點(diǎn)對機(jī)器人的引力持續(xù)衰減，而周圍障礙物對機(jī)器人的斥力則越來越大。此時(shí)人工勢場法路徑規(guī)劃易陷入目標(biāo)不可達(dá)問題。對此改進(jìn)斥力場函數(shù)，引入斥力勢場影響因子，針對目標(biāo)點(diǎn)附近障礙物排斥力進(jìn)行優(yōu)化，改進(jìn)后的斥力勢場函數(shù)為：

式（10）中，F()為障礙物指向機(jī)器人的斥力分量，具體表示為：

式（10）中，F()為機(jī)器人指向目標(biāo)點(diǎn)的引力分量，具體表示為：

2.2 融合蟻群算法優(yōu)化和人工勢場法

2.2.1 蟻群算法原理

蟻群算法（ACO）是一種用于優(yōu)化路徑尋找的概率型算法，最早由Marco Dorigo提出。蟻群算法模擬自然界中蟻群覓食的過程，其基本原理為：螞蟻在環(huán)境中隨機(jī)行走直至到達(dá)目標(biāo)地點(diǎn)，此路徑即為待優(yōu)化問題的可行解，全部螞蟻的行走路徑即為待優(yōu)化問題的解空間。其中，較短路徑上釋放的信息素較多，下次迭代時(shí)螞蟻會(huì)傾向于選擇信息素濃度更高的路徑。隨著迭代次數(shù)的增加，最終所有的螞蟻都會(huì)在正反饋機(jī)制的作用下集中到最短路徑上，此時(shí)的最短路徑即為待優(yōu)化問題的最優(yōu)解。

在標(biāo)準(zhǔn)蟻群算法中，螞蟻下一步所選節(jié)點(diǎn)的概率是根據(jù)可選路徑上的信息素濃度和啟發(fā)式信息決定。如在時(shí)刻，位于節(jié)點(diǎn)的螞蟻選擇下一節(jié)點(diǎn)的概率為：

其中，為信息素啟發(fā)因子，τ t()為信息素濃度，當(dāng)越大時(shí)，螞蟻越傾向于選擇信息素濃度高的節(jié)點(diǎn)；為啟發(fā)式因子；η t()為啟發(fā)式信息強(qiáng)度，η為節(jié)點(diǎn)到目標(biāo)點(diǎn)的歐式距離的倒數(shù)，當(dāng)越大時(shí)，螞蟻越傾向于選擇指向目標(biāo)點(diǎn)的最短路徑；表示下一步可選節(jié)點(diǎn)的集合。

當(dāng)螞蟻在路徑上行走時(shí)會(huì)遺留信息素，同時(shí)一部分信息素會(huì)隨時(shí)間揮發(fā)，每一次當(dāng)代螞蟻完成路徑后，按照如下信息素更新公式對全局信息素進(jìn)行更新：

2.2.2 人工勢場法引入啟發(fā)信息

在基本蟻群算法中，初始環(huán)境下蟻群信息素均勻分布，此時(shí)影響螞蟻選擇下一節(jié)點(diǎn)的主要因素為啟發(fā)式信息。原始啟發(fā)式信息的值為節(jié)點(diǎn)到目標(biāo)點(diǎn)的歐式距離的倒數(shù)，此時(shí)蟻群算法尋路方式類似于貪婪算法，當(dāng)位于特殊環(huán)境、如目標(biāo)點(diǎn)周圍存在較多障礙物時(shí)，蟻群算法初始路徑容易陷入局部最優(yōu)解，且由于蟻群算法的正反饋機(jī)制，易導(dǎo)致后續(xù)搜索局限在初始路徑周圍。

針對蟻群算法初始路徑受啟發(fā)式信息影響導(dǎo)致缺乏多樣性和陷入局部最優(yōu)解陷阱的問題，將人工勢場算法規(guī)劃的路徑距離信息引入到蟻群算法啟發(fā)信息中。同時(shí)為了避免蟻群算法后續(xù)迭代中受啟發(fā)式信息影響導(dǎo)致后續(xù)路徑缺少多樣性，在啟發(fā)信息中加入迭代次數(shù)N，隨著迭代次數(shù)N的增大自適應(yīng)減小啟發(fā)式信息對螞蟻下一節(jié)點(diǎn)選擇的影響。改進(jìn)后的啟發(fā)式信息函數(shù)為：

其中，為最大迭代次數(shù)；N為當(dāng)前迭代次數(shù)；d為可選節(jié)點(diǎn)到目標(biāo)點(diǎn)的歐式距離；R為改進(jìn)后的人工勢場法計(jì)算出的節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離；為可選節(jié)點(diǎn)集合。

2.2.3 信息素更新

基本蟻群算法中信息素更新公式為本次迭代完成的對全局路徑進(jìn)行處理，但是并未對當(dāng)前最優(yōu)路徑和當(dāng)前最差路徑做出區(qū)分，導(dǎo)致信息素濃度分布差異性不明顯，同時(shí)影響迭代效率。為解決此問題，在信息素更新規(guī)則中引進(jìn)狼群分配策略，即增強(qiáng)最優(yōu)路徑上信息素同時(shí)減少最差路徑信息素，從而引導(dǎo)螞蟻向最優(yōu)路徑靠攏，提高算法的收斂速度，改進(jìn)后的全局信息素更新公式為：

2.3 AGV沖突解決策略

在多AGV路徑規(guī)劃問題中，能否在保證路徑無沖突的情況下為每臺(tái)AGV規(guī)劃出各自的最優(yōu)路徑是問題的關(guān)鍵。以快消品制造車間為例，當(dāng)同車間的AGV運(yùn)輸物料基本相同，即AGV速度保持一致的情況下，多AGV運(yùn)行過程中可能會(huì)出現(xiàn)的沖突情況如圖2所示。由圖2可知，節(jié)點(diǎn)沖突表示當(dāng)2臺(tái)AGV在同一時(shí)間到達(dá)相同節(jié)點(diǎn)，此后駛向不同方向，2臺(tái)AGV僅在駛過碰撞節(jié)點(diǎn)時(shí)發(fā)生沖突。相向沖突1、相向沖突2都表示2臺(tái)AGV在到達(dá)相同節(jié)點(diǎn)后，對向行駛，此時(shí)2臺(tái)AGV在重合路徑上發(fā)生沖突。

圖2 沖突類型Fig.2 Conflict type

為避免多AGV路徑規(guī)劃時(shí)發(fā)生上述沖突，根據(jù)沖突類型采取不同沖突解決策略，具體規(guī)則如下：

（1）停車等待。針對節(jié)點(diǎn)沖突情況，采用優(yōu)先通行策略，即根據(jù)任務(wù)屬性、剩余路徑長度等因素為AGV賦予不同優(yōu)先級。當(dāng)2臺(tái)AGV到達(dá)同一節(jié)點(diǎn)時(shí)，優(yōu)先根據(jù)任務(wù)屬性分配臨時(shí)優(yōu)先級，當(dāng)任務(wù)屬性無法區(qū)分時(shí)，分別計(jì)算2臺(tái)AGV剩余路徑長度，為剩余路徑較短AGV賦予較高的臨時(shí)優(yōu)先級并優(yōu)先通行，另一臺(tái)臨時(shí)?？康却?。通過沖突節(jié)點(diǎn)后清空臨時(shí)優(yōu)先級。

（2）重新尋路-臨時(shí)避讓。針對相向沖突的2種情況，除了重新尋路解決沖突問題外，還要考慮是否可以通過臨時(shí)避讓解決沖突。具體表現(xiàn)為：當(dāng)AGV間出現(xiàn)相向沖突時(shí)，若優(yōu)先級較低、AGV當(dāng)前所在節(jié)點(diǎn)上存在其他可通行方向，且轉(zhuǎn)向其他方向后等待另一AGV通過時(shí)間和原剩余路徑長度行駛時(shí)間的和小于從當(dāng)前節(jié)點(diǎn)重新規(guī)劃的路徑行駛時(shí)間，則優(yōu)先采用臨時(shí)避讓策略；否則從當(dāng)前節(jié)點(diǎn)重新規(guī)劃到目標(biāo)點(diǎn)的路徑。重新尋路-臨時(shí)避讓流程如圖3所示。

圖3 重新尋路-臨時(shí)避讓流程圖Fig.3 Repathing-temporary avoidance flow chart

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

3.1 路徑規(guī)劃實(shí)現(xiàn)流程

改進(jìn)后的人工勢場蟻群算法結(jié)合多AGV路徑規(guī)劃沖突解決策略，制定多AGV路徑規(guī)劃流程圖，具體如圖4所示。

圖4 多AGV路徑規(guī)劃流程圖Fig.4 Multi-AGV path planning flow chart

3.2 單機(jī)器人仿真實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)后的人工勢場蟻群算法的可行性，通過Python3.9利用柵格法建立模擬環(huán)境，選取傳統(tǒng)蟻群算法、文獻(xiàn)［11］改進(jìn)勢場蟻群算法和本文改進(jìn)后的人工勢場蟻群算法進(jìn)行比較。

實(shí)驗(yàn)環(huán)境及參數(shù)為：環(huán)境為20×20二維平面，路徑柵格和障礙物柵格數(shù)量之比為6∶4，障礙物隨機(jī)分配，最大迭代次數(shù)100，螞蟻數(shù)量50，啟發(fā)式信息影響因子1，信息素?fù)]發(fā)系數(shù)04，信息素強(qiáng)度10。

傳統(tǒng)蟻群算法、文獻(xiàn)［11］算法、本文算法路徑規(guī)劃結(jié)果如圖5所示。圖5中，藍(lán)色虛線為傳統(tǒng)蟻群算法規(guī)劃路徑，紫色點(diǎn)虛線為文獻(xiàn)［11］算法規(guī)劃路徑，紅色實(shí)線為本文算法規(guī)劃路徑。

圖5 傳統(tǒng)蟻群算法、文獻(xiàn)［11］算法、本文算法路徑Fig.5 The path of traditional ant colony algorithm，the path of reference［11］algorithm and the algorithm path of this paper

傳統(tǒng)蟻群算法、文獻(xiàn)［11］算法、本文算法收斂結(jié)果對比如圖6所示。由圖6可以看出，在20×20隨機(jī)柵格環(huán)境下，本文算法生成的最優(yōu)路徑相比于傳統(tǒng)算法和文獻(xiàn)［11］改進(jìn)算法在路徑長度、轉(zhuǎn)彎次數(shù)上均有較好的表現(xiàn)。由圖6還可以看出本文算法相比于其他2種算法的收斂速度更快。在20×20環(huán)境下3種算法仿真對比結(jié)果見表1。由表1可知，本文相比于傳統(tǒng)算法最優(yōu)路徑長度減少14%，收斂于最優(yōu)路徑迭代次數(shù)減少51%，算法耗費(fèi)時(shí)間減少25%，轉(zhuǎn)彎次數(shù)減少45%。相比于文獻(xiàn)［11］，最優(yōu)路徑長度減少8%，收斂于最優(yōu)路徑迭代次數(shù)減少19%，算法耗費(fèi)時(shí)間減少12%，轉(zhuǎn)彎次數(shù)減少33%，這是因?yàn)槲墨I(xiàn)［11］未解決原始人工勢場法易陷入目標(biāo)不可達(dá)問題，導(dǎo)致機(jī)器人在障礙物較多環(huán)境中無法快速規(guī)劃出合理路線。綜上所述可知，本文算法相較于傳統(tǒng)蟻群算法和文獻(xiàn)［11］改進(jìn)算法，均有較好的表現(xiàn)。

表1 20×20環(huán)境下3種算法仿真結(jié)果對比Tab.1 Comparison of simulation results of 3 algorithms under 20×20 environment

圖6 傳統(tǒng)蟻群算法、文獻(xiàn)［11］算法、本文算法收斂比較Fig.6 Convergence comparison of traditional ant colony algorithm，reference［11］algorithm and the algorithm in this paper

3.3 多機(jī)器人仿真實(shí)驗(yàn)

為驗(yàn)證本文算法在實(shí)際倉儲(chǔ)環(huán)境下能否實(shí)現(xiàn)多AGV路徑?jīng)_突問題，通過Python3.9構(gòu)建倉儲(chǔ)布局柵格地圖，其中為每臺(tái)AGV設(shè)定行走占地范圍，當(dāng)2臺(tái)AGV存在占地范圍重疊時(shí)，即認(rèn)為路徑出現(xiàn)沖突。其中，未采用重新尋路-臨時(shí)避讓策略的多AGV行走路徑規(guī)劃如圖7所示。

圖7 多AGV路徑?jīng)_突Fig.7 Multi-AGV path conflict

由圖7可知，當(dāng)系統(tǒng)未采用重新尋路-臨時(shí)避讓策略時(shí)，所有AGV選擇各自最優(yōu)路徑執(zhí)行運(yùn)輸任務(wù)，其中系統(tǒng)運(yùn)行至第9步時(shí)，和在柵格出現(xiàn)節(jié)點(diǎn)沖突；和在柵格出現(xiàn)相向沖突。此時(shí)，系統(tǒng)的全局最優(yōu)路徑長度為117.799 m，運(yùn)行時(shí)間為27.242 6 s。

圖8 多AGV路徑?jīng)_突解決Fig.8 Multi-AGV path conflict resolution

采用本文沖突解決策略后，系統(tǒng)全局最優(yōu)路徑長度為119.627 4 m，系統(tǒng)運(yùn)行時(shí)間為28.071 1 s，相較于原始最優(yōu)路徑長度和運(yùn)行時(shí)間僅分別增加1.5%和3%。通過不同仿真環(huán)境下的實(shí)驗(yàn)可知，本文提出的人工勢場蟻群融合算法在不同環(huán)境下都可快速找到最優(yōu)路徑，實(shí)時(shí)規(guī)避動(dòng)態(tài)障礙物，規(guī)劃出全局最優(yōu)路徑，證明了本文提出的人工勢場蟻群融合算法的可行性和有效性。

4 結(jié)束語

在快消品制造行業(yè)快速發(fā)展的背景下，針對智能倉儲(chǔ)環(huán)境下多AGV路徑優(yōu)化的問題，本文通過對人工勢場法斥力場函數(shù)、蟻群算法啟發(fā)式、信息素更新算法及多AGV沖突解決策略等方面提出相應(yīng)優(yōu)化策略，提出人工勢場蟻群融合算法，在以倉儲(chǔ)車間的仿真環(huán)境下通過單AGV路徑規(guī)劃實(shí)驗(yàn)和多AGV路徑?jīng)_突實(shí)驗(yàn)進(jìn)行分析，驗(yàn)證了本文算法能夠在優(yōu)化路徑長度、提高收斂速度的基礎(chǔ)上完成多AGV路徑?jīng)_突的解決。本文算法已經(jīng)應(yīng)用于某大型快消品制造企業(yè)在漯河某地的無人化制造車間的倉儲(chǔ)物流設(shè)計(jì)中，不久將投入實(shí)際生產(chǎn)活動(dòng)中。