联盟结构图的性质及应用

• 作者: 刘兆伟 刘惊雷 孙雪姣 张伟
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 最优联盟结构 联盟结构图的性质 关键搜索集 较少冗余路径的图的连通性 EDP算法
• 年，卷（期）: 2011,（4）
• 所属期刊栏目: 人工智能
• 页码范围: 602-609
• 分类号: TP18
• 字数: 6857字
• 语种: 中文

摘要

形成有效的联盟是多Agent系统的一个重大课题.然而联盟结构的数目很大,对于包含n个Agent系统来说,其可能构成的联盟结构是O(nn),以至于通过穷举搜索最优联盟结构是不可能的.另外联盟结构空间是一个什么样的形态,这是目前为止很少有人系统研究的课题,尤其是其图性质的研究.从图的视点讨论多Agent系统中的最优联盟结构生成问题.首先将联盟结构空间抽象为一个联盟结构图,其中顶点代表联盟结构,有向边代表联盟结构的分解.随后总结和形式化该联盟结构图所具有的两个性质:最优子结构、重复子结构问题;推广了一个性质:关键搜索集;给出了一个新性质:较少冗余路径的图的连通性.为了理解联盟结构图的这些性质,将这些性质用到了有效动态规划法(effective dynamic programming,EDP)中,分析得到其时间复杂度的下界是Ω(2.1n),上界是O(3n).实验分析表明,EDP算法比DP算法的搜索次数更少,在含有21个Agent的系统中,EDP比DP减少42%的搜索次数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘惊雷	烟台大学计算机学院	63	262	8.0	13.0
2	张伟	烟台大学计算机学院	40	377	12.0	18.0
3	刘兆伟	烟台大学计算机学院	11	12	3.0	3.0
4	孙雪姣	烟台大学计算机学院	16	35	3.0	5.0