智能化倉庫的AGV路徑規劃與緊急避障系統

孫兆臣,孫曉琴,楊文

智能化倉庫的AGV路徑規劃與緊急避障系統

孫兆臣,孫曉琴,楊文

云南電網有限責任公司大理供電局, 云南 大理 671000

針對智能化倉庫復雜的物流環境，對AGV運作要求越來愈高，本文給出考慮任務優先級的多AGV系統路徑規劃算法，并基于倉庫復雜環境下AGV作業方式提出動態避障策略。以二維空間建立多AGV運作拓撲地圖，采用改進A*算法求解單AGV最優路徑，并應用Logistic函數描述多AGV系統路徑使用頻次的負載因子，減少多AGV系統阻塞路段以提高系統運作效率；同時提出兩項同步并行避碰機制以解決多AGV運作環境下存在的四種碰撞類型，實驗驗證方案可行。

智能化倉庫; 多AGV系統; 路徑規劃; 避障策略

近年來，隨著物流業的發展，普遍對物流的時效性和準確性提出越來越高的嚴苛要求。為緩解物流行業高成本和低時效問題，智能化倉庫應運而生。自動化導引車（AGV，Automatic Guided Vehicle）作為智能化倉庫必不可少的載體之一，在智能化立體倉庫廣泛應用，成為學者研究的熱點問題。

隨著物聯網技術的不斷發展，高效的調度管理和路徑規劃成為AGV研究熱點和得到更廣泛應用的難點。針對該問題，國內外學者做了大量研究，諸多成果在行業得到推廣應用。房殿軍等[1]依據電商行業倉儲需求，提出自動化立體倉庫中AGV群里靜態路徑規劃方法及動態避障決策策略；徐鎮華等[2]在考慮AGV運行時間窗的基礎上提出兩階段AGV路徑規劃方法并建立模型，采用改進Dijkstra算法求解驗證其方案有效可行；廉胤東等[3]提出在視覺引導條件下，建立多AGV系統模型，采用改進A*算法求解驗證系統運作效率的提升；霍凱歌等[4]針對特定區域下，考慮集裝箱碼運作需求建立GV調度管理的混合整數模型，并采用GUROBI和遺傳算法結合進行求解。此外，AGV系統避碰策略也得到廣泛研究。Singh Y等[5]提出考慮安全距離的改進A*路徑規劃算法，提高系統效率有效改善沖突異常；泰應鵬等[6]考慮AGV動態運行的節點時間窗，建立多AGV避碰數學模型，采用A*算法求解模型，避免AGV碰撞異常。

多數針對AGV系統多集中在適應特定場景的路徑規劃采用單一避碰策略。本文考慮智能倉庫物流運作復雜環境下，采用以二維空間描述倉庫多AGV運作拓撲地圖，用Logistic函數求解多AGV系統路徑使用頻次的負載因子，將該函數融入到改進A*算法求解以均衡地圖各段路徑負載，提高運作效率；提出并行避碰機制以解決多AGV運作環境下由于路徑沖突、節點等待影響運作效率的問題。

1 問題描述

研究對象為倉庫復雜物流作業區域下的多AGV系統。倉庫采用拓撲圖法將倉庫AGV運作環境抽象為特征節點和節邊，即：52個特征節點，89個特征邊，包含揀貨、出入庫、充電、搬運功能區。

圖1所示，1～8節點：分揀區，堆垛機根據指令從貨架取貨至AGV；9～40節點：AGV搬運作業節點；41～48節點：出入庫區；A～D節點：充電區。本文聚焦AGV路徑規劃和動態避障問題，邏輯框架圖2所示。

圖1 某智能倉庫物流拓撲節點圖

圖2 邏輯框架圖

對模型假設：AGV速度1 m/s；相鄰節點：5 m；AGV節點轉向時間2 s；障礙檢測1次/s；檢測半徑5 m。

2 多AGV任務分配與路徑規劃

2.1 AGV任務執行優先級

AGV任務來源：①搬運任務；②AGV自主充電和停靠；針對搬運任務，本文采用先到先服務原則。針對AGV充電和停靠作業，設定當電量低于20%時，優先執行充電，不接受搬運任務；在充電過程中，電量低于50%，繼續充電任務；電量大于50%，執行搬運任務，AGV任務執行優先級規則如圖3所示。

圖3 AGV任務執行優先級

2.2 多AGV路徑規劃

基于特征邊負載因子的路徑規劃目標：①路徑最短；②時間最短；目標的達成都無可避免路徑繁忙程度不同，為平衡負載考慮為路徑設置特征邊的負載因子。該負載因子作為懲罰項作用于特征邊長度，繁忙特征邊，負載因子越大，同樣環境下增大特征邊長度。采用Logistic函數描述對特征邊的負載因子φ：

式中：n為特征邊通過AG車頻次，為所有特征邊AGV總頻次。倉庫拓撲圖中特征邊長度權值[7]：

基于時間窗的多AGV路徑規劃在路徑規劃問題中，A*啟發式算法描述為：()=()+() (3)

式中，()：起始節點經過節點到目標節點的距離代價評估，()描述起始節點行駛至目前節點的實際距離；()描述目前節點行駛至目標節點的距離代價評估。算法思想：AGV從起始節點起算法不斷搜索當前節點至目標節點的最小距離()min，以此選擇AGV小車路徑的下個節點，已達到求解目標函數()min。多AGV系統在運行過程中，此時需對A*算法進行改進，引入不確定時間t改進A*算法：

(,t)=(,t)+(,t) (4)

式中：(,t)描述起始節點到節點的實際時間；(,t)描述從節點到目標節點的時間預估。

定義AGV起始節點、當前節點、目標節點坐標分別為(s,s)，(n,n)，(e,e)。當AGV節點出發，此時(,t)=0，相鄰,兩節點時間代價估計：(w())，則當前任一特征節點到目標節點可描述為[8]：

設定轉彎時間=2 s，通過規劃路徑和兩節點的相對位置，確定AGV在節點是否需要轉彎，在理想狀態下，兩相鄰特征節點時間間隔T=(,t)=(,t)，可得：

(,t)=(,t)+(w(t+))++(,t)=(,t)+(w(t))+(,t) (6)

A*算法維護兩個列表：表OpenList和CloseList，算法索引過程：

（1）起始節點處(,t)=0，并記錄AGV起始節點t，此時(,t)=0，將特征節點添加進CloseList；

（2）節點可達的特征節點加入OpenList中，將起始節點從OpenList中刪去，加入到CloseList。

（3）將OpenList表中各特征節點中(,t)取最小值加入到CloseList[8]；

（4）若CloseList表中包含終止特征節點，則算法停止搜索；若表不含終止特征節點，則返回（2）。

多AGV路徑規劃，采用改進A*算法執行AGV路徑規劃，A*算法迭代流程如圖4所示。

2.3 算例實施

分別指派1#AGV和2#AGV完成任務A和B。任務A指派1#AGV：特征節點27→特征節點22；任務B指派2#AGV：特征節點13→36。

圖4 多AGV路徑規劃迭代流程圖

圖5 某智能倉庫物流拓撲節點圖

調用改進A*算法分別對1-2#AGV路徑規劃如上圖5所示。1-2#AGV時間窗如下：

表1 任務A和B單獨路徑規劃

A和B在29節點出現交叉沖突。假設任務A優先級高于B，同時采用改進A*進行路徑規劃：

表2 任務A和B組合路徑規劃

由表2所示：任務A和B執行時間窗不再沖突，實例驗證改進A*算法能對多AGV系統進行路徑規劃。

此外，當AGV和任務足夠多時，特征邊“繁忙”不一，Logistic函數描述負載因子均衡化倉庫特征邊路徑負載，對優化多AGV系統路徑。如隨機給定倉庫500個任務序列，分別應用改進A*算法求解考慮Logistic函數描述負載因子下和不考慮負載因子的最優解，統計每條特征邊負載，即AGV通過頻次，如圖6所示。

如圖6所示，Logistic函數引入A*算法能有效均衡特征邊負載。然而當多AGV系統足夠復雜時，上述模型多出過多理想化假設，實際運行不可避免出現AGV系統出現等待、碰撞等路徑沖突。

圖6 有無Logistic函數對比圖

圖7 AGV碰撞類型

3 多AGV避碰策略

3.1 沖突檢測模型

常見的沖突，如圖7所示：（a）相對沖突；（b）節點占用沖突；（c）交叉沖突；（d）貨架占用沖突[9]。

針對以上存在四種碰撞類型，為建立AGV碰撞模型，設定以下參數：

結合以上參數，建立任兩AGV沖突類型檢測模型：

（1）若滿足（7）同時滿足約束條件(8)，則任兩AGV在特征邊((),()+1)發生相對沖突：

式中：，沖突檢測系數，為保證模型檢測準確性和實用性，根據實際運作系統，設置系數常數。

（2）若滿足（7）同時滿足約束條件(9)，則任兩AGV在特征邊((),()+1)發生交叉沖突：

（3）若滿足（10）同時滿足條件(11)，則任兩AGV在特征邊((),()+1)發生交叉沖突：

（4）若滿足（10）同時滿足條件(12)，則任兩AGV在特征邊((),()+1)發生貨架占用沖突：

3.2 并行避碰策略

針對倉庫多AGV系統，當AGV沖突時，讓優先級低的AGV等待。顯然傳統的等待策略大幅度降低系統的運行的效率，換句話說，通過犧牲系統的效率解決AGV碰撞問題。

多AGV系統的沖突解決策略對于智能倉庫的安全性和高效性運行至關重要，采取避障策略是關鍵，基于此，文中對傳統等待避障策略改進優化，提出并行動態策略。根據碰撞類型，提出解決避障措施[10]：

（1）等待策略：即傳統避障策略，不再贅述；

（2）更改路徑規劃策略：當任兩AGV路徑沖突時，任務優先級較高AGV執行原路徑，另一AGV在刪除物流拓撲圖沖突的特征節點和特征邊，重新進行路徑規劃，執行路徑規劃次優解[11]；

（3）任務重新指派策略：當任兩AGV路徑沖突時，任務優先級較高AGV執行原路徑，另一AGV關閉任務，該任務優先指派給未發生沖突且距離該AGV最近的AGV執行該次搬運任務。

上述3種策略中，考慮應用的普適性，采用等待和更改路徑規劃策略并行的自適應解決策略。

3.3 避碰策略算例

針對3.2提出的策略、更改路徑規劃策略以及兩者并行混合動態策略進行算例驗證。設定如下優先級遞減任務，Case1：1#AGV執行優先級較高搬運任務1，從特征節點17→特征節點19；Case2：2#AGV執行搬運任務2，從特征節點26→特征節點02；Case3：3#AGV執行搬運任務3，從特征節點21→特征節點40；Case4：3#AGV執行搬運任務3，從特征節點07→特征節點29。

分別采用改進A*算法得出1-4#AGV路徑規劃，如圖8所示。

圖8 多AGV路徑規劃簡圖

采用等待策略和更改路徑規劃策略結合動態混合策略下，采用改進A*算法[12]，對上述任務序列求解，不難得出倉庫中AGV經過各特征節點和特征邊的時間窗，如表3所示：

表3 任務A和B組合路徑規劃

在采用等待策和更改路徑規劃策略并行的自適應解決策略，完成任務27 s；此外，當單獨采用等待策略時，4#AGV任務路徑4：特征節點07→15→23→31→30→29→28，1-4#AGV完成任務需要37 s；單獨采用更改路徑規劃策略時，2#AGV任務路徑2：特征節點17→25→26→27→19，1-4#AGV完成任務需要29 s。不難看出相比單獨采用等待策和更改路徑規劃策略，采用兩者并行的自適應解決策略更有優，效率更高。

4 結論

本文針對智能倉庫多AGV系統的路徑規劃和避障策略問題展開研究。首先，倉庫采用拓撲地圖法將倉庫物理空間抽象為二維坐標模型的基礎上，同時創造性的應用Logistic函數描述地圖特征邊負載，在考慮任務優先級的情況下采用改進A*算法對倉庫多AGV系統進行路徑規劃；然后基于多AGV系統存在四種碰撞類型模型，提出等待策略與更改路徑規劃策略并行的動態策略，在保證安全性避免碰撞的基礎上，對比傳統等待策略或單獨采用更改路徑規劃策略具有更客觀的作業效率，具有現實指導實踐意義。

[1] 房殿軍,周濤.自動化立體倉庫中智能AGV群體的靜態路徑規劃與動態避障決策研究[J].物流技術,2017(6):177-185

[2] 徐鎮華,馬殷元.基于時間窗的改進兩階段AGV路徑規劃研究[J].測控技術,2018,37(6):145-149,154

[3] 廉胤東,謝巍.基于視覺引導多AGV系統的改進A*路徑規劃算法研究[J/OL].控制與決策.https://doi.org/10.13195/j.kzyjc.2019.1670

[4] 霍凱歌,張亞琦,胡志華.自動化集裝箱碼頭多載AGV調度問題研究[J].大連理工大學學報,2016,56(3):244-251

[5] Singh Y, Sharma S, Sutton R,. A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents [J]. Ocean Engineering, 2018, 169:187-201

[6] 泰應鵬,邢科新,林葉貴,等.多AGV路徑規劃方法研究[J].計算機科學,2017,44(11A):84-87

[7] 李偉光,蘇霞.基于改進A*算法的AGV路徑規劃[J].現代制造工程2015(10):33-36

[8] 張政.倉儲系統AGV路徑規劃研究[D].北京:北京化工大學,2018

[9] 李婷.自動化倉庫系統多AGV路徑規劃和避碰策略研究[D].哈爾濱:哈爾濱工業大學,2018

[10] Gao X, Jia Q, Sun H,. Research on Path Planning for 7-DOF Space Manipulator to Avoid Obstacle Based on A* Algorithm [J]. Sensor Letters, 2011,9(4):1515-1519

[11] Yuan RP, Dong TT, Li JT. Research on the Collision-Free Path Planning of Multi-AGVs System Based on Improved A-STAR Algorithm [J]. American Journal of Operations Research, 2016,6:442-449

[12] Liu CB, Tan J, Zhao HSPath Planning and Intelligent Scheduling of Multi-AGV Systems in Workshop [C]. Dalian China: Proceedings of the 36th Chinese Control Conference, 2017

AGV Path Planning and Emergency Obstacle Avoidance System in Intelligent Warehouse

SUN Zhao-chen, SUN Xiao-qin, YANG Wen

671000,

In view of the complex logistics environment of intelligent warehouse, higher requirements are placed on the operation of AGV. In this paper, the path-planning algorithm of multiple AGV systems considering task priority is given, and a dynamic obstacle avoidance strategy is proposed based on the AGV operation mode in the complex warehouse environment. The multi-AGV operation topology map is built in two-dimensional space, the single AGV optimal path is solved by improved A*algorithm, and the load factor of multi AGV system path usage frequency is described by logistic function to reduce the blocking road section of multi AGV system and improve the system operation efficiency. A parallel collision avoidance mechanism is proposed to solve the four collision types existing in the multi-AGV operating environment. The experimental verification scheme is feasible

intelligent warehouse; multi-AGV system; path planning; obstacle avoidance strategy

TH692.3

A

1000-2324(2021)03-0483-06

2020-05-27

2020-06-07

南方電網公司科技資助項目(YNKJXM20180007)

孫兆臣(1982-),男,本科,工程師,主要從事智能倉庫建設. E-mail:sunzhaochen@163.com