[發明專利]一種單通道場景下的啟發式路徑規劃方法、設備及介質

在審

• 申請號: 202210333852.7
• 申請日: 2022-03-30
• 公開（公告）號: CN114674322A
• 公開（公告）日: 2022-06-28
• 發明（設計）人: 單逸凡;董怡;李莉;葉飛揚;孫迪
• 申請（專利權）人: 同濟大學;上海快倉智能科技有限公司
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 上海科盛知識產權代理有限公司 31225
• 代理人: 翁惠瑜

本發明涉及一種單通道場景下的啟發式路徑規劃方法、設備及介質，包括以下步驟：1)獲取每個AGV的任務起始位置與終止位置，構建輸入列表；2)計算每個AGV的所述任務起始位置與終止位置間的曼哈頓距離，按曼哈頓距離由小到大，對各AGV進行排序，生成輸出列表；3)逐次按優先級從高到低使用WHCA*算法對各AGV進行路徑規劃，存儲規劃路徑，基于所述規劃路徑移動各AGV設定步數，統計當前規劃過程中每個AGV的碰撞次數；4)按所述碰撞次數由高到低更新所述輸出列表；5)重復步驟3)和步驟4)，直至所有AGV均到達各自的終止位置。與現有技術相比，本發明具有執行時間短、效率高、能夠解決循環碰撞問題等優點。

技術領域

本發明屬于智能倉儲交通控制與設計領域，涉及一種路徑規劃方法，尤其是涉及一種單通道場景下的啟發式路徑規劃方法、設備及介質。

背景技術

智能倉儲的建設是現代物流業發展的重要一環，其理念在于利用自動化設備和智能的管理方法，建立更加高效、柔性和精確的倉儲系統，以滿足消費者趨于多樣化和個性化的需求轉變。智能倉儲承擔的主要任務是在少數工作人員輔助、多種自動化設備協同工作的條件下，按照客戶下達的訂單內容將倉庫內種類繁多的商品以正確的種類和數量分別揀選出來，再各自裝進紙箱打包封箱，最后送達到物流公司的快遞攬收點裝車運出倉庫，其中，最主要的協同工作的自動化設備是自動引導工具(Automated Guided Vehicle，AGV)機器人。

其中，如何協同一個智能倉儲系統內部大量的AGV是一個非常復雜的問題。特別是在一些復雜場景下，比如單通道場景。在單通道場景中，由于可行空間十分有限，因此極其容易發生碰撞，死鎖，并且僅僅設定相應的規則是不夠的，因為空間狹小，很容易再次在相同的地方發生問題。

因此，在單通道復雜場景下，如何設定相應有效的多智能體路徑規劃方法就變得非常重要。而現有的普通路徑規劃方法并不適用于單通道復雜場景。

發明內容

本發明的目的就是為了克服上述現有路徑規劃方法在單通道場景下容易出現循環碰撞與死鎖的問題而提供一種執行時間短、效率高的單通道場景下的啟發式路徑規劃方法、設備及介質。

本發明的目的可以通過以下技術方案來實現：

一種單通道場景下的啟發式路徑規劃方法，包括以下步驟：

1)獲取每個AGV的任務起始位置與終止位置，構建輸入列表；

2)計算每個AGV的所述任務起始位置與終止位置間的曼哈頓距離，按曼哈頓距離由小到大，對各AGV進行排序，曼哈頓距離越小的AGV優先級越高，生成輸出列表；

3)逐次按優先級從高到低使用WHCA*算法對各AGV進行路徑規劃，存儲規劃路徑，形成預約表，基于所述規劃路徑移動各AGV設定步數，統計當前規劃過程中每個AGV的碰撞次數；

4)按所述碰撞次數由高到低更新所述輸出列表，碰撞次數越多的AGV優先級越高；

5)重復步驟3)和步驟4)，直至所有AGV均到達各自的終止位置。

進一步地，所述曼哈頓距離的計算公式為：

D_manhattan＝|Xi-Xj|+|Yi-Yj|

其中，(Xi,Yi)、(Xj,Yj)分別為id為i和j的AGV在任務地圖上的X與Y軸上的索引。

進一步地，步驟3)中，存儲所述規劃路徑的數據結構的數據格式為(位置，到達時間)。

進一步地，步驟3)中，所述設定步數為K，且KW，其中，W為WHCA*算法中的時間窗大小。

進一步地，步驟3)中，對各AGV進行路徑規劃時，當前AGV的規劃不得與預約表中已存在的路徑產生沖突。