第1期 闫书亚，等：概率规划的研究与发展 ·17· Subject to:0≥Bmax(①.iw:·bCase,() [S3]的基础上使用决策表(decision diagrams)优化 ⊙（©-1wi·bCase,(y);HA,s. (5) MDPs.使用该方法，需要把PPDDL域及规划定义 对于FOAPI来说，策略迭代要求一个由值函 转化为ADDs-based MDP表示.在比赛中作者使 数vCase(s)得到的合适的一阶策略表示.假设有m 用CUDD包S4来处理ADDs和BDDs. 个参数化的动作{A1(x),…,Am(x)},则策略 状态空间分解(factorization)包含有二元状态 πCase(s)表示为 变量的向量积：S=⊙1”，，这些变量是每一个常量 Case(s)max(U B(vCase(s))).(6) 和目标的PPDDL参数化谓词的实例化，这样的变 式中：B:(vCase(s))表示可由任一实例化的动作 量使得在适当的时候可以处理一个状态集而不是单 A,(x)得到的值，max操作算子保证了将最大可能 一的一个状态.动作由实例化PPDDL参数化的动 值赋给每一个3. 作而得到.对于每一个动作，转移概率函数可以通 根据Guestrin等Isol提供的factored MDPs的 过动态贝叶斯网络(dynamic Bayesian network, 近似策略迭代方法，可通过计算权w的连续迭代 DBN)ISs表示.而该DBNs可被编码为ADDs!531 来一般化近似策略迭代方法到一阶MDPs的过程， 此外，文中的方法不仅运用了初始状态信息 其中，w”表示在第i次迭代中策略πCase(s)的 还运用了目标状态信息，以减少状态空间的搜索 不动点值函数的最优近似.在第1次迭代中通过执 它使用确定可达性分析(deterministic reachability 行下述2步完成：1)从当前值函数获得策略 analysis)来计算可达子空间，通过运用初始状态和 目标状态知识，在任一近似或最优动态规划计算之 Case(y,并用式⑥)获得权∑-1wo,bCase,(y: 前计算可达子空间.计算的首要一步是确定化所有 2)求解下述LP公式，该公式决定策略Case(的 的转移，然后高效的扩展从初始状态可达的那些状 最小近似值函数的贝尔曼误差的权： 态直到至少一个目标状态被到达，而不用记忆从初 Variables:wit1,…w': 始状态到目标状态的所有动作】 Minimize: 产生初始可达状态子空间W后，计算最大化到 Subject to: 达目标状态子空间G(GCW)的概率的策略，这样 中Case(s⊙©-1 bCase,(yJ 的策略称为安全随机路径策略(safest stochastic ⊙©-1w(B bCase(y1VA,s.(7) path policy),它最大化到达至少一个目标状态的概 基于FOALP的方法可能不适合所有的域，但 率.前述得到的策略不保证在整个状态空间上是最 在box-world逻辑域上它是高效的.其缺点是在当 优的，因为它只是在WCS中最优.为提高策略的 前的情况下，该方法只能处理带有全程量词回报值 质量，作者采用交替执行确定性可达分析和安全随 的情况。 机路径策略最优化这2个步骤.当策略在先前(pre 2.7基于sfDP的方法 vious)可达状态子空间上收敛时，循环结束」 Florent和Patrick提出了基于MDPs的随机 sDP在初始状态和目标状态知识上更加关注 规划器sfDP(symbolic focused dynamic program- 策略.试验结果标明，它在一定程度上还是比较有 ming)s,该规划器将PPDDL问题转化为因子 效的 MDPs问题(factored MDPs),并通过一个修改的 2.8基于API的方法 VI(structed modified)算法来求解，其中修改的VI S.W.Yoon,A.Fern和R.Givan提出了新 算法是基于从初始状态到目标状态的安全随机路径 的规划器56]，该规划器系统基于一种变化的近似 计算(safest stochastic path computation)的.在进 策略迭代算法(approximate policy iteration),它采 行规划求解时，1)通过使所有的转移确定化的方法 用归纳机器学习(inductive machine learning)和模 计算一个状态子空间，2)在当前策略下，交替执行 拟进行策略改进.给定一个规划域，系统迭代改进 在当前可达的状态子空间上运用修改的VI算法和 当前找到的最优策略直到策略不再被改进或超过一 进行可达状态空间的扩展 定的时间限制」 文中的规划器使用基于ADDs(algebraic deci- 为处理大的状态空间问题，作者将系统建构在 sion diagrams)的MDPs紧致因子(compact fac- 不依赖于状态空间枚举的API(approximate policy tored)表示法s1,ADDs一般化了二元决策表(bi- iteration)上.现有的API框架s通过价值函数间 nary decision diagrams,BDDs),文献[51]在文献 接的表示策略，并使用机器学习的方法来选择价值 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netSubject to : 0 ≥B A max ( Ý k i = 1 wi ·bCasei (s) ) ß ( Ý k i = 1 wi ·bCasei (s) ) ; ΠA , s. (5) 对于 FOAPI 来说 , 策略迭代要求一个由值函 数vCase (s) 得到的合适的一阶策略表示. 假设有 m 个参数化的动作 { A1 ( x) , …, A m ( x) } , 则策略 πCase (s) 表示为 πCase (s) = max ( ∪i = 1 …m B A i ( vCase (s) ) ) . (6) 式中 :B A i ( vCase (s) ) 表示可由任一实例化的动作 Ai ( x) 得到的值 , max 操作算子保证了将最大可能 值赋给每一个 s. 根据 Guestrin 等[50 ] 提供的 factored MDPs 的 近似策略迭代方法 , 可通过计算权 w ( i) j 的连续迭代 来一般化近似策略迭代方法到一阶 MDPs 的过程 , 其中 , w ( i) j 表示在第 i 次迭代中策略πCase ( i) (s) 的 不动点值函数的最优近似. 在第 i 次迭代中通过执 行下述 2 步完成 : 1 ) 从 当前值函 数获得策 略 πCase (s) , 并用式(6) 获得权 ∑ k j = 1 w( i) j bCasej (s) ; 2) 求解下述 L P 公式 , 该公式决定策略πCase (s) 的 最小近似值函数的贝尔曼误差的权 : Variables: w i + 1 1 , …, w i + 1 k ; Minimize : Φ( i + 1) Subject to : Φ( i+1) ≥| πCaseA (s) Ý Ý k j = 1 [ w ( i+1) j bCasej (s) ] ß Ý k j =1 w ( i+1) j ( B A max bCasej) (s) | ΠA , s . (7) 基于 FOAL P 的方法可能不适合所有的域 , 但 在 box2world 逻辑域上它是高效的. 其缺点是在当 前的情况下 , 该方法只能处理带有全程量词回报值 的情况. 2. 7 基于 sfDP 的方法 Florent 和 Patrick 提出了基于 MDPs 的随机 规划器 sfDP (symbolic focused dynamic program2 ming) [ 51 ] , 该规划器将 PPDDL 问题转化为因子 MDPs 问题 (factored MDPs) , 并通过一个修改的 VI(structed modified) 算法来求解 , 其中修改的 VI 算法是基于从初始状态到目标状态的安全随机路径 计算(safest stochastic pat h comp utation) 的. 在进 行规划求解时 , 1) 通过使所有的转移确定化的方法 计算一个状态子空间 ; 2) 在当前策略下 , 交替执行 在当前可达的状态子空间上运用修改的 VI 算法和 进行可达状态空间的扩展. 文中的规划器使用基于 ADDs(algebraic deci2 sion diagrams) 的 MDPs 紧致因子 ( compact fac2 tored) 表示法[ 52 ] , ADDs 一般化了二元决策表 ( bi2 nary decision diagrams , BDDs) , 文献[ 51 ]在文献 [53 ]的基础上使用决策表 (decision diagrams) 优化 MDPs. 使用该方法 , 需要把 PPDDL 域及规划定义 转化为 ADDs2based MDP 表示. 在比赛中作者使 用 CUDD 包[54 ]来处理 ADDs 和 BDDs. 状态空间分解 (factorization) 包含有二元状态 变量的向量积 : S = á n i = 1 vi , 这些变量是每一个常量 和目标的 PPDDL 参数化谓词的实例化 , 这样的变 量使得在适当的时候可以处理一个状态集而不是单 一的一个状态. 动作由实例化 PPDDL 参数化的动 作而得到. 对于每一个动作 , 转移概率函数可以通 过动态贝叶斯网络 ( dynamic Bayesian network , DBN) [55 ]表示. 而该 DBNs 可被编码为 ADDs [ 53 ] . 此外 , 文中的方法不仅运用了初始状态信息 , 还运用了目标状态信息 , 以减少状态空间的搜索. 它使用确定可达性分析 ( deterministic reachability analysis) 来计算可达子空间 , 通过运用初始状态和 目标状态知识 , 在任一近似或最优动态规划计算之 前计算可达子空间. 计算的首要一步是确定化所有 的转移 , 然后高效的扩展从初始状态可达的那些状 态直到至少一个目标状态被到达 , 而不用记忆从初 始状态到目标状态的所有动作. 产生初始可达状态子空间 W 后 ,计算最大化到 达目标状态子空间 G( G < W ) 的概率的策略 , 这样 的策略称为安全随机路径策略 (safest stochastic pat h policy) , 它最大化到达至少一个目标状态的概 率. 前述得到的策略不保证在整个状态空间上是最 优的 , 因为它只是在 W < S 中最优. 为提高策略的 质量 , 作者采用交替执行确定性可达分析和安全随 机路径策略最优化这 2 个步骤. 当策略在先前(p re2 vious) 可达状态子空间上收敛时 , 循环结束. sfDP 在初始状态和目标状态知识上更加关注 策略. 试验结果标明 , 它在一定程度上还是比较有 效的. 2. 8 基于 API 的方法 S. W. Yoon , A. Fern 和 R. Givan 提出了新 的规划器[56 ] , 该规划器系统基于一种变化的近似 策略迭代算法(approximate policy iteration) , 它采 用归纳机器学习 (inductive machine learning) 和模 拟进行策略改进. 给定一个规划域 , 系统迭代改进 当前找到的最优策略直到策略不再被改进或超过一 定的时间限制. 为处理大的状态空间问题 , 作者将系统建构在 不依赖于状态空间枚举的 A PI(approximate policy iteration) 上. 现有的 API 框架[57 ] 通过价值函数间 接的表示策略 , 并使用机器学习的方法来选择价值 第 1 期 闫书亚 ,等 :概率规划的研究与发展 · 71 ·