基于協(xié)商的Agent資源沖突消解算法研究

楊 萍，龍正平，王 桐

（第二炮兵工程學(xué)院，陜西 西安 710025）

分布式規(guī)劃系統(tǒng)中Agent在制定計(jì)劃時(shí)，由于各個(gè)Agent的局部視點(diǎn)，合并得到的整體計(jì)劃往往存在沖突。Agent的計(jì)劃沖突主要表現(xiàn)為時(shí)間沖突和資源沖突。時(shí)間沖突指局部計(jì)劃合并為整體計(jì)劃時(shí)，計(jì)劃中的兩個(gè)或幾個(gè)子任務(wù)（或行動(dòng)）間違反了時(shí)序關(guān)系。文獻(xiàn)[1]對(duì)此進(jìn)行了專門研究，這里不再討論。本文主要針對(duì)計(jì)劃合并中的資源沖突，研究不同資源沖突類型下的沖突消解算法。

在過(guò)去二十多年，研究者開發(fā)了多種沖突消解技術(shù)，包括協(xié)商[2～4]、仲裁[5]、競(jìng)選[6]、意圖推理[7]等，以前的研究為 MAS沖突消解技術(shù)奠定了基礎(chǔ)。但這些研究大多以通用性的沖突消解框架為重點(diǎn)，較少涉及具體的最優(yōu)消解策略，特別是針對(duì)資源沖突這一具體背景的消解算法研究還比較少。

協(xié)商對(duì)多 Agent系統(tǒng)和分布式問(wèn)題求解系統(tǒng)（DPS）來(lái)說(shuō)是消解沖突，實(shí)現(xiàn)協(xié)作的最重要的方法之一，也是Agent交互中最普遍、最主要的表現(xiàn)形式[4]。本文運(yùn)用協(xié)商理論建立資源沖突消解算法，并著重研究如何最優(yōu)地制定協(xié)商策略，以提高協(xié)商效果。

1 資源沖突的分類

Agent在協(xié)作中使用的資源通常分為可重復(fù)利用的資源和消耗性資源，可重復(fù)利用資源實(shí)際中又可分為有限容量共享型資源，如信息、道路等，這些資源只能為有限用戶共同使用，以及不可分享型資源（具有排它性），如設(shè)備、容量為1的陣地等；消耗性資源一旦被某個(gè)或某幾個(gè)Agent占用，就不能再被其他Agent使用，如彈藥等。消耗性資源的一個(gè)最大特點(diǎn)仍是容量受限。

分析各種資源沖突可以看出，有限共享型資源當(dāng)資源容量為 1時(shí)轉(zhuǎn)化為可重復(fù)利用的不可分享型情形，而容量大于1時(shí)與容量受限的消耗型資源發(fā)生沖突條件的最大區(qū)別在于占用資源的時(shí)間上的限制，其消解沖突的實(shí)質(zhì)是一樣的，因此對(duì)資源沖突消解問(wèn)題的討論可轉(zhuǎn)化為對(duì)可重復(fù)利用的不可分享型資源以及容量受限的資源兩種情形的研究。本文只對(duì)可重復(fù)利用的不可分享型資源的沖突消解問(wèn)題進(jìn)行研究。

2 可重復(fù)利用的不可分享型資源的沖突消解算法

對(duì)于不可分享型資源，其重要特點(diǎn)在于對(duì)一個(gè)固定時(shí)間區(qū)間只能有一個(gè)Agent擁有對(duì)該資源的使用權(quán)。文獻(xiàn)[8]針對(duì)這類問(wèn)題提出了一個(gè)“多輪”（multi-round）協(xié)商模型框架，并且從局部的視點(diǎn)上給出了一些協(xié)商策略，但還不夠全面，本文從全局視點(diǎn)的角度探討最優(yōu)的協(xié)商策略，以更好地提高協(xié)商效果。

模型假設(shè)：

1）Agent間是合作的；

2）每個(gè)Agent均采用相同的出價(jià)策略，從而能保證結(jié)果度量值是一致和可比的；

3）Agent之間的通信是可靠的。

基于協(xié)商的不可分享型資源沖突消解算法思想是：每個(gè)沖突相關(guān)的Agent在接到協(xié)商消息后，發(fā)送一個(gè)占用該資源的時(shí)間區(qū)間、使用該資源的任務(wù)重要性效用和整個(gè)任務(wù)完成的時(shí)間消息；協(xié)商發(fā)起Agent根據(jù)收到的消息計(jì)算各Agent占用資源的綜合效用，由此決定誰(shuí)將獲得資源的使用權(quán)。對(duì)于獲得使用權(quán)的Agent將按照預(yù)定的方案使用該資源完成任務(wù)，其他的將不能按照原計(jì)劃執(zhí)行相關(guān)任務(wù)，他們將重新調(diào)度，然后開始新一輪的協(xié)商。具體的沖突消解算法為：

step1：每個(gè)Agent產(chǎn)生局部的計(jì)劃方案，并傳遞局部計(jì)劃；

step2：如果出現(xiàn)不可分享的資源沖突r，由發(fā)現(xiàn)沖突者Agenti發(fā)起協(xié)商，發(fā)送消息inform(i,j,u),j∈A,u∈S，其中A為參與協(xié)商的Agent集合，S為協(xié)商主題；

step3：每個(gè)收到消息的Agent計(jì)算自身占有該資源的任務(wù)重要性效用U1、該任務(wù)對(duì)資源占用的時(shí)間區(qū)間和整個(gè)任務(wù)完成時(shí)間etj，并發(fā)送協(xié)商消息 in form(j,i,u,vj1) ,u∈S,vj1∈V，其中V為Agent在協(xié)商過(guò)程中提交的協(xié)商意見(jiàn)，而vj1=U1∪∪et；

step4：協(xié)商發(fā)起者在規(guī)定時(shí)間內(nèi)收到所有消息后，根據(jù)各協(xié)商意見(jiàn)，計(jì)算各個(gè)Agent對(duì)資源占用的綜合效用，從中確定最佳的資源占有者，并發(fā)送accept(i,k,u,vks)；對(duì)其他Agent發(fā)送reject(i,h,u)；

step5：接到accept(i,k,u,vks)消息的Agent按原定計(jì)劃執(zhí)行任務(wù)，轉(zhuǎn)step7；接到reject(i,h,u) 消息的Agent，轉(zhuǎn)step6；

step6：對(duì)資源進(jìn)行重新調(diào)度，轉(zhuǎn)step1；

step7：監(jiān)控任務(wù)執(zhí)行過(guò)程，如果出現(xiàn)環(huán)境變化或意外情況，需要放棄該資源，則通知其他Agent；資源占用完成時(shí)，釋放該任務(wù)資源。

下面討論任務(wù)重要性效用和綜合效用的計(jì)算方法。

1）任務(wù)重要性效用

任務(wù)的重要性應(yīng)該包括兩個(gè)方面：

一是任務(wù)的地位。比如，在機(jī)動(dòng)作戰(zhàn)中，既有具有真正機(jī)動(dòng)作戰(zhàn)目的的作戰(zhàn)單元，也有配合其行動(dòng)的佯動(dòng)單元，顯然兩者任務(wù)的地位是不相同的。對(duì)任務(wù)地位的重要性可以通過(guò)一定的準(zhǔn)則進(jìn)行評(píng)估，也可以依據(jù)經(jīng)驗(yàn)打分進(jìn)行量化，這里不詳細(xì)討論評(píng)估細(xì)節(jié)，用一個(gè)反映任務(wù)地位的重要性權(quán)1表示。

二是對(duì)后續(xù)任務(wù)的影響。如果一個(gè)任務(wù)執(zhí)行時(shí)間的延遲，對(duì)后續(xù)任務(wù)的影響很大，那么這個(gè)任務(wù)應(yīng)該賦予更高的重要性權(quán)。評(píng)估對(duì)后續(xù)任務(wù)的影響也是一件比較復(fù)雜的事情，本文在這里將其簡(jiǎn)化，在大多數(shù)情況下，可以認(rèn)為該任務(wù)后續(xù)的任務(wù)數(shù)量越多，該任務(wù)計(jì)劃的變更產(chǎn)生的影響也越大。

設(shè)任務(wù)A后續(xù)任務(wù)的數(shù)量為n，對(duì)后續(xù)任務(wù)影響的重要性權(quán)為ω2A,0≤ω2A≤1，根據(jù)后續(xù)任務(wù)數(shù)量對(duì)重要性的影響特點(diǎn)，選用升半正態(tài)型曲線來(lái)刻畫這種影響關(guān)系，定義

其中，k(>0)為調(diào)節(jié)參數(shù)。

于是，任務(wù)的重要性效用為λ,0 ≤λ≤1為權(quán)重。

除了任務(wù)的重要性因素，往往還需要考慮任務(wù)完成的時(shí)間因素。

2）任務(wù)時(shí)間效用

對(duì)于時(shí)間因素，這里主要考慮最重要的三個(gè)方面：任務(wù)完成時(shí)間、任務(wù)開始時(shí)間和任務(wù)持續(xù)時(shí)間。

通常情況下，我們當(dāng)然希望通過(guò)協(xié)調(diào)資源使所有任務(wù)執(zhí)行后的最晚完成時(shí)間盡量早。

考慮兩個(gè)任務(wù)的情況，設(shè)要求A、B所在的整個(gè)任務(wù)最晚完成時(shí)間盡量早，并不是任何情況下任務(wù)A先開始就應(yīng)該先執(zhí)行，應(yīng)該對(duì)兩者綜合考慮。設(shè)任務(wù)A、B的持續(xù)時(shí)間分別為durA、durB，任務(wù)B滯后于任務(wù)A，其開始時(shí)間差為t，任務(wù)A、B所在的整個(gè)任務(wù)完成時(shí)間分別為etA,etB，令

則有如下結(jié)論成立：

對(duì)使整個(gè)任務(wù)最晚完成時(shí)間盡量早問(wèn)題，當(dāng)t2?t1＞t時(shí)（t＜durA），應(yīng)選B先執(zhí)行；當(dāng)t2?t1＜t時(shí)，應(yīng)選A先執(zhí)行；當(dāng)t2=t1,t＞0時(shí)，越早開始的任務(wù)應(yīng)先執(zhí)行。如圖1所示，

圖1 任務(wù)A和任務(wù)B執(zhí)行時(shí)間關(guān)系示意圖

若A先執(zhí)行時(shí)，A所在的任務(wù)鏈結(jié)束的時(shí)間為

B所在的任務(wù)鏈結(jié)束的時(shí)間為

而若B先執(zhí)行，A所在的任務(wù)鏈結(jié)束的時(shí)間為

B所在的任務(wù)鏈結(jié)束的時(shí)間為

顯然，式（3）的結(jié)束時(shí)間早于式（5），式（6）的結(jié)束時(shí)間早于式（4）（因?yàn)閠＜durtA）；

而當(dāng)式（4）大于式（5）時(shí)，即t1?t2＞t時(shí)，有式（4）大于式（5）且式（4）大于式（6），故選B先執(zhí)行；

而當(dāng)式（3）小于式（5）時(shí)，即t1?t2＞t時(shí)，有式（4）小于式（5）且式（3）小于式（5），故選A先執(zhí)行；

當(dāng)t2=t1,t＞0時(shí)，越早開始的任務(wù)先執(zhí)行可以節(jié)省資源等待時(shí)間，故A先執(zhí)行。

由上證明可以保證在盡量提早所有任務(wù)的最晚完成時(shí)間的基礎(chǔ)上，盡量減小資源等待浪費(fèi)的時(shí)間。

如果t=0,t2=t1，在動(dòng)態(tài)多變的環(huán)境中，任務(wù)的持續(xù)時(shí)間大小是應(yīng)該考慮的。例如，任務(wù)A和任務(wù)B有相同的任務(wù)重要性效用、任務(wù)開始時(shí)間和后續(xù)任務(wù)執(zhí)行時(shí)間，但任務(wù)A比任務(wù)B執(zhí)行時(shí)間短，在下一輪的協(xié)商中，若新加入一個(gè)任務(wù)C，其重要性大于A、B，若A先執(zhí)行，則重要任務(wù)C完成的時(shí)間要早于任務(wù)B先執(zhí)行的情況。因此這種情況下，任務(wù)持續(xù)時(shí)間越短的任務(wù)越先執(zhí)行。

綜上，對(duì)任務(wù)A（其任務(wù)開始時(shí)間小于等于任務(wù)B），其任務(wù)時(shí)間效用可以定義為

3）綜合效用

可以通過(guò)以下兩種方式綜合任務(wù)重要性和時(shí)間效用：

一是加權(quán)方式。這種方式對(duì)兩方面因素綜合考慮，綜合效用計(jì)算式如下

其中 0 ≤α2,α1≤1,α2+α1=1。

二是優(yōu)先方式。首先看任務(wù)重要性效用，如果相等，再根據(jù)時(shí)間效用進(jìn)行選擇，即

最終，資源占有權(quán)的選擇原則：arg max{UA,UB}

如果參與資源競(jìng)爭(zhēng)的不只兩個(gè)任務(wù)，則首先任選兩個(gè)任務(wù)依據(jù)上述原則進(jìn)行選擇，每次具有資源擁有權(quán)的任務(wù)再與剩余任務(wù)中的一個(gè)進(jìn)行競(jìng)爭(zhēng)選擇，直到所有任務(wù)進(jìn)行完畢。

3 算 例

在分布式作戰(zhàn)仿真系統(tǒng)中，設(shè)Agenti、j、k分別制定了各自的局部計(jì)劃如圖2（a）、圖2（b）、圖2（c）所示。

圖2 局部計(jì)劃圖

在將局部計(jì)劃合并為整體計(jì)劃中，執(zhí)行任務(wù)a3、b2、c1時(shí)出現(xiàn)了占用不可分享型資源R1的沖突。

① A genti首先檢測(cè)到該沖突，因此發(fā)起協(xié)商，發(fā)送消息 in form(i,j,u)， in form(i,k,u)，u= {R1}；

② 接到消息的Agentj、k分別計(jì)算自身占有該資源的任務(wù)重要性效用U1、該任務(wù)對(duì)資源占用的時(shí)間區(qū)間 [stR1,etR1]和整個(gè)任務(wù)完成時(shí)間et，并發(fā)送消息inform(h,i,u,vh1),h= {j,k}，其中vj1=0.8∪[10,18]∪34，vk1=0.85∪[12,21]∪45；

③ A genti接到消息后計(jì)算每個(gè)的綜合效用。設(shè)Agenti的任務(wù)重要性效用U1、對(duì)資源占用的時(shí)間區(qū)間[stR1,etR1]和整個(gè)任務(wù)完成時(shí)間et為：0.7 5∪[9,15]∪37，首先考慮a3與b2，根據(jù)式（7），易得U2a3=1，U2b2=0；利用式（8）計(jì)算綜合效用，得

故應(yīng)先選擇Agenti占用資源R1去執(zhí)行任務(wù)a3。類似地再在a3與c1中進(jìn)行選擇，最終得到：Ua3=0.525，Uc1=0.895，故在這一輪的協(xié)商中，選擇Agentk先執(zhí)行任務(wù)c1。

Agenti發(fā)送消息accept(i,k,u,vks)，對(duì)Agentj發(fā)送reject(i,j,u)；

④ A gentk按原計(jì)劃執(zhí)行任務(wù)，Agenti與Agentj需要重新調(diào)度。

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

本文研究了計(jì)劃合并中的資源沖突消解問(wèn)題，運(yùn)用Agent協(xié)商理論，提出了可重復(fù)利用的不可分享型資源的沖突消解算法，論證了最優(yōu)的協(xié)商策略，較好地解決了Agent分布式規(guī)劃中出現(xiàn)的一類資源沖突問(wèn)題。算例表明，論文給出的沖突消解算法具有可操作性。

[1]徐瑞.基于多智能體的深空探測(cè)器自主任務(wù)規(guī)劃方法與系統(tǒng)仿真[D].哈爾濱:哈爾濱工業(yè)大學(xué)，2004.

[2]徐潤(rùn)萍,王樹宗,顧健.兵力協(xié)同計(jì)劃資源沖突協(xié)商方法研究[J].系統(tǒng)仿真學(xué)報(bào),2005,17(5): 1216-1220.

[3]G.Zlotkin,J.S.Rosenschein.cooperation and conflict resolution via negotiation among autonomous agent in Non-cooperative domains[J].IEEE SMC,1991,21(6):1317-1324.

[4]N.R.Jennings,S.Parsons,C.Sierra.Automated negotiation[C].In: Proceedings of the 5th International Conference on the Practical Application of Intelligent Agents and Multi-Agent System (PAAM-2000).Manchester,UK.2000: 23-30.

[5]R.Steeb.Architectures for distributed intelligence for air fleet control[R],Rand Corp.,Santa Monica,CA,Tech.Rep.R-2728-ARPA,1981.

[6]E.Ephrati and J.S.Rosenschein.Multi-agents planningASa dynamic search for social consensus[C].In:Proceedings Thirteenth International Joint Conference Artificial Intelligence.Morgan Kaufmann,1993:423-429.

[7]H.Sugie.Placing objects with multiple mobile robotsmutual help using intention inference[C].In: Proceedings IEEE International Conference on Robotics Automation.IEEE,1995: 2181-2186.

[8]Keith Decker, Jinjiang Li.Coordinating Mutually Exclusive Resources using GPGP[J].Autonomous Agents and Multi-Agent Systems,2000(3):133-157.