任一时间面向任务联盟结构生成算法  

An Anytime Coalition Structure Generation in Task-Based Settings

作　　者：骆剑彬[1] 胡山立[1] 苏射雄[1] 林耀海[1,2] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002 [2]福建农林大学计算机与信息学院,福建福州350002

出　　处：《计算机工程与科学》2008年第12期85-89,共5页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60573076)

摘　　要：联盟形成是多Agent系统中的一个关键问题。目前,大多数学者都在CFG下研究联盟结构生成问题。然而,在很多实际应用中,联盟的形成往往是为了完成任务集中某些任务。但是,在CFG中并没有把联盟和任务一起考虑。显然,加入任务后,问题将变得更复杂。Dang等人已经证明,这是个NP难问题,并且要建立最坏情况下的限界K(n,m),搜索面向任务联盟结构集合L1、L2(除{(A,Φ),(Φ,T)})是必要且充分的,接着提出一个限界具有保证的任一时间算法。本文深刻分析了面向任务联盟结构间的关系,引入更小的搜索粒度(面向任务势结构),提出一种新的任一时间搜索算法;在搜索完最小搜索之后,进一步搜索CTS集合CTS(n,m,b)对应的部分面向任务联盟结构,渐进给出越来越低的限界,大大改进了Dang等人的工作。Coalition formation is a key topic in multi-agent systems. At present, most work on coalition structure generation has concentrated on simple characteristic function games（CFGs）. However, in many practical applications, it is often the case that a coalition is formed in order to perform some tasks. But in CFGs this connection between coalitions is absent. The notion of tasks generally increases the complexity of the problem. Dang et al. has shown that the problem is N-P-hard and it suffices to search the set of task-based coalition structure（except { （A, Φ）, （Φ, T）}） in order to establish a worst- case bound K（n, m） ,and has presented an anytime algorithm with bound guarantee. This paper analyzes the relations a- mong task-based coalition structures in depth and presents the smaller granularity of searching（task-based cardinality structure）. Then we presents a new anytime algorithm based on the cardinality structure that only has to take a step further and search those task-based coalition structures whose cardinality structure is in the CTS （n, m, b）. Consequently, the algorithms reported in this paper are obviously better than that of Dang et al.

关 键 词：多AGENT系统 联盟结构 任务 势结构 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]