第2期 俞奎，等：动态影响图模型研究 ·163* 般情况下，假设状态空间2，可用M个状态 MDP,因此其状态空间是连续的，POMDP的最优 变量表示，每个变量至多有S个状态和N个父结 值函数用分段线性凸函数表示，线性分段凸函数由 点.则利用条件独立性联合概率分布可用 一组a向量表示，如图4 O(M(S)参数，否则需要O(S“)个参数.假设M= 10,S=3,N=4,需要810个参数而不是5904900 个参数.下面考虑一个复杂一点的例子，如图3 D R 图42个状态的POMDP模型的值函数V: Fig.4 Value function VI'of POMDP for two states HC HC 根据定义，信状态度MDP模型是一个具有连 WC WC 续状态空间的模型，精确求解算法的复杂度非常高， COBS 以至于求解状态、动作和观察的集合元素超过10的 + 问题都非常困难6.一个重要的原因就是用来表示 最优值函数的线性分段凸函数，这种表示形式的复 图3一个动态影响图 杂度随着迭代的进行，增长得也非常得快.表示第 Fig.3 A example of DID i+l步值函数的a向量集的大小会在一步迭代后就 图3是一个动态影响图的例子，如果顾客想要 达到指数量级0(419)，这一步更新所需的 咖啡(want coffee,WC),并得到了咖啡(has coffee, 计算复杂度是0(0A川S219),其中I表示 HC机器人得到奖赏(reward,R),否则得到惩罚. 第1步值向量的数目，|9表示状态空间.如果假设 机器人如果在下雨(rain,R)的情况下穿过街道去 初始的值函数是线性的，那么经过次迭代后，第1 买咖啡(get coffee,GetC)的话，可能被淋湿(wet, 次值函数对应的向量集大小是0(44，即使 W),除非带伞(umbrella,U),当然机器人可以完成 对于简单的有限阶POMDP问题，求解最优策略的 其他的任务，详见文献[2].这里是一个简化的向前 时间复杂度也是PSPACE-hard问题.无限阶的问 看一步的动态影响图，图中只标出了时间片之间变 题求解则可能是不可计算的.一种解决办法是求解 量的关系.OBs是一组可观察变量，D,是决策（行 与最优解差距小于某个特定精度的近似解，但有时 为)结点.该例子有5个布尔型的状态变量：R、U、 即使是这样都是不可计算的).因此，大量的研究 W、HC、WC和一个决策变量D,U为效用结点，假 重点被放在寻找近似解的算法研究上，实际上求解 设1OBs=2,A=2 optimal策略也是NP-hard难题， 在图3中，S=2=32,10=2,|A=2,则 在DD中效用函数以效用结点的形式清晰地 POMDP模型需要的转移概率参数为S凶S× 表达出来，对于离散的DD模型，其变量的状态空 |4川=2048，观察模型需要的概率参数为1O1× 间仍然是离散的，避免了用分段线性凸函数表示效 |SA=128,这样使POMDP只适合处理小规 用函数.DD中的效用节点并不依赖所有的变量，通 模的问题.在DD模型中P(R',U',W,HC,WC个 常只由一部分变量决定.如图3，影响效用结点是 R.U.W.HC.WC.D)=P(RR)P(UU)P(W W、WC、HC,而与其他节点无关.这样大大简化了 R,U,W,D)P(HC1HCP(WCWC).这样就把 效用函数表示的复杂性，但其复杂性会随着其父节 整个系统变量的全联合分布转变成局部的概率分布 点的个数的增加而指数级的增加.但幸运的是由于 表示，图3中所需的转移概率参数转换为5个局部 父节点的个数总是有限的，又由定理2可知，效用函 概率表示，只需要40个参数，因此DD大大简化了 数的累加可分性可进一步分离效用函数，使每个效 系统的状态空间 用结点依赖于更小的一组状态和行为变量，如图5 3.2模型的值函数表示 在POMDP中，值函数被转化为与每个状态转 由于求解POMDP问题的算法通常把POMDP 移相联系的效用值.更改值函数可能需要对所有的 转换为一个连续状态下的MDP求解，即信度状态 转移和状态的回报函数重新构造.在DD中效用函 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net一般情况下 ,假设状态空间 Ωx 可用 M 个状态 变量表示 ,每个变量至多有 S 个状态和 N 个父结 点. 则 利 用 条 件 独 立 性 联 合 概 率 分 布 可 用 O( M ( S N ) ) 参数 ,否则需要 O( S M ) 个参数. 假设 M = 10 , S = 3 , N = 4 ,需要 810 个参数而不是 5 904 900 个参数. 下面考虑一个复杂一点的例子 ,如图 3. 图 3 一个动态影响图 Fig. 3 A example of DID 图 3 是一个动态影响图的例子. 如果顾客想要 咖啡(want coffee , W C) ,并得到了咖啡(has coffee , H C) 机器人得到奖赏 (reward , R) ,否则得到惩罚. 机器人如果在下雨 (rain , R) 的情况下穿过街道去 买咖啡 (get coffee , GetC) 的话 ,可能被淋湿 (wet , W ) ,除非带伞(umbrella , U) ,当然机器人可以完成 其他的任务 ,详见文献[ 2 ]. 这里是一个简化的向前 看一步的动态影响图 ,图中只标出了时间片之间变 量的关系. OBs 是一组可观察变量 , Dt 是决策 (行 为) 结点. 该例子有 5 个布尔型的状态变量 : R、U 、 W 、H C、W C 和一个决策变量 D , U 为效用结点 ,假 设| OBs| = 2 ,| A| = 2. 在图 3 中 ,| S | = 2 5 = 32 ,| O| = 2 , | A | = 2 ,则 POMDP 模型需要的转移概率参数为| S | ×| S | × | A| = 2 048 ,观察模型需要的概率参数为| O| × | S| ×| A| = 128 , 这样使 POMDP 只适合处理小规 模的问题. 在 DID 模型中 P( R′,U′, W′, H C′, W C′| R ,U , W , H C, W C , Dt) = P( R′| R) P(U′| U) P( W′| R ,U , W , Dt) P( H C′| H C) P ( W C| W C′) . 这样就把 整个系统变量的全联合分布转变成局部的概率分布 表示 ,图 3 中所需的转移概率参数转换为 5 个局部 概率表示 ,只需要 40 个参数 ,因此 DID 大大简化了 系统的状态空间. 3. 2 模型的值函数表示 由于求解 POMDP 问题的算法通常把 POMDP 转换为一个连续状态下的 MDP 求解 ,即信度状态 MDP ,因此其状态空间是连续的 ,POMDP 的最优 值函数用分段线性凸函数表示 ,线性分段凸函数由 一组 a 向量表示 ,如图 4. 图 4 2 个状态的 POMDP 模型的值函数 V 3 1 Fig. 4 Value function V 3 1 of POMDP for two states 根据定义 ,信状态度 MDP 模型是一个具有连 续状态空间的模型 ,精确求解算法的复杂度非常高 , 以至于求解状态、动作和观察的集合元素超过 10 的 问题都非常困难[ 6 ] . 一个重要的原因就是用来表示 最优值函数的线性分段凸函数 ,这种表示形式的复 杂度随着迭代的进行 ,增长得也非常得快. 表示第 i + 1步值函数的 a 向量集的大小会在一步迭代后就 达到指数量级 O (| A | | Гi | | Ω| ) ,这一步更新所需的 计算复杂度是 O( (| A| | S| 2 | Гi | | Ω| ) ,其中| Гi | 表示 第 i 步值向量的数目 , | Ω| 表示状态空间. 如果假设 初始的值函数是线性的 ,那么经过 i 次迭代后 ,第 i 次值函数对应的向量集大小是 O (| A | | Ω| i - 1 ,即 使 对 于简单的有限阶 POMDP 问题 ,求解最优策略的 时间复杂度也是 PSPACE2hard 问题. 无限阶的问 题求解则可能是不可计算的. 一种解决办法是求解 与最优解差距小于某个特定精度的近似解 ,但有时 即使是这样都是不可计算的[7 ] . 因此 ,大量的研究 重点被放在寻找近似解的算法研究上 ,实际上求解 ε2optimal 策略也是 NP2hard 难题. 在 DID 中效用函数以效用结点的形式清晰地 表达出来 ,对于离散的 DID 模型 ,其变量的状态空 间仍然是离散的 ,避免了用分段线性凸函数表示效 用函数. DID 中的效用节点并不依赖所有的变量 ,通 常只由一部分变量决定. 如图 3 ,影响效用结点是 W 、W C、H C ,而与其他节点无关. 这样大大简化了 效用函数表示的复杂性 ,但其复杂性会随着其父节 点的个数的增加而指数级的增加. 但幸运的是由于 父节点的个数总是有限的 ,又由定理 2 可知 ,效用函 数的累加可分性可进一步分离效用函数 ,使每个效 用结点依赖于更小的一组状态和行为变量 ,如图 5. 在 POMDP 中 ,值函数被转化为与每个状态转 移相联系的效用值. 更改值函数可能需要对所有的 转移和状态的回报函数重新构造. 在 DID 中效用函 第 2 期 俞 奎 ,等 :动态影响图模型研究 · 361 ·