计算机研究与发展

作者：王博,刘惊雷,

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

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

来源：2018年第8期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2018年第8期