第3卷第2期 智能系统学报 Vol.3№2 2008年4月 CAAI Transactions on Intelligent Systems Apr.2008 动态影响图模型研究 俞奎2，王浩2姚宏亮2 (1.常州纺织服装职业技术学院，江苏常州213164；2.合肥工业大学计算机与信息学院，安徽合肥230009) 摘要：部分可观察马尔可夫决策过程在策略空间和状态空间上的计算复杂性，使求解其一个最优策略成为NP hard难题.为此，提出一种动态影响图模型来建模不确定环境下的Agent动态决策问题.动态影响图模型以有向无 环图表示系统变量之间的复杂关系.首先，动态影响图利用动态贝叶斯网络表示转移模型和观察模型以简化系统的 状态空间：其次，效用函数以效用结点的形式清晰地表示出来，从而简化系统效用函数的表示；最后，通过决策结点 表示系统的行为来简化系统的策略空间.通过实例从3个方面和POMDP模型进行了比较研究的结果表明，动态影 响图模型为大型的POMDP问题提供了一种简明的表示方式，最后在Ro bocup环境初步验证了该模型. 关键词：动态贝叶斯网络；影响图，马尔可夫决策过程；部分可观察马尔可夫决策过程，动态影响图 中图分类号：TP181文献标识码：A文章编号：1673-4785(2008)02-015908 A dynamic influence diagram for dyna mic decision processes YU Kui'2,WANG Hao2,YAO Hong-liang' (1.Department of Computer Science,Institute of Textile and Garment of Changzhou,Changzhou 213164,China;2.School of Computer and Information,Hefei University of Technology,Hefei 230009,China) Abstract:Computational complexities in strategy space and state space make the partially observable Mark- ov decision process(POMDP)an NP-hard problem.Therefore,in this paper,a dynamic influence diagram is proposed to model the decisionmaking problem with a single agent,in which a directed acyclic diagram is used to express the complex relationships between systematic variables.Firstly,a dynamic Bayesian net- work is used to represent the transition and observation models so as to reduce the state space of the sys- tem.Secondly,in order to reduce the representational complexity of the utility function,it is expressed in terms of utility nodes.Finally,the actions of the system are represented with decision nodes to simplify the strategy space.The dynamic influence diagram is compared with the POMDP using these three as- pects.Our research indicates that a dynamic influence diagram provides a simple way to express POMDP problems.Experiments in the Robocup environment verified the effectiveness of the proposed model. Key words:dynamic Bayesian networks;influence diagrams;Markov decision process;partially observable Markov decision process;dynamic influence diagram 动态决策问题是人工智能领域研究的中心问题 POMDP通过从环境中获得的观察来感知环境的状 之一.马尔可夫决策过程I(Markov decision 态.因此POMDP更适合不确定情形下动态决策问 process,MDP)和部分可观察马尔可夫决策过程I 题的建模.求解POMDP的算法通常是把POMDP (partially observable Markov decision process, 转换为一个连续状态下的MDP求解.Kaelbling等 POMDP)是研究动态决策问题的有效模型.MDP 人给出了求解POMDP的精确求解算法1，由于信 所假设的是Aget能够确切获知环境的状态. 度状态MDP(belief MDP)是一个连续状态的模型， 策略空间和状态空间的复杂性呈指数级增长，算法 收稿日期：2007-0620. 基金项目：国家自然科学基金资助项目(60575023,60705015)；安徽 实际上不可行.因此许多研究者提出了POMDP的 省自然科学基金资助项目(070412064). 近似求解算法).实际上对于离散的POMDP,求 通讯作者：俞奎.Email:ykui713@hotmail.com 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3 卷第 2 期 智 能 系 统 学 报 Vol. 3 №. 2 2008 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2008 动态影响图模型研究 俞 奎1 ,2 ,王 浩2 ,姚宏亮2 (1. 常州纺织服装职业技术学院 ,江苏 常州 213164 ;2. 合肥工业大学 计算机与信息学院 ,安徽 合肥 230009) 摘 要 :部分可观察马尔可夫决策过程在策略空间和状态空间上的计算复杂性 ,使求解其一个最优策略成为 NP2 hard 难题. 为此 ,提出一种动态影响图模型来建模不确定环境下的 Agent 动态决策问题. 动态影响图模型以有向无 环图表示系统变量之间的复杂关系. 首先 ,动态影响图利用动态贝叶斯网络表示转移模型和观察模型以简化系统的 状态空间 ;其次 ,效用函数以效用结点的形式清晰地表示出来 ,从而简化系统效用函数的表示 ;最后 ,通过决策结点 表示系统的行为来简化系统的策略空间. 通过实例从 3 个方面和 POMDP 模型进行了比较 ,研究的结果表明 ,动态影 响图模型为大型的 POMDP 问题提供了一种简明的表示方式 ,最后在 Robocup 环境初步验证了该模型. 关键词 :动态贝叶斯网络 ; 影响图 ; 马尔可夫决策过程 ; 部分可观察马尔可夫决策过程 ; 动态影响图 中图分类号 : TP181 文献标识码 :A 文章编号 :167324785 (2008) 0220159208 A dynamic influence diagram for dynamic decision processes YU Kui 1 ,2 , WAN G Hao 2 , YAO Hong2liang 2 (1. Department of Computer Science , Institute of Textile and Garment of Changzhou , Changzhou 213164 , China ;2. School of Computer and Information , Hefei University of Technology , Hefei 230009 , China) Abstract :Comp utational complexities in strategy space and state space make t he partially observable Mark2 ov decision process (POMDP) an N P2hard problem. Therefore , in t his paper , a dynamic influence diagram is propo sed to model t he decision2making problem wit h a single agent , in which a directed acyclic diagram is used to express t he complex relationship s between systematic variables. Firstly , a dynamic Bayesian net2 work is used to represent the transition and observation models so as to reduce t he state space of the sys2 tem. Secondly , in order to reduce t he representational complexity of t he utility f unction , it is exp ressed in terms of utility nodes. Finally , t he actions of the system are represented wit h decision nodes to simplify t he strategy space. The dynamic influence diagram is compared wit h t he POMDP using these t hree as2 pects. Our research indicates t hat a dynamic influence diagram provides a simple way to exp ress POMDP problems. Experiments in the Robocup environment verified t he effectiveness of t he proposed model. Keywords :dynamic Bayesian networks; influence diagrams ; Markov decision process; partially observable Markov decision process ; dynamic influence diagram 收稿日期 :2007206220. 基金项目 :国家自然科学基金资助项目 (60575023 ,60705015) ;安徽 省自然科学基金资助项目(070412064) . 通讯作者 :俞 奎. E2mail :ykui713 @hotmail. com. 动态决策问题是人工智能领域研究的中心问题 之一. 马 尔 可 夫 决 策 过 程[1 ] ( Markov decision process , MDP) 和部分可观察马尔可夫决策过程[ 2 ] ( partially observable Markov decision process , POMDP) 是研究动态决策问题的有效模型. MDP 所假设的是 Agent 能够确切获知环境的状态. POMDP 通过从环境中获得的观察来感知环境的状 态. 因此 POMDP 更适合不确定情形下动态决策问 题的建模. 求解 POMDP 的算法通常是把 POMDP 转换为一个连续状态下的 MDP 求解. Kaelbling 等 人给出了求解 POMDP 的精确求解算法[3 ] ,由于信 度状态 MDP(belief MDP) 是一个连续状态的模型 , 策略空间和状态空间的复杂性呈指数级增长 ,算法 实际上不可行. 因此许多研究者提出了 POMDP 的 近似求解算法[425 ] . 实际上对于离散的 POMDP ,求