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

楊瑋，楊思瑤，張子涵

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

楊瑋，楊思瑤，張子涵

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

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

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

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

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

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

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

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

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

()=()+() (1)

1.1 A*算法

1.1.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 沖突檢測及避免算法

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

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

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

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

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

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

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

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

1.2.1 預(yù)約鎖格

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

圖3 不同沖突類型

圖4 預(yù)約鎖格

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

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

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

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

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

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

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

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

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

5）不斷獲取占用點(diǎn)信息，判斷安全距離內(nèi)是否會(huì)發(fā)生沖突。若發(fā)生沖突，則即刻啟用優(yōu)先級(jí)避障策略，在決策AGV通行順序的同時(shí)解決沖突，否則進(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ī)模仿真實(shí)驗(yàn)分析

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

表1 實(shí)驗(yàn)基本設(shè)置

Tab.1 Basic experimental settings

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

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

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

表2 算法有效性實(shí)驗(yàn)

Tab.2 Algorithm effectiveness experiment

表3 避障實(shí)驗(yàn)結(jié)果

Tab.3 Results of obstacle avoidance experiment

圖7 存在沖突的初始路徑

圖8 避免動(dòng)態(tài)沖突后的實(shí)際路徑

2.2 大規(guī)模仿真實(shí)驗(yàn)分析

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

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

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

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

Tab.4 Results of large-scale task experiments

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

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

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

Tab.5 Simulation results under different scales of AGVs

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

3 結(jié)語

針對(duì)“貨到人”揀選系統(tǒng)多AGV的路徑規(guī)劃和沖突避免問題進(jìn)行了研究，提出了一種考慮沖突檢測及避免的路徑規(guī)劃算法。首先考慮AGV空載、負(fù)載的不同狀態(tài)，調(diào)整其行駛方式，對(duì)路徑轉(zhuǎn)彎成本設(shè)置懲罰因子，動(dòng)態(tài)調(diào)整A*算法代價(jià)函數(shù)，改進(jìn)A*算法，以優(yōu)化AGV執(zhí)行任務(wù)時(shí)的轉(zhuǎn)彎次數(shù)。其次，設(shè)計(jì)沖突檢測及避免算法，為滿足路徑規(guī)劃的可通達(dá)性要求，提出了預(yù)約鎖格策略，通過不斷獲取占用的節(jié)點(diǎn)信息，鎖定安全距離，進(jìn)而始終保障優(yōu)先級(jí)高的AGV率先結(jié)束任務(wù)。針對(duì)系統(tǒng)中出現(xiàn)的局部動(dòng)態(tài)沖突問題，提出了節(jié)點(diǎn)等待和重新規(guī)劃等優(yōu)先級(jí)避障策略，解決了局部動(dòng)態(tài)沖突，進(jìn)而獲得了高效、可行的全局無碰撞路徑。最后，基于仿真軟件，通過多組不同任務(wù)量和不同AGV規(guī)模的仿真實(shí)驗(yàn)證明，文中所提的路徑規(guī)劃算法能有效避免系統(tǒng)中的沖突，并付出了較少的轉(zhuǎn)彎代價(jià)。該算法在提高路徑搜索效率的同時(shí)，能夠保證搜索質(zhì)量，具有較好的魯棒性和實(shí)用性，能實(shí)現(xiàn)100個(gè)任務(wù)、90個(gè)貨架單位和7個(gè)揀選站場景下的多AGV動(dòng)態(tài)路徑規(guī)劃，能為企業(yè)采用“貨到人”揀選系統(tǒng)促進(jìn)倉庫實(shí)際生產(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] 本刊編輯部. 國際機(jī)器人聯(lián)合會(huì)2021年全球工業(yè)機(jī)器人統(tǒng)計(jì)數(shù)據(jù)[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] 徐翔斌, 馬中強(qiáng). 基于移動(dòng)機(jī)器人的揀貨系統(tǒng)研究進(jìn)展[J]. 自動(dòng)化學(xué)報(bào), 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] 竇佳佳. 強(qiáng)化學(xué)習(xí)及其在智能倉儲(chǔ)中的應(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] 楊文華. 我國倉儲(chǔ)物流機(jī)器人發(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] 李曉旭, 馬興錄, 王先鵬. 移動(dòng)機(jī)器人路徑規(guī)劃算法綜述[J]. 計(jì)算機(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]. 計(jì)算機(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*算法的倉儲(chǔ)環(huán)境AGV路徑規(guī)劃[J]. 自動(dòng)化與儀表, 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ū)科技計(jì)劃（202203）

責(zé)任編輯：彭颋