[發明專利]一種應用于倉儲環境下多機器人路徑快速規劃方法

有效

• 申請號: 202010233690.0
• 申請日: 2020-03-30
• 公開（公告）號: CN111487962B
• 公開（公告）日: 2021-10-01
• 發明（設計）人: 胡標;徐圣杰;曹政才;黃冉
• 申請（專利權）人: 北京化工大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 沈波

本發明公開了一種應用于倉儲環境下多機器人路徑快速規劃方法，本發明屬于機器人路徑規劃技術領域。此算法應用于自動導引機器人(AGV)，可以在規模較大的倉庫中快速實現多機器人多任務無碰撞的路徑規劃，極大的節約計算時間和計算機資源，提高倉儲系統的實時性。該方法的核心算法是A*算法與網絡流算法相結合，針對非指派性任務，本發明還提出了相應的任務分配算法，本發明算法避免了工程實踐中時間和計算機資源的浪費，用較少的時間和內存便可得到多機器人多任務路徑規劃的次優解。

技術領域

本發明涉及機器人路徑規劃技術領域，具體是指一種應用于倉儲環境下多機器人路徑快速規劃方法。

背景技術

近年來，隨著電商的高速發展，包裹分揀作業量不斷增加，對作業效率、準確率和客戶體驗的要求也在不斷提高，商品倉庫規模也在逐漸變大，如何快速準確的對貨物進行分揀引起越來越大的關注。在此背景下，分揀機器人得到越來越廣泛的應用，而機器人的路徑規劃問題已成為貨物運輸、快遞分揀等領域中一項關鍵技術問題。倉儲環境布局規則，通道狹窄的特點很適合用A*算法進行單機路徑規劃。

近年來，由于網絡流算法能轉換為線性規劃問題，并且有效的解決多商品流的問題，在工程實踐和運輸等領域被廣泛應用。網絡流算法能最優的規劃多機路徑，并且能夠避免多機器人間的碰撞，但是當問題規模較大時，其求解最優路徑耗時過長是其主要問題。

傳統的網絡流算法需要通過逐步增加增廣時長來嘗試找到問題的解，這是一個冗長繁瑣的過程，當問題規模較大時需要進行大量的時間增廣，而且傳統的網絡流模型較為復雜，問題規模較大時占用計算機資源過多，計算速度會進一步降低。如何減少問題規模增長時網絡流模型的規模便成了亟待解決的問題。

同時，在倉儲環境中，多個機器人在協同作業的同時，每個機器人可以擁有多個任務，即每個機器人在一次旅途中要經過多個目標點，最后到達終點，在以往的研究中，大多數研究者都有意無意的忽略了這個問題，因為這會增加問題的復雜度，使問題更加難以求解。

因此，如何解決以上問題，是解決機器人應用在倉儲環境中的關鍵問題。

發明內容

以下給出一個或多個方面的主要概述以應對這些方面的基本理解。此概述不能將所有構想的方面進行詳述，其唯一的目的是要以簡化形式給出一個或多個方面的一些概念以為稍后給出的更加詳細的描述之序。

本發明的目的在于解決上述問題，提供了一種應用于倉儲環境下多機器人路徑快速規劃方法，該方法通過A*算法對單機器人進行路徑規劃，并用簡化模型的網絡流算法對碰撞區域進行重構，能在較短的時間內有效的解決了在單次旅途中每個機器人擁有多個指派性或非指派性任務的多機器人路徑規劃問題。

本發明提出一種應用于倉儲環境下多機器人路徑快速規劃方法，包括：

步驟一：使用柵格地圖建立真實的倉儲環境模型，每個Agent(智能體)在一次旅途中要完成多個任務；

步驟二：針對指派性任務，采用A*算法與網絡流算法相結合的方法，使用A*算法對每個Agent按照指派性任務的順序進行路徑規劃，隨后針對發生碰撞的地方采用網絡流算法進行重構；

步驟三：針對非指派性任務，使用A*算法對每個Agent從起點到終點進行路徑規劃，隨后將所有非指派性任務進行分配并用A*算法規劃路徑，最后針對發生碰撞的地方采用網絡流算法進行重構。

根據本發明的一種應用于倉儲環境下多機器人路徑快速規劃方法，在步驟一中，包括以下步驟：

步驟1：倉儲環境通過柵格法參照真實倉儲環境進行模型的建立；

步驟2：環境中加入多機器人及每個機器人要完成的多個指派性或非指派性任務。

根據本發明的一種應用于倉儲環境下多機器人路徑快速規劃方法，在步驟二中，包括以下進一步步驟：