联盟结构图的性质及应用  

Properties and Application of Coalition Structure Graph

作　　者：刘惊雷[1] 张伟[1] 刘兆伟[1] 孙雪姣[1] 

机构地区：[1]烟台大学计算机学院,山东烟台264005

出　　处：《计算机研究与发展》2011年第4期602-609,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60496323);山东省自然科学基金项目(Y2007G56)

摘　　要：形成有效的联盟是多Agent系统的一个重大课题.然而联盟结构的数目很大,对于包含n个Agent系统来说,其可能构成的联盟结构是O(nn),以至于通过穷举搜索最优联盟结构是不可能的.另外联盟结构空间是一个什么样的形态,这是目前为止很少有人系统研究的课题,尤其是其图性质的研究.从图的视点讨论多Agent系统中的最优联盟结构生成问题.首先将联盟结构空间抽象为一个联盟结构图,其中顶点代表联盟结构,有向边代表联盟结构的分解.随后总结和形式化该联盟结构图所具有的两个性质:最优子结构、重复子结构问题;推广了一个性质:关键搜索集;给出了一个新性质:较少冗余路径的图的连通性.为了理解联盟结构图的这些性质,将这些性质用到了有效动态规划法(effectivedynamic programming,EDP)中,分析得到其时间复杂度的下界是Ω(2.1n),上界是O(3n).实验分析表明,EDP算法比DP算法的搜索次数更少,在含有21个Agent的系统中,EDP比DP减少42%的搜索次数.Forming effective coalitions is a major research challenge in the field of multi-agent systems.The coalition structure generation problem is extremely challenging due to the exponential number of partitions that need to be examined.But what kind of appearance the space of coalition structure is,there is few people to research on it,particularly its graph properties.Optimal coalition structure generation problem is discussed from the viewpoint of graph theory.Firstly,the space of coalition structure is taken as a coalition structure graph,the vertex in which stands for coalition structure,the edge in which stands for splitting of coalition structure.Soon after two graph properties： optimal substructure,overlapping sub-structure,are summed up,one property： the key searching set is extended,and a new graph property： connectivity of graph with few redundancy paths is given.In order to understand and apply these properties,we devise an effective dynamic programming（EDP） algorithm to search the optimal coalition structure.In addition,we prove that the lower bound of EDP is Ω（2.1n）,and the upper bound is O（3n） in theory.Finally,empirical evaluation shows that the searching number of EDP algorithm is lower 42% than those of DP,when involving 21 agents.

关 键 词：最优联盟结构 联盟结构图的性质 关键搜索集 较少冗余路径的图的连通性 EDP算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]