桂海霞,趙邦磊,張國富,蘇兆品,蔣建國

(1.安徽理工大學(xué)經(jīng)濟與管理學(xué)院,安徽 淮南 232001;2.合肥工業(yè)大學(xué)計算機與信息學(xué)院,安徽 合肥 230009)

1 引言

在多Agent 系統(tǒng)(multi-agent systems,MAS)[1]中,當(dāng)單個Agent 的資源有限無法獨自完成某個任務(wù)時,可以聯(lián)合多個Agent 組成團隊共同完成任務(wù),這樣的團隊即為聯(lián)盟[2].作為MAS 中一種主要的協(xié)作方式,聯(lián)盟形成已廣泛應(yīng)用于電子商務(wù)[3]、研發(fā)合作[4]、多機器人協(xié)作[5]、傳感器網(wǎng)絡(luò)[6]、電力傳輸[7]、虛擬企業(yè)[8]和動態(tài)供應(yīng)鏈[9]等諸多領(lǐng)域.

聯(lián)盟形成是聯(lián)盟進行一切活動的基礎(chǔ),主要包含三個方面的研究內(nèi)容:聯(lián)盟值計算[10,11]、聯(lián)盟結(jié)構(gòu)生成[12,13]和效用分配[14,15].其中效用分配是聯(lián)盟形成的關(guān)鍵,直接影響了聯(lián)盟的穩(wěn)定性和Agent 執(zhí)行任務(wù)的積極性.效用分配的不合理會導(dǎo)致Agent 提前退出聯(lián)盟,從而可能導(dǎo)致任務(wù)執(zhí)行失敗.因此,在效用分配中,一般要求,每個Agent 獲得的效用應(yīng)該和它自身的貢獻相匹配.此外,新Agent 請求加入聯(lián)盟時要保證不能損害已有Agent 成員的原來的預(yù)期效用,即滿足效用非減.

雖然目前效用分配研究已經(jīng)取得了一些研究成果,但大都局限于非重疊聯(lián)盟[16],即要求每個Agent 在任意時刻只能參與一個任務(wù),造成Agent 資源的極大浪費.在重疊聯(lián)盟形成(overlapping coalition formation,OCF)[17]中,一個Agent 可以同時參與多個聯(lián)盟承擔(dān)多個任務(wù).這種重疊協(xié)作模式既提升了MAS 的資源利用率,又提升了任務(wù)的執(zhí)行效率.然而,如何在多個聯(lián)盟之間分配效用,尤其如何給參與多個任務(wù)的Agent 成員劃分效用是面臨的一個難點問題.已有效用分配策略效率低下,重疊聯(lián)盟形成困難,且新Agent 加入聯(lián)盟時往往難以滿足效用非減.

Rosenschein[18]最早將博弈論引入多Agent 系統(tǒng),以效用函數(shù)最大化為目標(biāo)進行了求解.在現(xiàn)實生活中動態(tài)復(fù)雜的環(huán)境下,隨機因素的增加使合作變得更復(fù)雜,主題合作缺乏納什均衡效率,靜態(tài)合作博弈就逐漸演變成動態(tài)合作博弈[19-22].在合作博弈的過程中,大部分效用劃分方案是根據(jù)夏普利(Shapley)值[23]求解的,Shapley 值體現(xiàn)了各Agent 對聯(lián)盟總目標(biāo)的貢獻程度,但是計算方法太過復(fù)雜,求解難度與聯(lián)盟形成的Agent 個數(shù)成指數(shù)倍增長.雖然一些學(xué)者對Shapley 值進行了改進[24-26],但是也難以跳脫階乘方法的局限性.

為了順應(yīng)聯(lián)盟靈活性的特點,一些學(xué)者設(shè)計了簡單有效的聯(lián)盟效益分配方式,羅翊等[27]設(shè)計了效用非減性分配原則,這種聯(lián)盟形成策略優(yōu)于Shapley 值方法,因為過分追求計算簡單而忽視了Agent 對聯(lián)盟貢獻的差異性,并且打擊了能給聯(lián)盟帶來額外效用的新Agent 加入的積極性.為了體現(xiàn)聯(lián)盟貢獻的差異性,夏娜等[28]采用了一種利益均衡的聯(lián)盟形成策略,提高了對額外效用分配的合理性,也在一定程度上維護了后加入聯(lián)盟Agent 的利益.蔣建國等[29]提出了一種基于能力向量發(fā)揮率和拍賣的效用行為分配原則,也體現(xiàn)出了聯(lián)盟貢獻差異,但是以上兩種效用分配策略都屬于非重疊聯(lián)盟機制的范疇.針對重疊聯(lián)盟效用劃分,張國富等[30]提出了討價還價的效用分配策略,但是該方法不能處理多任務(wù)并發(fā)的情形,只能對多聯(lián)盟的效用劃分依次串行進行.桂海霞等[31]基于能者多勞的思想對重疊聯(lián)盟的效用實現(xiàn)了并行分派,但是采取按比例分配效用方式缺乏靈活性,不利于重疊聯(lián)盟的形成.

通過以上研究發(fā)現(xiàn)聯(lián)盟效用分配策略主要存在以下問題:平均分配策略[27,28]、基于能力大小分配策略[29]等都沒有反映出Agent 之間對聯(lián)盟貢獻的差異性,不利于聯(lián)盟的穩(wěn)定性; 串行的重疊聯(lián)盟分配策略[30]導(dǎo)致效用分配效率低下,與高效快速的聯(lián)盟理念相悖;按比例分配效用分配策略[31]則難以滿足效用非減原則,不利于聯(lián)盟的形成等.為此,本文在總結(jié)和分析前人工作的基礎(chǔ)上,根據(jù)每個Agent 擁有的資源狀況和任務(wù)的實際需求,提出了一種面向任務(wù)優(yōu)先滿足和績效獎勵的重疊聯(lián)盟效用分配策略,并分別討論了效用分配應(yīng)用的兩種情形:1)聯(lián)盟形成初始;2)現(xiàn)有聯(lián)盟完成任務(wù)新成員加入時.針對情形1),按照現(xiàn)有效用分配策略,在聯(lián)盟形成時,各成員根據(jù)自身資源量去執(zhí)行各個任務(wù),當(dāng)任務(wù)需求量高于成員資源擁有量時則導(dǎo)致任務(wù)失敗.因此首先提出一種優(yōu)先滿足任務(wù)需求的任務(wù)分派方法,保證聯(lián)盟任務(wù)的順利完成,同時提出一種動態(tài)調(diào)整策略,當(dāng)Agent 成員之間資源出現(xiàn)沖突時進行利益均衡調(diào)整,保證聯(lián)盟平穩(wěn)運行.情形2),在超加環(huán)境中[32],新Agent 的加入會給聯(lián)盟帶來額外效用.為此,提出一種績效獎勵的方法,在面對原有重疊聯(lián)盟完成一定任務(wù)新Agent 請求加入的情形時,設(shè)置績效獎勵系數(shù),使原有Agent 可獲得更高的效用分配,滿足效益非減原則,新加入的Agent 也有利可圖,更易于聯(lián)盟的形成,規(guī)避現(xiàn)有重疊聯(lián)盟效用分配策略的缺陷.最后通過實例與現(xiàn)有效用分配策略進行了對比分析,證明了此方法的有效性,有效解決重疊聯(lián)盟并發(fā)多任務(wù)的資源沖突問題,提高求解效率,并體現(xiàn)了聯(lián)盟形成的穩(wěn)定性、時效性和動態(tài)性等特征.

2 重疊聯(lián)盟描述

其中式(6)表示重疊聯(lián)盟問題有可行解的條件,即所有Agent 能力之和不能低于所有任務(wù)需要的能力之和;式(7)任務(wù)分派量等于聯(lián)盟成員實際資源貢獻量的條件,即表示任務(wù)每種資源需求量等于聯(lián)盟成員每種資源實際貢獻量之和;式(8)表示聯(lián)盟成員避免資源沖突的條件,即聯(lián)盟中每個Agent 每種資源實際貢獻量不能超過自身擁有量.

3 重疊聯(lián)盟效用分配策略

3.1 效用分配原則

合法的MAS 中每個Agent 成員有自己的任務(wù),完成相應(yīng)任務(wù)獲得一定的效用.Agent 之間相互協(xié)作可以減少自己的工作量,以此獲得額外效用.單個Agent 資源向量有限,為獲得更多的額外效用則會選擇和其它Agent 結(jié)成聯(lián)盟.聯(lián)盟合作的基礎(chǔ)是Agent 自身擁有的資源總量,而聯(lián)盟穩(wěn)定長久則需要制定合理的效用劃分策略,聯(lián)盟形成具有一定的機制要求,根據(jù)Rosenschein[18]提出的相關(guān)理論,聯(lián)盟效用分配應(yīng)遵循以下原則:

1)穩(wěn)定性.聯(lián)盟形成后,總效用確定,不受成員退出影響.當(dāng)增加某些成員的效用時相應(yīng)成員效用必會減少,聯(lián)盟內(nèi)部部分成員重組也不會獲得更大的收益.

2)有效性.Agent 成員共享聯(lián)盟完成任務(wù)所獲總效用v(Cj)代表任務(wù)總效用,vc(ai)代表成員ai從聯(lián)盟中所應(yīng)分配的效用,所有成員的效用相加等于聯(lián)盟總效用.

3)簡單性.聯(lián)盟交互通信,開銷P(Cj)應(yīng)較小.

4)時效性.效用分配與加入聯(lián)盟的時間有關(guān),加入聯(lián)盟越早,在聯(lián)盟待的時間越久,分配效用越高.5)動態(tài)性.聯(lián)盟形成是根據(jù)Agent 本身資源和任務(wù)需求動態(tài)博弈構(gòu)建的,而任務(wù)的分派量就決定了每個Agent 獲得的效用.

3.2 任務(wù)分派

重疊聯(lián)盟中每個Agent 獲得的效用取決于其任務(wù)工作量分派情況,某個Agent 分派的任務(wù)越多則其獲得的效用也越多.因此,所謂的績效獎勵是給予完成任務(wù)的原有成員,在完成任務(wù)過程中會給它們分配額外的工作量.這樣越早加入聯(lián)盟的成員就越有利,這種分配策略更能體現(xiàn)效用分配的時效性和動態(tài)性特征.

已有的任務(wù)分派策略以聯(lián)盟成員Agent 資源量為基礎(chǔ)進行劃分,這樣容易出現(xiàn)聯(lián)盟成員資源貢獻量大于或者小于任務(wù)所需資源量的情況,因此本文提出一種優(yōu)先滿足任務(wù)需求的任務(wù)分派方法,即聯(lián)盟所有成員貢獻出與任務(wù)需求相等的資源量,這樣各Agent 成員貢獻的資源量可能大于自身擁有的資源量,就會出現(xiàn)資源沖突,就需要根據(jù)相應(yīng)的調(diào)整策略進行調(diào)整確定實際資源貢獻量.聯(lián)盟形成中應(yīng)避免單個Agent 獨攬任務(wù),也應(yīng)避免在一次任務(wù)中用完某個Agent 全部資源,使它有機會參與其余聯(lián)盟任務(wù).當(dāng)形成的聯(lián)盟完成任務(wù)T={t1,t2,...,tn}時,按照任務(wù)優(yōu)先級實現(xiàn)Agent 成員的資源分配,具體過程如下:

步驟1 如果T=?,結(jié)束;否則按照優(yōu)先級選取tj.

步驟2 根據(jù)任務(wù)T={t1,t2,...,tn}對聯(lián)盟Cj中成員ai進行任務(wù)分派.

3.3 效用分配

重疊聯(lián)盟Cj中成員ai效用分配的多少取決于完成任務(wù)tj所貢獻的資源量,r種資源量的價值是不同的,價值通過價格得以體現(xiàn),因此需要對相關(guān)概念描述如下:

1)資源價值

績效獎勵策略可以促進Agent 積極、及時地參加重疊聯(lián)盟,提高聯(lián)盟生成速度,且越早加入聯(lián)盟,獲得的效用分配也越高,具有較好的時效性.一方面,原有聯(lián)盟成員因為資源優(yōu)勢在整體效用分配過程中占據(jù)主動,并能滿足效用非減條件選擇繼續(xù)待在聯(lián)盟完成任務(wù);另一方面,后加入的Agent 因為原有Agent 完成任務(wù)消耗了一定資源,也能在加入重疊聯(lián)盟時成為主體地位,通過協(xié)商獲得令自己滿意的效用,不會退出聯(lián)盟去創(chuàng)建新的聯(lián)盟,該策略的協(xié)商一致穩(wěn)定性明顯優(yōu)于其他分配策略的強制穩(wěn)定性.

4 實例驗證與對比分析

假設(shè)存在3 個Agent,A={a1,a2,a3},需要合作完成2 個任務(wù),T={t1,t2},t1＞t2.每個Agent 初始資源數(shù)量B1=[4,3],B2=[4,5],B3=[3,3].t1,t2資源數(shù)量需求D1=[3,4],D2=[4,3].接下來討論不同情形和不同時刻下的分配策略應(yīng)用舉例.

4.1 聯(lián)盟形成初始

u2=(0.67×1.71+1×2.21)+(0.50×2.29+1.33×1.79)=6.88.

4.2 成員加入組成新聯(lián)盟

4.3 重疊聯(lián)盟分配策略對比

根據(jù)上面的實例,表1 和表2 分別給出了不同時刻本文方法與文獻[30,31]的對比情況.

表1 T1 時刻本文方法與相關(guān)分配策略對比Table 1 Comparison between the method of this paper and the related allocation strategy in T1

表2 T2 時刻本文方法與相關(guān)分配策略對比Table 2 Comparison between the method of this paper and the related allocation strategy in T2

表1 和表2 是不同情形、不同時刻現(xiàn)有分配策略與本文分配策略的對比實例,在情形1 中,本文分配策略和現(xiàn)有分配策略都能均衡各成員利益,完成聯(lián)盟任務(wù),但在更加復(fù)雜的情形2 中,現(xiàn)有分配策略就變得不再適用.文獻[30]的分配策略只能對任務(wù)依次串行進行,雖然在一定程度上避免了資源沖突問題,但不能滿足并發(fā)多任務(wù)的情形,因此在情形2 無論哪個時刻都不能形成新聯(lián)盟.文獻[31]的分配策略雖然在T2時刻滿足效用非減條件,但在時間更早的T1時刻聯(lián)盟Cj則拒絕新成員a3的加入,在情形2 中此分配策略也顯示出一定的局限性.利用本文分配策略,無論在情形1 還是情形2 都能較好解決資源沖突問題,對重疊聯(lián)盟的效用進行合理分配,從而提高聯(lián)盟形成的成功率.

4.4 分配策略相關(guān)特性分析

本文分配策略除了滿足有效性和簡單性兩個基本特性的基礎(chǔ)上,也較好滿足了其他特性:

1)時效性分析.本文分配策略時效性體現(xiàn)在兩個方面:一方面,與現(xiàn)有分配策略相比,在T2時刻本文分配策略會使聯(lián)盟原有成員a1,a2所得效用(6.41,8.86)高于文獻[31]分配策略原有成員所得效用(5.63,7.69),在同一時刻加入聯(lián)盟時,利用本文分配策略可獲得比現(xiàn)有分配策略更高的效用;另一方面,在情形2 中,T1時刻早于T2時刻,利用本文分配策略,當(dāng)新成員在T1時刻加入現(xiàn)有聯(lián)盟時所得效用為(6.51,9.33),在時間稍晚的T2時刻新成員加入時所得效用為(6.41,8.86),聯(lián)盟成員在時間較早的T1時刻加入會獲得比T2時刻更高的效用分配,說明加入聯(lián)盟時間越早,分得效用也就越多,體現(xiàn)了聯(lián)盟效用分配時效性特征.

2)穩(wěn)定性分析.通過對不同情形下聯(lián)盟形成分配策略的分析,現(xiàn)有分配策略在某些情形變得不再適用,影響聯(lián)盟的穩(wěn)定性,導(dǎo)致聯(lián)盟失敗.聯(lián)盟形成的基礎(chǔ)是各成員有利可圖,a1,a2已經(jīng)完成了相應(yīng)的任務(wù),當(dāng)新Agent 申請加入時,a1,a2獲得的額外聯(lián)盟效用已經(jīng)有了參照,要高于新成員加入之前的效用.a3作為新加入者,完成一定任務(wù)量就會獲得效用,只要達到滿意的效用分配,聯(lián)盟成員就不會退出當(dāng)前聯(lián)盟轉(zhuǎn)投其他聯(lián)盟.通過案例分析,本文分配策略在不同情形下都能適用,相比現(xiàn)有分配策略更能均衡各方成員利益,避免出現(xiàn)沖突的局面,保證聯(lián)盟的穩(wěn)定運行.

3)動態(tài)性分析.聯(lián)盟形成是在開放的環(huán)境中各成員動態(tài)博弈的過程,效用分配取決于聯(lián)盟成員資源貢獻量,成員資源貢獻量不是加入聯(lián)盟初始就確定的,成員之間依據(jù)任務(wù)需求量互相協(xié)商.當(dāng)有新成員加入現(xiàn)有聯(lián)盟時,聯(lián)盟原有成員與新成員也需要進行協(xié)商,逐步構(gòu)建新聯(lián)盟.在構(gòu)建新聯(lián)盟的過程中,原有聯(lián)盟成員a1,a2應(yīng)符合效用非減原則,現(xiàn)有分配策略按照某種硬性規(guī)則,一旦不滿足效用非減原則則會造成聯(lián)盟的失敗.本文加入績效獎勵系數(shù)可以使任務(wù)分配變得更具靈活性,當(dāng)成員之間出現(xiàn)利益沖突時可以通過協(xié)商的方式找到一種符合各方成員利益的分配方式,更能體現(xiàn)聯(lián)盟效用分配的動態(tài)性特征.

5 結(jié)束語

如何在多個重疊聯(lián)盟之間分配效用,尤其如何給同時參與了多個任務(wù)的Agent 成員劃分效用是MAS中的一個難點問題.為此,本文根據(jù)每個Agent 當(dāng)前擁有的資源狀況和任務(wù)的實際需求,提出一種面向任務(wù)優(yōu)先滿足和績效獎勵的重疊聯(lián)盟效用分配策略.基于任務(wù)優(yōu)先滿足可有效避免多個重疊聯(lián)盟之間的資源沖突問題,合理反映Agent 對聯(lián)盟貢獻的差異性;基于績效獎勵可在一定程度上保護原有聯(lián)盟成員的既得利益,維護聯(lián)盟的穩(wěn)定性.對比實例分析結(jié)果表明,本文所提策略可滿足效用非減、時效性、穩(wěn)定性和動態(tài)性等特征,為重疊聯(lián)盟效用分配提供了一個有益的嘗試.在未來的研究工作中,將探索一種對新加入Agent 成員更加公平的效用分配策略,以有效保護每個聯(lián)盟成員的合法權(quán)益.

附錄 相關(guān)定理證明

定理1若一個OCF 問題有可行解,則應(yīng)滿足式(6).

證明充分性.已知一個OCF 問題有解,意味著聯(lián)盟Cj的資源總和多于任務(wù)T的資源需求總量,tj的r維資源需求向量中任意一種資源需求總有至少一個Agent 可以滿足,如果存在任意一種資源沒有被滿足,則OCF 問題無解.對于k=1,2,...,r,符合,即因此得證.

必要性.假設(shè)任務(wù)tj存在某種資源需求大于聯(lián)盟Cj成員資源的初始總量和,即,則與的判定條件矛盾,綜合兩方面命題得證.證畢.

定理2對于?ai ∈A,若不存在資源沖突問題則應(yīng)滿足式(8).

證明充分性.若聯(lián)盟Cj完成任務(wù)不存在資源沖突,意味著Agent 成員每種資源擁有總量大于任務(wù)資源需求量,實際貢獻量則應(yīng)小于或等于任務(wù)資源需求量,即

定理3?tj ∈T經(jīng)過上述任務(wù)分派方式后均滿足式(7)和式(8).

證明經(jīng)式(9)分派任務(wù)后,實際資源貢獻量Wij=Lij,那么有

而

展開

式(7)得證.

式(8)得證.證畢.