一种基于势结构分组思想的任一时间联盟结构生成

摘要：

联盟形成是多agent系统中的一个关键问题,找到最优的联盟结构是NP-完全的.Sandholm和Larson等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能完全解决的问题.在任务分配等实际问题中,不同联盟存在同势同值的特征,或同势的2个联盟的值相差不大.研究了最优势结构生成问题,分析了基于势结构的分组思想,并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法.算法在最小搜索之后给出进一步降低限界至2的搜索,也讨论了限界从2降到1的过程中由底向上的补充搜索.从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法,是基于势结构的联盟生成问题的一个重要进展.

关键词：多agent系统、联盟结构、势结构、任一时间、分组

所属期刊栏目：48

分类号：TP18(自动化基础理论)

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

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：2047-2054