效用驱动的多agent合作机制

doi:10.3969/j.issn.1000-436x.2013.07.014

摘要/Abstract

摘要：

提出了一种多agent合作机制，以效用为基础，利用效用函数计算agent在不同任务下与其他agent合作而产生的效用值，以此为依据得到agent对不同合作方式的偏好序列，并选择最大偏好参与合作。通过这种方法， agent 可以主动选择最适合自己的合作方式来完成任务，与此同时，以效用为驱动可以使群体的任务收益达到最优，提高了agent群体的合作效率。最后给出了用于方法验证的多agent原型系统，同时在该系统下证明了合作机制的有效性。

关键词: 效用函数, 多智能体系统, 合作机制, 依赖关系

Abstract:

A cooperative mechanism amlong multiple agents was proposed. In the cooperative mechanism, a utility value was used to generate a preferred order for agents under different cooperative patterns. This utility value was achieved by computing the cooperative utility between one agent and the others under different tasks using a utility funct Accord-ing to this mechanism, agents can automatically choose the cooperative pattern, wh is the best to fit themselves to ac-complish their missions. Meanwhile, driven by utility, group task income can achieve the optimum, which enhances the cooperation efficiency of agent groups. A prototype system was designed at last to val te the proposed cooperative me-chanism. The effectiveness of this cooperative mechanism has been proved under the prototype system.

Key words: utility function, multi-agent system, cooperation mechanism, dependence relationship

邓寒冰,张霞,刘积仁. 效用驱动的多agent合作机制[J]. 通信学报, 2013, 34(7): 124-133.

Han-bing DENG,Xia ZHANG,Ji-ren LIU. Cooperation mechanism of multi-agent system driven by utility[J]. Journal on Communications, 2013, 34(7): 124-133.

图/表 10

图1

表1

表2

图2

图3

图4

表3

图5

表4

图6

参考文献 20

[1]	WOOLDRIDGE M . An Introduction to Multi agent System[M]. West Sussex: John Wiley ＆Sons Ltd, 2002.
[2]	BELLIFEMINE F , CALRE G , GREENWOOD D . Developing Mul-ti-agent Systems with JADE[M]. 2007.
[3]	SICHMAN J , DEMAZEAU Y . Exploiting social reasoning to with agency level inconsistency[A]. Proceedings of the 1st Interna-tional Conference on Multi-agent Systems (ICMAS-95)[C]. San Fran-cisco, USA, 1995. 352-359.
[4]	SICHMAN J . A social reasoning mechanism based on dependence net-works[A]. Proceedings of the 11th European Conference Artificial Intelligence (ECAI-94)[C]. Amsterdam, Netherlands, 1994. 188-192.
[5]	MILCH B , KOLLER D . Probabilistic models for agents'beliefs and decisions[A]. Proceedings of the 16th on Uncertainty i Artificial In-telligence (UAI-00)[C]. Stanford, California, 2000. 389-396.
[6]	PANZARASA P , JENNINGS N R . Social mental shaping: mode ling the impact of sociality on the mental states of autonomous agents[J]. Computation Intelligence, 2001,17(4):738-782.
[7]	PLOTKIN T K . Algorithms of distributed task allocation for coopera-tive agents[J]. Theoretical Computer Science, 2000,242(1-2):1-27.
[8]	POLLACK M E . In Intentions in Communication[M]. Cambridge:MIT Press, 1990.
[9]	SURYADI D , GMYTRASIEWICZ P J . Learning models of other agents using influence diagrams[A]. Proceedings of 7th International Confe-rence on User Modeling (UM-99)[C]. Banff, Canada, 1999. 223-232.
[10]	WOOLDRIDGE M , JENNINGS N R . Formalizing the cooperative problem solving process[A]. Proceedings of the 13th In national Workshop on Distributed Artificial Intelligence (IWDAI-94)[C]. Lake Quinalt, WA, 1998. 403-417.
[11]	HADDADI A S . Communication and cooperation in agent system: a pragmatic theory[A]. Lecture Notes in Artificial Intelligence and Lec-ture Notes in Computer Science[C]. New York: Springer-Verlag Inc, USA, 1996. 1-134.
[12]	DUNIN-KEPLICZ B , VERBRUGGE R . Collective intentions[A]. Proceedings of the 2th International Conference on Multi-agent Sys-tem[C]. Menlo Park, California, 1996. 56-63.
[13]	CASTELFANCHI C . From individual intentions to groups and organ-izations[A]. Proceedings of the 1th International Conference on Multi agent System[C]. San Francisco, USA, 1995. 34-40.
[14]	ZLOTKIN G , ROSENSCHEIN J S . A domain theory for task oriental negotiation[A]. Proceedings of the 13th International Joint Conference on Artificial Intelligence[C]. California, USA, 1993. 416-423.
[15]	MATSUBAYASHI K , TOKORO M . A collaboration mechanism on positive interactions in multi-agent environment[A]. Proceedings of the 13th International Joint Conference on Artificial ntelligence[C]. California, USA, 1993. 345-351.
[16]	BARBER T , LIU H , HAN D C . agent-Oriented Design[M]. Austin:The University of Texas, 1999.
[17]	WOOLDRIDGE M , JENNINGS N R , KINNY D . A methodology for agent-oriented analysis and design[A]. Proceedings of the 6th National Conference on Artificial Intelligence (AAAI-99)[C]. Orlando, FL, 1999. 153-162.
[18]	PANZARASA P , JENNINGS N R . Formalizing collaborative deci-sion-making and practical reasoning in multi-agent systems[J]. Journal of Computation, 2002,12(1):55-117.
[19]	SHEHORY O , KRAUS S . A kernel-oriented model for coalition for-mation in general environments: implementation and res lts[A]. Pro-ceedings of the 3th National Conference on Artificial ntelligence (AAAI-96)[C]. Anaheim, CA, 1996. 715-723.[20] Java agent development framework (JADE)[EB/OL].
[20]	Java agent development framework (JADE)[EB/OL].

依赖关系	不合作(N,N)	单向合作(C,N)/(N,C)	双向合作(C,C)
独立	是	否	否
单向依赖	否	是	否
相互依赖	否	否	是
交互依赖	否	是	是

合作方式	agent i	agent j
不合作	cost(i,t) ＞punish (i,t)≥0cashI＞punish (i,t) –cost(i,t)	cost(j,t) ＞punish (j,t)≥0cashJ＞punish (j,t) –cost(j,t)
单向合作	cashI＜ –cost(i,t)cost(i,t) ＜ 0≤punish(i,t)	cashJ＜ 0
双向合作	cashI＜ –cost(i,t)	cashJ＜ –cost(j,t)
双向合作	≥ 或≤(,) ＞ (,) 0 (,) ＜ 0 (,) cost i t punish i t cost i t punish i t	≥ 或≤(,) ＞ (,) 0 (,) ＜ 0 (,) cost j t punish j t cost j t punish j t

组数	cash(i,t_i)	cash(i,t_i')	(i, '- ) cash t_it_i	cost(i,t)	(,) pu-nish i t
组1	1.1t_i	't_i	’-t_it_i	0.2t	0.1t
组2	1.1t_i	't_i	’-t_it_i	-0.2t	0.1t
组3	1.5t_i	't_i	’-t_it_i	0.2t	0.1t

测评参数	无合作	随机合作	效用合作
个数agent	10	10	10
运行时间/min	10	10	10
任务总量	447	438	445
完成总量	192	326	364
完成比例	42.95%	74.42%	81.79%
单效率agent	1.9/min	3.3/min	3.6/min