面向任務的重疊聯盟結構生成計算復雜性

張國富 宋曉曉蘇兆品岳 峰

(1.合肥工業大學計算機與信息學院,安徽 合肥 230601;2.合肥工業大學智能互聯系統安徽省實驗室,安徽 合肥 230009;3.合肥工業大學工業安全應急技術安徽省重點實驗室,安徽 合肥 230601)

1 引言

聯盟形成是多智能體系統中最基本、最重要的交互與合作形式.形成一個協作聯盟可以讓一組資源不足的agent通過共享資源和合作完成單個智能體不可能完成的任務,已在無線網絡[1]和電力調度[2]等領域得到廣泛應用.然而,為一批給定的任務分配最合適的協作聯盟在計算復雜性上具有很大的挑戰性,其核心是確定將形成哪些聯盟,以及哪些聯盟最有利于有效和穩定的完成給定的任務[3].

為了解決上述問題,在人工智能基礎研究領域涌現了一批優秀的聯盟形成模型和算法,如聯盟結構生成[4]、技能結盟博弈[5]、資源結盟博弈[6–7]、重疊聯盟形成博弈(overlapping coalition formation games,OCFGs)[8–9]等.具體來說,經典的聯盟結構生成問題旨在尋找智能體集的最優劃分,以使特征函數返回的聯盟值總和最大,但通常和任務無關,這使得聯盟結構生成理論和方法難以在實際中應用.

為了使聯盟形成更貼切實際,技能結盟博弈、資源結盟博弈和OCFGs將聯盟值與其完成的任務或實現的目標聯系起來.此外,上述模型還允許一個聯盟同時承擔多個不同的任務,這意味著每個智能體可以變相的參加不同的任務.不過,技能結盟博弈和資源結盟博弈都強制要求每個智能體都必須且只能加入一個聯盟,無論其能力或資源情況如何,這大大降低了智能體響應任務的積極性,導致資源利用率極低,并限制了聯盟的協作靈活性.應該看到的是,擁有足夠資源或強大能力的智能體完全可以加入更多的不同聯盟,以求解更多的任務、追求更多的效用.為此,OCFGs提供了最具擴展性和靈活性的協作機制,規定每個智能體都可以參與所有可能的聯盟,以自由競爭所有的任務.這種協作方式可以最大限度的利用智能體的資源,在時間有限、資源稀缺但需求量很大的實際場景中具有重要意義[10].但是,這種合作的靈活性也極大的增加了問題的復雜性和計算負擔,使得聯盟決策極其困難.

需要指出的是,在大多數實際應用場景中,智能體的行為通常是由任務驅動的,即智能體僅會為符合其自身利益或感興趣的任務貢獻資源.例如,在協作運輸[11]中,每輛卡車往往只會響應附近的運輸訂單,以盡可能降低運輸成本.在無線網絡[1]中,為了節省能量和延長網絡壽命,每個節點傾向于僅在其當前感知范圍內跟蹤目標,而不會主動增加發射功率以感知未知目標.此外,當一次涉及的智能體數或任務數較大時,一個突出的問題是如何減少聯盟的規模和可能的聯盟結構數,以有效利用智能體資源,節省計算成本,提高任務求解性能.在這種情況下,合理的選擇通常是限制聯盟的大小[12],而通過限制每個智能體可以響應的任務子集規模是一個非常貼切實際的選擇[7].

基于上述背景,本文從并發多任務視角出發,根據智能體當前的資源狀況和每個智能體的興趣集,致力于如何劃分任務子集給智能體去承擔,從而實現社會效用最大化.本文的主要貢獻有:

1)本文提出了一種新的面向任務的重疊聯盟結構生成(overlapping coalition structure,OCS)模型.與已有工作不同的是,在所提的模型中,聯盟結構中的聯盟是智能體集合的一個覆蓋,而聯盟結構承擔的任務是任務集的一個劃分子集,適用于各種并發多任務調度場景,即根據給定的批量并發任務,在考慮智能體資源狀況的前提下,決策選擇哪些智能體組成哪些聯盟去執行哪些任務;

2)本文對所提模型的解空間和計算復雜性進行了理論分析.研究發現,判斷重疊聯盟結構的成功性是一個P問題,即是多項式時間可解的,而搜索最優重疊聯盟結構是一個NP完全問題,即是多項式時間難解的;

3)為了驗證上述結果,本文基于流網絡分別設計了相應的孤立聯盟、重疊聯盟、重疊聯盟結構成功性判別算法和最優重疊聯盟結構生成算法.分析結果表明,判別孤立聯盟、重疊聯盟、重疊聯盟結構的成功性的時間復雜度均與智能體數和任務數呈多項式關系,而搜索最優重疊聯盟結構的時間復雜度與智能體數和任務數呈指數關系.

2 數學建模

定義1在面向任務的環境下,每個重疊聯盟是一個二元組(C,V),其中,C ?A表示一組智能體子集,滿足C?,且C中的成員可能是重疊的,即還會參加其他的聯盟;V ?T表示該聯盟的集體任務集.

定義2在任務偏好下,每個OCS是一組重疊聯盟的集合,其中的智能體子集是A的一個覆蓋,且每個重疊聯盟承擔互不相同的任務子集,如圖1所示,滿足:這些任務子集之間沒有任何交集;這些任務子集中最多只有一個可以為空集,這時所有的任務都已被其他聯盟承擔,或者剩余的智能體子集已無力承擔任何子任務.假設OCS={(C1,V1),···,(Cq,Vq)},q ∈N為OCS 中的重疊聯盟個數,則

圖1 面向任務的重疊聯盟結構示意圖Fig.1 Diagram of the task-oriented OCS

1)Cl ?A,Cl=?,?l ∈{1,···,q},即每個Cl都是A的一個非空子集;

2)Cx ∩Cy?,?x,y ∈{1,···,q},xy,即各Cl之間可能存在重疊的智能體成員;

4)Vl ?T,?l ∈{1,···,q},即每個Vl都是T的一個子集;

5)Vx ∩Vy=?,?x,y ∈{1,···,q},xy,即各Vl之間不相交;

6)|{Vl|Vl=?}|≤1,l ∈{1,···,q},即所有的Vl中至多只有一個為空集.

定義3OCS中的聯盟(Cl,Vl)是成功的,當且僅當

1)Vl=?,即不承擔任務的聯盟毫無實際意義;

2)?aj ∈Cl,Tj ∩Vl?,即Cl中的每個智能體成員都能夠在集體任務集Vl中找到一個其感興趣的子任務;

3)Vl中的每個子任務都能夠被Cl順利完成;

4)(Cl,Vl)內部以及和OCS中的其他聯盟之間沒有任何資源沖突.

定義4OCS是成功的,當且僅當OCS中至少包含一個成功聯盟.

從上述定義可以看出,對于一個OCS,所有的智能體子集Cl恰好構成A的一個覆蓋,所有的集體任務集Vl構成了任務集T的一個劃分子集.OCS中的每個聯盟要想成功,不僅需要考慮其內部,還需要考慮聯盟之間是否存在資源沖突.當聯盟內部因資源競爭而找不到可行的資源分配方案時,該聯盟就不可能成功.另一方面,當幾個不同聯盟因為重疊成員而存在資源沖突時,與重疊成員相關聯的這些聯盟均不可能成功.

如果聯盟(Cl,Vl)是成功的,則其聯盟值為

否則,v(Cl,Vl)=0.進一步的,OCS的值為

基于上述描述,最優OCS生成問題就是尋找一個OCS?,利用有限的智能體資源謀求社會效用最大化,即

其中表示在A和T上產生的所有OCS的集合.

3 計算復雜性分析

在本節,本文將分析面向任務的OCS生成問題的解空間和計算復雜性,有如下結果.

命題1OCS={(C1,V1),···,(Cq,Vq)}中包含的重疊聯盟數q≤m+1.

證由定義2可知,所有的集體任務集都沒有交集并且最多只能有一個集體任務集為空,因此有如下兩種情況: 首先,所有的集體任務集均不為空集,則OCS中最多只有m個聯盟,也就是每一個子任務ti構成一個集體任務集Vl,因此有q≤m;其次,當有且僅有一個集體任務集為空時,根據前面的分析,其他也最多只有m個集體任務集,此時每個集體任務集Vl里面有且僅有一個任務ti,因此有q-1 ≤m.綜合兩種情況,可得q≤m+1.證畢.

命題2OCS中的C1,···,Cq構成了智能體集合A的一個覆蓋,其可能的覆蓋數為.

證已知給定n個智能體,有2n-1個非空智能體子集[6].在OCFGs中,每個智能體可能同時參加這2n-1 個子集.不失一般性,對于OCS={(C1,V1),···,(Cq,Vq)},假設C1有2n-1 種情況,那么C2有2n-2種情況,以此類推,Cq只剩2n-q種可能.因此,可能的覆蓋數為

命題6判別OCS 中任意聯盟(Cl,Vl)是否成功是一個P問題.

證對于給定的任意(Cl,Vl),只有兩種情況:(Cl,Vl)是孤立的,即不包含任何重疊成員;(Cl,Vl)是一個重疊聯盟,其成員還參加了其他聯盟.如果(Cl,Vl)是一個非重疊聯盟,首先需要判斷Vl是否為空集.如果Vl不為空集,則再檢查Vl是否被Cl中的每個智能體感興趣,即對?aj ∈Cl,檢查Tj ∩Vl?是否成立.顯然,上述操作可以在多項式時間內完成.其次,需要判斷是否能夠找到一個可行的資源分配方案使得Cl能夠順利完成Vl.也就是說,對?ti ∈Vl,都有對其感興趣的智能體貢獻資源完成它,且子任務之間不存在任何資源沖突.由于|Cl|,|Vl|和r均是有界的,這種資源分配嘗試也很容易在多項式時間內完成.另一方面,如果(Cl,Vl)是一個重疊聯盟,將與之關聯的所有集體任務集非空的重疊聯盟放在一起進行考慮,檢查的步驟與上面類似,首先檢查智能體是否對任務集感興趣,然后檢查能否在幾個重疊聯盟之間找到一個可行的資源分配方案,使得每個重疊聯盟都能夠得到滿足.由于考察的重疊聯盟數是有限的,每個重疊聯盟的智能體子集和集體任務集也是有限的,這種資源分配也可以在多項式時間內完成.綜上可得,判別聯盟(Cl,Vl)是否成功是多項式時間可解的,即是一個P問題.

證畢.

命題7判別OCS是否成功也是一個P問題.

證一個OCS最多包含q≤m+1個重疊聯盟,顯然|OCS|是有界的.根據定義4可知,只要OCS包含一個成功聯盟(Cl,Vl),則OCS就是成功的.而根據命題6可知,判別(Cl,Vl)是否成功是多項式可解的.因此,判別OCS是否成功也是多項式時間可解的,即是一個P問題.證畢.

命題8搜索最優OCS是一個NP完全問題.

證根據式(3),搜索最優OCS 的決策問題可以描述為在智能體集A、任務集T和一些聯盟(C,V)(C ?A,V ?T)下,是否存在一個值至少為Y的OCS?首先,需要檢查這個決策問題的NP性,這需要猜測一個成功的OCS,因為只有成功OCS才可能有聯盟結構值.由命題1可知,OCS中最多有m+1個重疊聯盟,再根據命題6和命題7可知,驗證每個聯盟是否成功并且計算聯盟結構值都是可以在多項式時間內完成的.因此,上述決策是一個NP問題.其次,還需要進一步證明上述決策是一個NP難問題.根據規約法,將NP完全問題集中的0–1背包問題約簡為上述決策問題.0–1背包問題可表示為:給定一個容量為?的背包和一組物品{g1,···,gm},每個物品gi有一個體積wi和一個價值vi,是否存在一個序列{x1,···,xm}∈{0,1}m,使得? 為此,本文使用如下約簡方法.讓Tj=T,r=1,Y=Z,=?,且對?i ∈{1,···,m},ti=gi,Di=wi,μi=vi.可以看到,OCS中的每個智能體子集C恰好對應一個已選擇并放置在背包中的物品ti.|V >1|意味著背包中為V的每個任務分配的聯盟是相同的.因此,存在一個值至少為Y的OCS 當且僅當存在一個序列{x1,···,xm}∈{0,1}m可以滿足≤?和≥Z.綜上可得,搜索最優OCS是一個NP完全問題,即是多項式時間難解的.證畢.

4 成功性判別算法

要想計算OCS的值,就必須明確OCS中的聯盟是否成功.根據前面的分析,OCS中的聯盟分為兩種情況: 一種是孤立聯盟,即沒有任何交叉成員;另一種是重疊聯盟,即部分智能體成員還參加了其他聯盟.顯然,針對孤立聯盟,只需要檢查聯盟內部是否能找到一個合理的資源分配方案,而針對重疊聯盟,不僅需要檢查聯盟內部,還需要檢查幾個關聯的重疊聯盟在交叉智能體成員上是否有資源沖突.顯然,這兩種情形需要分別處理.在本節,本文針對OCS中的孤立聯盟和重疊聯盟分別設計了相應的成功性判別算法,并分析了每個算法的時間復雜度,探討了一些決策問題的復雜性與智能體數和任務數的關系,以進一步驗證前面命題的分析結果,即是否真的存在多項式時間算法可以判別聯盟的成功性,以及搜索最優重疊聯盟結構是否是多項式時間難解的,本文的結論見表1.需要指出的是,這些判別算法并不能求解出一個成功的聯盟,只能用于判斷一個業已形成的聯盟是否成功.下面,本文將針對表1中的結果進行詳細闡述.

表1 計算復雜性分析結果Table 1 Main complexity results relating to OCS

4.1 孤立聯盟的成功性判別

給定一個孤立聯盟(Cl,Vl),很難直接看出(Cl,Vl)在任務偏好下是否可以成功,主要因為(Cl,Vl)內部存在如下情形:

1)如果?aj ∈Cl中,Tj ∩Vl=?,這意味著aj對Vl根本不感興趣,此時(Cl,Vl)不可能成功;

2)即使情形1)滿足要求,如果?ti ∈Vl,對?aj ∈Cl,ti?Tj,即Cl中沒有一個成員對ti感興趣,此時(Cl,Vl)也不可能成功;

3)即使情形1)–2)均滿足要求,如果?ti ∈Vl,?k ∈,即Cl中所有對ti感興趣的智能體擁有的資源總量不可能滿足ti的需求,則(Cl,Vl)也不可能成功;

4)即使情形1)–3)均滿足要求,如果不同任務對同一智能體的資源需求超過了該智能體的負荷,即因為不同任務的競爭而產生資源沖突,則找不到一個可行的資源分配方案讓Vl中的所有任務都同時滿足,此時(Cl,Vl)也不可能成功.

顯而易見,上述4種情形中,前面3種情形很容易基于(Cl,Vl)進行判定,如算法1所示(算法1見表2).如果經過算法1檢查后,(Cl,Vl)是有效的,需要進一步檢查(Cl,Vl)是否存在潛在的、不可見的資源沖突,這將最終決定(Cl,Vl)是否成功.為此,一個棘手的問題擺在本文面前: 如何檢查(Cl,Vl)以發現潛在的資源沖突?

表2 算法1 (Cl,Vl)的成員有效性判別Table 2 Algorithm 1 Feasibility checking of the members in(Cl,Vl)

表3 算法2 孤立聯盟(Cl,Vl)的成功性判別Table 3 Algorithm 2 Succcess checking of the non-overlappin coalition(Cl,Vl)

表4 算法3 關聯聯盟集的成功性判別Table 4 Algorithm 3 Succcess checking of SIOC

為了解決這個問題,本文基于(Cl,Vl)構造一個如圖2所示的流網絡.具體來說,首先在有向圖中添加一個源點和一個匯點.Cl中的每個智能體成員aj都是源點附近的供應節點,在源點和每個aj之間都有一條弧,弧上的容量值為aj持有的第k維資源量.Vl中的每個任務ti都是匯點旁邊的一個需求節點,在匯點和每個ti之間也有一條弧,弧上的容量值為ti對第k維資源的需求量.對于?aj ∈Cl和?ti ∈Vl,只要ti ∈Tj,即aj對ti感興趣,aj和ti之間就會存在一條弧,弧上的容量值為aj在第k維資源上能夠為ti貢獻的最大值,即min.

圖2 基于(Cl,Vl)構造的流網絡Fig.2 Flow network construction based on(Cl,Vl)

構造好上述的流網絡,本文可以使用經典的Edmonds-Karp算法[13]計算網絡中的最大流.根據最大流最小割定理,如果網絡中的最大流小于,則網絡中不可能存在一個可行流使得匯點到ti之間的每條弧都飽和.這意味著,Vl中的多任務之間在第k維資源上存在著激烈的資源沖突,根本找不到一個可行的資源分配方案使得Vl滿足.如果網絡中的最大流大于或等于,則這個最大流即是一個可行的資源分配方案使得Vl中的每個任務在第k維資源上都能被滿足,且沒有任何資源沖突.

命題9算法2的時間復雜度至多為O(n6).

證首先,Cl中至多有n個智能體,Vl中至多有m個任務.因此,判斷(Cl,Vl)中智能體和任務有效性的時間復雜度至多為O(n+m).其次,對Vl中的每一個ti,本文需要判斷每一維資源是否能被滿足,其時間復雜度至多為O(m×r).此外,計算最大流的Edmonds-Karp算法其時間復雜度為O(ν×ε2)[13],其中ν和ε分別是網絡中的節點數和弧數.從圖2中可以看到,網絡中最多有(2+n+m)個節點和(n+n×m+m)條弧,又每一維資源都需要通過流網絡進行評估,故其時間復雜度至多為O(r×(n+m)×(n+n×m+m)2).綜上,算法1的時間復雜度至多為O(n+n2+n6)=O(n6),具有多項式復雜度,這與命題6的結果一致.證畢.

4.2 重疊聯盟的成功性判別

給定一個重疊聯盟(Cl,Vl),不僅需要檢查其內部是否是有效的,即需要檢查第4.1節的情形1)–4),還需要檢查與(Cl,Vl)交叉成員相關聯的其他重疊聯盟的有效性,以及這些重疊聯盟之間是否存在資源沖突問題.為此,本文將與(Cl,Vl)相關聯的所有重疊聯盟放在一起綜合考慮.例如,OCS={({a1,a2},{t1}),({a2,a3},{t2}),({a3,a4},{t3})},對重疊聯盟{({a1,a2},{t1})來說,與之關聯的其他聯盟有({a2,a3},{t2}),而({a2,a3},{t2})又與({a3,a4},{t3})關聯.因此,需要把這3個聯盟放在一起考慮,構成一個關聯聯盟集(set of involved overlapping coalitions,SIOC).

本文首先基于算法1依次對這些重疊聯盟進行有效性檢查,只要有一個聯盟是無效的,則將該聯盟從SIOC中剔除.如果最后的SIOC=?,則這些關聯的重疊聯盟均不可能成功.如果檢查過后的SIOC?,則再基于SIOC 構造一個流網絡,如圖3所示.與圖2不同的是,這里智能體aj和任務ti之間存在一條弧,當且僅當aj和ti屬于同一個重疊聯盟,且aj對ti感興趣.也就是說,智能體aj和任務ti之間的弧是根據每個重疊聯盟來劃分的.如果ti和aj不在同一個聯盟里面,即使aj對ti感興趣,也不能構造一條弧,因為SIOC里面根本不存在這樣的協作.

圖3 基于關聯聯盟集構造的流網絡Fig.3 Flow network construction based on SIOC

命題10算法3的時間復雜度至多為O(n7).

證由命題9可知,算法3的主要耗時在于最大流計算,其時間復雜度至多為O(n6).此外,由命題1可知,SIOC中至多有m個集體任務集非空的重疊聯盟.因此,算法3 的時間復雜度至多為O(m×n6)=O(n7),也是多項式復雜度,與命題6的結果也是一致的.證畢.

4.3 OCS的成功性判別

基于算法2和算法3,本文提出一種OCS成功性判別算法,如算法4所示(算法4見表5).具體來說,對于待評估的一個OCS,首先對OCS進行遍歷,劃分出所有的孤立聯盟和關聯聯盟集.對于每個孤立聯盟,調用算法2進行判別;對于每一個關聯聯盟集,調用算法3進行判別.然后對于所有判定成功的聯盟,基于式(1)–(2)計算聯盟結構值.需要注意的是,關聯聯盟集可能不止一個.

表5 算法4 OCS成功性判別Table 5 Algorithm 4 Succcess checking of OCS

命題11算法4的時間復雜度至多為O(n7).

證在算法4中,對孤立聯盟和關聯聯盟集的判別占據了主要的計算開銷.根據命題9和命題10可知,其時間復雜度分別至多為O(n6)和O(n7).因此,算法4的時間復雜度至多為O(n7),也是多項式復雜度,與命題7的結果一致.證畢.

4.4 最優OCS生成

利用算法4,就可以基于窮舉法,通過遍歷所有可能的OCS,尋找最優重疊聯盟結構OCS?,如算法5所示(算法5見表6).

表6 算法5 最優OCS生成Table 6 Algorithm 5 Optimal OCS generation

命題12算法5 的時間復雜度至多為O(7).

證由命題11可知,算法4的時間復雜度至多為O(n7).在算法5中,要想找到最優聯盟結構OCS?,需要遍歷所有可能的重疊聯盟結構,而總共可能的重疊聯盟結構數為.因此,算法5的時間復雜度至多為O(7).又根據命題5可知,至少是指數級的,可知算法5的時間復雜度至少是指數級的,這與命題8的結果一致.證畢.

5 仿真實驗

由命題8和命題12可知,搜索最優重疊聯盟結構是多項式時間難解的,只有在智能體數和任務數很小的情況下才是可行的,為了驗證這一猜測,在本節,本文基于不同的參數來測試算法5.這些參數選自筆者前期的數據集[7,14].每組參數在Intel Xeon CPU2.2 GHz、內存32 GB、操作系統Windows Server 2012的個人計算機上獨立運行30次.

需要指出的是,當n=5,m=5時,根據命題5,可能的重疊聯盟結構總數將近225≈108.經過測試,此時保存這些重疊聯盟結構需要耗費的內存達到了10.3 GB左右,導致算法5無法正常執行.因此,在下面的測試中,以n=3,r=5,1 ≤m≤5和m=3,r=5,1 ≤n≤5 的參數設置進行仿真實驗,以驗證搜索最優重疊聯盟結構的時間消耗是否與智能體數和任務數呈指數關系.

圖4 給出了算法5 在不同n或m下占用的內存(均值,字節).由圖4可以看出,當m=3,r=5,1 ≤n≤5時,隨著智能體數的增加,算法5占用的內存緩慢增長,到n=5 時劇烈增加,增加了2.5 倍多.當n=3,r=5,1 ≤m≤5時,隨著任務數的增加,算法5占用的內存也是增長緩慢,但在n=5時陡然增加,增加了3.5倍多.上述實驗結果表明,算法5的解空間隨著n,m的增加至少是指數級的,與命題5的分析結果一致.

圖4 不同n或m下算法5占用的內存(均值,字節)Fig.4 Consumed memory (mean,in bytes) of Algorithm 5 under different numbers of agents and tasks

圖5給出了算法5在不同n或m下耗費的時間(均值,s).由圖5可以看出,當m=3,r=5,1 ≤n≤5時,隨著智能體數的增加,算法5耗費的時間緩慢增長,到n=5時劇烈增加,增加了近4 倍.當n=3,r=5,1 ≤m≤5 時,隨著任務數的增加,算法5耗費的時間也是增長緩慢,但在n=5時陡然增加,增加了8倍多.上述實驗結果表明,算法5耗費的時間隨著n,m的增加至少呈指數級增長,與命題8和命題12的分析結果一致.

圖5 不同n或m下算法5占用的時間(均值,s)Fig.5 Consumed time (mean,s) of Algorithm 5 under different numbers of agents and tasks

6 與已有模型的對比分析

在本節,本文討論幾個與本文面向任務的OSG模型類似的幾個聯盟博弈模型,并分析之間的異同.

傳統的聯盟結構生成博弈[4]旨在尋找智能體集合的一個最優劃分,以使聯盟結構值最大化.不過,每個聯盟的效用是已知的,與任務無關.因此,聯盟結構生成博弈只具有理論上的價值,難以應用實際.

技能結盟博弈[5]是不確定環境中一個聯盟協作模型,其中每個智能體都有一組完成各種任務所需的技能,每個任務都需要一組技能才能完成,但每個技能都很難量化,只能定性的表達.

在資源結盟博弈[6–7]中,每個智能體都有自己的興趣集,并且只有當智能體在聯盟的協作任務集中發現一個其感興趣的目標時,才會加入該聯盟.但是,一旦智能體加入該聯盟,它就可以向協作任務集中的所有任務提供資源,哪怕對這個任務根本不感興趣.此外,只有當協作任務集能夠激勵聯盟中的每個成員,同時聯盟擁有足夠的資源來實現協作任務集中的所有任務時,聯盟才被認為是成功的.Su等[7]約定每個智能體只能對其感興趣的任務貢獻資源,并分析了這種苛刻條件下的單個聯盟成功性條件和計算復雜性,但沒有涉及聯盟結構模型的分析.

傳統OCFGs允許每個智能體都可以參與任何聯盟,響應任何任務,只要其擁有足夠多的資源.在這種情況下,OCS是智能體集合的一個覆蓋,而不是劃分.Chalkiadakis等[15]首先探討了OCFGs的核及其穩定性問題.Zick等[8–9]提出了一種仲裁OCFGs模型,并討論了仲裁核的穩定性,還證明了仲裁OCFGs中許多決策問題的計算復雜性在很大程度上取決于每個智能體擁有的資源量和聯盟規模.Mamakos 和Chalkiadakis[16–17]提出了一種迭代OCFGs,其中每個智能體都不知道其他智能體擁有的資源量,但對其他智能體的潛在資源投資具有一個貝葉斯信念.魏冰茹等[18]考慮智能體的資源具有成本代價,基于動態規劃求解總成本最小的OCS.郭志鵬和劉驚雷[19]通過限制聯盟數和計算聯盟結構相似度設計了一種聯盟約束貪心算法.桂海霞等[20]和Zhang等[14]將進化算法與啟發式搜索相結合,可以為給定的批量任務快速生成近似最優OCS.

與上述聯盟模型,尤其是與傳統OCFGs不同的是,本文聚焦面向任務的重疊聯盟形成,規定每個智能體都只有有限的資源,且只能對任務集中的部分子任務做出響應,OCS中的每個聯盟只能承擔相互不相交的任務子集,即不允許任務重復執行.此外,每個聯盟是智能體子集和任務子集的一個二元組合,所有的智能體子集構成所有智能體的一個覆蓋,而不是傳統的劃分,所有的任務子集構成所有任務的一個劃分子集,旨在根據當前有限的智能體資源,選擇一個最佳OCS來完成給定任務集中最有利可圖的子集.

7 結論

在面向任務的環境下,如何判別聯盟結構的成功性成為一個難點.為此,本文首先構建了一種新的面向任務的最優重疊聯盟結構生成問題模型,給出了成功聯盟和成功聯盟結構的相關定義,并分析了其解空間和計算復雜性.本文還基于流網絡分別設計了相應的孤立聯盟、重疊聯盟、重疊聯盟結構成功性判別算法和最優重疊聯盟結構搜索算法,并進行了仿真實驗.結果表明,搜索最優重疊聯盟結構需要占用巨大的內存和計算開銷,難以滿足實際應用.因此,在下一步研究工作中,本文將重點研究如何基于元啟發式算法在可接受的存儲和計算開銷內快速搜索到近似最優重疊聯盟結構.