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

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

单位：福州大学计算机科学与技术系 福建福州350002 福建农林大学计算机与信息学院 福建福州350002