亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2023-12-20 03:32:44楊瑋楊思瑤張子涵
        包裝工程 2023年23期
        關鍵詞:任務量貨架沖突

        楊瑋,楊思瑤,張子涵

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

        楊瑋,楊思瑤,張子涵

        (陜西科技大學 機電工程學院,西安 710021)

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

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

        隨著電商行業(yè)的快速發(fā)展和人工智能技術的不斷成熟,采用機器人代替人工作業(yè)已成為制造業(yè)及物流業(yè)發(fā)展的大趨勢,越來越多的企業(yè)開始在生產車間應用移動機器人系統(tǒng)協(xié)助生產[1]。有報告顯示[2-3],全球已有超十萬的多移動機器人系統(tǒng)和超百萬的移動機器人被應用于物流的倉儲環(huán)節(jié)。2008年,亞馬遜公司首次在物流倉庫使用了Kiva System,該系統(tǒng)是一種自動化程度較高的移動機器人履行系統(tǒng)(Robotic Mobile Fulfillment Systems,RMFS),通過多輛自動導引小車(Automated Guided Vehicle,AGV)合作進行貨物的存儲、搜索、選擇和運送工作,完成倉儲環(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)代物流設備的自動化和智能化發(fā)展,未來倉庫的發(fā)展趨勢必將是規(guī)模化和集約化。提高多AGV的集群化調度能力,尤其是針對較大規(guī)模的多AGV路徑規(guī)劃,是倉儲系統(tǒng)自動化與智能化發(fā)展中必須克服和突破的技術難點,也是影響企業(yè)物流效率的重要因素[7]。

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

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

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

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

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

        ()=()+() (1)

        1.1 A*算法

        1.1.1 問題描述

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

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

        圖2 負載AGV可通行路徑情況

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

        1.1.2 改進A*算法

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

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

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

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

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

        4)判斷OpenList是否為空,若是,搜索路徑失??;否則以OpenList中改進的評價函數(shù)()最小的節(jié)點作為當前節(jié)點,檢查其周圍4個鄰接節(jié)點,并計算()。

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

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

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

        1.2 沖突檢測及避免算法

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

        1)在同一時刻內,1個柵格僅能被1輛AGV占用,1輛AGV不能同時占用2個及以上的柵格。

        2)在AGV接收到揀選任務時,已知該任務的起始點和目標點位置。

        3)不考慮AGV行進過程中的變速,設置其勻速通過每個柵格,通過1個柵格的時間為1 s。

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

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

        5)設置通道為雙向單車道,AGV可以在巷道內沿著路徑方向自由行駛。

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

        1.2.1 預約鎖格

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

        圖3 不同沖突類型

        圖4 預約鎖格

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

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

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

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

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

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

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

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

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

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

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

        7)當前所有AGV完成揀選任務后,判斷任務列表是否已為空。若列表已空,則規(guī)劃結束,否則重復步驟2)~6),直至所有任務結束。

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

        2 結果與分析

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

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

        表1 實驗基本設置

        Tab.1 Basic experimental settings

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

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

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

        表2 算法有效性實驗

        Tab.2 Algorithm effectiveness experiment

        表3 避障實驗結果

        Tab.3 Results of obstacle avoidance experiment

        圖7 存在沖突的初始路徑

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

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

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

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

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

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

        Tab.4 Results of large-scale task experiments

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

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

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

        Tab.5 Simulation results under different scales of AGVs

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

        3 結語

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

        [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]. 機器人技術與應用, 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]. 自動化學報, 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ī)劃與調度研究[J]. 中國管理科學, 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] 竇佳佳. 強化學習及其在智能倉儲中的應用研究[D]. 南京: 南京大學, 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]. 物流技術與應用, 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] 劉生偉, 馬鉞, 孟樹峰, 等. 改進A*算法的AGV路徑規(guī)劃[J]. 計算機應用, 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] 李偉光, 蘇霞. 基于改進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] 牟德君, 初鵬祥. 基于改進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)

        責任編輯:彭颋

        猜你喜歡
        任務量貨架沖突
        捉迷藏
        戰(zhàn)時裝備修理任務量計算研究?
        耶路撒冷爆發(fā)大規(guī)模沖突
        “三宜”“三不宜”化解師生沖突
        井岡教育(2020年6期)2020-12-14 03:04:32
        基于模糊層次分析法的通信裝備維修任務量建模方法
        軟件(2020年3期)2020-04-20 01:45:06
        邵國勝:實現(xiàn)從“書架”到“貨架”的跨越
        科學中國人(2018年1期)2018-06-08 05:42:58
        投資無人貨架適合嗎?
        中國儲運(2018年4期)2018-04-08 10:56:22
        員工績效考核管理制度研究
        大經貿(2017年6期)2017-07-29 09:42:12
        基于定性與定量分析的聯(lián)絡中心任務量預測法
        “鄰避沖突”的破解路徑
        浙江人大(2014年6期)2014-03-20 16:20:40
        热re99久久精品国99热| 国产又大又硬又粗| 女优免费中文字幕在线| 看中文字幕一区二区三区| 国产偷国产偷亚洲综合av| 日本成本人片免费网站| 午夜男女爽爽爽在线视频| 国产精品偷伦免费观看的| 日韩一二三四区免费观看| 日韩精品网| 国产大学生自拍三级视频| 激情文学婷婷六月开心久久| 国产乱子伦| 亚洲综合无码一区二区三区 | 日韩女优视频网站一区二区三区| 亚洲av成人无码久久精品老人| 国产免费av片在线观看| 欧美专区在线| 免费观看成人稀缺视频在线播放| 麻婆视频在线免费观看| 亚洲成aⅴ人片久青草影院 | 在线观看午夜亚洲一区| 91福利国产在线观一区二区 | 美国少妇性xxxx另类| 理论片87福利理论电影| 国产精品女同久久免费观看| 日韩av免费一区二区| 国产福利视频在线观看| 精品乱子伦一区二区三区| 国内偷拍第一视频第一视频区| 18禁止进入1000部高潮网站| 中文字幕一区二区三区精华液| 91精品国产91久久综合桃花| 蜜桃免费一区二区三区| 亚洲人精品亚洲人成在线| 亚洲aⅴ无码国精品中文字慕| 中文字幕手机在线精品| 日日摸天天摸97狠狠婷婷| 久久精品久久精品中文字幕| 日本在线免费一区二区三区| 十八禁视频在线观看免费无码无遮挡骂过 |