ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.342-345



Agentϵͳļֹ淶ɻ
һʯһ
ժҪHCR(highest cumulative reward)Ƕagentϵͳеһֹ淶ɻ,ڸû£ϵͳĹ淶ı仯仯.½˹淶Ķ,˹淶ȶ,ڹ淶ɵHAR(highest average reward)HRR(highest recent reward),ڹ淶ݻ,HCRиõٶ.
ؼʡagentϵͳ,Э,淶,ͻΪ,ݻ.
ͼšTP18
Strategy-Selection Rules for Developing Conventions in Multi-Agent System
WANG Yi-chuanSHI Chun-yi
(Department of Computer Science and Technology Tsinghua University Beijing100084)
AbstractHighest cumulative reward (HCR) is a rule for developing conventions in multi-agent systems.But it will keep system maintaining an emerged convention from evolving to more rational ones while conditions of system are developing.In this paper,the notion of conventions is defined,and the stability of them is analyzed.Furthermore,two rules called highest average reward (HAR) and highest recent reward (HRR) are introduced.They both guarantee the evolving process of stable conventions,and the convergence rate of them is better than that of HCR.
Key wordsMulti-Agent system,coordination,convention,emergent behavior,evolution.
Ϊ淶agentЭƵһ.Agentڽʱ,Ϊ淶ڶܵΪֱ֮ѡ,ӶͨźЭ.Ϊ淶ȹ涨,ҲĳֻƵԼϵͳɣ1,2.ֿɷΪ,һƽȷΪ淶,һ಻ƵȨ.agentλƽ,ڽɹ淶,ʵּ򵥵ŵ.ķֻԺһ.MASеĹ淶ɡȶݻȹ,ǰ漰ΪԵĴΪĴ,ϵͳﵽ淶״̬ı仯й.淶γɺ,ĳЩagentΪøߵĶΥ淶ʱ,ѭ淶agent淢仯,ʱ淶ֳܱȶ߽ı仯,ǹ淶ȶ.֮,ϵͳδ֪Ϊ,ʹϵͳгָŵΪʱ,淶ΪԵתǹ淶ݻ.淶ɹ̴Ӿֲ,ҲһݻĹ.,ù淶Ŀڱ֤ŻͬʱЭ,ҪȫַΧagentΪͬ3,4ǲҪ.
Ĺ淶ɻƿɷΪֵƣ3,5,6ݺƣ7,߶δܿǵ淶ȶ̺ݻ.ף3ڶԲ۵Ŀ¶淶,HCR(highest cumulative reward)֤ڸЧĹ淶,agentνеĸΪԵۻΪѡΪ.HCRƵȱǲݻ,ͬʱagentԤ֪ΪԼ.ף6HCRĻоagentľֲԺȨԶڹ淶ɽӰ,Լͻ֯ṹ¹淶ɹ.ַʽHCRƵȱ,֯ṹвͬεagentԤ趨,ڶ̬б֤.ף7ģ»оagent淶ɹԡٶйصļ.Agent¼ÿνʱԷΪ,ʷϢѡǰ,ȱϵͳֻʼʽϸߵĲ.ף5оΪԵĴ,Ƚ˲ͬĴʽЧʺͿ,δ漰agentΪԵۺȡ.
1淶Ķ
ȸҪĸ
E=e1,e2,...,en,eiǸĵiagentʱĳ,eiej(ij)ȵģCΪEвͬԪعɵļϣA=a1,a2,...,apΪпѡΪF=f1,f2,...,fqΪΪԼ,fiCA.
ЧúuAnRn,u(i1,i2,...,in)=(ui1,ui2,...,uin),uijΪ뽻agentڳejʵʩΪijõ棻ЧúUAnR,U(i1,i2,...,in)=ui1+ui2 +...+uin.
Fϵȼ۹ϵ֡,fifjU(fi(e1),fi(e2),...,fi(en))=U(fj(e1),fj(e2),...,fj(en)),ɴ˵õFϵһ֣F1,F2,...,Fs,ϵͳЧε.FӼFcfi1,fi2,...,finFc,U(fi1(e1),fi2(e2),...,fin(en))UFc,UFcΪһ.Ȼ,ݼиfȼ.FݼļΪFC.
淶ConvFC,淶FһӼ,Ա֤ΪԼ䲻ͻ.ConvŵȼۼϵӼ,Ƹù淶ȫŻ淶.ٶagentڽл,һѭ淶ConvĽǰ,agentΪeu=UConvn,ʱȫŻĹ淶Ҳagentĸ.
Ϊ˷淶ȶ,ǶΪfݼFcųkʣ1,n,fj1,fj2,...,fjnFc,fF,u(fj1(e1),fj2(e2),...,fjn(en))=(uj1,uj2,...,ujn),u(fj1(e1),fj2(e2),...,f(ek),...,fjn(en))=(uj1,uj2,...,ujk,...,ujn),U(fj1(e1),fj2(e2),...,f(ek),...,fjn(en))<UFcujk>ujk,ʵʩΪfagentͬʱ,ʱfųݼFc.ĳݼFf,Fcȶģĳf,fj1,fj2,...,fjnFcU(fj1(e1),fj2(e2),...,f(ek),...,fjn(en))<UFcujk>ujk,FcǲȶģνȶͲȶ֮,ɸݱųȶ̶.Ȼ,ݼȶӼ.
2HARHRR㷨
HCRƲܹݻҪ,ڻڴĹ淶ɹвܱ֤.ǸHAR(highest average reward)HRR(highest recent reword)ۻЧӦ,ʺڹ淶ݻ.HARʷϢиΪԵƽΪѡǰΪԵ,ƽֵHCRеۻֵ.HRRۼʷϢʱùһļȨϵ,ԽԽߵȨֵ,ڹһHCRۻЧӦ.Ǳڹ淶ȶ,HARHRRҲʹϵͳ淶.
㷨HARHRR.C={e1,e2,...,em},A={a1,a2,...,aq},agentʼʱ֪пΪ.
㷨1.HAR
rewardmݣq,ۻĳ²ĳΪ棻ǰcurStrm,ڼ¼ǰmӦΪ;timesmݣq,ڼ¼ĳ²ĳΪĴ.
(1) ʼ
rewardmݣqԪֵΪĳϴֵ,ʹڸ²ͬΪлᱻִ.
curStrmʼΪ1,qϵֵ.
timesmݣqݸԪسʼΪĳ.ֱۺΪagentжϵγ̶.
(2) ÿν,ִ¼
(a) ݵǰei,õǰµĶӦΪacurStriݣ
(b) ִΪacurStri,õ curu
(c) rewardiݣcurStrmݣ curu;
timesiݣcurStrmݣ1
(d) curu<rewardiݣcurStrmݣtimesiݣcurStrmݣ,ѡڳeiӦȡΪaj,ʹökʣ1,q,rewardiݣjtimesiݣjݡrewardiݣkݣtimesiݣkݣcurStri=j.
㷨2.HRR
rewardmݣqڼ¼ۻȨ棻ǰcurStrmݺͬ㷨HARȡweightʣ0,1ΪȨ.
(1) ʼ
rewardmݣqԪֵΪĳϴֵ,ʹڸ²ͬΪлᱻִ.
curStrmʼΪ1,qϵֵ.
(2) ÿν,ִ¼
(a) ݵǰei,õǰµĶӦΪacurStriݣ
(b) ִΪacurStri,õ curu
(c) rewardiݣcurStrmݣ= rewardiݣcurStrmݣݡweight+curu(1-weight)
(d) curu<rewardiݣcurStrmݣ,ѡڳeiӦȡΪaj,ʹkʣ1,q,rewardiݣjݡrewardiݣkݣcurStri=j.
3ʵ
3.1ʵ˵
ʵ鱳100agent,agent,ڼΪ淶ɻƵԺݻ.ı׼1 000νа淶еĴ950,ֵʱΪʱ.ÿʵ޶Ϊ8 000,1 000.
ʵ1.ֵ¸Ƶ
E=(e1,e1)A={a1,a2}u(a1,a1)=u(a2,a2)=(4,4),u(a2,a1)=u(a1,a2)=(1,1)F={f1,f2},f1(e1)=a1,f2(e1)=a2.
ʼʱÿagent֪ȫΪ.
HRRȡweight=0.8.
ʵ2.ͬʼ¸Ƶ
E=(e1,e1)A={a1,a2}u(a1,a1)=(4,4),u(a2,a2)=(1,1),u(a2,a1)=u(a1,a2)=(-1,-1)F={f1,f2},f1(e1)=a1,f2(e1)=a2.
ʼʱÿagentֻ֪һֲ,òf1ĸʣΪP,agentڽ໥.PСʱ,ϵͳf1Ҳһ淶ݻĹ.
HRRȡweight=0.8.HCR֪δԵΪѡʱȨ.
3.2ʵ
ʵ1УHARHRR㷨1 000ȫ,HCR㷨.
ʵ2Ľ1,Ϊڱ궨1 000زĻ.Կ,Pͬʱ,HCRԵı仯ܴ,PԽԽ.HARHRR㷨ԲͬPкܺõ.
Table 1
1

1 0002 0003 0004 0005 0006 0007 0008 000
HCR P=1/29979999991 0001 0001 0001 0001 000
HCR P=1/3650778811820830831834836
HCR P=1/4178284328345357363365367
HCR P=1/6929353838404040
HCR P=1/2500000000
HAR P=1/21 0001 0001 0001 0001 0001 0001 0001 000
HAR P=1/25954976976976976976976976
HRR P=1/21 0001 0001 0001 0001 0001 0001 0001 000
HRR P=1/25977977977977977977977977

3.3
agent֪Чúȷӳʱ,ԽļƽƵֵ,ʱ,HCRԿ.ʵ,agentԤ֪ϵͳЧú,ʵ1ָHCRƶagent֪Ҫ,HARHRRû.
ʵ2,HCRƵPֵй,PԽ,ԽãPֵСʱ,ʼΪf2agentܹڻཻл㹻谭f1ٴαѡȡ,ͬʱҲʹǰΪf1agentཻĿԼ.
4ᡡ
޳ͻΪ㽨˶ೡ¹淶һģ,ͨ淶ɹ,ֻڼֵѡĹ淶ɻ,ͨʵȽ˼ֻڼµ.ûagentڳʶٶagentھ߱ʶ𳡾,һЩ,ʶΪй,͹淶ɻӰ,ʹù淶ɹ̸Ӹ.ʵвųΪ,ûм淶ɻƵȶ.
оõȻѧ(No.69773026,69733020).
һ,1973,ʿ,ҪоΪֲʽ˹.
ʯһ,1935,,ʿʦ,ҪоΪ˹Ӧû.
һ(廪ѧѧ뼼ϵ100084)
ʯһ(廪ѧѧ뼼ϵ100084)
ο
1Ephrati E,Pollack M E,Ur S.Deriving multi-agent coordination through filtering strategies.In:Mellish C S ed.Proceedings of the 14th International Joint Conference on Artificial Intelligence,Vol 1.San Mateo,CA:Morgan Kaufmann Publishers,1995.679685
2Goldman C V,Rosenschein J S.Emergent coordination through the use of cooperative state-changing rules.In:Proceedings of the 12th National Conference on Artificial Intelligence,Vol 1.Cambridge,MA:MIT Press,1994.408413
3Shoham Y,Tennenholtz M.On the emergence of social conventions:modeling,analysis,and simulations.Artificial Intelligence,1997,94(12):139166
4Tennenholtz M.On stable social laws and qualitative equilibria.Artificial Intelligence,1998,102(1):120
5Luo Yi.Agent model and solving method in multi-agent system Ph.D.Thesis.Beijing:Tsinghua University,1996
(.AgentϵͳAgentģͺⷽ۲ʿѧλģ.:廪ѧ,1996)
6Kittock J E.The impact of locality and authority on emergent conventions:initial observations.In:Proceedings of the 12th National Conference on Artificial Intelligence,Vol 1.Cambridge,MA:MIT Press,1994.420425
7Walker A,Wooldridge M.Understanding the emergence of conventions in multi-agent systems.In:Lesser V,Gasser L eds.Proceedings of the 1st International Conference on Multi-Agent Systems.Cambridge,MA:MIT Press,1995.384389
ոڣ1998-12-01
޸ڣ1999-03-11
