第1期 闫书亚，等：概率规划的研究与发展 ·13· RTDP算法终止.LRTDP返回的策略兀，是就状态 到达的不一致的状态进行一个统一的搜索，给试验 s而言的一个偏序最优策略，它只保证了在s和s 中的最后一个未解决(unslo ved)的状态s标记.如 可达的那些状态上策略π，最优，与RTDP一样不 果这样一个状态被找到了，更新它，然后新的试验 需要考虑整个状态空间.LRTDP的代码在文献 被执行，否则，状态s和它所有的未解决的后继被 [13]中的算法4中给出， 标记为可解的，一个新的RTDP循环和标记检查被 实践证明，LRTDP大大地加快了RTDP的收 激活.HDP采用这种方法，但对其进行了改进，它 敛速度.当启发式值h=0时，LRTDP通常也比VI 去掉了标记检查所需要的额外搜索.标记检查作为 收敛速度快.这表明，LRTDP会有一个广泛的应 Find搜索的一部分，它运用Tarjan线性算法o1来 用空间.mGPT规划器2]就将LRTDP作为主要的 检查有向图的强连通分支.在有向图G,中，s与s 算法之一.mGPT利用启发式搜索求解由高层规划 之间的“~”关系为s=s'或s可从s’到达且s'可从 语言PPDDL描述的MDP模型，它支持多种算法 s到达.G中的强连通分支称为等价类，由s与s 和启发式函数，其中最主要的2个算法就是La 之间的“~”定义，并因此形成一个特定的集合，用 beled RTDP和HDp2),mGPT在IPC4中表现突 C表示，并定义当C中的所有s都满足：一致时， 出，下面就来介绍基于HDP的方法 Component C是&一致的，当C中的每一个s都是 2.2.3基于HDP的方法 可解的Component C是可解的.由此定义G:当C Bonet和Geffner在文献[29]中提出了新的启 中某一状态能由C中的某一状态到达时，图的顶点 发式动态规划算法HDP(faster heuristic and dy- 是G中的Components,边是C→C'.显然，Gf是 namic programming search al gorithms for plan- 一个非循环的图.另外： ning),在Tarjan的强连通分支o的基础上，通过 1)状态s是可解的当且仅当Component C是 引入标记机制来对状态进行判断更新 可解的： 文献29J模型化了带有回馈feedback)的非确 2)Component C是可解的当且仅当C是一致 定规划问题，具体说是随机最短路径问题.它首先 的且所有的C'、C→C'是可解的 给出一个一般化的算法框架Find-and-Revise,并给 从而在循环图G,中标记状态的问题可映射到 定e-一致/不一致贪婪图(greedy graph)的定义. 非循环图G中标记Components的问题，而后者 一个值函数v在状态s上是&一致/不一致的是指 则可通过标准的动态规划方法解决。 它在s上的剩余(residual)不大于/大于e:v本身是 HDP算法阐明了存在于HSDP算法背后的 一致的当它在所有的状态上是&一致的，这里的 基本观点：寻找不一致的状态并更新它们，直到不 状态是指在兀下，从sm可以到达的那些状态.贪 存在这样的状态.试验结果显示，与当前的一些算 婪图G,是从初始状态s出发，执行贪婪策略兀得 法相比，HDP还是很有竞争力的 到的图，即0是G,中唯一的根节点，对于G中的 2.2.4基于LDFS的方法 每一非目标状态5，他们的孩子节点是在s上执行 启发式动态规划算法可以有效处理大状态空间 动作π(y可能引起的那些状态. 问题，但这些问题和它们使用的各种技术之间的共 Find-and-Revise通过在贪婪图中搜索不一致 同点往往不是那么清晰.如何将它们转化为更一般 状态并更新它们来计算￡-一致值函数，直到不存在 的模型以有效的利用，针对此问题，Bonet和Gef- 不一致的状态.HDP是Find-and-Revise的一个实 fner结合DP算法的优点和HS算法的有效性，发 例化算法，通过Find操作，系统地进行深度优先搜 展了一种通用的算法框架(learning in depth-first 索，并为访问过的状态作标记.一个状态定义为可 search LDFS)B-2],以期达到一般性和有效性」 解的(solved)是指：在s上值函数v是e-一致的， LDFS框架清晰化和一般化了贯穿于各种算法 并且在所有从s出发，经贪婪策略兀能到达的状态 模型中的启发式算法族的2个关键点：学习(learn- 上也是￡-一致.当这些条件满足时，在s及从s能 ing)和下界(lower bounds).LDFS结合更新，下界 到达的状态上，不需要进一步进行更新.当初始状 和初始状态知识来为规划问题计算偏序最优策略 态∞是可解的并且因此一个￡-一致的值函数找到 (partial optimal policies),它利用这些概念，表示 的时候，算法结束 出一个一般性的框架，这个框架能够覆盖一系列模 由于贪婪图中存在环，HDP采用LRTDPII 型问题 中解决循环的标记方法.在LRTDP中，通过对从s LDFS算法的基本特点是：求解时，结合有界 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netRTDP 算法终止. L RTDP 返回的策略πv 是就状态 s 而言的一个偏序最优策略 , 它只保证了在 s 和 s 可达的那些状态上策略πv 最优 , 与 RTDP 一样不 需要考虑整个状态空间. L RTDP 的代码在文献 [13 ]中的算法 4 中给出. 实践证明 , L RTDP 大大地加快了 RTDP 的收 敛速度. 当启发式值 h = 0 时 , L RTDP 通常也比 VI 收敛速度快. 这表明 , L RTDP 会有一个广泛的应 用空间. mGPT 规划器[28 ]就将 L RTDP 作为主要的 算法之一. mGPT 利用启发式搜索求解由高层规划 语言 PPDDL 描述的 MDP 模型 , 它支持多种算法 和启发式函数 , 其中最主要的 2 个算法就是 La2 beled RTDP 和 HDP [ 29 ] , mGPT 在 IPC24 中表现突 出 ,下面就来介绍基于 HDP 的方法. 2. 2. 3 基于 HDP 的方法 Bonet 和 Geff ner 在文献[ 29 ]中提出了新的启 发式动态规划算法 HDP (faster heuristic and dy2 namic programming search algorit hms for plan2 ning) , 在 Tarjan 的强连通分支[30 ] 的基础上 , 通过 引入标记机制来对状态进行判断更新. 文献[29 ]模型化了带有回馈 (feedback) 的非确 定规划问题 , 具体说是随机最短路径问题. 它首先 给出一个一般化的算法框架 Find2and2Revise , 并给 定ε2一致/ 不一致贪婪图 ( greedy grap h) 的定义. 一个值函数 v 在状态 s 上是ε2一致/ 不一致的是指 它在 s 上的剩余(residual) 不大于/ 大于ε; v 本身是 ε2一致的当它在所有的状态上是ε2一致的 , 这里的 状态是指在πv 下 , 从 s0 可以到达的那些状态. 贪 婪图 Gv 是从初始状态 s0 出发 , 执行贪婪策略πv 得 到的图 , 即 s0 是 Gv 中唯一的根节点 , 对于 Gv 中的 每一非目标状态 s, 他们的孩子节点是在 s 上执行 动作π(s) 可能引起的那些状态. Find2and2Revise 通过在贪婪图中搜索不一致 状态并更新它们来计算ε2一致值函数 , 直到不存在 不一致的状态. HDP 是 Find2and2Revise 的一个实 例化算法 , 通过 Find 操作 , 系统地进行深度优先搜 索 , 并为访问过的状态作标记. 一个状态定义为可 解的(solved) 是指 : 在 s 上值函数 v 是ε2一致的 , 并且在所有从 s 出发 , 经贪婪策略πv 能到达的状态 上也是ε2一致. 当这些条件满足时 , 在 s 及从 s 能 到达的状态上 , 不需要进一步进行更新. 当初始状 态 s0 是可解的并且因此一个ε2一致的值函数找到 的时候 , 算法结束. 由于贪婪图中存在环 , HDP 采用 L RTDP [ 13 ] 中解决循环的标记方法. 在 LRTDP 中 , 通过对从 s 到达的不一致的状态进行一个统一的搜索 , 给试验 中的最后一个未解决 ( unsloved) 的状态 s 标记. 如 果这样一个状态被找到了 , 更新它 , 然后新的试验 被执行 , 否则 , 状态 s 和它所有的未解决的后继被 标记为可解的 , 一个新的 RTDP 循环和标记检查被 激活. HDP 采用这种方法 , 但对其进行了改进 , 它 去掉了标记检查所需要的额外搜索. 标记检查作为 Find 搜索的一部分 , 它运用 Tarjan 线性算法[30 ] 来 检查有向图的强连通分支. 在有向图 Gv 中 , s 与 s’ 之间的“～”关系为 s = s’或 s 可从 s’到达且 s’可从 s 到达. Gv 中的强连通分支称为等价类 , 由 s 与 s’ 之间的“～”定义 , 并因此形成一个特定的集合 , 用 C表示 , 并定义当 C 中的所有 s 都满足ε2一致时 , Component C 是ε2一致的 ,当 C 中的每一个 s 都是 可解的 Component C 是可解的. 由此定义 G: 当 C’ 中某一状态能由 C 中的某一状态到达时 ,图的顶点 是 Gv 中的 Components, 边是 C →C’. 显然 , G C v 是 一个非循环的图. 另外 : 1) 状态 s 是可解的当且仅当 Component C 是 可解的; 2) Component C 是可解的当且仅当 C 是一致 的且所有的 C’、C →C’是可解的. 从而在循环图 Gv 中标记状态的问题可映射到 非循环图 G C v 中标记 Components 的问题 , 而后者 则可通过标准的动态规划方法解决. HDP 算法阐明了存在于 HS/ DP 算法背后的 基本观点 : 寻找不一致的状态并更新它们 , 直到不 存在这样的状态. 试验结果显示 , 与当前的一些算 法相比 , HDP 还是很有竞争力的. 2. 2. 4 基于 L D FS 的方法 启发式动态规划算法可以有效处理大状态空间 问题 , 但这些问题和它们使用的各种技术之间的共 同点往往不是那么清晰. 如何将它们转化为更一般 的模型以有效的利用 ,针对此问题 , Bonet 和 Gef2 f ner 结合 DP 算法的优点和 HS 算法的有效性 , 发 展了一种通用的算法框架 (learning in dept h2first search ,LDFS) [31232 ] , 以期达到一般性和有效性. LDFS 框架清晰化和一般化了贯穿于各种算法 模型中的启发式算法族的 2 个关键点 : 学习(learn2 ing) 和下界(lower bounds) . LDFS 结合更新 , 下界 和初始状态知识来为规划问题计算偏序最优策略 (partial optimal policies) , 它利用这些概念 , 表示 出一个一般性的框架 , 这个框架能够覆盖一系列模 型问题. LDFS 算法的基本特点是 : 求解时 , 结合有界 第 1 期 闫书亚 ,等 :概率规划的研究与发展 · 31 ·