楊 萍，龍正平，王 桐

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

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

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

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

1 資源沖突的分類

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

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

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

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

模型假設(shè)：

1）Agent間是合作的；

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

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

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

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

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：每個收到消息的Agent計算自身占有該資源的任務(wù)重要性效用U1、該任務(wù)對資源占用的時間區(qū)間和整個任務(wù)完成時間etj，并發(fā)送協(xié)商消息 in form(j,i,u,vj1) ,u∈S,vj1∈V，其中V為Agent在協(xié)商過程中提交的協(xié)商意見，而vj1=U1∪∪et；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然，式（3）的結(jié)束時間早于式（5），式（6）的結(jié)束時間早于式（4）（因為t＜durtA）；

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

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

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

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

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

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

3）綜合效用

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

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

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

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

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

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

3 算 例

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

圖2 局部計劃圖

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

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

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

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

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

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

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

4 結(jié)束語

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

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

[2]徐潤萍,王樹宗,顧健.兵力協(xié)同計劃資源沖突協(xié)商方法研究[J].系統(tǒng)仿真學(xué)報,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.