[發明專利]一種基于共識的捆綁算法的分布式任務分配方法

在審

• 申請號: 202211305140.0
• 申請日: 2022-10-24
• 公開（公告）號: CN115689184A
• 公開（公告）日: 2023-02-03
• 發明（設計）人: 辛斌;李翀;王晴;郭苗;賀英媚;陳杰
• 申請（專利權）人: 北京理工大學
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 張麗娜

本發明屬于多智能體分布式任務規劃技術領域，具體涉及一種基于共識的捆綁算法的分布式任務分配方法，用于完成在智智能體與總體的通訊條件受限情況下多智能體的任務分配，系統具有良好的擴展性和魯棒性。本發明提出了一種基于共識的捆綁算法的分布式任務分配方法，以經典的拍賣算法為核心，并再此基礎上進行改進和調整，相較拍賣算法得到的分配方案更加合理，具體體現在后續的任務執行時間和執行效率都有較大提升，且運算時間與拍賣算法基本相同，可以滿足對于時間快速性的需求和分配結果有效性的要求。

技術領域

本發明屬于多智能體分布式任務規劃技術領域，具體涉及一種基于共識的捆綁算法的分布式任務分配方法，用于完成在智智能體與總體的通訊條件受限情況下多智能體的任務分配，系統具有良好的擴展性和魯棒性。

背景技術

多智能體任務分配問題是當前的多智能體領域的熱點問題。多智能體任務分配是指多智能體協同完成某項任務時，將任務分別分配給智能體，從而實現時間最短或某項收益值最大。目前多智能體協同任務分配問題按照智能體的通信方式分為兩種：集中式與分布式。

集中式方法指的是由一個中央控制器來完成所有的分配計算，該中央控制器掌握全局信息，能獲得全局最優的分配方案，但其魯棒性較差，且中央控制器的計算負載過大，當中央控制器損壞則無法完成分配工作。分布式方法指智能體均有控制器能運算分配方案，并能實時通信與其他智能體交換分配方案，以實現信息的一致性，該方法的魯棒性較強，如若其中一個智能體損壞，不影響整個系統的繼續運轉，但該方法由于各智能體均從自身來計算分配方案，不易得到全局最優的分配方案。

在復雜的動態現實環境中，由于通訊條件、實時性以及不確定性的存在，分布式方法的適用范圍更加廣泛。分布式任務分配中沒有中心節點，也沒有中心控制器，每個智能體獨立地做自身決策，任務規劃方案由智能體之間通訊、協作、協商來實現。分布式決策并行計算，擴展性和魯棒性都較好，適用于較大規模的系統。

發明內容

本發明的技術解決問題是：克服現有技術的不足，提出一種基于共識的捆綁算法的分布式任務分配方法，該方法為了在有智能體之間的通訊條件受限制的情況下，在既定的時間內快速、高效的實現對多目標的任務分配，本發明提供了一種基于共識的捆綁算法的分布式任務分配方法，該方法可以適用于有智能體的通訊條件受限以及智能體以及任務信息動態變化的場景，且可以有效地完成沖突消解，從而達到快速分配方案的形成同時保證最優的分配效率。

實現本發明的技術方案如下：

一種基于共識的捆綁算法的分布式任務分配方法，包括如下步驟：

步驟1，總體根據智能體的能力信息和任務信息選擇任務代理，得到作為任務代理的智能體；

選擇任務代理時分兩種情況：

第一種為：初始狀態，即所有的智能體和任務均未分配，則根據智能體的能力值選擇能力值最高的智能體作為任務代理；

第二種為：非初始狀態，即存在智能體或任務的信息發生變化，則選擇距離該任務最近的智能體作為任務代理；

所述的總體表示分布式架構中單個智能體的中央控制器，總體的決策和規劃能力遠遠高于單個智能體，所有的智能體都屬于總體的下級單位，聽從總體的指揮和調遣；

所述的任務代理為負責協調任務分配方案的智能體；

所述的單個智能體的信息包括：編號、位置坐標、速度、通訊范圍、所帶傳感器的類型、智能體的狀態；

所述的任務信息包括：編號、位置坐標、任務類型、任務難度、任務價值；

所有的智能體初始化狀態都是空閑；

所述的攜帶不同類型傳感器的智能體能完成的任務類型不同；