о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



һֻڵȼ۵ݻ
͡ʯһ
ժҪǶAgent֮һҪĺ.ûп˵ݻ⣬Աļ㣻Ҷֵ֪ļҲǲʵʵ.иĵȼԺӦݻƣֵͨԤȼ㣬Ľ⣬Խͼ㸴Ӷ.Shehory & KrausĹ˵ĵȼۺݻ˶ֵ֪ļ.
ؼʡˣֵȼۣݻ
ͼšTP18
A MECHANISM OF COALITION EVOLVEMENT 
BASED ON EQUIVALENCE
XU Jin-Hui and SHI Chun-Yi
(Department of Computer Science, Tsinghua University, Beijing100084)
AbstractCoalition is an important cooperative method in multi-agent systems. Most of the methods don't consider evolvement of coalition, so it is difficult to avoid a mass of computation, and assumption about coalition value known isn't realistic. In the paper here, equivalence of coalition and mechanism of evolvement are presented, which can obtain solution of coalition by non-computing of coalition value and may reduce computational complexity. The work of the paper introduces equivalence and evolvement of coalition, and releases restriction of assumption about coalition value known, compared with the work of Shehory & Kraus.
Key wordscoalition, coalition value, equivalence, evolvement
1
1993ף1ݵף3˷ȡһĽչ.ͨ˿Agentøı꣬ǶAgentϵͳ(MAS)Ҫ.
1.1
AgentN={A1,A2,,An}ԴQ={(q1,q2,,qn)}qi=(q1i,q2i,,qkii)qjiʾAijԴT={T1,T2,,Tn}Ti={t1i,t2i,,tmii}Ai񼯣tjiAiĵj񣬶ÿһжӦԴ˵ÿһAgentʼһԴ.
MASĺAgent֮Դ飬ʹÿһAgentܽʡԴȡıꣿͨ˷.
һCáNc,qc,Qc,Tc,Tc,V(c),UcNcNӼqcCӵеԴQcԴĽTcC񼯺ϣTcĽV(c)˵ֵUc=(u1,,u|c|)V(c)CԱһ.
һȶҪ{U,CS}(U,CS)Ϊһм״̬˽ṹCS={C1,C2,,Cp}Nһ֣U=(u1,u2,,un)ÿAgentñ.
V2NRӳ䣬NӼSTST=գV(ST)V(S)+V(T)V㳬ԣV(ST)<V(S)+V(T)VμԣڳеAgentӦһˣCS={N}෴ڴμӦˣCS={{A1},{A2},,{An}}.ͨAgentͨ˺ĶЧΪ˵ֵһV({Ai})=0.
1.2˵γɹ
˵γɹ̣˽ṹCSĲֵ˽ṹÿһܵ˵ԴϷ䣬Ӧֵ۽ֵڳԱ֮з䣬һȶU.3ǻཻģ費ϷһȶҪ{U,CS}.
Ϊһ˷ӦСҪ
(1) Ч.ָͨ˴ĶЧòӦñγͨźͼԴС
(2) ȶ.иˡȺ塢3Ҫ󣬼ٸԹʽuiV({Ai}),ȺԹʽǶڣСAiSui=V(S)(ейʽǡAiNui=V(N)ֻԳ)ԹʽǣڣҡAiTuiV(T)ǿҪԱ֤.
(3) ķֲ.ͨŵķֲֹͨƿ̱ķ.
(4) ̵ļ.ҪһĽпܵķǲʵģΪһNP.
еҲᵽԳԣ4ݣǼԣ5ݵ.
1.3صĹ
Shehory & Kraus267,Zlotkin & Rosenschein4,Ketchpel38ݺSandholm & Lesser910ݵĹûп˵ݻÿµʱҪγ㷨½ˣɺ˽壬Ʊдļͨſеķٶ˵ֵԤõģֵԤȼѵģΪֻɣʵȷ˵ֵ.
Щ⣬ȸ˵ȼ۵ĶӦ⣬˵ȼ۸˵Ļ̡ƥ䷽Եݻ.
2˵ȼ
N˺ԲвԵȼۣĵȼ.Բ
Բ (N,v)  (N,u) ΪԵȼ۵ģaʵ1,2,,n,ʹ

vuֵ޶V({Ai})=0.
1. P1P2ӦֵV1V2aʹ

ôP1P2ֵϵȼ.
1. P1P2ֵϵȼۣP2һ(U2,CS2)ô(aU2,CS2)P1һ.
ǶģġˡȶȶԲ߽Ǽϵĺ壬ָShapleyֵġˡȶȵһ.1ӲͬĽⶨ֤.
1. N={1,2,3}P1V1({1})=V1({2})=V1({3})=0V1({1,2})=V1({1,3})=V1({2,3})=4V1({1,2,3})=8P2V2({1})=V2({2})=V2({3})=0V2({1,2})=V2({1,3})=V2({2,3})=2V2({1,2,3})=4ɼԣV1(S)=2V2(S)ôP1P2ֵϵȼ.P2ShapleyֵϵĽǣU2=(4/3,4/3,4/3),CS2={{1,2,3}}ҽ(U2,CS2)ǡҲںġ˺ȶ.֤U1=2(4/3,4/3,4/3),CS1={{1,2,3}}P1ShapleyֵϵĽ⣬ͬʱP1ĺġ˺ȶ.
ѰõȼĽ⣬ҪֵԤãѵģɽֵϵ.
ۺEǴAgentˣ񼯵ʵRӳ.
ԼֵAgnet֮ͨĶЧ棬Ҳ۵Ľ.CN
V(C)=iCE(Ti)-E(TC).
TiAi񼯣TC=UiCTiC.
V1(C)=aV2(C)
iCE(T1i)-E(T1C)=aiCE(T2i)-E(T2C)=aiCE(T2i)-aE(T2C)CN.
T1iP1Ai.
2. P1P2aʹ
iCE(T1i)-E(T1C)=aiCE(T2i)-E(T2C)=aiCE(T2i)-aE(T2C)CN,
ôP1P2ڴϵȼ.
2. P1P2ڴϵȼۣô1ĽԳ.
ж۵ȼѵģΪҪNӼбȽϣֵжϵȼ۽һ.
Ϊ˷㣬޶iNE(T1i)=aE(T2i)CNE(T1C)=aE(T2C)޶ΪEԼ.
3. P1P2EԼaʹ
C(T1i)=aC(T2i)iN
ôP1P2ڴϵȼ.
ʱͿԸÿAi񼯣жǷȼ.
4. P1P2ֵϵȼ۵ҽP1P2ڴϵȼ.
ȼۣô֪һĽ⣬ͿֱӼһĽ.
3ݻ
ݻʷйأʷ({⣬˽})Уÿ{⣬˽} Ϊ˵һʷָ((HE1,1),(HE2,2),,(HEn,n))(HEi,i)ǶAiHEiʷۣ˽(U,CS).
i=HEi/(AjNHEj)ǵȼƥ䷶Χ.ʽ֪ʶÿһAgentָһʵķΧƥĳɹʣʧҪͨγһļͨŵĿС.UвֵһҶеCCSСiCui=1ֻɣŸӦıֵķ.
3.1ݻ
1. ÿһAgentۣ֪ͨAgent
2. 뱣ʷеȼƥ䣺
 ƥɹôԳɹƥʷĽΪʱĽ
 ƥ䲻ɹǷͨﵽƥ䣬еγɷ
3. õ(U,CS)ˣԸк⣬ֵʵʷ.ͨγõĽӦĽ浽ʷ.
ù̿MASʵ.
3.2ֲʽȼƥ
3. AiһʷaΪοƥ䣬ָĿǰEiڣ(a-i)HEi,(a+i)HEiݷΧ.
CһʷaΪοƥ䣬ָе˳ԱaΪοʷƥ.
һʷaΪοƥ䣬ָCSе˾aΪοʷƥ.
ֲʽȼƥ̣
1. ÿһAgentΪ㣬ĿǰEiʷıa
2. ÿһʷжڵԱǷӦaΪοʷƥ䣻
3. гԱƥʷӦa֪ͨAgent
4. еAgent֮һͬʷaҲͬôƥɹ.
3.3ڴתƵĵ
ֲȼƥ䲽4УȻﲻȫͬʷһʷԲôתƵķʹͬ.
һʷӦǣCSֻһûƥ䣬Ҹ˳Ա٣ɵ.
ɵiCEi=iCaHEiָȻĿܲƥ䣬ƥ.
ÿһAgentӦaiaaС߽һתƣͬʱҪӦıҲתƣתƵת֮ͨЭ̻ƴﵽͬ⣬һֱƥΪֹ.
AgentһʷΪƥ䣬ֻмΪƥ䣬ұͬAgentΪͬһڣôͬ߿Ҫ֮ͬеﵽȫֵһ£ʽ֪ʶڿɵ֤˵ĳɹڵУ۵תͬʱ汨ת.
3.4γ
ƥ䲻ɹҲܽеʱҪеγɷ.ݻĳ׶ΣᾭʹγɷʷĻۣƥĳɹߣһʱܻ᲻Ҫγ.
3.5ʵ
Աĵ1ΪձĵķP1ʷôP2ʱͨƥԷP2P1ȼۣʱֱӵõP2Ľγ㷨ĵ.
4ᡡ
ݻƵҪǵȼ۵ƥ䣬ӶO(m)mʷĸ.ʷ࣬ƥĳɹߣӦĸӶ󣬲ҪĴ洢ռ֧֣һìܣԽCBRйط.
ĸݻʺһΣV㳬ԣеγɷڳΣṩһֲͨԤȼֵķƥɹԵ£㸴ӶԶеķΪеķɱҪֵ㡢ֵķ䣻ƥ䲻ɹ£еķƥļ.
ÿһ⣬ƥ䲻ɹ£ͨʵĵһȼ⣬ʡȥγɷݻдоĹ.
õȻѧ(Ŀ 6977302669733020)廪ѧоԺʿѧλĻ.
߼飺ͣУ19664ʿооΪAgentϵͳ˻.ʯһУ19358ڣʿʦоΪ˹Ӧû.
ߵλ廪ѧѧϵ100084
ο
1Zlotkin G,Rosenschein J S. One,two,many:Coalitions in multi-agent systems. In:Castelfranchi C,Pmuller J Eds.From Reaction to Cognition,Lecture Notes in Artificial Intelligence,Vol 957.Berlin:Springer,1993
2Shehory O,Kraus S. Coalition formation among autonomous agents: Strategies and complexity. In: Castelfranchi C,Pmuller J Eds.From Reaction to Cognition,Lecture Notes in Artificial Intelligence,Vol 957.Berlin:Springer,1993.5772
3Ketchpel S. Coalition formation among autonomous agents. In:Castelfranchi C,Pmuller J Eds.From Reaction to Cognition,Lecture Notes in Artificial Intelligence,Vol 957.Berlin:Springer,1993.7388
4Zlotkin GRosenschein J S. Coalition,cryptography and stability: Mechanisms for coalition formation in task oriented. In:Proc AAAI-94.Seattle,1994.432437
5,ʯһ.AgentЭγ˵Ϊ.ѧ1997,20(11):961965
(Luo Yi, Shi Chunyi. The behavior strategy to form coalition in agent cooperative problem solving. Chinese Journal of Computers(in Chinese),1997,20(11):961965)
6Shehory O,Kraus S. Task allocation via coalition formation among autonomous agents. In: Proc IJCAI-95.Montreal,1995.655661
7Shehory O, Kraus S. A kernel-oriented model for coalition formation in general environments: Implementation and results. In:Proc AAAI-96.Portland,1996.134140
8Ketchpel S. Forming coalitions in the face of uncertain rewards. In: Proc AAAI-94.Seattle,1994.414419
9Sandholm T W, Lesser V R. Coalition formation among bounded rational agents. In: Proc IJCAI-95.Montreal,1995.694701
10Sandholm T W, Lesser V R. Coalition among computationally bounded agents. Artificial Intelligence,1997,94(1):99137
ԭյڣ1998-08-11
޸ĸյڣ1998-10-28
