任務(wù)優(yōu)先滿足和績(jī)效獎(jiǎng)勵(lì)的重疊聯(lián)盟效用分配

桂海霞,趙邦磊,張國(guó)富,蘇兆品,蔣建國(guó)

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

1 引言

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

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

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

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

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

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

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

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

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

3.1 效用分配原則

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

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

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

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

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

3.2 任務(wù)分派

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

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

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

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

3.3 效用分配

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

1)資源價(jià)值

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

4 實(shí)例驗(yàn)證與對(duì)比分析

假設(shè)存在3 個(gè)Agent,A={a1,a2,a3},需要合作完成2 個(gè)任務(wù),T={t1,t2},t1＞t2.每個(gè)Agent 初始資源數(shù)量B1=[4,3],B2=[4,5],B3=[3,3].t1,t2資源數(shù)量需求D1=[3,4],D2=[4,3].接下來討論不同情形和不同時(shí)刻下的分配策略應(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)盟分配策略對(duì)比

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

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

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

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

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

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

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

2)穩(wěn)定性分析.通過對(duì)不同情形下聯(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 申請(qǐng)加入時(shí),a1,a2獲得的額外聯(lián)盟效用已經(jīng)有了參照,要高于新成員加入之前的效用.a3作為新加入者,完成一定任務(wù)量就會(huì)獲得效用,只要達(dá)到滿意的效用分配,聯(lián)盟成員就不會(huì)退出當(dāng)前聯(lián)盟轉(zhuǎn)投其他聯(lián)盟.通過案例分析,本文分配策略在不同情形下都能適用,相比現(xiàn)有分配策略更能均衡各方成員利益,避免出現(xiàn)沖突的局面,保證聯(lián)盟的穩(wěn)定運(yùn)行.

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

而

展開

式(7)得證.

式(8)得證.證畢.