[發明專利]一種用于大型倉儲環境的AGV路徑規劃方法

在審

• 申請號: 202110974440.7
• 申請日: 2021-08-24
• 公開（公告）號: CN113703452A
• 公開（公告）日: 2021-11-26
• 發明（設計）人: 陳娟;張政;郭青
• 申請（專利權）人: 北京化工大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 北京細軟智谷知識產權代理有限責任公司 11471
• 代理人: 鮑亞平

本發明涉一種用于大型倉儲環境的AGV路徑規劃方法，通過限制搜索樹向著AGV的目標點方向擴展，提高單次搜索速度；改進傳統MCTS算法在搜索樹擴展至目標點才進行節點評價，使其每進行一次節點擴展便進行一次評價，避免“反向傳播”過程的時間浪費，提高了算法效率。然后，將DP算法多階段優化問題的思想和改進的MCTS算法相結合建立DP?MCTS算法，進一步提高了大型自動化倉儲系統下AGV的路徑規劃效率；能夠縮短AGV路徑規劃時間，得到多AGV的距離和時間均最短的路徑、降低多AGV系統能量消耗，能夠方便快捷的選擇出最優的AGV路徑有利于提高整個倉儲系統的實時性。

技術領域

本發明屬于AGV路徑規劃技術領域，具體涉及一種用于大型倉儲環境的AGV路徑規劃方法。

背景技術

大型自動化倉儲系統指僅需少量人工作業，通過自動引導車(AGV)實現自動存取物料的系統。作為自動化倉儲系統中主要的運輸工具，AGV承擔從指定起點到指定目標點的貨物運輸工作。AGV的運行效率對系統的整體效率有重要影響，而AGV的運行效率取決于路徑規劃的效率。對AGV的路徑進行合理規劃不僅可以提高倉儲系統的效率，還可以節省大量的能源。多AGV路徑規劃逐漸演化成一個多目標組合優化問題：除了需要關注算法快速性外，還需要考慮路徑距離最短、時間最小和耗能最少。因此，大型自動化倉儲系統下多AGV的路徑規劃問題得到了廣泛的關注。

現有的Dijkstra算法是AGV路徑規劃最有效的方法之一，但是其不能滿足倉儲環境規模不斷擴大的需求；傳統的動態規劃算法(Dynamic Programming，DP)通過隨機選擇起點對樣本集進行迭代，經多次訓練得到最接近最優策略的Value Function，從而找到解決問題的策略。隨著路徑規劃環境規模的擴大，訓練次數和單次訓練時間也會越來越大，DP算法在大型自動化倉儲系統中的計算量會隨著工位點個數的增加而指數增加；傳統的蒙特卡洛樹搜索算法(Monte Carlo Tree Search，MCTS)缺少啟發機制不能平衡“探索”與“利用”，其“盲目搜索”機制計算量較大。此外，在傳統的MCTS的節點擴展過程中，當搜索樹的葉子節點擴展至目標點時才對已遍歷過的節點進行評價，在大型倉儲系統中效率不高。

因此如何方便快捷的選擇出最優的AGV路徑已經成為亟需解決的技術問題。

發明內容

為了解決現有技術存在的效率低、實時性差的問題，本發明提供了一種用于大型倉儲環境的AGV路徑規劃方法，其具有效率更高、實時性更好等特點。

根據本發明的具體實施方式的一種用于大型倉儲環境的AGV路徑規劃方法，包括：

基于AGV的行駛起點和目標點的位置所確定的區域進行區域劃分，以確定AGV的路徑搜索范圍；

基于搜索范圍內當前節點與目標節點的位置對AGV節點擴展過程進行限定，以限定其搜索的方向；

在每進行一次節點擴展時則對該節點進行一次篩選直到目標節點，以找到AGV起點至目標點的所有可行路徑；

對所述可行路徑進行評分，選擇分值最小的可行路徑作為AGV的距離-時間最短路徑，并根據優先級確定AGV最優路徑。

進一步的，所述用于大型倉儲環境的AGV路徑規劃方法還包括：

對多個AGV的距離-時間最短路徑進行成對沖突預檢測，并確定路徑沖突關鍵段及其長度。

進一步的，所述用于大型倉儲環境的AGV路徑規劃方法還包括：

獲取存在路徑沖突的相關AGV的優先級，并采用自適應的方法對相關AGV的路徑和/或到達路徑中每個節點的時間進行修改；

在AGV遇到臨時障礙物時采用自適應的方法解決路徑沖突。

進一步的，所述用于大型倉儲環境的AGV路徑規劃方法還包括：