楊瑋，楊思瑤，張子涵

考慮沖突避免的多AGV路徑規(guī)劃研究

楊瑋，楊思瑤，張子涵

（陜西科技大學(xué) 機電工程學(xué)院，西安 710021）

提高物流企業(yè)“貨到人”揀選系統(tǒng)在實際生產(chǎn)中的工作效率，避免自動導(dǎo)引小車（AGV）間的沖突死鎖，研究大規(guī)模多AGV的無沖突路徑規(guī)劃和協(xié)同避障問題。首先考慮AGV空載、負(fù)載情況和路徑擴展成本，改進(jìn)A*算法，動態(tài)調(diào)整代價函數(shù)，優(yōu)化路徑擴展方式。其次，提出沖突檢測及避免算法，對可能產(chǎn)生局部沖突的路徑交叉點進(jìn)行避障調(diào)度，通過預(yù)約鎖格，實現(xiàn)局部沖突的檢測，制定優(yōu)先級避障策略，解決AGV動態(tài)行駛路徑上產(chǎn)生的局部沖突和死鎖，進(jìn)而實現(xiàn)全局無沖突路徑規(guī)劃。對多組不同任務(wù)量和不同AGV規(guī)模的場景進(jìn)行仿真，實驗結(jié)果表明，考慮沖突避免的改進(jìn)A*算法能有效實現(xiàn)100個任務(wù)、90個貨架單位和7個揀選站場景下的多AGV動態(tài)路徑規(guī)劃，相較于傳統(tǒng)A*算法，其平均揀選時長縮短了52.61%。該方法可實現(xiàn)大規(guī)模場景下的多AGV動態(tài)路徑規(guī)劃，在付出較小轉(zhuǎn)彎代價的同時有效避免局部動態(tài)沖突，該方法可為相關(guān)企業(yè)實現(xiàn)多AGV協(xié)同調(diào)度提供新的思路和理論依據(jù)。

“貨到人”揀選系統(tǒng)；自動導(dǎo)引小車；改進(jìn)A*算法；沖突檢測及避免算法；動態(tài)路徑規(guī)劃

隨著電商行業(yè)的快速發(fā)展和人工智能技術(shù)的不斷成熟，采用機器人代替人工作業(yè)已成為制造業(yè)及物流業(yè)發(fā)展的大趨勢，越來越多的企業(yè)開始在生產(chǎn)車間應(yīng)用移動機器人系統(tǒng)協(xié)助生產(chǎn)[1]。有報告顯示[2-3]，全球已有超十萬的多移動機器人系統(tǒng)和超百萬的移動機器人被應(yīng)用于物流的倉儲環(huán)節(jié)。2008年，亞馬遜公司首次在物流倉庫使用了Kiva System，該系統(tǒng)是一種自動化程度較高的移動機器人履行系統(tǒng)（Robotic Mobile Fulfillment Systems，RMFS），通過多輛自動導(dǎo)引小車（Automated Guided Vehicle，AGV）合作進(jìn)行貨物的存儲、搜索、選擇和運送工作，完成倉儲環(huán)節(jié)的作業(yè)[4]。傳統(tǒng)物流倉庫的揀貨、補貨等作業(yè)大多由人工完成，存在揀選時間長、揀選效率低等問題，無法滿足現(xiàn)代物流快速、高效的發(fā)展需求[5]。與傳統(tǒng)倉庫“人到貨”的揀選模式不同，RMFS系統(tǒng)通過中央控制系統(tǒng)集中控制AGV，實現(xiàn)了高效的“貨到人”揀選作業(yè)，是一種典型的“貨到人”揀選系統(tǒng)，多AGV合作作業(yè)取代了傳統(tǒng)倉儲系統(tǒng)中人工作業(yè)的方式，使得RMFS系統(tǒng)具有更高的揀貨效率、更高的吞吐能力、更好的可擴展性和系統(tǒng)柔性[6]。隨著現(xiàn)代物流設(shè)備的自動化和智能化發(fā)展，未來倉庫的發(fā)展趨勢必將是規(guī)?；图s化。提高多AGV的集群化調(diào)度能力，尤其是針對較大規(guī)模的多AGV路徑規(guī)劃，是倉儲系統(tǒng)自動化與智能化發(fā)展中必須克服和突破的技術(shù)難點，也是影響企業(yè)物流效率的重要因素[7]。

路徑規(guī)劃是移動機器人搬運作業(yè)中的關(guān)鍵問題之一，根據(jù)路徑規(guī)劃目標(biāo)和規(guī)劃路徑時系統(tǒng)環(huán)境狀態(tài)的不同，可以將移動機器人的路徑規(guī)劃問題劃分為GPP和LPP[8]，即移動機器人的全局路徑規(guī)劃和局部路徑規(guī)劃[9]，文中綜合考慮GPP和LPP研究“貨到人”揀選系統(tǒng)的路徑規(guī)劃問題。目前，多AGV路徑規(guī)劃的研究內(nèi)容主要集中在數(shù)學(xué)方法、仿真研究和智能算法方面，以“貨到人”揀選系統(tǒng)等智能物流系統(tǒng)為背景的研究較少涉及AGV數(shù)量和任務(wù)量，且對動態(tài)實時性問題考慮不足[10]。由于倉庫中大規(guī)模機器人集群調(diào)度的問題較復(fù)雜，是動態(tài)、多目標(biāo)的，已被證明是NP難問題[11]，因此對于移動機器人路徑規(guī)劃問題的研究仍是探索移動機器人控制領(lǐng)域的重要方向[12]。傳統(tǒng)的AGV路徑規(guī)劃是為AGV規(guī)劃出一條到達(dá)目標(biāo)點的無碰撞最短路徑，一般利用可視圖、Voronoi 圖、柵格圖、人工勢場等路徑規(guī)劃方法[13]，并通過深度優(yōu)先算法、廣度優(yōu)先算法[5]、Dijkstra算法、A*算法或 D*算法等求解[14]。劉生偉等[15]剔除了尋路過程中的冗余節(jié)點，進(jìn)而改進(jìn)A*算法，其尋優(yōu)效果好，但其中涉及的機器人數(shù)量較少。Duchon等[16]提出一種改進(jìn)的A*算法，通過修改代價函數(shù)，為個別場景下的路徑規(guī)劃提供參考，但其涉及的AGV數(shù)量較少。李偉光等[17]提出了一種考慮轉(zhuǎn)彎因素的改進(jìn)A*算法，但未考慮AGV規(guī)模大量增加時其算法的路徑搜索效率。Singh等[18]考慮了安全距離，采用改進(jìn)的 A*算法進(jìn)行路徑規(guī)劃，有效避免了沖突，提高了系統(tǒng)的整體效率。牟德君等[19]以總工作時間最短為目標(biāo)，改進(jìn)了A*算法代價函數(shù)計算公式，提出了一種適用于倉儲環(huán)境的改進(jìn)A*算法。Ren等[20]提出了一種基于特征圖的全局路徑規(guī)劃算法，使得優(yōu)化后的路線更短且更平穩(wěn)。Zhong等[21]提出了一種混合路徑規(guī)劃方法，用于解決大規(guī)模動態(tài)環(huán)境下移動機器人的全局路徑規(guī)劃、實時監(jiān)測和避障等問題。Wang等[22]以路徑最短為目標(biāo)進(jìn)行了全局路徑規(guī)劃，確定了由初始點到參考直線的最佳切線弧路徑。

雖然上述學(xué)者的研究取得了一定的效果，但在大規(guī)模AGV倉儲系統(tǒng)中，多AGV共同作業(yè)時的沖突和碰撞次數(shù)將呈指數(shù)增加，導(dǎo)致規(guī)劃的局限性。鑒于此，筆者在前人研究的基礎(chǔ)上，進(jìn)一步優(yōu)化路徑規(guī)劃算法，綜合研究了轉(zhuǎn)彎因素、路徑擴展成本、沖突避免等，實現(xiàn)了“貨到人”揀選系統(tǒng)的全局無碰撞路徑規(guī)劃，提高了系統(tǒng)分揀效率，并通過仿真軟件驗證了文中所提路徑規(guī)劃算法的優(yōu)越性。

1 考慮沖突避免的路徑規(guī)劃算法

A*算法是由Peter H等設(shè)計的一種啟發(fā)式搜尋路徑方法，結(jié)合了Dijkstra算法和快速隨機搜索樹算法[23]，利用等代價搜索和啟發(fā)式搜索有效地計算出最優(yōu)路徑，計算出最佳優(yōu)先搜索，具有搜索路徑時間短[18]、魯棒性好、運行速度快等優(yōu)點。A*算法的核心在于不斷更新OpenList和CloseList，通過選取OpenList中代價最小的節(jié)點作為優(yōu)先級最高的節(jié)點進(jìn)行擴展，在OpenList中存放待擴展節(jié)點，在CloseList中存放已擴展節(jié)點，當(dāng)目標(biāo)節(jié)點出現(xiàn)在CloseList中時，路徑搜索結(jié)束，并回溯至父節(jié)點，得到路徑。

A*算法見式（1），式中，()表示從初始節(jié)點到當(dāng)前節(jié)點的總代價值，()表示從初始節(jié)點到當(dāng)前節(jié)點的實際代價值，()表示從當(dāng)前節(jié)點到目標(biāo)節(jié)點的估計代價值。采用曼哈頓距離表達(dá)式計算估計代價值，見式（2）。式中，(,)表示節(jié)點與節(jié)點之間的曼哈頓距離，X表示目標(biāo)節(jié)點的橫坐標(biāo)，Y表示目標(biāo)節(jié)點的縱坐標(biāo)，X表示當(dāng)前節(jié)點的橫坐標(biāo)，Y表示當(dāng)前節(jié)點的縱坐標(biāo)。()的啟發(fā)式函數(shù)可用式（3）表示，其中為AGV直線行駛1個柵格的代價，表示當(dāng)前節(jié)點，表示目標(biāo)節(jié)點。

()=()+() (1)

1.1 A*算法

1.1.1 問題描述

當(dāng)系統(tǒng)中存在較大規(guī)模的AGV同時運行時，受到A*算法路徑搜索機制的影響，在AGV行駛路徑上可能存在較多的轉(zhuǎn)彎節(jié)點，A*算法不能保證在解決多AGV碰撞和沖突的同時仍能搜尋到最優(yōu)路徑，且在轉(zhuǎn)彎過程中AGV的單位耗電量將大大增加，因而會浪費系統(tǒng)資源[5]。此外，在倉庫環(huán)境中一般將通道設(shè)置為雙向單車道，AGV在空載時允許在無任務(wù)的可移動貨架下方穿行，AGV在負(fù)載時僅允許在預(yù)設(shè)行駛規(guī)則的可通行巷道上通行，如圖1～2所示。將貨架、在駐點停留的AGV、載有可移動貨架并在存儲區(qū)執(zhí)行任務(wù)的AGV分別視為靜態(tài)和動態(tài)的障礙物，不同行駛方向的AGV可能在行駛路徑的部分區(qū)域發(fā)生沖突，從而影響彼此通行，降低系統(tǒng)效率。

圖1 空載AGV可通行路徑情況

圖2 負(fù)載AGV可通行路徑情況

基于上述分析，在研究多AGV全局路徑規(guī)劃問題時，重點考慮以下3個問題：AGV負(fù)載和空載的不同行駛方式；減少AGV轉(zhuǎn)彎次數(shù)，降低轉(zhuǎn)彎成本；避免沖突，減少碰撞次數(shù)。研究目的在于提高“貨到人”揀選系統(tǒng)中多AGV最優(yōu)路徑的搜尋效率和可靠性，解決多AGV間的沖突問題。

1.1.2 改進(jìn)A*算法

A*算法總代價()主要取決于()和()的變化，在搜尋初期受其影響較大，算法的運行速度快、效率高。隨著搜尋進(jìn)程的變化，實際行走代價()逐漸增大，而估算代價()逐漸減小，()受啟發(fā)式搜索的影響變小，算法需要搜尋更多節(jié)點才能完成搜尋目標(biāo)，搜尋效率降低。為了穩(wěn)定路徑規(guī)劃算法的性能，首先對實際代價()和估算代價()設(shè)置權(quán)重，動態(tài)調(diào)整它們在算法搜尋進(jìn)程中的影響。設(shè)置動態(tài)調(diào)整權(quán)重后的總代價()，見式（4）。其中，AGV的當(dāng)前起始位置為(x,y)，目標(biāo)節(jié)點位置為(goal,goal)，中間節(jié)點位置為(x,y)，分別將起始位置、目標(biāo)位置與中間位置曼哈頓距離的比值作為實際代價和估算代價的動態(tài)權(quán)重。

為了避免搜尋路徑上出現(xiàn)轉(zhuǎn)彎次數(shù)過多的情況，進(jìn)一步將轉(zhuǎn)彎代價加入代價函數(shù)中進(jìn)行考慮。若AGV的當(dāng)前位置為(x,y)，那么與其對應(yīng)的父節(jié)點為(x–1,y–1)，子節(jié)點為(x+1,y+1)?？衫霉?jié)點信息判定轉(zhuǎn)彎，當(dāng)(x,y)–(x–1,y–1)與(x+1,y+1)–(x,y)相等時，表示AGV向下一節(jié)點移動時未發(fā)生轉(zhuǎn)彎動作，否則表示AGV在節(jié)點(x,y)發(fā)生轉(zhuǎn)彎動作；AGV移動1個柵格的基礎(chǔ)代價為，設(shè)置轉(zhuǎn)彎懲罰因子為。當(dāng)判定發(fā)生轉(zhuǎn)彎時，為1，否則為0，則轉(zhuǎn)彎懲罰代價可表示為式（5）。改進(jìn)A*算法的代價函數(shù)表達(dá)見式（6），具體步驟如下。

1）確定AGV空載和負(fù)載狀態(tài)時的系統(tǒng)搜索地圖MAP1、MAP2，將路徑規(guī)劃分為3個階段，在3個階段內(nèi)分別以MAP1、MAP2、MAP2的順序進(jìn)行路徑搜索。

2）輸入AGV的起始點、中間節(jié)點、目標(biāo)點，需要尋找的3段最短路徑為→，→，→，標(biāo)記為P1、P2和P3。

3）構(gòu)建OpenList和CloseList存儲節(jié)點位置信息，將起始點插入OpenList，同時置空CloseList；再將起始點插入CloseList，循環(huán)規(guī)劃3段路徑。

4）判斷OpenList是否為空，若是，搜索路徑失??；否則以O(shè)penList中改進(jìn)的評價函數(shù)()最小的節(jié)點作為當(dāng)前節(jié)點，檢查其周圍4個鄰接節(jié)點，并計算()。

5）判斷()最小的鄰接節(jié)點'是否為障礙物，若是，則放棄該節(jié)點；否則計算該節(jié)點的'()。若'()<()，則將其放入OpenList，并更新()。

6）循環(huán)Step 4至Step 5，直至輸出最短路徑P1。

7）最短路徑P2、P3的搜索流程同上，移動機器人執(zhí)行任務(wù)的最短路徑為3段路徑的長度和。

1.2 沖突檢測及避免算法

為了滿足路徑規(guī)劃可通達(dá)性的要求，首先采用改進(jìn)A*算法對已知分配結(jié)果的貨架及AGV進(jìn)行初步靜態(tài)路徑規(guī)劃。根據(jù)任務(wù)執(zhí)行時間的優(yōu)先級設(shè)置二維預(yù)約表，并通過預(yù)約鎖格方法進(jìn)行局部沖突檢測，隨后設(shè)計優(yōu)先級避障策略，解決局部沖突，最終完成全局無沖突路徑規(guī)劃。為了便于研究，對以下條件進(jìn)行假設(shè)。

1）在同一時刻內(nèi)，1個柵格僅能被1輛AGV占用，1輛AGV不能同時占用2個及以上的柵格。

2）在AGV接收到揀選任務(wù)時，已知該任務(wù)的起始點和目標(biāo)點位置。

3）不考慮AGV行進(jìn)過程中的變速，設(shè)置其勻速通過每個柵格，通過1個柵格的時間為1 s。

4）已知倉庫中可移動貨架、充電站和揀選臺的位置，動態(tài)障礙物僅包括在倉庫中行駛的其他AGV，且所有AGV的運動信息已知。

取大鼠腦組織（處死前已注射FITC-D）置于4%多聚甲醛溶液中固定24 h后，常規(guī)脫水、石蠟包埋、切片（5 μm），參照Weidner法[21]測定大鼠腦組織梗死區(qū)域的MVD。尋找梗死區(qū)域內(nèi)5個血管密集區(qū)，于200倍熒光倒置顯微鏡下計算該區(qū)域內(nèi)被染成綠色的微血管數(shù)目。每份切片均選取5個高倍視野計數(shù)，取其平均值。

5）設(shè)置通道為雙向單車道，AGV可以在巷道內(nèi)沿著路徑方向自由行駛。

多臺AGV同時執(zhí)行任務(wù)，不可避免地會發(fā)生路徑?jīng)_突。為了有效解決AGV在行走過程中可能出現(xiàn)的碰撞和死鎖問題，主要針對AGV行駛過程中可能出現(xiàn)的交叉點沖突、對向沖突、追擊沖突和連續(xù)沖突提出相應(yīng)的沖突解決策略，并進(jìn)行局部路徑規(guī)劃，沖突示意圖如圖3所示。

1.2.1 預(yù)約鎖格

預(yù)約鎖格的核心是在AGV移動過程中不斷檢查路徑上柵格節(jié)點的占用情況，為優(yōu)先級高的AGV連續(xù)提前鎖定一段安全距離，在安全距離內(nèi)保障當(dāng)前AGV的無障礙通行，并更新預(yù)約表，直至所有任務(wù)完成。預(yù)約表鎖定的安全距離隨著AGV移動位置的變化而改變，安全距離的長度由鎖格范圍決定。不同的鎖格范圍會影響AGV在系統(tǒng)中的等待時間，鎖格范圍過長會影響路徑規(guī)劃的效率[24]。由此可見，只有確定AGV當(dāng)前位置、任務(wù)起始位置，并設(shè)置好鎖格范圍后，才能確定在預(yù)約鎖格策略下的AGV運行路線。如圖4所示，已知AGV1和AGV2的任務(wù)起始節(jié)點和終點，若將鎖格范圍設(shè)置為2，則系統(tǒng)始終在到+2時刻內(nèi)將每輛AGV鎖定接下來的2個柵格單元作為安全行駛范圍，已被AGV1鎖定的柵格單元不能同時被其他AGV鎖定。

圖3 不同沖突類型

圖4 預(yù)約鎖格

1.2.2 優(yōu)先級避障策略

1）節(jié)點等待。在AGV執(zhí)行任務(wù)過程中，預(yù)約表檢測到同一時刻內(nèi)下一鎖格范圍內(nèi)即將發(fā)生的沖突，則使優(yōu)先級低的AGV在當(dāng)前節(jié)點等待一個安全的時間間隔后再出發(fā)。

2）重新規(guī)劃。在AGV執(zhí)行任務(wù)過程中，等待時間過長或與其他AGV形成死鎖時，對死鎖環(huán)上優(yōu)先級低的AGV重新規(guī)劃路徑，優(yōu)先級高的AGV按原規(guī)劃繼續(xù)通行，然后依次調(diào)度其他優(yōu)先級低的AGV。

3）組合策略。AGV已經(jīng)采用某一策略進(jìn)行路徑規(guī)劃時，由于實際運行時系統(tǒng)中存在大規(guī)模AGV同時執(zhí)行任務(wù)，且可能存在再次沖突的情況，因此通過多個避障策略組合進(jìn)行避免。

綜上所述，考慮沖突避免的改進(jìn)A*算法（Improved A*algorithm considering conflict avoidance，IPA*-CA）搜尋全局無沖突路徑的過程如圖5所示，步驟如下。

1）系統(tǒng)接收實時任務(wù)后，采用柵格法對地圖進(jìn)行編號，定位AGV、貨架和揀選臺的位置。

2）調(diào)用改進(jìn)A*算法進(jìn)行初步路徑規(guī)劃，獲取靜態(tài)障礙下的臨時路徑。

3）根據(jù)任務(wù)列表中的執(zhí)行時間和初始行駛路徑構(gòu)建二維預(yù)約表，對每輛AGV執(zhí)行目標(biāo)貨架的起始時間設(shè)置安全時間間隔，降低初始規(guī)劃時AGV擁堵的可能性，AGV按照更新后的預(yù)約表執(zhí)行揀選任務(wù)。

4）啟用預(yù)約鎖格策略。始終為每輛AGV鎖定一段柵格節(jié)點作為安全距離，以確保其順利通行。當(dāng)某輛AGV路徑確定后，其他AGV經(jīng)過預(yù)約表查詢相繼鎖定路徑并完成任務(wù)。

5）不斷獲取占用點信息，判斷安全距離內(nèi)是否會發(fā)生沖突。若發(fā)生沖突，則即刻啟用優(yōu)先級避障策略，在決策AGV通行順序的同時解決沖突，否則進(jìn)入下一步驟。

6）判斷所有目標(biāo)貨架的揀選路徑是否均已檢測。若是，則更新預(yù)約表，并執(zhí)行下一步驟，否則繼續(xù)檢測，并執(zhí)行步驟4）。

7）當(dāng)前所有AGV完成揀選任務(wù)后，判斷任務(wù)列表是否已為空。若列表已空，則規(guī)劃結(jié)束，否則重復(fù)步驟2）～6），直至所有任務(wù)結(jié)束。

圖5 考慮沖突避免的路徑規(guī)劃算法

2 結(jié)果與分析

2.1 小規(guī)模仿真實驗分析

為了討論所提IPA*-CA算法搜尋路徑的有效性，基于Matlab 2022b設(shè)置1組小規(guī)模實驗進(jìn)行研究。采用柵格法建立小規(guī)模環(huán)境模型，生成3項調(diào)度安排，包括2個揀選站、3臺AGV和3項揀選任務(wù)，AGV起始駐留位置、目標(biāo)貨架位置、揀選臺位置及各項任務(wù)的起始時刻如表1所示，設(shè)置每輛AGV的行駛速度為1 m/s，柵格尺寸為1 m×1 m。分別采用A*算法、ACO算法和IPA*-CA算法進(jìn)行多AGV路徑規(guī)劃實驗。

表1 實驗基本設(shè)置

Tab.1 Basic experimental settings

如圖6所示，分別使用3種算法規(guī)劃出多AGV行駛路徑，重復(fù)實驗10次，3種算法在路徑長度和轉(zhuǎn)彎次數(shù)方面的表現(xiàn)如表2所示。實驗結(jié)果表明，相較于A*算法和ACO算法，文中所提算法能有效提高路徑搜索效率，并保持路徑質(zhì)量，AGV空載可穿行于貨架下方的策略和動態(tài)調(diào)整A*算法代價函數(shù)的操作，使得規(guī)劃的路徑總長度更短、轉(zhuǎn)彎次數(shù)更少。為了討論IPA*-CA算法的動態(tài)避障效果，參考Bolu等[24]對多機器人路徑規(guī)劃的研究，設(shè)置鎖格范圍為2，采用文中所提算法進(jìn)行避障實驗。AGV路徑規(guī)劃結(jié)果如表3所示。節(jié)點通行順序為3輛AGV通過各個節(jié)點的先后順序，未調(diào)用避障算法時規(guī)劃的臨時路徑，如圖7所示。由圖6c和圖7a可知，AGV1與AGV2在節(jié)點190處的位置發(fā)生重疊，說明2輛AGV在相同時間范圍內(nèi)需要鎖定同一資源點，在路徑上發(fā)生了沖突。由圖6c和圖7b可知，AGV1與AGV3交換了在節(jié)點185和186處的位置，說明2輛AGV在相同時間范圍內(nèi)需要鎖定對方資源點，在路徑上發(fā)生了沖突。

調(diào)用沖突檢測及避免算法，并完整運行所提算法后，獲得了多AGV運行的實際路徑。由于AGV1最早開始執(zhí)行任務(wù)且與其他AGV發(fā)生沖突時均為負(fù)載狀態(tài)，因此總是具有最高優(yōu)先級。由圖8a可以觀察到，AGV1與AGV2沖突時，二者分別位于節(jié)點191和節(jié)點211處，由于AGV1的優(yōu)先級較高，且設(shè)置的鎖格范圍為2，因而AGV1先占用了節(jié)點190和189，AGV2在節(jié)點211處等待2 s后繼續(xù)執(zhí)行任務(wù)，避免了沖突1。由圖8b可以觀察到，AGV1與AGV3沖突時，二者分別位于節(jié)點184和節(jié)點215處，由于AGV1的優(yōu)先級較高，且設(shè)置的鎖格范圍為2，因而AGV1先占用了節(jié)點185和186，AGV2在節(jié)點211處等待4 s后繼續(xù)執(zhí)行任務(wù)，避免了沖突2。由圖8c可知，3輛AGV在執(zhí)行任務(wù)的全過程中不再出現(xiàn)相同時間范圍內(nèi)鎖定同一資源點或?qū)Ψ劫Y源點的情況，執(zhí)行任務(wù)的總時長分別為87、76、72 s，行駛的路徑總長度分別為51、36、30 m。由此可見，文中所提算法對避免多AGV沖突問題有效。

圖6 3種算法的路徑規(guī)劃結(jié)果

表2 算法有效性實驗

Tab.2 Algorithm effectiveness experiment

表3 避障實驗結(jié)果

Tab.3 Results of obstacle avoidance experiment

圖7 存在沖突的初始路徑

圖8 避免動態(tài)沖突后的實際路徑

2.2 大規(guī)模仿真實驗分析

為了討論所提算法的優(yōu)化效果，設(shè)置實驗基本參數(shù)，基于Flexsim仿真軟件建立一個貨架排列方式為2×8、布局為5列18排、共計90個貨架單位和7個揀選站的倉庫模型。在實驗中，AGV隨機駐留的貨架位置為初始位置，訂單任務(wù)隨機生成并就近分配，設(shè)置AGV的行駛速度為1 m/s，柵格尺寸為1 m×1 m，將AGV每次轉(zhuǎn)彎、抬起和放下貨架的時間均設(shè)置為1 s，揀選每個貨架的平均時間為30 s。系統(tǒng)中AGV需要經(jīng)歷3個階段，分別為AGV前往目標(biāo)點馱運貨架、AGV將可移動貨架馱至揀選臺、AGV將可移動貨架放回原存儲位置。為了方便研究，下文統(tǒng)稱考慮沖突避免的改進(jìn)A*算法為算法1，A*算法為算法2，分別采用2種算法對不同實驗參數(shù)下的模型進(jìn)行仿真，進(jìn)而研究所提算法在“貨到人”揀選系統(tǒng)中的應(yīng)用效果。

統(tǒng)計固定使用10輛AGV并改變系統(tǒng)任務(wù)量從20至200個時的仿真結(jié)果（表4），GAP值表示算法1與算法2平均揀選1個任務(wù)的時間差異度。通過比較結(jié)果可知，當(dāng)系統(tǒng)中可用的AGV數(shù)量固定時，在2種算法下，AGV的轉(zhuǎn)彎次數(shù)、系統(tǒng)中出現(xiàn)局部沖突的次數(shù)和完成揀選任務(wù)的總時長均隨著揀選任務(wù)量的增加而增大，其原因是每輛AGV在同一時間段內(nèi)僅能處理1項任務(wù)，任務(wù)量的累加使得系統(tǒng)內(nèi)部更加復(fù)雜，AGV必須通過更高頻次的工作才能完成所有任務(wù)，在等待和處理沖突過程中產(chǎn)生了時間損耗，并增加了沖突的可能性。

執(zhí)行算法1和算法2時，路徑上的轉(zhuǎn)彎次數(shù)對比結(jié)果如圖9a所示。相較于算法2，算法1規(guī)劃的路徑始終具有更少的轉(zhuǎn)彎次數(shù)，隨著任務(wù)量的增加，2種算法在規(guī)劃路徑轉(zhuǎn)彎次數(shù)方面的差異更加明顯。執(zhí)行算法1和算法2時，路徑上產(chǎn)生的局部沖突次數(shù)對比情況如圖9b所示。算法1相較于算法2，產(chǎn)生的沖突始終更少，當(dāng)任務(wù)量為20～80個時，2種算法下產(chǎn)生的沖突次數(shù)差距較小，當(dāng)任務(wù)量超過100個后，算法1中產(chǎn)生的沖突次數(shù)緩慢增加，而算法2的沖突次數(shù)急劇增加，兩者之間的差距快速增大。出現(xiàn)上述實驗結(jié)果的原因是，在較少任務(wù)量下，AGV分配到的任務(wù)較平均，系統(tǒng)中發(fā)生沖突的頻率較低，隨著任務(wù)量的增大，AGV的工作頻率明顯增大，系統(tǒng)中相遇的可能性隨之增加。當(dāng)發(fā)生沖突時，算法2無法快速解決沖突，使得系統(tǒng)出現(xiàn)大量擁堵現(xiàn)象，而算法1則通過沖突預(yù)檢測、優(yōu)先級避障和預(yù)約鎖格等操作避免了大量沖突，緩解了系統(tǒng)的擁堵情況。執(zhí)行算法1和算法2時，AGV完成所有任務(wù)的揀選總時長對比情況如圖9c所示。算法1的平均揀選時長為43.01 s/個，算法2的平均揀選時長為90.75 s/個，與算法2相比，算法1始終具有更快的揀選完成時間。說明當(dāng)AGV在行駛中遇到動態(tài)的局部沖突或死鎖等突發(fā)事件時，算法1能快速解決問題，并節(jié)約了大量時間資源。相較于算法2，算法1的平均揀選時間優(yōu)化率為52.61%，優(yōu)化效果明顯。

表4 大規(guī)模任務(wù)量實驗結(jié)果

Tab.4 Results of large-scale task experiments

圖9 不同算法的規(guī)劃結(jié)果對比

統(tǒng)計固定系統(tǒng)任務(wù)量為100、改變AGV規(guī)模從5～30個的仿真結(jié)果如表5所示。將AGV行駛總路程、完成所有揀選任務(wù)的總時間作為衡量指標(biāo)，討論文中所提算法在不同AGV規(guī)模下的表現(xiàn)。當(dāng)任務(wù)量固定時，隨著AGV數(shù)量的增加，系統(tǒng)完成揀選任務(wù)的總時長逐漸縮短，而AGV行駛的總路程呈現(xiàn)先減少后增加的趨勢。出現(xiàn)此現(xiàn)象的原因是，隨著AGV規(guī)模的增加，系統(tǒng)的整體工作效率得到提高，但逐漸飽和的AGV容量增加了系統(tǒng)負(fù)荷，導(dǎo)致系統(tǒng)中出現(xiàn)了更多的局部沖突，算法1為了避免沖突而犧牲了部分路徑成本。實驗結(jié)果表明，算法1能有效地在不同系統(tǒng)規(guī)模下規(guī)劃路徑，但系統(tǒng)中AGV的數(shù)量并不是越多越好。在當(dāng)前倉庫規(guī)模下配置15輛AGV時，AGV行駛的總路程和完成揀選的總時長均較短，能獲得更好的使用效果。

表5 不同AGV規(guī)模的仿真結(jié)果

Tab.5 Simulation results under different scales of AGVs

綜上所述，考慮沖突避免的改進(jìn)A*算法在多AGV調(diào)度問題中的效果較好，尤其是系統(tǒng)中存在一定規(guī)模的待處理任務(wù)量和AGV時其效果更加突出。文中所提方法能夠為物流倉庫或制造業(yè)生產(chǎn)車間的調(diào)度提供思路。由于不同的系統(tǒng)環(huán)境存在差異，因此相關(guān)企業(yè)在配置倉庫設(shè)備時，需要綜合考慮倉庫布局、揀選需求和系統(tǒng)容量，更好地對AGV規(guī)模進(jìn)行決策。當(dāng)AGV規(guī)模超過系統(tǒng)飽和狀態(tài)所需的AGV數(shù)量時，系統(tǒng)整體能耗將隨之增加，系統(tǒng)工作效率將受到影響，造成企業(yè)資源浪費。

3 結(jié)語

針對“貨到人”揀選系統(tǒng)多AGV的路徑規(guī)劃和沖突避免問題進(jìn)行了研究，提出了一種考慮沖突檢測及避免的路徑規(guī)劃算法。首先考慮AGV空載、負(fù)載的不同狀態(tài)，調(diào)整其行駛方式，對路徑轉(zhuǎn)彎成本設(shè)置懲罰因子，動態(tài)調(diào)整A*算法代價函數(shù)，改進(jìn)A*算法，以優(yōu)化AGV執(zhí)行任務(wù)時的轉(zhuǎn)彎次數(shù)。其次，設(shè)計沖突檢測及避免算法，為滿足路徑規(guī)劃的可通達(dá)性要求，提出了預(yù)約鎖格策略，通過不斷獲取占用的節(jié)點信息，鎖定安全距離，進(jìn)而始終保障優(yōu)先級高的AGV率先結(jié)束任務(wù)。針對系統(tǒng)中出現(xiàn)的局部動態(tài)沖突問題，提出了節(jié)點等待和重新規(guī)劃等優(yōu)先級避障策略，解決了局部動態(tài)沖突，進(jìn)而獲得了高效、可行的全局無碰撞路徑。最后，基于仿真軟件，通過多組不同任務(wù)量和不同AGV規(guī)模的仿真實驗證明，文中所提的路徑規(guī)劃算法能有效避免系統(tǒng)中的沖突，并付出了較少的轉(zhuǎn)彎代價。該算法在提高路徑搜索效率的同時，能夠保證搜索質(zhì)量，具有較好的魯棒性和實用性，能實現(xiàn)100個任務(wù)、90個貨架單位和7個揀選站場景下的多AGV動態(tài)路徑規(guī)劃，能為企業(yè)采用“貨到人”揀選系統(tǒng)促進(jìn)倉庫實際生產(chǎn)提供參考。

[1] CHEN Hai-long, WANG Qiang, YU Meng, et al. Path Planning for Multi-Robot Systems in Intelligent Warehouse[C]// International Conference on Internet and Distributed Computing Systems. Cham: Springer, 2018: 148-159.

[2] 本刊編輯部. 國際機器人聯(lián)合會2021年全球工業(yè)機器人統(tǒng)計數(shù)據(jù)[J]. 機器人技術(shù)與應(yīng)用, 2022(1): 47-48.

Editorial Department. The International Federation of Robotics 2021 Global Industrial Robot Statistics[J]. Robot Technique and Application, 2022(1): 47-48.

[3] RIZK Y, AWAD M, TUNSTEL E W. Cooperative Heterogeneous Multi-Robot Systems[J]. ACM Computing Surveys, 2020, 52(2): 1-31.

[4] ROY D, NIGAM S, DE KOSTER R, et al. Robot-Storage Zone Assignment Strategies in Mobile Fulfillment Systems[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 122: 119-142.

[5] VAN DEN BERG J P, ZIJM W H M. Models for Warehouse Management: Classification and Examples[J]. International Journal of Production Economics, 1999, 59(1/2/3): 519-528.

[6] 徐翔斌, 馬中強. 基于移動機器人的揀貨系統(tǒng)研究進(jìn)展[J]. 自動化學(xué)報, 2022, 48(1): 1-20.

XU Xiang-bin, MA Zhong-qiang. Robotic Mobile Fulfillment Systems: State-of-the-Art and Prospects[J]. Acta Automatica Sinica, 2022, 48(1): 1-20.

[7] YANG Xi-ying, HUA Guo-wei, HU Lin-yuan, et al. Joint Optimization of Order Sequencing and Rack Scheduling in the Robotic Mobile Fulfilment System[J]. Computers & Operations Research, 2021, 135: 105467.

[8] LI Hong-li, ZHU Hong-rui, XU Dong-ming, et al. Dynamic Task Allocation Based on Auction in Robotic Mobile Fulfilment System[J]. Journal of Industrial and Management Optimization, 2023, 19(10): 7600-7615.

[9] MURILLO M, SáNCHEZ G, GENZELIS L, et al. A Real-Time Path-Planning Algorithm Based on Receding Horizon Techniques[J]. Journal of Intelligent & Robotic Systems, 2018, 91(3): 445-457.

[10] 李昆鵬, 劉騰博, 賀冰倩, 等. “貨到人”揀選系統(tǒng)中AGV路徑規(guī)劃與調(diào)度研究[J]. 中國管理科學(xué), 2022, 30(4): 240-251.

LI Kun-peng, LIU Teng-bo, HE Bing-qian, et al. A Study on Routing and Scheduling of Automated Guided Vehicle in "Cargo-to-Picker" System[J]. Chinese Journal of Management Science, 2022, 30(4): 240-251.

[11] 竇佳佳. 強化學(xué)習(xí)及其在智能倉儲中的應(yīng)用研究[D]. 南京: 南京大學(xué), 2016: 14-33.

DOU Jia-jia. Research on Reinforcement Learning and Its Application in Intelligent Warehousing[D]. Nanjing: Nanjing University, 2016: 14-33.

[12] 楊文華. 我國倉儲物流機器人發(fā)展現(xiàn)狀與未來趨勢[J]. 物流技術(shù)與應(yīng)用, 2017, 22(9): 100-102.

YANG Wen-hua. Development Status and Future Trend of Warehousing and Logistics Robots in China[J]. Logistics & Material Handling, 2017, 22(9): 100-102.

[13] 李曉旭, 馬興錄, 王先鵬. 移動機器人路徑規(guī)劃算法綜述[J]. 計算機測量與控制, 2022, 30(7): 9-19.

LI Xiao-xu, MA Xing-lu, WANG Xian-peng. A Survey of Path Planning Algorithms for Mobile Robots[J]. Computer Measurement & Control, 2022, 30(7): 9-19.

[14] KARUR K, SHARMA N, DHARMATTI C, et al. A Survey of Path Planning Algorithms for Mobile Robots[J]. Vehicles, 2021, 3(3): 448-468.

[15] 劉生偉, 馬鉞, 孟樹峰, 等. 改進(jìn)A*算法的AGV路徑規(guī)劃[J]. 計算機應(yīng)用, 2019, 39(S2): 41-44.

LIU Sheng-wei, MA Yue, MENG Shu-feng, et al. Improved A*Algorithm for Path Planning of AGV[J]. Journal of Computer Applications, 2019, 39(S2): 41-44.

[16] DUCHO? F, BABINEC A, KAJAN M, et al. Path Planning with Modified a Star Algorithm for a Mobile Robot[J]. Procedia Engineering, 2014, 96: 59-69.

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

LI Wei-guang, SU Xia. AGV Path Planning Based on Improved A*Algorithm[J]. Modern Manufacturing Engineering, 2015(10): 33-36.

[18] SINGH Y, SHARMA S, SUTTON R, et al. 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.

[19] 牟德君, 初鵬祥. 基于改進(jìn)A*算法的倉儲環(huán)境AGV路徑規(guī)劃[J]. 自動化與儀表, 2022, 37(4): 40-45.

MU De-jun, CHU Peng-xiang. AGV Path Planning for Warehouse Environment Based on Improved A*Algorithm[J]. Automation & Instrumentation, 2022, 37(4): 40-45.

[20] REN Gong-chang, LIU Peng, HE Zhou. A Global Path Planning Algorithm Based on the Feature Map[J]. IET Cyber-Systems and Robotics, 2022, 4(1): 15-24.

[21] ZHONG Xun-yu, TIAN Jun, HU Huo-sheng, et al. Hybrid Path Planning Based on Safe A*Algorithm and Adaptive Window Approach for Mobile Robot in Large-Scale Dynamic Environment[J]. Journal of Intelligent & Robotic Systems, 2020, 99(1): 65-77.

[22] WANG Li-hui, LIU Ming-jie. Path Tracking Control for Autonomous Harvesting Robots Based on Improved Double Arc Path Planning Algorithm[J]. Journal of Intelligent & Robotic Systems, 2020, 100(3): 899-909.

[23] WANG Jian-kun, CHI Wen-zheng, LI Chen-ming, et al. Neural RRT*: Learning-Based Optimal Path Planning[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(4): 1748-1758.

[24] BOLU A-li, KOR?AK ?. Path Planning for Multiple Mobile Robots in Smart Warehouse[C]// 2019 7th International Conference on Control, Mechatronics and Automation (ICCMA) Delft, Netherlands IEEE, 2020: 144-150.

Multi-AGV Path Planning Considering Conflict Avoidance

YANG Wei, YANG Si-yao,ZHANG Zi-han

(School of Mechanical and Electrical Engineering, Shaanxi University of Science and Technology, Xi'an 710021, China)

The work aims to improve the efficiency of the "goods to people" picking system in logistics enterprises during actual production, avoid conflict deadlock between automatic guided vehicles (AGVs), and study the conflict free path planning and collaborative obstacle avoidance problem of large-scale multi AGVs. Firstly, A*algorithm was improved considering the empty load, load situation, and path expansion cost of AGV, the cost function was adjusted dynamically and the path expansion method was optimized. Then, a conflict detection and avoidance algorithm was proposed, which scheduled path intersections that might generate local conflicts. Local conflict detection was achieved through reserved lock grids, and priority obstacle avoidance strategies were developed to solve local conflicts and deadlocks generated on AGV dynamic driving paths, to achieve global conflict free path planning. Multiple scenarios with different task volumes and AGV scales were simulated. The experimental results showed that the improved A*algorithm considering conflict avoidance could effectively achieve dynamic path planning for multiple AGVs in scenarios with 100 tasks, 90 shelf units, and 7 picking stations. Compared to the traditional A*algorithm, the average picking time was optimized by 52.61%. This method can achieve dynamic path planning for multiple AGVs in large-scale scenarios, effectively avoiding local dynamic conflicts while paying less turning costs. This method can provide new ideas and theoretical basis for relevant enterprises to achieve collaborative scheduling of multiple AGVs.

"goods to people" picking systems; automated guided vehicles; improved A*algorithm; conflict detection and obstacle avoidance algorithm; dynamic path planning

TP24

A

1001-3563(2023)23-0181-10

10.19554/j.cnki.1001-3563.2023.23.022

2023-02-24

陜西省西安市未央?yún)^(qū)科技計劃（202203）

責(zé)任編輯：彭颋