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

楊 萍，龍正平，王 桐

（第二炮兵工程學院，陜西 西安 710025）

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

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

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

1 資源沖突的分類

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

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

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

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

模型假設：

1）Agent間是合作的；

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

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

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

step1：每個Agent產生局部的計劃方案，并傳遞局部計劃；

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

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

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

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

step6：對資源進行重新調度，轉step1；

step7：監控任務執行過程，如果出現環境變化或意外情況，需要放棄該資源，則通知其他Agent；資源占用完成時，釋放該任務資源。

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

1）任務重要性效用

任務的重要性應該包括兩個方面：

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

二是對后續任務的影響。如果一個任務執行時間的延遲，對后續任務的影響很大，那么這個任務應該賦予更高的重要性權。評估對后續任務的影響也是一件比較復雜的事情，本文在這里將其簡化，在大多數情況下，可以認為該任務后續的任務數量越多，該任務計劃的變更產生的影響也越大。

設任務A后續任務的數量為n，對后續任務影響的重要性權為ω2A,0≤ω2A≤1，根據后續任務數量對重要性的影響特點，選用升半正態型曲線來刻畫這種影響關系，定義

其中，k(>0)為調節參數。

于是，任務的重要性效用為λ,0 ≤λ≤1為權重。

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

2）任務時間效用

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

通常情況下，我們當然希望通過協調資源使所有任務執行后的最晚完成時間盡量早。

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

則有如下結論成立：

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

圖1 任務A和任務B執行時間關系示意圖

若A先執行時，A所在的任務鏈結束的時間為

B所在的任務鏈結束的時間為

而若B先執行，A所在的任務鏈結束的時間為

B所在的任務鏈結束的時間為

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

而當式（4）大于式（5）時，即t1?t2＞t時，有式（4）大于式（5）且式（4）大于式（6），故選B先執行；

而當式（3）小于式（5）時，即t1?t2＞t時，有式（4）小于式（5）且式（3）小于式（5），故選A先執行；

當t2=t1,t＞0時，越早開始的任務先執行可以節省資源等待時間，故A先執行。

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

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

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

3）綜合效用

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

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

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

二是優先方式。首先看任務重要性效用，如果相等，再根據時間效用進行選擇，即

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

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

3 算 例

在分布式作戰仿真系統中，設Agenti、j、k分別制定了各自的局部計劃如圖2（a）、圖2（b）、圖2（c）所示。

圖2 局部計劃圖

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

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

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

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

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

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

④ A gentk按原計劃執行任務，Agenti與Agentj需要重新調度。

4 結束語

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

[1]徐瑞.基于多智能體的深空探測器自主任務規劃方法與系統仿真[D].哈爾濱:哈爾濱工業大學，2004.

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