[發明專利]一種基于平衡聯盟的多智能體聯盟形成方法

有效

• 申請號: 201610470945.9
• 申請日: 2016-06-24
• 公開（公告）號: CN106055390B
• 公開（公告）日: 2018-02-06
• 發明（設計）人: 方浩;盧少磊;陳杰;張帆
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 北京理工大學專利中心11120
• 代理人: 仇蕾安,高燕燕

技術領域

本發明涉及智能機器人技術領域，具體涉及一種基于平衡聯盟的多智能體聯盟形成方法。

背景技術

在多智能體系統中，多智能體能夠協同完成單個智能體無法勝任的任務，并保證任務的順利完成，提高完成任務的成功率。在多智能體協同任務分配過程中，形成聯盟是一個實現多智能體任務分配的有效途徑。形成的聯盟的平衡系數越高，聯盟的容錯率越大。

文獻(Vig L,Adams J A.Multi-robot coalition formation[J].Robotics,IEEE Transactions on,2006,22(4):637-649.)給出了平衡聯盟的證明，并且通過對所有潛在聯盟的平衡系數的計算，篩選出平衡系數最大的聯盟作為最終聯盟。但是，采用文獻中提到的選擇方法，存在以下幾個問題：

1、隨著潛在聯盟個數的增長，計算量也隨之增大，導致聯盟形成時間延長，影響任務執行效率。

2、上述方法是將智能體系統中的所有智能體相互形成聯盟，進而獲得平衡系數。但在實際情況下，有些潛在聯盟因通信阻塞等異常和突發事件的影響，導致該潛在聯盟無法形成。

3、在實際情況下，大多數智能體通常具備多項資源或能力，但文獻中設定的智能體的資源或能力為1維數值量，不符合實際情況。

發明內容

有鑒于此，本發明提供了一種基于平衡聯盟的多智能體聯盟形成方法，根據智能體的實際情況，結合平衡系數的原理，形成最優聯盟。

一種基于平衡聯盟的多智能體聯盟形成方法，具體包括如下步驟：

步驟一、獲得主智能體與其相鄰的鄰居智能體之間的結盟傾向度，具體為：

將智能體系統中的任意一個智能體定義為智能體i，并作為主智能體，其能力向量用r_i表示；主智能體i的鄰居智能體定義為智能體j，j∈{1,2,…,||N_i||}，其能力向量用r_j表示；N_i表示主智能體i的鄰居智能體的集合，||N_i||表示鄰居智能體的個數；

根據α_ij＝ω₁×cos(θ_ij)+ω₂×d_ij，獲得主智能體i與鄰居智能體j的相似程度，即兩智能體之間的結盟傾向度α_ij，θ_ij為向量r_i和向量r_j之間的夾角；d_ij為向量r_i的模長和向量r_j的模長之差的相對大小；ω₁和ω₂為權值系數；且ω₁＝0.6，ω₂＝0.4；

步驟二、獲得智能體自身能力向量與任務需求向量的一致程度：

根據獲得主智能體i的能力向量與任意任務t_q的任務需求向量之間的相關程度其中，為任務t_q的任務需求向量；代表主智能體i的能力向量與任務需求向量間的內積；為任務需求向量的模值；|r_i|為能力向量r_i的模值；

步驟三、按照步驟一的方法，遍歷主智能體與其所有鄰居智能體的結盟傾向度，并求其平均值，獲得主智能體與鄰居智能體的平均結盟傾向度；并根據該主智能體i的能力向量與任意任務t_q的任務需求向量之間的相關程度分別對平均結盟傾向度和相關程度分配相應權值ω₃和ω₄，并加權求和，獲得主智能體對任務的t_q的傾向度；其中，權值ω₃和ω₄均等于0.5；

步驟四、按照步驟一至步驟三的方法，遍歷整個智能體系統，分別以智能體系統中的每個智能體作為主智能體，獲得各個智能體對所有任務的傾向度；

步驟五、針對每個智能體，選擇其對應的最大傾向度值所對應的任務作為該智能體選擇的最終任務；將選擇同一最終任務的所有智能體形成初始聯盟；

步驟六、分別判斷每個初始聯盟是否符合形成最終聯盟的條件，并對初始聯盟中的成員進行調整，具體為：

以其中一個初始聯盟為例，定義該初始聯盟為聯盟C，其對應選擇的任務為t_q；根據聯盟C所選任務t_q的任務需求向量計算聯盟C的聯盟能力值Q_C；若：