一種agen聯(lián)盟形成策略

一種agen聯(lián)盟形成策略

1中心協(xié)調(diào)管理agent在多功能系統(tǒng)中，單件設(shè)備的知識和技能是有限的。為了完成復(fù)雜的任務(wù)，提高工作效率，通常需要通過互動和合作完成各種任務(wù)的解決方案。因此，多因素合作解決方案已成為多因素網(wǎng)絡(luò)系統(tǒng)的研究領(lǐng)域。現(xiàn)有的合作機制有Smith提出的合同網(wǎng)協(xié)議(ContractNetProtocol)。當(dāng)一個Agent需要確定其協(xié)作Agent時,首先以廣播的方式向其他Agent發(fā)送任務(wù)標(biāo)書;其他Agent接收到標(biāo)書后,根據(jù)自身的資源情況決定是否要參加投標(biāo),并向要求幫助的Agent發(fā)送應(yīng)標(biāo)書,請求幫助的Agent對所有的應(yīng)標(biāo)書評估;最后確定合適的協(xié)作Agent。由于合同網(wǎng)協(xié)議需要向所有其他Agent廣播標(biāo)書,對系統(tǒng)的通信和資源提出了很高的要求。雖然一些人對合同網(wǎng)協(xié)議做了一些改進,如Genesereth和Ketchpel通過設(shè)立專門的中心協(xié)調(diào)管理Agent,負(fù)責(zé)保存和協(xié)調(diào)處理所有其他Agent的信息,可以降低廣播通信的代價,但這種中心協(xié)調(diào)方法仍然需要大量向中心管理Agent請求查找協(xié)作Agent的通信開銷。為了實現(xiàn)高效的MAS合作,最好是讓每個Agent都了解其他所有Agent的信息,不再為確定合作Agent付出額外的通信開銷。Roda和Jennings等人提出了熟人模型(AcquaintanceModel)用于獲取協(xié)作Agent的基本信息。在這種MAS體系結(jié)構(gòu)中,設(shè)計了一個自我模型表示Agent自身的信息,一個熟人模型專門用來表示其他Agent的資源和能力方面的信息,如果需要確定協(xié)作Agent,它先對各熟人的活動進行評估,再從中選擇最適合于合作的Agent。這種方法雖然降低了系統(tǒng)的通信開銷,但增加了在本地建立和維護熟人模型所帶來的系統(tǒng)資源開銷。本文通過引入一種新的社會合作機制——關(guān)系網(wǎng)模型(RelationWebModel),很好地解決了上述多Agent系統(tǒng)存在的通信開銷和資源開銷問題,并就該模型中Agent聯(lián)盟的形成策略進行了研究,通過在系統(tǒng)中保存聯(lián)盟信息,利用這些信息減少聯(lián)盟形成過程中的通信開銷和聯(lián)盟形成時間,從而提高了整個系統(tǒng)的效率。2網(wǎng)絡(luò)模型2.1社會關(guān)系網(wǎng)模型在現(xiàn)實社會中,當(dāng)一個人遇到難題時,解決的途徑一般是首先試圖憑借自己的能力去解決;當(dāng)問題得不到解決時,就會向其熟人尋求幫助,希望熟人能協(xié)助自己一同解決難題;如果問題仍然得不到解決時,由熟人再向其熟人請求幫助。這樣一直下去,直至問題最終得到解決。那么圍繞解決問題的所有這些熟人關(guān)系的總和便形成了一個所謂的社會關(guān)系網(wǎng)。由此我們想到一種新的合作機制——關(guān)系網(wǎng)模型。該模型不需要建立一個專門的中間協(xié)調(diào)Agent或熟人模型來記錄所有Agent的通信信息,有效地降低了系統(tǒng)資源的開銷;由于其采用了一種完全分布的方式來訪問和維護Agent信息,降低了集中方式訪問中間Agent和維護熟人模型帶來的代價。社會關(guān)系網(wǎng)中的每個Agent節(jié)點只需要在內(nèi)部建立并維護一個經(jīng)常訪問的熟人通信錄,該通信錄容量是有限的,Agent的選擇以及Agent之間的任務(wù)協(xié)商均是在Agent社會關(guān)系網(wǎng)上實現(xiàn)的。2.2網(wǎng)絡(luò)模型的一些基本定義(1)聯(lián)系地址平臺在此模型中,我們可定義如下:Agenta:Agent(Name,Address,Ability,Contact_List)其中,Name(a)表示Agenta的名字;Address(a)表示Agenta的聯(lián)系地址,可將其表示為常見的Name.IP_Address.Port;Ability(a)主要用來描述Agenta的問題求解能力,它可表示為一個能力集合,即Ability(a)={ba1a1,ba2a2,…,bakak},其中集合中的元素baiai是Agenta能夠完成某一特定任務(wù)的量化能力。為了簡化問題,我們用一個固定的值表示Ability,并規(guī)定該值越大,Agent求解問題的能力越強,反之越弱。Contact_List(a)表示Agenta的通信錄,即Agenta的所有熟人通信信息的列表。系統(tǒng)中的所有Agent構(gòu)成一個集合,將其表示為A∶A={a1,a2,…,an},其中ai表示單個的Agent。(2)a提取交往記錄,即記錄每條通信記錄,即記錄每條通信記錄,即記錄每條通信記錄;熟人通信錄中存放的是該Agent的所有熟人的集合,我們也將其稱為熟人集,具體定義為Contact_List(a)=<L1,L2,…,Ln>,列表中的每個元素稱為一條通信記錄,記錄每個熟人的聯(lián)系信息,其中每條通信記錄可表示為Li=<Name,Ability,Address,T>其中,Name(i),Ability(i),Address(i),Tai分別表示Agenta的熟人i的名字、能力、聯(lián)系地址、可信任度;T定義為在一段時間內(nèi)Agent之間相互成功合作的頻度,T的值越大,說明該熟人的可信任度越大,與之越熟悉,它們合作成功的可能性也越大。(3)acqb,b給出Agenta和b,如果b∈Contact_List(a).Name,則我們說a認(rèn)識b,記為Acq(a,b)。顯然Agent總是認(rèn)識它自身的,即有Acq(a,a)。認(rèn)識關(guān)系是自反的、非對稱的和非傳遞的,即如果Acq(a,b),不一定有Acq(b,a);由Acq(a,b)及Acq(b,c)成立,我們不能推出Acq(a,c)。(4)相關(guān)的原理a,b我們將Agenta與b具有簡單的熟人關(guān)系A(chǔ)R(a,b)定義為AR(a,b)≡defAcq(a,b)∧Acq(b,a),我們稱滿足AR(a,b)的Agenta和Agentb互為熟人。3聯(lián)合組織機制3.1任務(wù)求解小組的形成在多Agent系統(tǒng)中,由于單個的Agent無法獨立完成某一任務(wù)或者通過多個Agent共同協(xié)作來提高求解的效率,各Agent之間會通過一定的協(xié)商形成一個任務(wù)求解小組共同承擔(dān)該任務(wù),我們將這個任務(wù)求解小組稱之為聯(lián)盟。下面我們介紹一些聯(lián)盟的基本概念。聯(lián)盟的形成和能力聯(lián)盟是一組合作的、共同完成某一任務(wù)并共享任務(wù)收益的Agent集合:C={ai,aj,…,ak}。形成聯(lián)盟時,總是試圖使該聯(lián)盟的聯(lián)盟值(后面解釋)盡可能大,以保證在較小的開銷下獲得盡可能大的效用。聯(lián)盟形成時不需要中央決策,形成聯(lián)盟時的通信開銷和計算工作量僅限于聯(lián)盟參與者。聯(lián)盟C的能力為Bc={bc1c1,bc2c2,…,bcncn},等于其所有成員能力分量之和。顯然聯(lián)盟C能夠承攬任務(wù)tk的必要條件是?i(0≤i≤n)bkiki≤bcici,式中bkiki表示求解任務(wù)tk所需的能力分量。聯(lián)盟體積調(diào)整|C|是指聯(lián)盟中包含Agent的個數(shù),系統(tǒng)中可以有多個聯(lián)盟,但其必須滿足c1∪c2∪ck?A。任務(wù)的經(jīng)濟效益一個聯(lián)盟C的聯(lián)盟值Value是聯(lián)盟成員通過集體行動完成某一特定任務(wù)而得到的,它可以簡單地表示如下:Value(C)=Profit(ti)/Cost(ti)其中,Profit(ti)指聯(lián)盟C完成任務(wù)ti所獲得的收益,聯(lián)盟代價Cost(ti)是指聯(lián)盟C的成員通過聯(lián)盟活動完成任務(wù)ti的開銷總和。3.2修改人際通信記錄的規(guī)則一次成功的合作會引起所有聯(lián)盟成員對其熟人通信錄進行修改,下面給出具體的修改規(guī)則。修改聯(lián)盟成員的可信任度我們用Tij表示Agentai對aj的可信任度,也就是ai和aj之間的熟悉程度。在一個成功聯(lián)盟C內(nèi)部,所有聯(lián)盟成員均會修改其熟人的可信任度,即Ifai與aj合作成功(ai∈C∧aj∈C)ThenTij=min(Tij+λ,1)其中,λ∈(0,1)稱為合作因子,其值隨著Agent熟人集的大小進行調(diào)整。gent與聯(lián)盟成員的可信任度一次成功的聯(lián)盟將會引起聯(lián)盟成員檢查其熟人集,那些沒有參加合作的熟人Agent與聯(lián)盟成員的可信任度T將降低。Ifai與aj未能進行合作(ai∈C∧aj?C)ThenTij=max(Tij-μ,0)其中,μ∈(0,1)稱為淡忘因子,其值也隨著Agent熟人集的大小進行調(diào)整。gent教學(xué)gent教學(xué)檢查Agent之間的可信任度,如果Tij大于閾值Tk,則Agentai應(yīng)在其熟人通信錄中添加Agentaj以及aj的能力分量,即IfTij≥TkThenContact_List(ai)←(Contact_List(ai)∪aj)被救贖aj一次成功的聯(lián)盟會引起聯(lián)盟成員檢查其熟人集,當(dāng)可信任度下降到一定程度(<Tk)的熟人就會從熟人集中退出,變成普通的認(rèn)識關(guān)系,即IfTij≤TkThenContact_List(ai)←(Contact_List(ai)-aj)退出規(guī)則是單向的,也就是說即使ai將aj看成是普通的認(rèn)識關(guān)系時,而aj仍然能將ai當(dāng)成其熟人。線上的舉證權(quán)在一個成功的聯(lián)盟內(nèi)部,如果Agentai,aj均是Agentak的熟人,但ai,aj它們本身并不是熟人,在這種情況下,我們允許Agentak將其好友ai(aj)推薦給它的另一個好友aj(ai),這樣使得ai和aj也成為好友,即IfAR(ai,ak)∧AR(ak,aj)ThenAR(ai,aj)這種舉薦規(guī)則有助于我們形成更加有效的聯(lián)盟。擴張規(guī)則采用了擴張規(guī)則當(dāng)一個Agent的熟人集小于我們規(guī)定的某一極限時,它可以采用擴張規(guī)則將與其是普通認(rèn)識關(guān)系的Agent強行變成熟人,以保證能形成成功的聯(lián)盟完成任務(wù)。由于它們不處于同一聯(lián)盟內(nèi),所以此過程需要消耗一些額外的通信開銷來完成。4基于聯(lián)盟最終的任務(wù)系統(tǒng)基于關(guān)系網(wǎng)模型的Agent聯(lián)盟形成策略的基本思想是:讓系統(tǒng)中所有的Agent維護其通信錄中的熟人集,當(dāng)有新任務(wù)下達(dá)需要形成聯(lián)盟時,各Agent通過互相通信交換其熟人集,然后基于這些熟人形成聯(lián)盟候選集。由于候選集反映了它們共同承擔(dān)任務(wù)的合作關(guān)系,因而該集合小于系統(tǒng)中所有Agent構(gòu)成的集合,再以這些候選集為基礎(chǔ)形成完成任務(wù)的真正聯(lián)盟。在整個過程中系統(tǒng)能保存聯(lián)盟信息,可以為下一次聯(lián)盟的形成奠定基礎(chǔ),因而能大大減少聯(lián)盟形成過程中的系統(tǒng)開銷,提高了聯(lián)盟的效率和質(zhì)量。Agent互相交互形成可能的聯(lián)盟以及完成任務(wù)的具體過程如圖1所示。(1)聯(lián)盟總能力的形成①系統(tǒng)初期,假設(shè)所有的Agent之間都是熟人,則每個Agent的熟人集包含其他所有的Agent,即Contact_List(ai)=<L1,L2,…,Ln>,因而其可能形成的聯(lián)盟候選集數(shù)目非常大,表示為Ν=n∑i=1Cin=2n-1(nN=∑i=1nCin=2n?1(n為Agent數(shù)),同時每個聯(lián)盟可以通過獲取其成員的能力分量來形成聯(lián)盟的總能力。在聯(lián)盟形成過程中,由于Agent要窮盡所有的聯(lián)盟,所以它要與系統(tǒng)中所有的Agent進行通信并互相交換它們的能力分量,這存在著巨大的通信開銷。②系統(tǒng)經(jīng)過一段時間的運行后,由于熟人通信錄修改規(guī)則的應(yīng)用,從而使其熟人集逐步減少并趨于穩(wěn)定(聯(lián)盟在形成過程中熟人不斷地加入和離開,熟人集一直是動態(tài)變化的,這里的穩(wěn)定只是相對的),即Contact_List(ai)=<Lj,Lk,…,Ln>,其可能形成的聯(lián)盟候選集也大大減小,理論最大值＜nk+1∑i=1Cik+1=n(2k+1-1)(k為熟人集中包含Agent的最大數(shù))。由于熟人集中保存了Agent熟人的能力分量,從而使形成聯(lián)盟過程的通信開銷和計算量大大降低,系統(tǒng)效率得以提高。(2)能力分量bki①將下達(dá)的任務(wù)分解成若干個子任務(wù),即T=(t1,t2,…,tk)。②比較完成該任務(wù)所需的能力分量bki與候選集中所有可能聯(lián)盟的總能力bci,找出所有滿足條件的聯(lián)盟C,并計算其聯(lián)盟值。③如果沒有滿足條件的聯(lián)盟,則等待新的聯(lián)盟形成。(3)任務(wù)2—篩選恰當(dāng)?shù)穆?lián)盟,完成下達(dá)的任務(wù)。①從所有滿足條件的聯(lián)盟中選擇聯(lián)盟值最大的聯(lián)盟。②將任務(wù)T委托給該聯(lián)盟,則該聯(lián)盟中的Agent會自動合作完成該任務(wù)。③從任務(wù)集中刪除任務(wù)T,同時刪除所有含有該聯(lián)盟中的Agentai的聯(lián)盟。(4)聯(lián)盟能力任務(wù)完成以后,就會引起所有聯(lián)盟成員檢查其熟人