基于關系網模型的Ａｇｅｎｔ聯盟形成策略

摘 要：從研究Agent社會合作機制入手，引入了一個表示Agent之間聯系的社會關系網模型，并以該模型中的熟人集為基礎提出了一種Agent聯盟形成策略。該策略能有效地減少系統中的聯盟數，避免聯盟形成過程中的盲目性，節省協商時間并提高協商效率。

關鍵詞：多Agent系統； 關系網模型； 聯盟； 熟人

中圖法分類號：TP311．5 文獻標識碼：A 文章編號：1001-3695(2006)10-0041-03

Strategy to Form Agent Coalition Based on Relation Web Model

WEI Wei， LIU Hong

（Dept.of Computer， Shandong Normal University， Jinan Shandong 250014， China）

Abstract:From social cooperation mechanism， this paper introduces a relation Web model to represent the relationships among Agents， and proposes a strategy to form an Agent coalition based on acquaintance set of this model.The strategy can reduce the number of coalition effectively，avoid blindness in coalition formation and improve the efficiency of negotiation.

Key words:MultiAgent System(MAS); Relation Web Model; Coalition; Acquaintance

1 引言

在多Agent系統中，單個Agent的知識和能力是有限的，為了完成復雜的任務或提高工作效率，常常需要多個Agent通過交互和協同共同完成任務求解，因此多Agent合作求解成為MultiAgent系統的一個重要研究領域。

現有的合作機制有Smith提出的合同網協議（Contract Net Protocol）[1]。當一個Agent需要確定其協作Agent時，首先以廣播的方式向其他Agent發送任務標書；其他Agent接收到標書后，根據自身的資源情況決定是否要參加投標，并向要求幫助的Agent發送應標書，請求幫助的Agent對所有的應標書評估；最后確定合適的協作Agent。由于合同網協議需要向所有其他Agent廣播標書，對系統的通信和資源提出了很高的要求。雖然一些人對合同網協議做了一些改進，如Genesereth和Ketchpel[2]通過設立專門的中心協調管理Agent，負責保存和協調處理所有其他Agent的信息，可以降低廣播通信的代價，但這種中心協調方法仍然需要大量向中心管理Agent請求查找協作Agent的通信開銷。

為了實現高效的MAS合作，最好是讓每個Agent都了解其他所有Agent的信息，不再為確定合作Agent付出額外的通信開銷。Roda和Jennings等人提出了熟人模型（Acquaintance Model）[3，4]用于獲取協作Agent的基本信息。在這種MAS體系結構中，設計了一個自我模型表示Agent自身的信息，一個熟人模型專門用來表示其他Agent的資源和能力方面的信息，如果需要確定協作Agent，它先對各熟人的活動進行評估，再從中選擇最適合于合作的Agent。這種方法雖然降低了系統的通信開銷，但增加了在本地建立和維護熟人模型所帶來的系統資源開銷。

本文通過引入一種新的社會合作機制——關系網模型(Relation Web Model)[5]，很好地解決了上述多Agent系統存在的通信開銷和資源開銷問題，并就該模型中Agent聯盟的形成策略進行了研究，通過在系統中保存聯盟信息，利用這些信息減少聯盟形成過程中的通信開銷和聯盟形成時間，從而提高了整個系統的效率。

2 關系網模型

2．1 關系網模型的提出

在現實社會中，當一個人遇到難題時，解決的途徑一般是首先試圖憑借自己的能力去解決；當問題得不到解決時，就會向其熟人尋求幫助，希望熟人能協助自己一同解決難題；如果問題仍然得不到解決時，由熟人再向其熟人請求幫助。這樣一直下去，直至問題最終得到解決。那么圍繞解決問題的所有這些熟人關系的總和便形成了一個所謂的社會關系網。

由此我們想到一種新的合作機制——關系網模型。該模型不需要建立一個專門的中間協調Agent或熟人模型來記錄所有Agent的通信信息，有效地降低了系統資源的開銷；由于其采用了一種完全分布的方式來訪問和維護Agent信息，降低了集中方式訪問中間Agent和維護熟人模型帶來的代價。社會關系網中的每個Agent節點只需要在內部建立并維護一個經常訪問的熟人通信錄，該通信錄容量是有限的，Agent的選擇以及Agent之間的任務協商均是在Agent社會關系網上實現的。

2．2 關系網模型的幾個基本定義

（1）Agent的定義及其能力描述

在此模型中，我們可定義如下：

Agent a:Agent(Name，Address，Ability，Contact_List)

其中，Name(a)表示Agent a的名字；Address(a)表示Agent a的聯系地址，可將其表示為常見的Name.IP_Address.Port；Ability(a)主要用來描述Agent a的問題求解能力，它可表示為一個能力集合，即Ability(a)={ba1，ba2，…，bak}，其中集合中的元素bai是Agent a能夠完成某一特定任務的量化能力。為了簡化問題，我們用一個固定的值表示Ability，并規定該值越大，Agent求解問題的能力越強，反之越弱。Contact_List(a)表示Agent a的通信錄，即Agent a的所有熟人通信信息的列表。

系統中的所有Agent構成一個集合，將其表示為A∶A={a1，a2，…，an}，其中ai表示單個的Agent。

(2)熟人通信錄的定義

熟人通信錄中存放的是該Agent的所有熟人的集合，我們也將其稱為熟人集，具體定義為Contact_List(a)=，列表中的每個元素稱為一條通信記錄，記錄每個熟人的聯系信息，其中每條通信記錄可表示為

Li=

其中，Name(i)，Ability(i)，Address(i)，Tai分別表示Agent a的熟人i的名字、能力、聯系地址、可信任度；T定義為在一段時間內Agent之間相互成功合作的頻度，T的值越大，說明該熟人的可信任度越大，與之越熟悉，它們合作成功的可能性也越大。

(3)認識關系的定義

給出Agent a和b，如果b∈Contact_List(a).Name，則我們說a認識b，記為Acq(a，b)。顯然Agent總是認識它自身的，即有Acq(a，a)。認識關系是自反的、非對稱的和非傳遞的，即如果Acq(a，b)，不一定有Acq(b，a)；由Acq(a，b)及Acq(b，c)成立，我們不能推出Acq(a，c)。

(4)熟人關系的定義

我們將Agent a與b具有簡單的熟人關系AR(a，b)定義為AR(a，b)≡def Acq(a，b)∧Acq(b，a)，我們稱滿足AR(a，b)的Agent a和Agent b互為熟人。

3 聯盟機制

3．1 聯盟機制的基本概念

在多Agent系統中，由于單個的Agent無法獨立完成某一任務或者通過多個Agent共同協作來提高求解的效率，各Agent之間會通過一定的協商形成一個任務求解小組共同承擔該任務，我們將這個任務求解小組稱之為聯盟。下面我們介紹一些聯盟的基本概念。

定義1 聯盟及其能力描述

聯盟是一組合作的、共同完成某一任務并共享任務收益的Agent集合：C={ai，aj，…，ak}。形成聯盟時，總是試圖使該聯盟的聯盟值(后面解釋)盡可能大，以保證在較小的開銷下獲得盡可能大的效用[6]。聯盟形成時不需要中央決策，形成聯盟時的通信開銷和計算工作量僅限于聯盟參與者。

聯盟C的能力為Bc={bc1，bc2，…，bcn}，等于其所有成員能力分量之和。顯然聯盟C能夠承攬任務tk的必要條件是i(0≤i≤n)bki≤bci，式中bki表示求解任務tk所需的能力分量。

定義2 聯盟體積

|C|是指聯盟中包含Agent的個數，系統中可以有多個聯盟，但其必須滿足c1∪c2∪ckA。

定義3 聯盟值

一個聯盟C的聯盟值Value是聯盟成員通過集體行動完成某一特定任務而得到的，它可以簡單地表示如下：

Value(C)=Profit(ti)/Cost(ti)

其中，Profit(ti)指聯盟C完成任務ti所獲得的收益，聯盟代價Cost(ti)是指聯盟C的成員通過聯盟活動完成任務ti的開銷總和。

3．2 熟人通信錄修改規則

一次成功的合作會引起所有聯盟成員對其熟人通信錄進行修改，下面給出具體的修改規則。

規則1 可信任度增強規則

我們用Tij表示Agent ai對aj的可信任度，也就是ai和aj之間的熟悉程度。在一個成功聯盟C內部，所有聯盟成員均會修改其熟人的可信任度，即

If ai與aj合作成功(ai∈C∧aj∈C) Then Tij=min(Tij+λ，1)

其中，λ∈(0，1)稱為合作因子，其值隨著Agent熟人集的大小進行調整。

規則2 可信任度減弱規則

一次成功的聯盟將會引起聯盟成員檢查其熟人集，那些沒有參加合作的熟人Agent與聯盟成員的可信任度T將降低。

If ai與aj未能進行合作(ai∈C∧ajC) Then Tij=max(Tij-μ，0)

其中， μ∈(0，1)稱為淡忘因子，其值也隨著Agent熟人集的大小進行調整。

規則3 熟人進入規則

檢查Agent之間的可信任度，如果Tij大于閾值Tk，則Agent ai應在其熟人通信錄中添加Agent aj以及aj的能力分量，即

If Tij≥Tk Then Contact_List(ai)←(Contact_List(ai)∪aj)

規則4 熟人退出規則

一次成功的聯盟會引起聯盟成員檢查其熟人集，當可信任度下降到一定程度（＜Tk）的熟人就會從熟人集中退出，變成普通的認識關系，即

If Tij≤Tk Then Contact_List(ai)←(Contact_List(ai)-aj)

退出規則是單向的，也就是說即使ai將aj看成是普通的認識關系時，而aj仍然能將ai當成其熟人。

規則5 熟人舉薦規則

在一個成功的聯盟內部，如果Agent ai，aj均是Agent ak的熟人，但ai，aj它們本身并不是熟人，在這種情況下，我們允許Agent ak將其好友ai(aj)推薦給它的另一個好友aj(ai)，這樣使得ai和aj也成為好友，即

If AR(ai，ak)∧AR(ak，aj) Then AR(ai，aj)

這種舉薦規則有助于我們形成更加有效的聯盟。

規則6 熟人擴張規則

當一個Agent的熟人集小于我們規定的某一極限時，它可以采用擴張規則將與其是普通認識關系的Agent強行變成熟人，以保證能形成成功的聯盟完成任務。由于它們不處于同一聯盟內，所以此過程需要消耗一些額外的通信開銷來完成。

4 基于關系網模型的Agent聯盟形成策略

基于關系網模型的Agent聯盟形成策略的基本思想是：讓系統中所有的Agent維護其通信錄中的熟人集，當有新任務下達需要形成聯盟時，各Agent通過互相通信交換其熟人集，然后基于這些熟人形成聯盟候選集。由于候選集反映了它們共同承擔任務的合作關系，因而該集合小于系統中所有Agent構成的集合，再以這些候選集為基礎形成完成任務的真正聯盟。在整個過程中系統能保存聯盟信息，可以為下一次聯盟的形成奠定基礎，因而能大大減少聯盟形成過程中的系統開銷，提高了聯盟的效率和質量。Agent互相交互形成可能的聯盟以及完成任務的具體過程如圖1所示。

（1）初始化熟人集，形成所有可能的聯盟集。

①系統初期，假設所有的Agent之間都是熟人，則每個Agent的熟人集包含其他所有的Agent，即Contact_List(ai)=，因而其可能形成的聯盟候選集數目非常大，表示為N=∑ni=1Cin=2n-1（n為Agent數），同時每個聯盟可以通過獲取其成員的能力分量來形成聯盟的總能力。在聯盟形成過程中，由于Agent要窮盡所有的聯盟，所以它要與系統中所有的Agent進行通信并互相交換它們的能力分量，這存在著巨大的通信開銷。

②系統經過一段時間的運行后，由于熟人通信錄修改規則的應用，從而使其熟人集逐步減少并趨于穩定（聯盟在形成過程中熟人不斷地加入和離開，熟人集一直是動態變化的，這里的穩定只是相對的），即Contact_List(ai)=，其可能形成的聯盟候選集也大大減小，理論最大值＜n∑k+1i=1Cik+1=n(2k+1-1)（k為熟人集中包含Agent的最大數）。由于熟人集中保存了Agent熟人的能力分量，從而使形成聯盟過程的通信開銷和計算量大大降低，系統效率得以提高。

（2）接收任務。

①將下達的任務分解成若干個子任務，即T=(t1，t2，…，tk)。

②比較完成該任務所需的能力分量bki與候選集中所有可能聯盟的總能力bci，找出所有滿足條件的聯盟C，并計算其聯盟值。

③如果沒有滿足條件的聯盟，則等待新的聯盟形成。

（3）篩選恰當的聯盟，完成下達的任務。

①從所有滿足條件的聯盟中選擇聯盟值最大的聯盟。

②將任務T委托給該聯盟，則該聯盟中的Agent會自動合作完成該任務。

③從任務集中刪除任務T，同時刪除所有含有該聯盟中的Agent ai的聯盟。

（4）修改更新。

任務完成以后，就會引起所有聯盟成員檢查其熟人通信錄。

①根據前面定義的修改規則對Agent之間的可信任度、聯盟能力以及聯盟值等進行一些修改，并保存已有的聯盟信息。

②更新熟人集，重新形成所有可能的聯盟集。

（5）如果還有新任務，轉而執行步驟（2），否則結束。

5 結束語

本文引入了一種新的合作機制——關系網模型來表示Agent之間的聯系，并以該模型為基礎提出了一種新的聯盟形成策略。該策略適用于動態、開放的環境，無中心控制，能有效地減少聯盟形成過程中的通信開銷和計算量。下一步我們還有許多工作要做，如合作因子、淡忘因子的確定、閾值的確定、各Agent之間的交互和協商等。

參考文獻：

[1]Smith R G. The Contact Net Protocol:Highlevel Communication and Control in a Distributed Problem Solver[J].IEEE Trans.on Computer， 1980，C-29(12):11041113.

[2]M Inverno， M Luck. A Formal View of Social Dependence Networks[C]. Proc.of the 1st Australian Workshop on DAI， Berlin: Springer Verlag，1996.115-129.

[3]Y Lashkari， M Metral， P Maes. Collaborative Interface Agents[C]. Proc.of the 12th National Conf.on Artificial Intelligence， Seattle: AA AI Press， 1994.444-449.

[4]C Roda， N R Jennings， E H Mamdani. The Impact of Heterogeneity on Cooperating Agents[C].Anaheim:The AAAI Workshop on Cooperation among Heterogeneous Intelligent Systems， 1991.

[5]陳剛，陸汝鈐.關系網模型——基于社會合作機制的多Agent協作組織方法[J].計算機研究與發展，2003，40(1):108109.

[6]蘭少華，葉東海，吳慧中.一種Agent任務求解聯盟形成策略[J].小型微型計算機系統，2004，25(5):941-942.

作者簡介：

魏巍（1981-），女，山西大同人，碩士研究生，主要研究方向為人工智能、多Agent系統；劉弘（1955-），女，山東濟南人，教授，博導，主要研究方向為CSCW、多Agent系統及機器學習。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文