智能倉儲車間中多AGV路徑優化算法研究

韓 強，何利力

（浙江理工大學 信息學院，杭州 310018）

0 引 言

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

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

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

1 問題描述和環境建模

1.1 問題描述

在智能倉儲車間內，為使多AGV運輸系統完成運輸任務，要求每臺AGV從起點出發，避開靜態障礙物，同時根據任務屬性賦予的優先級信息，完成沖突路徑的避讓，最終到達目標位置完成運輸任務。每臺AGV所歸劃的行駛路徑都應當是當前AGV從起點出發到達目標點的最優或次優路徑（無碰撞、無沖突）。在進行多AGV路徑規劃則需考慮如下約束條件：

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

（2）每臺AGV的起點和目標點已知。

（3）所有AGV逐步進行路徑規劃直至到達目標點。

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

因此本文提出人工勢場法蟻群混合算法，結合人工勢場法收斂速度快和蟻群算法全局規劃能力較強的優點，通過引入人工勢場法先導路徑到蟻群算法啟發信息中，提高蟻群算法收斂速度，結合多AGV沖突避讓策略確定了每臺AGV從起點到目標點的最佳路徑。

1.2 環境建模

AGV路徑規劃的首要條件是建立工作環境模型，通過標注環境信息產生AGV能理解的環境地圖，使機器人可以在環境地圖中模擬實際運輸路徑。常用的環境建模方法有拓撲圖法、可視圖法和柵格法等，其中柵格法具有易于實現、原理簡單等優點，故本文中采用柵格法建立環境地圖，地圖中陰影部分代表障礙物，白色柵格為AGV可選柵格，如圖1所示。

圖1 柵格環境Fig.1 Grid environment

為柵格賦于序號的目的是方便表示路徑，而在計算柵格之間距離時需使用坐標計算，兩者之間的轉換關系為：

其中，（x，y）表示序號為的坐標；表示取余函數；表示橫坐標的最大值；表示橫坐標的最小值；表示縱坐標的最大值；表示縱坐標的最小值。

本文在序號法下，若路徑表示為｛X，，，，…，X，X｝，則表示從序號X為起點，行駛到目標點X路徑經過序號為X的柵格，則全局路徑長度函數為：

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

2.1 人工勢場法優化

2.1.1 人工勢場法原理

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

在二維空間中機器人當前位置為（，），目標位置為X（x，y），障礙物位置為X（x，y），則有合力勢場函數為：

其中，U()為目標點對機器人的引力勢場函數，具體計算公式為：

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

機器人所受到的引力為引力勢場函數的負梯度，其值可由如下公式計算得到：

機器人所受到的斥力為斥力勢場函數的負梯度，其值可由如下公式計算得到：

當機器人處于障礙物的最大影響距離內時，機器人所受到的合力為：

傳統人工勢場法相比其他路徑規劃方法具有計算量小、反應速度較快及實時性較強的優點，但是仍存在一定的局限性，如目標不可達問題。

2.1.2 斥力場優化

傳統人工勢場法中，機器人在空間中運行時同時受到來自目標點的引力和來自障礙物的斥力作用。當目標點周圍存在障礙物時，隨著機器人越來越接近目標點，目標點對機器人的引力持續衰減，而周圍障礙物對機器人的斥力則越來越大。此時人工勢場法路徑規劃易陷入目標不可達問題。對此改進斥力場函數，引入斥力勢場影響因子，針對目標點附近障礙物排斥力進行優化，改進后的斥力勢場函數為：

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

式（10）中，F()為機器人指向目標點的引力分量，具體表示為：

2.2 融合蟻群算法優化和人工勢場法

2.2.1 蟻群算法原理

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

在標準蟻群算法中，螞蟻下一步所選節點的概率是根據可選路徑上的信息素濃度和啟發式信息決定。如在時刻，位于節點的螞蟻選擇下一節點的概率為：

其中，為信息素啟發因子，τ t()為信息素濃度，當越大時，螞蟻越傾向于選擇信息素濃度高的節點；為啟發式因子；η t()為啟發式信息強度，η為節點到目標點的歐式距離的倒數，當越大時，螞蟻越傾向于選擇指向目標點的最短路徑；表示下一步可選節點的集合。

當螞蟻在路徑上行走時會遺留信息素，同時一部分信息素會隨時間揮發，每一次當代螞蟻完成路徑后，按照如下信息素更新公式對全局信息素進行更新：

2.2.2 人工勢場法引入啟發信息

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

針對蟻群算法初始路徑受啟發式信息影響導致缺乏多樣性和陷入局部最優解陷阱的問題，將人工勢場算法規劃的路徑距離信息引入到蟻群算法啟發信息中。同時為了避免蟻群算法后續迭代中受啟發式信息影響導致后續路徑缺少多樣性，在啟發信息中加入迭代次數N，隨著迭代次數N的增大自適應減小啟發式信息對螞蟻下一節點選擇的影響。改進后的啟發式信息函數為：

其中，為最大迭代次數；N為當前迭代次數；d為可選節點到目標點的歐式距離；R為改進后的人工勢場法計算出的節點到目標點的距離；為可選節點集合。

2.2.3 信息素更新

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

2.3 AGV沖突解決策略

在多AGV路徑規劃問題中，能否在保證路徑無沖突的情況下為每臺AGV規劃出各自的最優路徑是問題的關鍵。以快消品制造車間為例，當同車間的AGV運輸物料基本相同，即AGV速度保持一致的情況下，多AGV運行過程中可能會出現的沖突情況如圖2所示。由圖2可知，節點沖突表示當2臺AGV在同一時間到達相同節點，此后駛向不同方向，2臺AGV僅在駛過碰撞節點時發生沖突。相向沖突1、相向沖突2都表示2臺AGV在到達相同節點后，對向行駛，此時2臺AGV在重合路徑上發生沖突。

圖2 沖突類型Fig.2 Conflict type

為避免多AGV路徑規劃時發生上述沖突，根據沖突類型采取不同沖突解決策略，具體規則如下：

（1）停車等待。針對節點沖突情況，采用優先通行策略，即根據任務屬性、剩余路徑長度等因素為AGV賦予不同優先級。當2臺AGV到達同一節點時，優先根據任務屬性分配臨時優先級，當任務屬性無法區分時，分別計算2臺AGV剩余路徑長度，為剩余路徑較短AGV賦予較高的臨時優先級并優先通行，另一臺臨時停靠等待。通過沖突節點后清空臨時優先級。

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

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

3 算法仿真實驗

3.1 路徑規劃實現流程

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

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

3.2 單機器人仿真實驗

為了驗證改進后的人工勢場蟻群算法的可行性，通過Python3.9利用柵格法建立模擬環境，選取傳統蟻群算法、文獻［11］改進勢場蟻群算法和本文改進后的人工勢場蟻群算法進行比較。

實驗環境及參數為：環境為20×20二維平面，路徑柵格和障礙物柵格數量之比為6∶4，障礙物隨機分配，最大迭代次數100，螞蟻數量50，啟發式信息影響因子1，信息素揮發系數04，信息素強度10。

傳統蟻群算法、文獻［11］算法、本文算法路徑規劃結果如圖5所示。圖5中，藍色虛線為傳統蟻群算法規劃路徑，紫色點虛線為文獻［11］算法規劃路徑，紅色實線為本文算法規劃路徑。

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

傳統蟻群算法、文獻［11］算法、本文算法收斂結果對比如圖6所示。由圖6可以看出，在20×20隨機柵格環境下，本文算法生成的最優路徑相比于傳統算法和文獻［11］改進算法在路徑長度、轉彎次數上均有較好的表現。由圖6還可以看出本文算法相比于其他2種算法的收斂速度更快。在20×20環境下3種算法仿真對比結果見表1。由表1可知，本文相比于傳統算法最優路徑長度減少14%，收斂于最優路徑迭代次數減少51%，算法耗費時間減少25%，轉彎次數減少45%。相比于文獻［11］，最優路徑長度減少8%，收斂于最優路徑迭代次數減少19%，算法耗費時間減少12%，轉彎次數減少33%，這是因為文獻［11］未解決原始人工勢場法易陷入目標不可達問題，導致機器人在障礙物較多環境中無法快速規劃出合理路線。綜上所述可知，本文算法相較于傳統蟻群算法和文獻［11］改進算法，均有較好的表現。

表1 20×20環境下3種算法仿真結果對比Tab.1 Comparison of simulation results of 3 algorithms under 20×20 environment

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

3.3 多機器人仿真實驗

為驗證本文算法在實際倉儲環境下能否實現多AGV路徑沖突問題，通過Python3.9構建倉儲布局柵格地圖，其中為每臺AGV設定行走占地范圍，當2臺AGV存在占地范圍重疊時，即認為路徑出現沖突。其中，未采用重新尋路-臨時避讓策略的多AGV行走路徑規劃如圖7所示。

圖7 多AGV路徑沖突Fig.7 Multi-AGV path conflict

由圖7可知，當系統未采用重新尋路-臨時避讓策略時，所有AGV選擇各自最優路徑執行運輸任務，其中系統運行至第9步時，和在柵格出現節點沖突；和在柵格出現相向沖突。此時，系統的全局最優路徑長度為117.799 m，運行時間為27.242 6 s。

圖8 多AGV路徑沖突解決Fig.8 Multi-AGV path conflict resolution

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

4 結束語

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