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

联盟形成是多Agent系统中的一个关键问题。目前，大多数学者都在CFG下研究联盟结构生成问题。然而，在很多实际应用中，联盟的形成往往是为了完成任务集中某些任务。但是，在CFG中并没有把联盟和任务一起考虑。显然，加入任务后，问题将变得更复杂。Dang等人已经证明，这是个NP难问题，并且要建立最坏情况下的限界K（n，m），搜索索面向任务联盟结构集合L1、L2（除{（A，Φ），（Φ，T）}）是必要且充分的，接着提出一个限界具有保证的任一时间算法。本文深刻分析了面向任务联盟结构间的关系，引入更小的搜索粒度（面向任务势结构），提出一种新的任一时间搜索算法；在搜索完最小搜索之后，进一步搜索CTS集合CTS（n，m，b）对应的部分面向任务联盟结构，渐进给出越来越低的限界，大大改进了Dang等人的工作。

An Anytime Coalition Structure Generation in Task-Based Settings

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.