关键词: 多Agent系统 联盟结构 任务 势结构

Abstract:

Coalition formation is a key topic in multi-agent systems. At present, most work on coalition structure generation has concentrated on simple characte ristic 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  h 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 coali  ition structures in depth and presents the smaller granularity of searching（task-based cardinality structure）. Then we presents a new anytime algorith
          hm 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.

Key words: multi-agent system, coalition structure, task, cardinality structure