布尔Game的核求解算法

摘要：

布尔Game是一种重要的多Agent合作求解框架,它利用命题逻辑来表达静态的Agent博弈场景.其中每个Agent的目标采用命题公式来表示,其目标是否满足取决于命题公式的赋值.目前布尔Game多从知识表示角度和纳什均衡计算的角度来研究,从联盟角度研究核的求解却不多,布尔Game 求核是生成策略组合然后在策略组合内对比的过程.首先,通过以布尔Game的决策变量为顶点、以目标为超边,构成布尔Game上的超图结构来求满足核的约束满足的解.其次,以Agent为顶点、以Agent 间的依赖关系为边构成的有向依赖图,可以将布尔Game根据稳定集分解为规模上更小的布尔Game.这2种结构简化了求核的生成过程和比较过程,进而在一定程度上提高了布尔Game求核效率.然后基于超图的超树分解和依赖图的稳定集分解,给出了不同的布尔Game的求核算法.最后实验验证了算法的有效性.

关键词：布尔Game、核求解、约束可满足问题、超图、超树分解、稳定集

所属期刊栏目：55

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

资助基金：国家自然科学基金项目61572419,61773331,61703360;山东省高等学校科技计划项目J17KA091

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

页数：共16页

页码：1735-1750