[發明專利]基于跳點尋路與協同避障的多AGV路徑規劃方法

有效

• 申請號: 202110253326.5
• 申請日: 2021-03-05
• 公開（公告）號: CN113074728B
• 公開（公告）日: 2022-07-22
• 發明（設計）人: 程翔;都圓圓
• 申請（專利權）人: 北京大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

本發明公布了一種基于跳點尋路與協同避障的多AGV路徑規劃方法，包括步驟：對AGV運行空間場地建模，將AGV運行空間劃分為緊密排列的多個柵格類型的柵格區域；將每個柵格區域作為一個路徑節點；根據跳點尋路算法為AGV規劃初始運行軌跡；根據反應式協同避障方法處理AGV之間在運行過程中可能遇到的各類沖突。通過對場地地圖采用跳點尋路算法和協同避障方法進行設計規劃，得到多AGV的分布式路徑，使得各個AGV無沖突地執行分派的分揀任務，有效提升分布式多AGV的工作效率。本發明方法在保障最短路徑情況下，算法的計算和通信成本低、主控的計算和管理負擔小，方法具有可行性和高效性，可為智能倉庫的分布式多AGV調度提供完整高效的解決方案。

技術領域

本發明屬于多智能體路徑規劃技術領域，涉及物流系統中的多自動引導車的分布式自動分揀中的路徑規劃任務。尤其涉及一種基于跳點尋路與協同避障的多AGV路徑規劃方法。

背景技術

工業4.0的到來，對于我國既是機遇也是挑戰。我國機器人擁有量世界最大，但是機器人使用密度低，機器人進入智能倉庫，便是一個需求量極大的應用方向。同時，由于我國土地資源逐漸緊缺、勞動成本急劇上升等現實因素，傳統的物流行業受到嚴重的限制。所以，以物聯網、云計算、大數據等為支撐，伴隨著智慧工廠和自動化物流的發展，自動引導小車(AGV–Automated Guided Vehicle)成為工業生產中一個研究熱點，在實現由自動化向全智能化轉型的工業生產中發揮著不可或缺的作用。智慧物流作為新一輪科技與產業革命背景下的新型的商業模式，不僅是現代科學技術在物流領域的一項高級應用，更是優化我國物流的產業結構、改善物流發展趨勢的重要途經。

相對于傳統倉庫人工操作而言，智能倉庫主要分配訂單任務給多輛AGV構成的集群式AGV 系統來進行復雜耗時的分揀操作。AGV是智能倉儲的重要組成部分，屬于移動式機器人范疇，通過磁感、視覺、激光及各種組合方式導引和定位。針對多AGV調度問題的研究，主要需要解決的問題可歸納為如下：1)單車實時高效路徑規劃問題，2)多車可靠快速沖突處理問題。

但是，現有的多AGV路徑規劃調度技術大多存在如下問題：

只追求路徑長度最短進行單目標調度，大地圖場景下耗時長，沒有考慮路徑平滑等處理，導致轉折點過多、還存在冗余節點或需要額外進行路徑平滑化處理等。這會造成系統效率低、控制難度大、機器磨損、存儲壓力大等問題。并且，控制系統大多采用集中式控制，將所有信息都匯聚于主智能體上位機之中，是一種分層的自上而下的管控方式，AGV只需被動接收控制，簡單易行，但AGV需要和中心頻繁通信，管理中心面臨著較大的管理和計算壓力。

同時當前方案大多在AGV數量較少場景下具有良好性能，但是隨著AGV數量增加，算法弊端會逐漸展露出來，低效的沖突解決策略難以應對由于AGV共享網絡路徑、競爭資源帶來的頻發復雜的沖突死鎖，AGV常處于原地等待的狀態，浪費了大量寶貴的時間。此外還存在有決策信息滯后的問題：按照先前的預判沖突進行規劃，與運行過程實際情況存在滯后。并且在高密度AGV場景下算法的求解難度大。這些都會導致各AGV的運行效率低，導致算法可用性、靈活性差。綜上，多AGV場景下可用分布式協同作業算法設計是一個有待解決的問題。

發明內容

為了克服上述現有技術的不足，本發明提供了一種基于跳點尋路與協同避障的多AGV路徑規劃方法。在給定倉庫場地地圖的基礎上，設計規劃得到多AGV的分布式路徑，以滿足各個AGV可以無沖突地執行分派的分揀任務的作業需求。本發明方法適用性廣，可有效提升分布式多AGV的工作效率。

本發明為實現上述目的，采用以下技術方案：

一種基于跳點尋路與協同避障的多AGV路徑規劃方法，跳點尋路算法主要解決多AGV路徑規劃問題，協同避障主要解決運行過程中遇到的各類AGV間的沖突問題。該方法包括如下步驟：