交互式动态影响图研究及其最优K模型解法

• 作者: 曾一锋 潘颖慧
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 多智能体系统 影响图 序贯决策问题 行为等价
• 年，卷（期）: 2018,（1）
• 所属期刊栏目: 人工智能
• 页码范围: 28-46
• 页数: 19页
• 分类号: TP18
• 字数: 16197字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.00028

摘要

不确定性多智能体序贯决策是人工智能研究领域一个重要的研究问题,主要求解智能体如何在与其他智能体的交互中优化本身的决策.特别在部分可观测的随机博弈设置下,智能体不能探测到真实的外部环境状态,必须依靠所接收的观察来推断可能的状态;同时,智能体的动作也具有相当的随机性,直接影响到其他智能体的决策.智能体的交互主要通过对共同环境状态的影响决定它们各自决策的报酬.因此,如何对多智能体之间的交互进行建模是求解该问题的核心任务.目前大部分的研究主要通过对整个智能体系统进行建模,采取集中规划、分散控制的求解机制:首先,统一计算所有智能体的联合决策;然后,各个智能体执行分配得到的局部决策.该求解技术往往要求所有的智能体必须对全局环境有一个共同的知识假设,因此该研究工作一般只适用于合作型的多智能体系统.相比之下,交互式动态影响图是从个体决策者的角度研究不确定性多智能体序贯决策问题的一种普遍适用的建模方法,克服了传统的博弈论方法求解多智能体决策问题的局限性.求解交互式动态影响图模型的主要困难在于复杂的智能体相互建模过程.特别是在竞争的环境下,由于智能体缺少相互交流的机会,也不能预知其他智能体的真实模型,必须通过预测和推理其他智能体的行为来决定本身的动作.主要求解思路是首先假设其他智能体的可能模型,然后通过求解这些可能的模型来预测智能体的行为.由于其他智能体的备选模型往往有很多,而且随着决策时间的推移,模型的不确定性增强,导致可能的模型呈指数增长,这给求解交互式动态影响图带来了极大的困难.基于目前大量的交互式动态影响图研究工作,文中旨在总结归纳模型的具体表达方式和求解方法,并在此基础上提出一种新的模型求解方法.针对巨大的其他智能体备选模型空间,新方法侧重于研究模型的选取技术,把模型选取问题转化为一个构造最优K模型的函数优化问题.优化的目标是尽量使得选取的K个模型能在最大程度上覆盖整个其他智能体的模型空间.从本质上说,新的函数优化问题具有NP难度.文中通过挖掘目标函数的单调子模特性提出一种贪婪算法以迅速求解该优化问题,并在理论上保证了解的质量.此外,新的求解方法克服了目前近似方法的随机性和参数设置的复杂性.该方法在一个经典计算机游戏领域得到了大量的实验验证,展示了较强的实际应用能力.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曾一锋	厦门大学自动化系	3	4	1.0	1.0
2	潘颖慧	江西财经大学信息管理学院	1	1	1.0	1.0