孫兆臣,孫曉琴,楊文

智能化倉庫的AGV路徑規(guī)劃與緊急避障系統(tǒng)

孫兆臣,孫曉琴,楊文

云南電網(wǎng)有限責(zé)任公司大理供電局, 云南 大理 671000

針對(duì)智能化倉庫復(fù)雜的物流環(huán)境，對(duì)AGV運(yùn)作要求越來愈高，本文給出考慮任務(wù)優(yōu)先級(jí)的多AGV系統(tǒng)路徑規(guī)劃算法，并基于倉庫復(fù)雜環(huán)境下AGV作業(yè)方式提出動(dòng)態(tài)避障策略。以二維空間建立多AGV運(yùn)作拓?fù)涞貓D，采用改進(jìn)A*算法求解單AGV最優(yōu)路徑，并應(yīng)用Logistic函數(shù)描述多AGV系統(tǒng)路徑使用頻次的負(fù)載因子，減少多AGV系統(tǒng)阻塞路段以提高系統(tǒng)運(yùn)作效率；同時(shí)提出兩項(xiàng)同步并行避碰機(jī)制以解決多AGV運(yùn)作環(huán)境下存在的四種碰撞類型，實(shí)驗(yàn)驗(yàn)證方案可行。

智能化倉庫; 多AGV系統(tǒng); 路徑規(guī)劃; 避障策略

近年來，隨著物流業(yè)的發(fā)展，普遍對(duì)物流的時(shí)效性和準(zhǔn)確性提出越來越高的嚴(yán)苛要求。為緩解物流行業(yè)高成本和低時(shí)效問題，智能化倉庫應(yīng)運(yùn)而生。自動(dòng)化導(dǎo)引車（AGV，Automatic Guided Vehicle）作為智能化倉庫必不可少的載體之一，在智能化立體倉庫廣泛應(yīng)用，成為學(xué)者研究的熱點(diǎn)問題。

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

多數(shù)針對(duì)AGV系統(tǒng)多集中在適應(yīng)特定場(chǎng)景的路徑規(guī)劃采用單一避碰策略。本文考慮智能倉庫物流運(yùn)作復(fù)雜環(huán)境下，采用以二維空間描述倉庫多AGV運(yùn)作拓?fù)涞貓D，用Logistic函數(shù)求解多AGV系統(tǒng)路徑使用頻次的負(fù)載因子，將該函數(shù)融入到改進(jìn)A*算法求解以均衡地圖各段路徑負(fù)載，提高運(yùn)作效率；提出并行避碰機(jī)制以解決多AGV運(yùn)作環(huán)境下由于路徑?jīng)_突、節(jié)點(diǎn)等待影響運(yùn)作效率的問題。

1 問題描述

研究對(duì)象為倉庫復(fù)雜物流作業(yè)區(qū)域下的多AGV系統(tǒng)。倉庫采用拓?fù)鋱D法將倉庫AGV運(yùn)作環(huán)境抽象為特征節(jié)點(diǎn)和節(jié)邊，即：52個(gè)特征節(jié)點(diǎn)，89個(gè)特征邊，包含揀貨、出入庫、充電、搬運(yùn)功能區(qū)。

圖1所示，1～8節(jié)點(diǎn)：分揀區(qū)，堆垛機(jī)根據(jù)指令從貨架取貨至AGV；9～40節(jié)點(diǎn)：AGV搬運(yùn)作業(yè)節(jié)點(diǎn)；41～48節(jié)點(diǎn)：出入庫區(qū)；A～D節(jié)點(diǎn)：充電區(qū)。本文聚焦AGV路徑規(guī)劃和動(dòng)態(tài)避障問題，邏輯框架圖2所示。

圖1 某智能倉庫物流拓?fù)涔?jié)點(diǎn)圖

圖2 邏輯框架圖

對(duì)模型假設(shè)：AGV速度1 m/s；相鄰節(jié)點(diǎn)：5 m；AGV節(jié)點(diǎn)轉(zhuǎn)向時(shí)間2 s；障礙檢測(cè)1次/s；檢測(cè)半徑5 m。

2 多AGV任務(wù)分配與路徑規(guī)劃

2.1 AGV任務(wù)執(zhí)行優(yōu)先級(jí)

AGV任務(wù)來源：①搬運(yùn)任務(wù)；②AGV自主充電和停靠；針對(duì)搬運(yùn)任務(wù)，本文采用先到先服務(wù)原則。針對(duì)AGV充電和?？孔鳂I(yè)，設(shè)定當(dāng)電量低于20%時(shí)，優(yōu)先執(zhí)行充電，不接受搬運(yùn)任務(wù)；在充電過程中，電量低于50%，繼續(xù)充電任務(wù)；電量大于50%，執(zhí)行搬運(yùn)任務(wù)，AGV任務(wù)執(zhí)行優(yōu)先級(jí)規(guī)則如圖3所示。

圖3 AGV任務(wù)執(zhí)行優(yōu)先級(jí)

2.2 多AGV路徑規(guī)劃

基于特征邊負(fù)載因子的路徑規(guī)劃目標(biāo)：①路徑最短；②時(shí)間最短；目標(biāo)的達(dá)成都無可避免路徑繁忙程度不同，為平衡負(fù)載考慮為路徑設(shè)置特征邊的負(fù)載因子。該負(fù)載因子作為懲罰項(xiàng)作用于特征邊長(zhǎng)度，繁忙特征邊，負(fù)載因子越大，同樣環(huán)境下增大特征邊長(zhǎng)度。采用Logistic函數(shù)描述對(duì)特征邊的負(fù)載因子φ：

式中：n為特征邊通過AG車頻次，為所有特征邊AGV總頻次。倉庫拓?fù)鋱D中特征邊長(zhǎng)度權(quán)值[7]：

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

式中，()：起始節(jié)點(diǎn)經(jīng)過節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離代價(jià)評(píng)估，()描述起始節(jié)點(diǎn)行駛至目前節(jié)點(diǎn)的實(shí)際距離；()描述目前節(jié)點(diǎn)行駛至目標(biāo)節(jié)點(diǎn)的距離代價(jià)評(píng)估。算法思想：AGV從起始節(jié)點(diǎn)起算法不斷搜索當(dāng)前節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)的最小距離()min，以此選擇AGV小車路徑的下個(gè)節(jié)點(diǎn)，已達(dá)到求解目標(biāo)函數(shù)()min。多AGV系統(tǒng)在運(yùn)行過程中，此時(shí)需對(duì)A*算法進(jìn)行改進(jìn)，引入不確定時(shí)間t改進(jìn)A*算法：

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

式中：(,t)描述起始節(jié)點(diǎn)到節(jié)點(diǎn)的實(shí)際時(shí)間；(,t)描述從節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的時(shí)間預(yù)估。

定義AGV起始節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)坐標(biāo)分別為(s,s)，(n,n)，(e,e)。當(dāng)AGV節(jié)點(diǎn)出發(fā)，此時(shí)(,t)=0，相鄰,兩節(jié)點(diǎn)時(shí)間代價(jià)估計(jì)：(w())，則當(dāng)前任一特征節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)可描述為[8]：

設(shè)定轉(zhuǎn)彎時(shí)間=2 s，通過規(guī)劃路徑和兩節(jié)點(diǎn)的相對(duì)位置，確定AGV在節(jié)點(diǎn)是否需要轉(zhuǎn)彎，在理想狀態(tài)下，兩相鄰特征節(jié)點(diǎn)時(shí)間間隔T=(,t)=(,t)，可得：

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

A*算法維護(hù)兩個(gè)列表：表OpenList和CloseList，算法索引過程：

（1）起始節(jié)點(diǎn)處(,t)=0，并記錄AGV起始節(jié)點(diǎn)t，此時(shí)(,t)=0，將特征節(jié)點(diǎn)添加進(jìn)CloseList；

（2）節(jié)點(diǎn)可達(dá)的特征節(jié)點(diǎn)加入OpenList中，將起始節(jié)點(diǎn)從OpenList中刪去，加入到CloseList。

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

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

多AGV路徑規(guī)劃，采用改進(jìn)A*算法執(zhí)行AGV路徑規(guī)劃，A*算法迭代流程如圖4所示。

2.3 算例實(shí)施

分別指派1#AGV和2#AGV完成任務(wù)A和B。任務(wù)A指派1#AGV：特征節(jié)點(diǎn)27→特征節(jié)點(diǎn)22；任務(wù)B指派2#AGV：特征節(jié)點(diǎn)13→36。

圖4 多AGV路徑規(guī)劃迭代流程圖

圖5 某智能倉庫物流拓?fù)涔?jié)點(diǎn)圖

調(diào)用改進(jìn)A*算法分別對(duì)1-2#AGV路徑規(guī)劃如上圖5所示。1-2#AGV時(shí)間窗如下：

表1 任務(wù)A和B單獨(dú)路徑規(guī)劃

A和B在29節(jié)點(diǎn)出現(xiàn)交叉沖突。假設(shè)任務(wù)A優(yōu)先級(jí)高于B，同時(shí)采用改進(jìn)A*進(jìn)行路徑規(guī)劃：

表2 任務(wù)A和B組合路徑規(guī)劃

由表2所示：任務(wù)A和B執(zhí)行時(shí)間窗不再?zèng)_突，實(shí)例驗(yàn)證改進(jìn)A*算法能對(duì)多AGV系統(tǒng)進(jìn)行路徑規(guī)劃。

此外，當(dāng)AGV和任務(wù)足夠多時(shí)，特征邊“繁忙”不一，Logistic函數(shù)描述負(fù)載因子均衡化倉庫特征邊路徑負(fù)載，對(duì)優(yōu)化多AGV系統(tǒng)路徑。如隨機(jī)給定倉庫500個(gè)任務(wù)序列，分別應(yīng)用改進(jìn)A*算法求解考慮Logistic函數(shù)描述負(fù)載因子下和不考慮負(fù)載因子的最優(yōu)解，統(tǒng)計(jì)每條特征邊負(fù)載，即AGV通過頻次，如圖6所示。

如圖6所示，Logistic函數(shù)引入A*算法能有效均衡特征邊負(fù)載。然而當(dāng)多AGV系統(tǒng)足夠復(fù)雜時(shí)，上述模型多出過多理想化假設(shè)，實(shí)際運(yùn)行不可避免出現(xiàn)AGV系統(tǒng)出現(xiàn)等待、碰撞等路徑?jīng)_突。

圖6 有無Logistic函數(shù)對(duì)比圖

圖7 AGV碰撞類型

3 多AGV避碰策略

3.1 沖突檢測(cè)模型

常見的沖突，如圖7所示：（a）相對(duì)沖突；（b）節(jié)點(diǎn)占用沖突；（c）交叉沖突；（d）貨架占用沖突[9]。

針對(duì)以上存在四種碰撞類型，為建立AGV碰撞模型，設(shè)定以下參數(shù)：

結(jié)合以上參數(shù)，建立任兩AGV沖突類型檢測(cè)模型：

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

式中：，沖突檢測(cè)系數(shù)，為保證模型檢測(cè)準(zhǔn)確性和實(shí)用性，根據(jù)實(shí)際運(yùn)作系統(tǒng)，設(shè)置系數(shù)常數(shù)。

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

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

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

3.2 并行避碰策略

針對(duì)倉庫多AGV系統(tǒng)，當(dāng)AGV沖突時(shí)，讓優(yōu)先級(jí)低的AGV等待。顯然傳統(tǒng)的等待策略大幅度降低系統(tǒng)的運(yùn)行的效率，換句話說，通過犧牲系統(tǒng)的效率解決AGV碰撞問題。

多AGV系統(tǒng)的沖突解決策略對(duì)于智能倉庫的安全性和高效性運(yùn)行至關(guān)重要，采取避障策略是關(guān)鍵，基于此，文中對(duì)傳統(tǒng)等待避障策略改進(jìn)優(yōu)化，提出并行動(dòng)態(tài)策略。根據(jù)碰撞類型，提出解決避障措施[10]：

（1）等待策略：即傳統(tǒng)避障策略，不再贅述；

（2）更改路徑規(guī)劃策略：當(dāng)任兩AGV路徑?jīng)_突時(shí)，任務(wù)優(yōu)先級(jí)較高AGV執(zhí)行原路徑，另一AGV在刪除物流拓?fù)鋱D沖突的特征節(jié)點(diǎn)和特征邊，重新進(jìn)行路徑規(guī)劃，執(zhí)行路徑規(guī)劃次優(yōu)解[11]；

（3）任務(wù)重新指派策略：當(dāng)任兩AGV路徑?jīng)_突時(shí)，任務(wù)優(yōu)先級(jí)較高AGV執(zhí)行原路徑，另一AGV關(guān)閉任務(wù)，該任務(wù)優(yōu)先指派給未發(fā)生沖突且距離該AGV最近的AGV執(zhí)行該次搬運(yùn)任務(wù)。

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

3.3 避碰策略算例

針對(duì)3.2提出的策略、更改路徑規(guī)劃策略以及兩者并行混合動(dòng)態(tài)策略進(jìn)行算例驗(yàn)證。設(shè)定如下優(yōu)先級(jí)遞減任務(wù)，Case1：1#AGV執(zhí)行優(yōu)先級(jí)較高搬運(yùn)任務(wù)1，從特征節(jié)點(diǎn)17→特征節(jié)點(diǎn)19；Case2：2#AGV執(zhí)行搬運(yùn)任務(wù)2，從特征節(jié)點(diǎn)26→特征節(jié)點(diǎn)02；Case3：3#AGV執(zhí)行搬運(yùn)任務(wù)3，從特征節(jié)點(diǎn)21→特征節(jié)點(diǎn)40；Case4：3#AGV執(zhí)行搬運(yùn)任務(wù)3，從特征節(jié)點(diǎn)07→特征節(jié)點(diǎn)29。

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

圖8 多AGV路徑規(guī)劃簡(jiǎn)圖

采用等待策略和更改路徑規(guī)劃策略結(jié)合動(dòng)態(tài)混合策略下，采用改進(jìn)A*算法[12]，對(duì)上述任務(wù)序列求解，不難得出倉庫中AGV經(jīng)過各特征節(jié)點(diǎn)和特征邊的時(shí)間窗，如表3所示：

表3 任務(wù)A和B組合路徑規(guī)劃

在采用等待策和更改路徑規(guī)劃策略并行的自適應(yīng)解決策略，完成任務(wù)27 s；此外，當(dāng)單獨(dú)采用等待策略時(shí)，4#AGV任務(wù)路徑4：特征節(jié)點(diǎn)07→15→23→31→30→29→28，1-4#AGV完成任務(wù)需要37 s；單獨(dú)采用更改路徑規(guī)劃策略時(shí)，2#AGV任務(wù)路徑2：特征節(jié)點(diǎn)17→25→26→27→19，1-4#AGV完成任務(wù)需要29 s。不難看出相比單獨(dú)采用等待策和更改路徑規(guī)劃策略，采用兩者并行的自適應(yīng)解決策略更有優(yōu)，效率更高。

4 結(jié)論

本文針對(duì)智能倉庫多AGV系統(tǒng)的路徑規(guī)劃和避障策略問題展開研究。首先，倉庫采用拓?fù)涞貓D法將倉庫物理空間抽象為二維坐標(biāo)模型的基礎(chǔ)上，同時(shí)創(chuàng)造性的應(yīng)用Logistic函數(shù)描述地圖特征邊負(fù)載，在考慮任務(wù)優(yōu)先級(jí)的情況下采用改進(jìn)A*算法對(duì)倉庫多AGV系統(tǒng)進(jìn)行路徑規(guī)劃；然后基于多AGV系統(tǒng)存在四種碰撞類型模型，提出等待策略與更改路徑規(guī)劃策略并行的動(dòng)態(tài)策略，在保證安全性避免碰撞的基礎(chǔ)上，對(duì)比傳統(tǒng)等待策略或單獨(dú)采用更改路徑規(guī)劃策略具有更客觀的作業(yè)效率，具有現(xiàn)實(shí)指導(dǎo)實(shí)踐意義。

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

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

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

[4] 霍凱歌,張亞琦,胡志華.自動(dòng)化集裝箱碼頭多載AGV調(diào)度問題研究[J].大連理工大學(xué)學(xué)報(bào),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] 泰應(yīng)鵬,邢科新,林葉貴,等.多AGV路徑規(guī)劃方法研究[J].計(jì)算機(jī)科學(xué),2017,44(11A):84-87

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

[8] 張政.倉儲(chǔ)系統(tǒng)AGV路徑規(guī)劃研究[D].北京:北京化工大學(xué),2018

[9] 李婷.自動(dòng)化倉庫系統(tǒng)多AGV路徑規(guī)劃和避碰策略研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),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

南方電網(wǎng)公司科技資助項(xiàng)目(YNKJXM20180007)

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