·160· 智能系统学报 第3卷 解一个最优策略是PSPACE-complete难题l;求解 状态s采用a动作使环境状态转移到s的概率 &optimal策略是NP-hard难题).状态空间、值函 MDP模型所假设的是Agent能够确切获知环境的 数和策略表示的复杂性是造成求解POMDP问题 状态 的主要难点」 POMDP不要求Agent事先了解身处环境的状 本文在动态贝叶斯网络和影响图的基础上提出 态，而是通过从环境中获得的观察来感知环境的状 一种动态影响图(dynamic influence diagram,DD) 态.POMDP模型的定义如下： 模型来建模不确定环境下的Agent动态决策问题， POMDP由六元组<S,A,T,R,Z,G定义 以解决POMDP模型不能有效求解复杂的动态决 其中)S:环境状态的有限集合；2A:动作的有限 策问题.DD是一个有向无环图，用DBN表示转移 集合；3)T:S×A→WS);其中《S)为状态的分 模型和观察模型，用效用节点表示效用函数，决策节 布，在某一状态s执行动作a后，下一个状态s的概 点表示系统的行为，这样DD利用图模型蕴涵的条 率分布，一般用T(s,a,s)表示：4)R:S*A→R:报 件独立性简洁表示了系统中变量之间的复杂关系. 酬函数，表示在状态s执行动作a所能获得的报酬， 动态贝叶斯网络s](dynamic bayesian net~ 也用R(s,ad表示：5)Z:观察的有限集合，即系统可 works,DBN)是贝叶斯网络的一种扩展模型，是对 以感知的世界状态集合：6)O:S*A一→爪☑；其中 具有随机过程性质的不确定性问题进行建模的一种 T☑为观察的分布.观察函数，表示系统在采取动 有力的工具.由于DBN没有决策节点，DBN不易处 作a转移到状态s时，观察函数O确定其在可能观 理Agent的决策问题. 察上的概率分布，记为O(s',a,o 影响图I)(influence diagrams,D)是贝叶斯网 p(b,a =>R(s,a b(s) 络的另一种扩展模型，影响图可以同贝叶斯网络一 由于POMDP问题最优策略学习转变为“信度 样，表示多变量之间的复杂关系：另外，由于其结合 状态MDP”(belief MDP)最优策略的学习，造成一 了效用理论，因而比贝叶斯网络更适合处理Agent 个严重的问题就是由于其状态空间是连续的，值函 决策.它虽然在贝叶斯网络基础上结合了效用理论， 数、策略表示和状态空间的复杂性使求解POMDP 但不易表示和处理动态的决策问题 是一个NP-hard难题， DD将DBN简洁的表示动态领域知识的能力 因此针对状态空间和值函数表示的复杂性， 和影响图具有的决策能力有机地结合起来，使DD Boutilier和Poole把因式MDP扩展应用到POM 从状态空间、值函数的表示和策略空间3个方面降 DP模型中，提出了因式POMDP(factored POM- 低了求解动态决策问题的复杂性 DP)I.因式POMDP利用动态贝叶斯网络来表示 1)DBN表示DD的转移模型和观察模型.DD 转移模型和观察模型，用决策树或代数决策图来表 利用DBN蕴涵的条件独立性和稀疏性简化系统的 示转移概率和值函数.由于POMDP模型的值函数 状态空间； 是分段线性凸函数，随着状态空间的增长，表示值函 2)效用函数用效用结点的形式清晰地表示出 数的决策树或代数决策树的数目会指数级的增长」 来，简化系统的效用函数的表示； 因此，因式POMDP仍然不能有效处理大型的 3)DD中的决策结点表示系统的行为，一个决 POMDP的最优决策问题 策节点只和少数几个状态变量相联系，简化系统的 在Boutilier等人研究的基础上，把动态贝叶斯 策略空间 网络和影响图结合，提出动态影响图(dynamic in 研究表明DD为大型的POMDP问题提供了 fluence diagram,DD)模型来建模不确定环境下的 一种简明的表示方式 Agent动态决策问题，以解决复杂情况下的动态决 1 POMDP模型 策问题 MDP是表示和处理单个Agent动态决策问题 2动态影响图模型 的主要模型.MDP由四元组<S,A,R,T>定义，S 2.1动态影响图模型的表示 是一个环境状态集，A表示系统行为集合，奖赏函数 动态影响图可以定义成一个二元组<B, R:SXA→R和状态转移函数T:S X4-PD(S.记 B。>,其中B,表示t时刻的影响图，B。=(E,Vs), R(s,a,s)为系统在状态s采用a动作使环境状态 其中E,表示连接B,和B1的有向边，Vs表示E: 转移到s获得的瞬时奖赏值，记T(s,a,s)为系统在 所连接的顶点的集合.动态影响图结点集合V= 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net解一个最优策略是 PSPACE2complete 难题[6 ] ;求解 ε2optimal 策略是 NP2hard 难题[7 ] . 状态空间、值函 数和策略表示的复杂性是造成求解 POMDP 问题 的主要难点. 本文在动态贝叶斯网络和影响图的基础上提出 一种动态影响图(dynamic influence diagram , DID) 模型来建模不确定环境下的 Agent 动态决策问题 , 以解决 POMDP 模型不能有效求解复杂的动态决 策问题. DID 是一个有向无环图 ,用 DBN 表示转移 模型和观察模型 ,用效用节点表示效用函数 ,决策节 点表示系统的行为 ,这样 DID 利用图模型蕴涵的条 件独立性简洁表示了系统中变量之间的复杂关系. 动态 贝 叶 斯 网 络[8 ] ( dynamic bayesian net2 works , DBN) 是贝叶斯网络的一种扩展模型 ,是对 具有随机过程性质的不确定性问题进行建模的一种 有力的工具. 由于 DBN 没有决策节点 ,DBN 不易处 理 Agent 的决策问题. 影响图[9 ] (influence diagrams , ID) 是贝叶斯网 络的另一种扩展模型 ,影响图可以同贝叶斯网络一 样 ,表示多变量之间的复杂关系 ;另外 ,由于其结合 了效用理论 ,因而比贝叶斯网络更适合处理 Agent 决策. 它虽然在贝叶斯网络基础上结合了效用理论 , 但不易表示和处理动态的决策问题. DID 将 DBN 简洁的表示动态领域知识的能力 和影响图具有的决策能力有机地结合起来 ,使 DID 从状态空间、值函数的表示和策略空间 3 个方面降 低了求解动态决策问题的复杂性. 1) DBN 表示 DID 的转移模型和观察模型. DID 利用 DBN 蕴涵的条件独立性和稀疏性简化系统的 状态空间 ; 2) 效用函数用效用结点的形式清晰地表示出 来 ,简化系统的效用函数的表示 ; 3) DID 中的决策结点表示系统的行为 ,一个决 策节点只和少数几个状态变量相联系 ,简化系统的 策略空间. 研究表明 DID 为大型的 POMDP 问题提供了 一种简明的表示方式. 1 POMDP 模型 MDP 是表示和处理单个 Agent 动态决策问题 的主要模型. MDP 由四元组 < S , A , R , T > 定义 , S 是一个环境状态集 , A 表示系统行为集合 ,奖赏函数 R : S ×A →R 和状态转移函数 T : S ×A →PD ( S) . 记 R (s, a , s′) 为系统在状态 s 采用 a 动作使环境状态 转移到 s′获得的瞬时奖赏值;记 T (s, a ,s′) 为系统在 状态 s 采用 a 动作使环境状态转移到 s′的概率. MDP 模型所假设的是 Agent 能够确切获知环境的 状态. POMDP 不要求 Agent 事先了解身处环境的状 态 ,而是通过从环境中获得的观察来感知环境的状 态. POMDP 模型的定义如下[2 ] : POMDP 由六元组 < S , A , T , R , Z , О> 定义. 其中 :1) S :环境状态的有限集合; 2) A :动作的有限 集合;3) T : S ×A →П( S) ;其中 П( S) 为状态的分 布 ,在某一状态 s 执行动作 a 后 ,下一个状态 s′的概 率分布 ,一般用 T (s, a , s′) 表示; 4) R : S 3 A →R;报 酬函数 ,表示在状态 s 执行动作 a 所能获得的报酬 , 也用 R (s, a) 表示;5) Z :观察的有限集合 ,即系统可 以感知的世界状态集合; 6) O : S 3 A →П( Z) ;其中 П( Z) 为观察的分布. 观察函数 ,表示系统在采取动 作 a 转移到状态 s′时 ,观察函数 О确定其在可能观 察上的概率分布 ,记为 O(s′, a , o) . p ( b, a) = s∑∈S R (s, a) b(s) . 由于 POMDP 问题最优策略学习转变为“信度 状态 MDP”( belief MDP) 最优策略的学习 ,造成一 个严重的问题就是由于其状态空间是连续的 ,值函 数、策略表示和状态空间的复杂性使求解 POMDP 是一个 NP2hard 难题. 因此针对状态空间和值函数表示的复杂性 , Boutilier 和 Poole 把因式 MDP 扩展应用到 POM2 DP 模型中 ,提出了因式 POMDP (factored POM2 DP) [10 ] . 因式 POMDP 利用动态贝叶斯网络来表示 转移模型和观察模型 ,用决策树或代数决策图来表 示转移概率和值函数. 由于 POMDP 模型的值函数 是分段线性凸函数 ,随着状态空间的增长 ,表示值函 数的决策树或代数决策树的数目会指数级的增长. 因此 , 因式 POMDP 仍然不能有 效处理大 型的 POMDP 的最优决策问题. 在 Boutilier 等人研究的基础上 ,把动态贝叶斯 网络和影响图结合 ,提出动态影响图 ( dynamic in2 fluence diagram , DID) 模型来建模不确定环境下的 Agent 动态决策问题 ,以解决复杂情况下的动态决 策问题. 2 动态影响图模型 2. 1 动态影响图模型的表示 动态影响 图 可以定 义成一个 二元组 < Bt , Bts > ,其中 Bt 表示 t 时刻的影响图 , Bts = ( Et ,V ts ) , 其中 Er 表示连接 B t 和 B t - 1 的有向边 , V ts 表示 Et 所连接的顶点的集合. 动态影响图结点集合 V = · 061 · 智 能 系 统 学 报 第 3 卷