约束条件下联盟生成研究进展  

Research progress of constrained coalition formation

作　　者：任子仪 童向荣 REN Ziyi;TONG Xiangrong(School of Computer and Control Engineering,Yantai University,Yantai 264005,China)

机构地区：[1]烟台大学计算机与控制工程学院

出　　处：《智能系统学报》2019年第3期413-422,共10页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学基金项目(61572418);山东省科技发展计划项目(2016GGX109004)

摘　　要：联盟生成是在多 Agent系统的研究中最为重要的挑战之一。如何对 Agent进行划分使所得社会福利最大化是当前面临的主要问题。假设每个 Agent都具有理性和自利性的特性,为了追求自身的利益最大化而选择和其他的 Agent进行联合,进而使整个系统实现利益的最大化。目前,联盟生成问题有很大的计算挑战,即使在进行联盟的时候添加了约束条件,也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下的联盟生成的研究进行综述,主要包括 4部分:最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、联盟生成求近似最优解和约束条件下联盟生成求最优解。Coalition formation is one of the most important challenges in the research of multiagent systems.Currently,our main problem is how to divide Agent to maximize the social welfare.We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests.An Agent integrates with another Agent,which also maximizes the interest of the whole system.At present,the coalition formation problem presents notable computational challenges.If constraints are added during the coalition process,new algorithms are needed to solve the problem more rapidly and effectively.This paper mainly summarizes the study of coalition structure generation under constraint conditions.This paper comprises four parts:the coalition structure generation with the worst case guaranteed,the use of the dynamic programming to find the exact optimal solution,the near-optimal solution after formation of the coalition structure,and the optimal solution to the constrained coalition formation.

关 键 词：联盟结构 社会福利 联盟生成 约束条件 特征函数 联盟结构图 联盟博弈 动态规划 

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