[發明專利]一種基于網絡擁堵模型的多AGV全局規劃方法

在審

• 申請號: 202110379885.0
• 申請日: 2021-04-08
• 公開（公告）號: CN113516429A
• 公開（公告）日: 2021-10-19
• 發明（設計）人: 謝巍;周雅靜;楊啟帆;廉胤東;錢文軒;林丹淇;張宜旭;林健峰
• 申請（專利權）人: 華南理工大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q10/06
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 何淑珍;江裕強

本發明公開了一種基于網絡擁堵模型的多AGV全局規劃方法，首先建立區域化的地圖，并根據運輸需求給AGV分配任務，確定AGV路徑的起始區域和目標區域；然后，在距離代價的基礎上，引入包含轉彎代價的時間代價與基于修正網絡擁塞擴散模型的區域密度估值，以更新A*算法的估計代價值；最后基于改進A*算法進行區域間全局路徑規劃，獲取連接當前區域和目標區域的路徑區域集。本發明根據區域擁堵情況這一指標對傳統的A*算法進行改進。本發明利用網絡擁塞模型預測各個區域的擁堵情況，在調度時盡可能使AGV合理分布在各個區域內，提高了多AGV系統的運輸效率的同時降低了調度算法的復雜度。

技術領域

本發明屬于智能車路徑規劃領域，涉及一種基于網絡擁堵模型的多AGV全局規劃方法。

背景技術

我國電子商務的崛起推動了物流倉儲行業發展，快遞業務量保持高速增長態勢，物流倉庫的分揀運輸工作日益繁重，不少電商巨頭已進軍倉儲自動化領域，嘗試以機器分揀運輸代替人工，先有亞馬遜的Kiva機器人，后有京東、菜鳥等的各種倉儲AGV，倉儲自動化、智能化已成趨勢。

但目前國內智能化倉儲仍處于發展階段，現有技術仍有提升空間。在單臺AGV路徑規劃算法方面，現行主流方法多采用A*算法和D*算法，盡管這兩種經典路徑規劃方法在進行單臺機器路徑規劃時都能取得不錯的效果，但對于復雜環境中的多AGV協同路徑規劃，傳統A*算法與D*算法存在一定局限性。傳統A*算法規劃路徑時默認地圖環境是靜態的，因而若環境改變，如出現新的障礙物時，原規劃路徑將被丟棄，需要進行重規劃，這種路徑規劃方法不適于實時變化的復雜倉儲環境；改進的D*算法考慮了環境的實時變化，一定程度上減少了重規劃的計算量。當D*算法檢測到周圍環境變化后，AGV會重新規劃并求出最優路徑。但是當AGV數量增加，重規劃的次數也隨之遞增，給大規模AGV的實時調度任務帶來挑戰。

為此，本發明利用A*算法路徑固定這一特點，引入時間變量對A*算法進行改進，通過改進現有的網絡擁堵擴散模型(G.Wen,N.Huang,C.Wang,Network congestiondiffusion model considering congestion distribution information,IEEE Access 7(2019)102064–102072.)(A.Tareen,N.S.Wingreen,R.Mukhopadhyay,Modeling evolutionof crosstalk in noisy signal transduction networks,Phys.Rev.E97(2)(2018)20402)預測各個區域的擁堵情況，在調度時盡可能使AGV合理分布在各個區域內，使A*算法單次規劃的調度效果與基于模型預測控制的D*算法(V.Digani,M.A.Hsieh,L.Sabattini,C.Secchi,Coordination of multiple AGVs:aquadratic optimization method,Auton.Robot.43(3)(2019)539–555.)多次重規劃后的調度效果近似的同時大大減少了算法的規劃次數。經過測試，本發明能夠適應于大規模AGV的調度，在算法復雜度和調度效率之間進行了一個科學的權衡。

發明內容

本發明旨在通過修正網絡擁塞擴散模型對現有路徑規劃算法進行改進，以提高多AGV系統的運輸效率和智能倉庫的空間利用率，故提供一種基于網絡擁堵模型的多AGV全局規劃方法。

本發明至少通過如下技術方案之一實現。

一種基于網絡擁堵模型的多AGV全局規劃方法，包括以下步驟：

1)建立區域化的倉儲環境地圖，為各空閑AGV分配運輸任務；

2)分別獲取各區域的距離代價與時間代價；

3)預測各區域的AGV密度，根據倉儲系統的調度建立改進的網絡擁堵擴散模型；

4)根據各區域的AGV密度，獲取各區域密度估值；