第3卷第1期 智能系统学报 Vol.3 Ne 1 2008年2月 CAAI Transactions on Intelligent Systems Fcb.2008 概率规划的研究与发展 闫书亚，殷明浩2，谷文祥1，刘小飞 (1.东北师范大学计算机学院，吉林长春130117：2.吉林大学计算机科学技术学院，吉林长春130012) 摘要：概率规划是智能规划研究的一个重要方面，首先给出概率规划领域定义语言，并介绍其语法及语义，随后 重点介绍了求解概率规划的各种方法，如动态规划、启发式动态规划和基于规划图的方法等，并分析了各种方法的 特点.最后对国际概率规划比赛进行了介绍. 关键词：智能规划：概率规划：动态规划：概率规划领域定义语言 中图分类号：TP18文献标识码：A文章编号：1673-4785(2008)01-000914 Research and advances in proba bilistic planning YAN Shurya',YIN Ming-hao'2,GU Wemxiang',LIU Xiao-fei' (1.School of Computer,Northeast Normal University,Changchun 130117,China;2.College of Computer Science and Tech- nology,Jilin University,Changchun 130012,China) Abstract:Probabilistic planning has an important role in allowing intelligent planning to adapt to uncertain- ty.This paper introduces a new probabilistic plan domain definition language (PPDDL),followed by its syntax and semantics.Various methods of probabilistic planning are described,such as dynamic program- ming algorithms,heuristic dynamic programming algorithms and algorithms based on planning graph.The features of each algorithm are then analyzed.Finally,we give a brief introduction to the international probabilistic planning competition.The conclusions in this paper should be helpful to researchers interest- ed in this field. Key words:intelligent planning;probabilistic planning;dynamic programming;PPDDL 智能规划是当前人工智能领域中极为活跃的一[2-5]中，Wld等人提出了一致性规划问题，在这 个研究热点，近10年来，有关智能规划的研究在 类规划问题中，Agent需要考虑到初始状态和动作 问题描述和问题求解两方面得到了新的突破.相对 的不确定性；感知规划问题需要在规划执行过程中 于早期的智能规划系统，现代规划系统无论在规划 考虑感知动作6刃；时态规划问题和资源规划问题 求解效率上还是在规划求解规模上都有指数级的提 在生成规划解时需要考虑时态约束和资源约 高.然而，经典智能规划要求知识的完整性，即 束山：概率规划问题通过使用概率分布来刻画动 假设Agent对于规划世界的知识是完全的，规划过 作效果的不确定性，试图找到完成规划目标的最大 程中动作的效果是确定的，但是，在现实世界中得 概率规划解.事实上，非经典规划问题的研究 到的信息往往是不完全、不确定的，这就使规划理 已经成为目前人工智能规划领域研究的主要研究领 论的应用范围受到极大的限制. 域之一.在2004年举办的第4届国际智能规划竞 针对这些问题，国内外很多研究人员开始寻找 赛中，智能规划研究人员举办了第1届概率规划组 更一般的算法来处理这些不确定性问题.在文献 的比赛；在2006年的第5届智能规划竞赛中，同样 有概率组的比赛.人工智能研究杂志(journal of ar 收稿日期：2007-0719. 基金项目：因家自然科学基金资助项目(60573067,60473042)：东北 tificial intelligence research,JAIR)组织专f刊以发 师范大学青年自然科学基金资助项目(20070601). 表参加比赛的智能规划系统的研究报告.人工智能 通讯作者：闫书亚.E-mail:yansy276@nenu.edu.cn. 杂志在2003年也组织了一期专刊用于介绍和推广 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3 卷第 1 期 智 能 系 统 学 报 Vol. 3 №. 1 2008 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2008 概率规划的研究与发展 闫书亚1 , 殷明浩1 ,2 , 谷文祥1 , 刘小飞1 (1. 东北师范大学 计算机学院 ,吉林 长春 130117 ; 2. 吉林大学 计算机科学技术学院 ,吉林 长春 130012) 摘 要 :概率规划是智能规划研究的一个重要方面 , 首先给出概率规划领域定义语言 , 并介绍其语法及语义 , 随后 重点介绍了求解概率规划的各种方法 , 如动态规划、启发式动态规划和基于规划图的方法等 , 并分析了各种方法的 特点. 最后对国际概率规划比赛进行了介绍. 关键词 :智能规划 ; 概率规划 ; 动态规划 ; 概率规划领域定义语言 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2008) 0120009214 Research and advances in probabilistic planning YAN Shu2ya 1 , YIN Ming2hao 1 ,2 , GU Wen2xiang 1 , L IU Xiao2fei 1 (1. School of Computer , Northeast Normal University , Changchun 130117 , China ; 2. College of Computer Science and Tech2 nology , Jilin University , Changchun 130012 , China) Abstract :Probabilistic planning has an important role in allowing intelligent planning to adapt to uncertain2 ty. This paper introduces a new probabilistic plan domain definition language (PPDDL) , followed by its syntax and semantics. Various met hods of probabilistic planning are described , such as dynamic program2 ming algorit hms , heuristic dynamic programming algorit hms and algorithms based on planning grap h. The feat ures of each algorithm are t hen analyzed. Finally , we give a brief introduction to the international probabilistic planning competition. The conclusions in t his paper should be helpf ul to researchers interest2 ed in t his field. Keywords : intelligent planning ; probabilistic planning ; dynamic programming ; PPDDL 收稿日期 :2007207219. 基金项目 :国家自然科学基金资助项目(60573067 , 60473042) ;东北 师范大学青年自然科学基金资助项目(20070601) . 通讯作者 :闫书亚. E2mail :yansy276 @nenu. edu. cn. 智能规划是当前人工智能领域中极为活跃的一 个研究热点 , 近 10 年来 , 有关智能规划的研究在 问题描述和问题求解两方面得到了新的突破. 相对 于早期的智能规划系统 , 现代规划系统无论在规划 求解效率上还是在规划求解规模上都有指数级的提 高[1 ] . 然而 , 经典智能规划要求知识的完整性 , 即 假设 Agent 对于规划世界的知识是完全的 , 规划过 程中动作的效果是确定的 , 但是 , 在现实世界中得 到的信息往往是不完全、不确定的 , 这就使规划理 论的应用范围受到极大的限制. 针对这些问题 , 国内外很多研究人员开始寻找 更一般的算法来处理这些不确定性问题. 在文献 [225 ]中 , Weld 等人提出了一致性规划问题 , 在这 类规划问题中 , Agent 需要考虑到初始状态和动作 的不确定性 ; 感知规划问题需要在规划执行过程中 考虑感知动作[627 ] ; 时态规划问题和资源规划问题 在生 成 规 划 解 时 需 要 考 虑 时 态 约 束 和 资 源 约 束[8211 ] ; 概率规划问题通过使用概率分布来刻画动 作效果的不确定性 ,试图找到完成规划目标的最大 概率规划解[12214 ] . 事实上 , 非经典规划问题的研究 已经成为目前人工智能规划领域研究的主要研究领 域之一. 在 2004 年举办的第 4 届国际智能规划竞 赛中 ,智能规划研究人员举办了第 1 届概率规划组 的比赛 ; 在 2006 年的第 5 届智能规划竞赛中 , 同样 有概率组的比赛. 人工智能研究杂志(journal of ar2 tificial intelligence research , J AIR) 组织专刊以发 表参加比赛的智能规划系统的研究报告. 人工智能 杂志在 2003 年也组织了一期专刊用于介绍和推广
·10· 智能系统学报 第3卷 不确定规划问题.概率规划问题作为不确定规划问 的前提和效果不涉及变量reward. 题，也得到了研究者的广泛关注，其求解方法也日 图1显示了咖啡传送域11的PPDDL语言表 趋成熟.文中首先对概率规划问题进行介绍，然后 示，当“buy-coffee”动作执行时，如果使用者得到了 着重介绍解决概率规划问题的概率规划算法，并比 coffee,则获得0.8的回报.当在iswet为假时，执 较分析各种方法，最后对国际概率规划比赛进行了 行“buy-coffee”动作，获得的回报则是0.2.而当 介绍. user-has-coffee和iswet均为真的时候，得到的回 报则可以是1。 1概率规划表示 1.1概率规划领域定义语言 (define (domain coffee-delivery) 1998年，Drew McDermott提出了规划领域定 (requirements negative-preconditions 义语言(plan domain definition language,PDDL), disjunctive-preconditions :conditional-effects mdp) 随后PDDL逐渐成为规划领域模型表示和交流的 (predicates (imoffice)(raining)(hasumbrella) 通用标准，并成为国际智能规划比赛的标准语 (is wet)(hascoffee)(user-has-coffee)) 言o,516.2004年，H.H.Younes和M.Littman (:action buy-coffee 提出了PPDDL1.0以处理动作带有不确定效果的 effect (and (when (not (imroffice)) 概率规划问题)，概率部分的比赛使用的语言即 (probabilistic 0.8 (has-coffee))) 是PPDDL1.018割. (when (user-has-coffee)(increase (reward)0.8))(when (not (is wet)) 1.2 PPDDL语法 (increase (reward)0.2)))) 相对于经典规划领域定义语言PDDL,PPD DL1.0增加了新的表达能力，主要包括2个方面， 即对概率效果的支持、对马尔可夫决策过程回报值 图1咖啡传送域的部分PPDDL编码 的支持.在概率规划中，动作的效果是随机的，因 Fig.1 Part of PPDDL encoding of"coffee delivery"domain 此PPDDL增加了对概率效果的支持，其语法表 如果在规划问题定义中没有明确定义一个规划 示为 尺度(planning metric),则求解一个概率规划问题 (probabilistic pie,.pes) 时默认的目标为寻找到一条最大化目标实现概率的 式中：e表示动作的一个可能效果，p,表示动作效 规划 果e:出现的概率，并且p:满足如下约束 1.3 PPDDL语义 p≥0，p=1. 一个基于PPDDL描述的概率规划问题通常可 以被映射为一个带有回报的概率转移系统(proba- 但有时也允许某个空的概率效果出现，即 bilistic transition system). (probabilistic pie,pre). 设V为一个概率规划问题的状态变量集合，状 式中：P:≤1 态s为对状态变量的一次赋值，则变量的所有可能 这种表示和下面的表示是等价的： 赋值的集合构成了概率规划问题的整个状态空间. (probabilistic pie,.preq (and)). pm:S0,1],∑spo()=1即m是状态上的 概率分布)，V上的公式中刻画了目标状态G={ 式中：g=1-,P:,(and表示空效果 =$,动作集合A由动作概要实例化得到. 例如，(probabilistic0.9(clogged)表示命题 动作a∈A包含前提中。和效果e。.动作a在状 clogged以0.9的概率在下一状态中变为真，以0.1 态s上可用当且仅当s|=$,如果s|纯，在s上运 的概率保持原有真值。 用a则是错误的.这与PDDL2.1的语义是一致 另一方面，PPDDL使用关键字reward来表示 的.效果循环如下定义： 动作或规划的回报值，其基本语法表示为 l)T是空效果，在PPDDL中用(and)表示； ( 2)若b∈是一个布尔型状态变量，则b和7b 式中：为增加回报算子或减少回报 是其效果： 算子；是不包括reward的数值表达，动作 3)xf是一效果，如果x∈是一数值型状 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
不确定规划问题. 概率规划问题作为不确定规划问 题 , 也得到了研究者的广泛关注 , 其求解方法也日 趋成熟. 文中首先对概率规划问题进行介绍 , 然后 着重介绍解决概率规划问题的概率规划算法 , 并比 较分析各种方法 , 最后对国际概率规划比赛进行了 介绍. 1 概率规划表示 1. 1 概率规划领域定义语言 1998 年 , Drew McDermott 提出了规划领域定 义语言(plan domain definition language , PDDL) , 随后 PDDL 逐渐成为规划领域模型表示和交流的 通用标准 , 并成为国际智能规划比赛的标准语 言[10 ,15216 ] . 2004 年 , H. H. Younes 和 M. Littman 提出了 PPDDL1. 0 以处理动作带有不确定效果的 概率规划问题[17 ] , 概率部分的比赛使用的语言即 是 PPDDL1. 0 [18 ] . 1. 2 PPDDL 语法 相对于经典规划领域定义语言 PDDL , PPD2 DL1. 0 增加了新的表达能力 , 主要包括 2 个方面 , 即对概率效果的支持、对马尔可夫决策过程回报值 的支持. 在概率规划中 , 动作的效果是随机的 , 因 此 PPDDL 增加了对概率效果的支持 , 其语法表 示为 (p robabilistic p1 e1 , …, pk ek ) . 式中 : ei 表示动作的一个可能效果 , pi 表示动作效 果 ei 出现的概率 , 并且 pi 满足如下约束 : pi ≥0 , ∑ k i = 1 pi = 1. 但有时也允许某个空的概率效果出现 , 即 (probabilistic p1 e1 , …, pl el) . 式中 : ∑ l i = 1 pi ≤1. 这种表示和下面的表示是等价的 : (probabilistic p1 e1 , …, plel q (and) ) . 式中 : q = 1 - ∑ l i = 1 pi , (and) 表示空效果. 例如 , (probabilistic 0. 9 (clogged) ) 表示命题 clogged 以 0. 9 的概率在下一状态中变为真 , 以 0. 1 的概率保持原有真值. 另一方面 , PPDDL 使用关键字 reward 来表示 动作或规划的回报值 , 其基本语法表示为 ( ) . 式中 : 为增加回报算子或减少回报 算子 ; 是不包括 reward 的数值表达 ,动作 的前提和效果不涉及变量 reward. 图 1 显示了咖啡传送域[19 ] 的 PPDDL 语言表 示 , 当“buy2coffee”动作执行时 , 如果使用者得到了 coffee , 则获得 0. 8 的回报. 当在 is2wet 为假时 , 执 行“buy2coffee”动作 , 获得的回报则是 0. 2. 而当 user2has2coffee 和 ┐is2wet 均为真的时候 , 得到的回 报则可以是 1. (define (domain coffee2delivery) ( :requirements :negative2preconditions :disjunctive2preconditions :conditional2effects :mdp) ( :predicates (in2office) (raining) (has2umbrella) (is2wet) (has2coffee) (user2has2coffee) ) ( :action buy2coffee :effect (and (when (not (in2office) ) (probabilistic 0. 8 (has2coffee) ) ) (when (user2has2coffee) (increase (reward) 0. 8) ) (when (not (is2wet) ) (increase (reward) 0. 2) ) ) ) . . . ) 图 1 咖啡传送域的部分 PPDDL 编码 Fig. 1 Part of PPDDL encoding of“coffee delivery”domain 如果在规划问题定义中没有明确定义一个规划 尺度 (planning metric) , 则求解一个概率规划问题 时默认的目标为寻找到一条最大化目标实现概率的 规划. 1. 3 PPDDL 语义 一个基于 PPDDL 描述的概率规划问题通常可 以被映射为一个带有回报的概率转移系统 (proba2 bilistic transition system) . 设 V 为一个概率规划问题的状态变量集合 , 状 态 s 为对状态变量的一次赋值 , 则变量的所有可能 赋值的集合构成了概率规划问题的整个状态空间. p0 :S →[0 , 1 ] , ∑s ∈S p0 (s) = 1 (即 p0 是状态上的 概率分布) , V 上的公式 < 刻画了目标状态 G = { s| s| = <} , 动作集合 A 由动作概要实例化得到. 动作 a ∈A 包含前提 <a 和效果 e a . 动作 a 在状 态 s 上可用当且仅当 s | = <a , 如果 s | ≠<a , 在 s 上运 用 a 则是错误的. 这与 PDDL2. 1 [10 ]的语义是一致 的. 效果循环如下定义 : 1) 是空效果 , 在 PPDDL 中用(and) 表示 ; 2) 若 b∈V 是一个布尔型状态变量 , 则 b和 ┐b 是其效果; 3) x ←f 是一效果 , 如果 x ∈V 是一数值型状 · 01 · 智 能 系 统 学 报 第 3 卷
第1期 闫书亚，等：概率规划的研究与发展 ·11 态变量且∫是数值状态变量上的实值函数， 显然价值迭代算法和策略迭代算法可以用于求 4)r↑f是一效果，如果f是数值状态变量上 解上述问题 的实值函数： 2.1.1价值迭代算法 5)e个…八en是效果，如果e,em是 价值迭代算法(value iteration,VI)）是求解 效果： MDP问题的一种经典的动态规划算法，它从任意 6)c>e是效果，如果c是V上的一个公式且e 的初始评估值开始，通过迭代来求解方程.令f:(s 是一个效果： 为状态s在第i次迭代中的评估值，那么价值迭代 )pme…|pmen是效果，如果a,en是 执行下述更新： 效果，对于所有i∈{1，n},p:≥0且 f(s)=min [c(a.s)+>T(s,a.s)f(s)1. >p.=1. 2 其中2)~4)称为简单效果，x一∫意为当前状 如果无限地应用贝尔曼更新方程，价值迭代最终会 态中的值f在下一状态变为数值状态变量x的值， 收敛在贝尔曼方程组的惟一解上.在这种情况下， 效果r↑∫用来与转移回报相联系 对应的策略是最优的 动作a=(虫，ea〉定义了一个转移概率矩阵P。 和转移回报矩阵R。,p表示在状态i上运用动作 (=arg ile(a.T(s.a.s)f(s)1. a,转移到状态j时的概率：表示在状态i上运用 (3) 动作a,转移到状态j时得到的回报.效果c>e定 对于s∈S,当lf:(-f1(s川≤e,价值迭 义了一组状态转移，其中e是简单效果的合取.计 代算法停止，其中￡>0是给定的误差界限，即当评 算P。和Ra时，可首先将ea转化为p1e|…| 估函数∫足够接近于最优时，价值迭代算法停止： pmem,其中e是确定效果.具体的转化方法见文献 但是，由于V1更新每一个状态的值，它求解的过 187. 程是相当缓慢的.一个优化的措施是当它进行状态 当结果为多个效果pmel…pren时，具有同 更新时，对其进行限制，只更新那些从初始状态可 样的转移，这时要求一个特定转移的回报与结果是 以到达的状态的评估值 一致的 2.1.2策略迭代算法 2概率规划求解方法 价值迭代算法中，在每一时间步，评估函数只 是被用来计算动作，而策略则没有被显式地存储或 2.1动态规划算法 记录.策略迭代，在求解过程中则在存储更新评估 一个概率规划问题通常可以模型化为随机最短 值的同时也存储并更新策略的值， 路径问题(stochastic shortest path problems, 策略迭代算法从某个初始策略乃开始，交替 SSPs)2o).随机最短路径问题是一类特殊的马尔可 执行下面的2个步骤22-21： 夫决策问题(Markov decision problems,MDPs). 1)策略评价：确定当前策略的评估函数∫，即 SSPs为一个六元组：(S,A,T,c,G,S),其中， 给定策略刀，计算”； S是一组有限状态的集合：A是有限动作的集合， 2)策略改进：基于当前评估函数，更新当前策 对任一s∈S,A(表示在状态s上的可用动作的集 略，即当前策略π不是最优策略时，利用更新方 合；T是转移模型，即对在每个可能状态中的每种 程，找到一个新的策略π’，使得对任一状态， 行动的结果概率的详细说明.对于s,s’∈S,T(s, ∫”()≤f”(),并且至少存在一个状态i,使得 a,s')表示在状态s上执行动作a时到达状态s'的 f()<f(). 概率；c是代价函数，对任一s∈S,a∈A(s, 当策略改进步骤没有产生评估值的改变时，算 c(a,s表示在状态s上执行动作a的立即代价；G 法终止.对于有限的状态空间而言，策略数是有限 是目标集，GSS;S∈S是初始状态 的，并且每一次迭代都可以产生更好的策略，所以 这时，求解概率规划问题即转换为求解下述不 动点方程： 在有限次迭代后，算法会收敛于一个最优策略，并 终止 (=mc(a(s.a.s)f(s)1. 因为策略把每个状态中的行动都固定了，在第 1) i次迭代中，策略兀指定了状态s中的行动π：(s), 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
态变量且 f 是数值状态变量上的实值函数; 4) r ↑f 是一效果 , 如果 f 是数值状态变量上 的实值函数; 5) e1 ∧ … ∧en 是效果 , 如果 e1 , …, en 是 效果; 6) c þ e 是效果 , 如果 c 是 V 上的一个公式且 e 是一个效果; 7) p1 e1 | …| pne n 是效果 , 如果 e1 , …, en 是 效果 , 对 于 所 有 i ∈{ 1 , …, n } , pi ≥0 且 ∑ n i = 1 pi = 1 . 其中 2) ～4) 称为简单效果 , x ←f 意为当前状 态中的值 f 在下一状态变为数值状态变量 x 的值 , 效果 r ↑f 用来与转移回报相联系. 动作 a =〈 0 是给定的误差界限 , 即当评 估函数 f 足够接近于最优时 , 价值迭代算法停止. 但是 , 由于 V I 更新每一个状态的值 , 它求解的过 程是相当缓慢的. 一个优化的措施是当它进行状态 更新时 , 对其进行限制 , 只更新那些从初始状态可 以到达的状态的评估值. 2. 1. 2 策略迭代算法 价值迭代算法中 , 在每一时间步 , 评估函数只 是被用来计算动作 , 而策略则没有被显式地存储或 记录. 策略迭代 , 在求解过程中则在存储更新评估 值的同时也存储并更新策略的值. 策略迭代算法从某个初始策略π0 开始 , 交替 执行下面的 2 个步骤[22223 ] : 1) 策略评价 : 确定当前策略的评估函数 f , 即 给定策略π, 计算 f π ; 2) 策略改进 : 基于当前评估函数 , 更新当前策 略 , 即当前策略π不是最优策略时 , 利用更新方 程 , 找到一个新的策略 π’, 使得对任一状态 i , f π’( i) ≤f π ( i) , 并且至少存在一个状态 i , 使得 f π’( i) < f π ( i) . 当策略改进步骤没有产生评估值的改变时 , 算 法终止. 对于有限的状态空间而言 , 策略数是有限 的 , 并且每一次迭代都可以产生更好的策略 , 所以 在有限次迭代后 , 算法会收敛于一个最优策略 , 并 终止. 因为策略把每个状态中的行动都固定了 , 在第 i 次迭代中 , 策略πi 指定了状态 s 中的行动πi (s) , 第 1 期 闫书亚 ,等 :概率规划的研究与发展 · 11 ·
·12 智能系统学报 第3卷 由此，可得到贝尔曼方程的一个简化版本2 状态空间. f9=c(g,9+y7s,,ss1. Kof等人以模拟自动车辆行驶路径的路径追 踪问题为例26)，比较了几种不同算法2)，得出 (4) RTDP能够快速收敛于一种次优策略，其后，其他 在求解规划的过程中，由于策略迭代要更新每 研究人员也以实验结果证明了较大状态空间问题中 个状态的策略，其求解速度也是相对缓慢的 该算法的快速收敛性.因而RTDP的最大优点是可 2.2启发式动态规划算法 以在较短的时间内得到一个较好的策略.但由于很 用动态规划方法求解规划问题起到了良好的效 多状态被频繁地更新，所以在每个状态上完全收敛 果.但是，这些算法在更新状态的评估值时，均考 的速度是非常慢的，这是其缺点之一.另外，RT 虑了所有状态的评估值或策略，对于大的状态空间 DP算法要求系统的状态是完全可观察的，但在现 问题，其复杂度是让人望而却步的.鉴于此，研究 实中却很难满足，因此，还需要改进算法，以提高 者将启发式技术引入到动态规划算法中，以提高求 效率或者解决更复杂的问题 解规划的效率.下面重点介绍几种启发式动态规划 2.2.2基于Labeled RTDP的方法 (heuristic search dynamic programming algo- 由于RTDP的收敛速度比较缓慢，Labeled rithms.HS/DP) RTDP(LRTDP)算法I引入一个标记方案，提高 2.2.1基于RTDP的方法 了RTDP的收敛速度，同时保留了RTDP的其他 1995年Barto等人提出了实时动态规划算法 优点 (real-time dynamic programming,RTDP)241, Labeled RTDP算法的标记功能由一个被称为 里的“实时”指的是动作必须在严格的时间约束下执 Checksolved的标记程序完成.它的主要思想是： 行，其实质是通过对Kof提出的LRTA*2)算法 当贪婪策略定义在状态s上的启发式值和从s出发 进行扩展，来解决随机最短路径问题.在RTDP算 利用贪婪选择策略可达的那些状态上的启发式值都 法中，并不对所有状态的评估函数进行更新，因而 收敛时，标记状态为可解状态(solved).状态s及 减少了状态空间，在一定的假设前提条件下，RT- 由s出发利用贪婪策略可达的那些状态组成的图称 DP收敛于一种最优策略， 为状态s的贪婪图(greedy graph),贪婪图中的状 RTDP在一个单一的执行路迹(trace)上模拟 态构成的集合成为状态s的贪婪封装集(greedy en- 贪婪策略，并使用贝尔曼更新方程更新它们访问到 velope).状态s被激活时，Checksolved程序开始 的状态的评估值.这里主要介绍tria-based RTDP 搜索以s为根结点的贪婪图，寻找是否存在误差大 算法.该算法通过将状态上的计算组织为Sequem- 于E的状态s',如果不存在误差大于e的状态，则 tial trials而求解规划问题.Sequential trials是一 标记s为可解状态且Checksolved(s)返回true,即 种一边试验一边修正试验方案的试验方法.一个 当值函数在状态s上收敛时，标记s为可解.如果 RTDP试验是一个路径，每一个试验包含一系列步 在状态s的贪婪封装集中出现误差大于ε的一个状 骤(steps)).在每一步骤中，根据前向一步或多步深 态s'时，状态s和与其相关的状态都要被更新 度搜索而选择动作，基于动作的结果，选择当前的 Checksolved(s)返▣false.Checksolved的代码在 状态.包含当前状态的一个状态子集的代价函数被 文献[13]中的算法3中给出，状态s的标记在程序 更新，也即控制器总是遵循与最近更新的最优评估 中用哈希表的1个比特位表示，记为s.solved,一 函数相对应的贪婪策略，通过这个策略来选择将要 个状态s被标记为可解当且仅当s.solved=true 执行的动作，基于被选择的这个动作来更新当前状 LRTDP算法通过模拟试验实现，除了终止条件不 态.在每一个试验的开始，当前状态被设置为开始 同，它与RTDP的试验非常相似.实验从初始状态 状态，当到达目标状态或经过一定的步骤数之后，开始，以贪婪策略π，选择动作，以相应的转移概率 试验结束.RTDP反复执行这样的试验，直至收 选择后继状态，直到到达一个可解状态时实验结束 敛.RTDP的一个重要特性是，它只更新从初始状 (初始时只有目标状态是可解状态).每次实验结 态能够到达的那些状态的评估值，可能忽略了状态 束，调用标记程序Checksolved,反向核对状态的 空间中的许多状态，因而可以相对比较快地产生一 值函数的值，从最后一个不可解状态(unsolved)开 个相对比较好的策略.文献[24]证明在确定性合理 始回溯遍历到%，直到程序在一些状态上返回 条件下，RTDP逐渐收敛于最优解而不用估计整个 false.当初始状态so被标记为可解时，Labeled 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
由此 , 可得到贝尔曼方程的一个简化版本[22 ] : f i (s) = c(πi (s) ,s) +γ s′∑∈S T (s,πi (s) ,s′) f i (s′) . (4) 在求解规划的过程中 , 由于策略迭代要更新每 个状态的策略 , 其求解速度也是相对缓慢的. 2. 2 启发式动态规划算法 用动态规划方法求解规划问题起到了良好的效 果. 但是 , 这些算法在更新状态的评估值时 , 均考 虑了所有状态的评估值或策略 , 对于大的状态空间 问题 , 其复杂度是让人望而却步的. 鉴于此 ,研究 者将启发式技术引入到动态规划算法中 , 以提高求 解规划的效率. 下面重点介绍几种启发式动态规划 算法( heuristic search / dynamic programming algo2 rit hms , HS/ DP) . 2. 2. 1 基于 R TD P 的方法 1995 年 Barto 等人提出了实时动态规划算法 (real2time dynamic programming , RTDP) [24 ] , 这 里的“实时”指的是动作必须在严格的时间约束下执 行 , 其实质是通过对 Korf 提出的 LRTA 3 [25 ] 算法 进行扩展 , 来解决随机最短路径问题. 在 RTDP 算 法中 , 并不对所有状态的评估函数进行更新 , 因而 减少了状态空间 , 在一定的假设前提条件下 , RT2 DP 收敛于一种最优策略. RTDP 在一个单一的执行路迹 (trace) 上模拟 贪婪策略 , 并使用贝尔曼更新方程更新它们访问到 的状态的评估值. 这里主要介绍 trial2based RTDP 算法. 该算法通过将状态上的计算组织为 Sequen2 tial trials 而求解规划问题. Sequential trials 是一 种一边试验一边修正试验方案的试验方法. 一个 RTDP 试验是一个路径 , 每一个试验包含一系列步 骤(step s) . 在每一步骤中 , 根据前向一步或多步深 度搜索而选择动作 , 基于动作的结果 , 选择当前的 状态. 包含当前状态的一个状态子集的代价函数被 更新 , 也即控制器总是遵循与最近更新的最优评估 函数相对应的贪婪策略 , 通过这个策略来选择将要 执行的动作 , 基于被选择的这个动作来更新当前状 态. 在每一个试验的开始 , 当前状态被设置为开始 状态 , 当到达目标状态或经过一定的步骤数之后 , 试验结束. RTDP 反复执行这样的试验 , 直至收 敛. RTDP 的一个重要特性是 , 它只更新从初始状 态能够到达的那些状态的评估值 , 可能忽略了状态 空间中的许多状态 , 因而可以相对比较快地产生一 个相对比较好的策略. 文献[24 ]证明在确定性合理 条件下 , RTDP 逐渐收敛于最优解而不用估计整个 状态空间. Korf 等人以模拟自动车辆行驶路径的路径追 踪问题为例[26 ] , 比较了几种不同算法[27 ] , 得出 RTDP 能够快速收敛于一种次优策略 ; 其后 , 其他 研究人员也以实验结果证明了较大状态空间问题中 该算法的快速收敛性. 因而 RTDP 的最大优点是可 以在较短的时间内得到一个较好的策略. 但由于很 多状态被频繁地更新 , 所以在每个状态上完全收敛 的速度是非常慢的 , 这是其缺点之一. 另外 , RT2 DP 算法要求系统的状态是完全可观察的 , 但在现 实中却很难满足. 因此 , 还需要改进算法 , 以提高 效率或者解决更复杂的问题. 2. 2. 2 基于 Labeled RTDP 的方法 由于 RTDP 的收敛速度比较缓慢 , Labeled RTDP(LRTDP) 算法[ 13 ] 引入一个标记方案 , 提高 了 RTDP 的收敛速度 , 同时保留了 RTDP 的其他 优点. Labeled RTDP 算法的标记功能由一个被称为 Checksolved 的标记程序完成. 它的主要思想是 : 当贪婪策略定义在状态 s 上的启发式值和从 s 出发 利用贪婪选择策略可达的那些状态上的启发式值都 收敛时 , 标记状态为可解状态 (solved) . 状态 s 及 由 s 出发利用贪婪策略可达的那些状态组成的图称 为状态 s 的贪婪图 (greedy grap h) , 贪婪图中的状 态构成的集合成为状态 s 的贪婪封装集(greedy en2 velope) . 状态 s 被激活时 , Checksolved 程序开始 搜索以 s 为根结点的贪婪图 , 寻找是否存在误差大 于ε的状态 s’, 如果不存在误差大于ε的状态 , 则 标记 s 为可解状态且 Checksolved (s) 返回 true , 即 当值函数在状态 s 上收敛时 , 标记 s 为可解. 如果 在状态 s 的贪婪封装集中出现误差大于ε的一个状 态 s’时 , 状态 s 和与其相关的状态都要被更新 , Checksolved (s) 返回 false. Checksolved 的代码在 文献[ 13 ]中的算法 3 中给出 , 状态 s 的标记在程序 中用哈希表的 1 个比特位表示 , 记为 s. solved , 一 个状态 s 被标记为可解当且仅当 s. solved = true. L RTDP 算法通过模拟试验实现 , 除了终止条件不 同 , 它与 RTDP 的试验非常相似. 实验从初始状态 开始 , 以贪婪策略πv 选择动作 , 以相应的转移概率 选择后继状态 , 直到到达一个可解状态时实验结束 (初始时只有目标状态是可解状态) . 每次实验结 束 , 调用标记程序 Checksolved , 反向核对状态的 值函数的值 , 从最后一个不可解状态 ( unsolved) 开 始回溯遍历到 s0 , 直到程序在一些状态上返回 false. 当初始状态 s0 被标记为可解时 , Labeled · 21 · 智 能 系 统 学 报 第 3 卷
第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.net
RTDP 算法终止. 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 ·
·14 智能系统学报 第3卷 和深度优先搜索算法进行求解.在每次迭代中，如 效.而FPG借鉴了策略梯度增强学习的算法思想 果存在一个不超过最优代价的解，那么找到解，否 这类算法不需要估计规划状态-动作对的值，而是 则，更新评价函数，求解过程重新开始.LDFS用 估计整个搜索过程长期平均回报的梯度.FPG使用 统一的符号元素为不同的模型定义，如确定的、非 的是OL POMDP(在线部分可观察马尔可夫决策过程) 确定的MDP、GT模型等，并给出针对这些模型的 策略梯度强化算法3).梯度的计算与控制与在决 贝尔曼方程.在此基础上，给出一个一般化的算 策点选择动作的参数有关，这些参数决定了策略、 法，即Find-and-Revise.对于任何一个可采纳的评 规划及系统.在梯度的影响下，调节参数的值使得 估函数，算法在策略π下找到一个从初始状态s0出 期望回报增加或初始状态的值增加. 发能够到达的状态s,在保证Res,(s>e情况下更 FPG的分解参数策略通过对每个动作应用参 新状态的评价值，最后返回评价函数.LDFS作为 数函数生成，此函数输入规划状态的描述，返回每 这一算法框架的一个实例，主要通过2个循环来实 个可取动作的概率分布.FPG的输入语言是mdp~ 现算法：一个循环位于状态s中的贪婪动作a上， sim可处理的全部语言，即在PDDL上进行了微小 a∈A(:另一个循环位于s的可能后继s’上.搜 的扩展36).FPG使用了mdpsim的数据结构和函 索中的端ip)节点是不一致的状态s、终止状态和 数实现了一个规划域的模拟器.文中算法1完整的 被标记为可解(solved)的状态.一个状态被标记为描述了FPG是怎样利用OL POMDE分解动作策略实 可解的，即在s下的搜索没有找到不一致的状态.现规划的.算法的目的是从状态空间中抽取一条路 如果s是一致的且在对s的后继状态s'搜索后标记 径：1)第1个状态作为规划的第0时间步的初始状 位为真，则s被标记为可解的，并记录动作a,s上 态；2)与可取动作相连的感知机输入当前状态s 的其他动作将不再被搜索.否则，对下一贪婪动作 的观察向量0：；3)每个感知机的网络计算其相对 进行试验，一直到没有这样的动作存在时为止，更 应动作的可取程度；4)选择一个规划动作；5)选 新s值.算法结束时返回评估函数和贪婪策略 择一个状态转移；6)规划器接收新的状态动作的 试验结果表明，在某些模型问题中，如Max、 全局回报同时生成即时梯度g=ne,;7)所有参数 AND/OR图中，LDFS并不比其他的一些算法表现 在梯度g的导向下立即更新. 差，事实上，在某些方面LDFS的性能还略胜一筹. FPG规划器能对较大问题域生成好的策略，它 2.3FPG方法 的缺点是其局部最优性、参数简化、观察范围减少导 分解策略梯度规划器(factored policy gradient 致可能生成次优规划.梯度的变化次数是关于 planner,.FPGB]是为解决较大规划问题域而设计 POMDP混合时间(mixing time)的函数，随着状态 的概率时序规划器，FPG与传统规划方法的区别主 的增多会成指数级增长，怎样计算任意MDP的 要有2点，首先，FPG是有导向的进行规划搜索， mixing time仍是一个开放问题 利用在线梯度下降法寻找最优的参数规划.其次， 2.4基于LA0的方法 策略被分解到每个动作中，从部分观察值映射到动 经典的启发式搜索算法可找到以简单路径 作可能执行的概率，反映出每个动作可取的程度 (A)、树或非循环图(AO`)形式的解.EicA. 与其他概率时序规划器不同，FPG在保证总 Hansen和Shlomo Zilberstein提出了一个新的一般 makespan最小的同时使成功到达目标的概率最大. 化的启发式搜索算法LAO`(generalization of FPG的目标是处理现实世界问题域并生成好 A0)2,列)，它是目前求解决策理论规划问题最为 的策略，它通过以下几点能实现目标：1)使用梯度 高效的算法之一.该算法结合了启发式搜索和动态 下降法导向策略搜索：2)将策略分解成针对每个 规划的优点，可以在不需评估整个状态空间的基础 动作简单的近似策略；3)利用临界观察提取出每 上寻找一条带有循环(1oop)的最优解.在2004年 个策略：4)使用蒙特卡罗(Monte-Carlo)算法的思 举办的第1届国际不确定智能规划比赛中，它取得 想，存储器需求独立于状态空间的大小.而前面所 了“overall,nomblocks/box”组的冠军 介绍的规划算法将概率规划问题描述成为一个状态 AO'是AI中应用于状态空间搜索的一个著名 空间，对长期价值效用和选择每个动作的代价进行 启发式算法.AO算法找到的解是解图，形式化为 评估4).它们的缺点是需要估计大量的状态·动 树或更一般化的是一个非循环的图.AO'算法通过 作对的值，即使算法修剪了大部分状态，但当问题 从初始状态出发，逐渐构造一个解图的方法来解决 域扩大时，相关状态会成指数级增长，使得算法失 状态空间搜索问题.它可以理解为下列2个主要运 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
和深度优先搜索算法进行求解. 在每次迭代中 , 如 果存在一个不超过最优代价的解 , 那么找到解 , 否 则 , 更新评价函数 , 求解过程重新开始. LDFS 用 统一的符号元素为不同的模型定义 , 如确定的、非 确定的、MDP、GT 模型等 , 并给出针对这些模型的 贝尔曼方程. 在此基础上 , 给出一个一般化的算 法 , 即 Find2and2Revise. 对于任何一个可采纳的评 估函数 , 算法在策略π下找到一个从初始状态 s0 出 发能够到达的状态 s, 在保证 Res v (s) >ε情况下更 新状态的评价值 , 最后返回评价函数. LDFS 作为 这一算法框架的一个实例 , 主要通过 2 个循环来实 现算法 : 一个循环位于状态 s 中的贪婪动作 a 上 , a ∈A (s) ; 另一个循环位于 s 的可能后继 s’上. 搜 索中的端(tip) 节点是不一致的状态 s、终止状态和 被标记为可解(solved) 的状态. 一个状态被标记为 可解的 ,即在 s 下的搜索没有找到不一致的状态. 如果 s 是一致的且在对 s 的后继状态 s’搜索后标记 位为真 , 则 s 被标记为可解的 , 并记录动作 a , s 上 的其他动作将不再被搜索. 否则 , 对下一贪婪动作 进行试验 , 一直到没有这样的动作存在时为止 , 更 新 s 值. 算法结束时返回评估函数和贪婪策略. 试验结果表明, 在某些模型问题中, 如 Max、 AND/ OR 图中 , LDFS 并不比其他的一些算法表现 差 , 事实上 , 在某些方面 LDFS 的性能还略胜一筹. 2. 3 F PG方法 分解策略梯度规划器 (factored policy gradient planner , FPG) [33 ]是为解决较大规划问题域而设计 的概率时序规划器 , FPG与传统规划方法的区别主 要有 2 点 , 首先 , FPG 是有导向的进行规划搜索 , 利用在线梯度下降法寻找最优的参数规划. 其次 , 策略被分解到每个动作中 , 从部分观察值映射到动 作可能执行的概率 , 反映出每个动作可取的程度. 与其他 概 率 时 序 规 划 器 不 同 , FPG 在 保 证 总 makespan 最小的同时使成功到达目标的概率最大. FPG的目标是处理现实世界问题域并生成好 的策略 , 它通过以下几点能实现目标 : 1) 使用梯度 下降法导向策略搜索 ; 2) 将策略分解成针对每个 动作简单的近似策略 ; 3) 利用临界观察提取出每 个策略 ; 4) 使用蒙特卡罗 (Monte2Carlo) 算法的思 想 , 存储器需求独立于状态空间的大小. 而前面所 介绍的规划算法将概率规划问题描述成为一个状态 空间 , 对长期价值效用和选择每个动作的代价进行 评估[ 34 ] . 它们的缺点是需要估计大量的状态 - 动 作对的值 , 即使算法修剪了大部分状态 ,但当问题 域扩大时 ,相关状态会成指数级增长 ,使得算法失 效. 而 FPG借鉴了策略梯度增强学习的算法思想 , 这类算法不需要估计规划状态 - 动作对的值 , 而是 估计整个搜索过程长期平均回报的梯度. FPG使用 的是 OL POMDP (在线部分可观察马尔可夫决策过程) 策略梯度强化算法[35 ] . 梯度的计算与控制与在决 策点选择动作的参数有关 , 这些参数决定了策略、 规划及系统. 在梯度的影响下 , 调节参数的值使得 期望回报增加或初始状态的值增加. FPG的分解参数策略通过对每个动作应用参 数函数生成 , 此函数输入规划状态的描述 , 返回每 个可取动作的概率分布. FPG 的输入语言是 mdp2 sim 可处理的全部语言 ,即在 PDDL 上进行了微小 的扩展[ 36 ] . FPG 使用了 mdp sim 的数据结构和函 数实现了一个规划域的模拟器. 文中算法 1 完整的 描述了 FPG 是怎样利用 OL POMDP分解动作策略实 现规划的. 算法的目的是从状态空间中抽取一条路 径 : 1) 第 1 个状态作为规划的第 0 时间步的初始状 态 ; 2) 与可取动作相连的感知机输入当前状态 st 的观察向量 ot ; 3) 每个感知机的网络计算其相对 应动作的可取程度 ; 4) 选择一个规划动作 ; 5) 选 择一个状态转移 ; 6) 规划器接收新的状态动作的 全局回报同时生成即时梯度 gt = rt et ; 7) 所有参数 在梯度 gt 的导向下立即更新. FPG规划器能对较大问题域生成好的策略 ,它 的缺点是其局部最优性、参数简化、观察范围减少导 致可能生成次优规划. 梯度的变化次数是关于 POMDP 混合时间(mixing time) 的函数 , 随着状态 的增多会成指数级增长 , 怎样计算任意 MDP 的 mixing time 仍是一个开放问题. 2. 4 基于 LAO 3 的方法 经典的启发式搜索算法可找到以简单路径 (A 3 ) 、树或非循环图 ( AO 3 ) 形式的解. Eric A. Hansen 和 Shlomo Zilberstein 提出了一个新的一般 化的 启 发 式 搜 索 算 法 LAO 3 ( generalization of AO 3 ) [ 12 ,37 ] , 它是目前求解决策理论规划问题最为 高效的算法之一. 该算法结合了启发式搜索和动态 规划的优点 , 可以在不需评估整个状态空间的基础 上寻找一条带有循环 (loop) 的最优解. 在 2004 年 举办的第 1 届国际不确定智能规划比赛中 , 它取得 了“overall , non2blocks/ box”组的冠军[ 14 ] . AO 3 是 AI 中应用于状态空间搜索的一个著名 启发式算法. AO 3 算法找到的解是解图 , 形式化为 树或更一般化的是一个非循环的图. AO 3 算法通过 从初始状态出发 , 逐渐构造一个解图的方法来解决 状态空间搜索问题. 它可以理解为下列 2 个主要运 · 41 · 智 能 系 统 学 报 第 3 卷
第1期 闫书亚，等：概率规划的研究与发展 ·15· 算的反复.首先，一个自上而下的图生长运算，通 确定动作和感知动作61.1999年，Blum和J. 过跟踪有标记的连接符寻找最好的局部解图.这些 Langford提出利用规划图结构来进行概率规划问 以前计算过的标记指明在搜索图中离开每个节点的 题求解的算法Pgraphplan41.2003年，谷文祥、欧 当前的最好局部解图（在该算法终止之前，最好的 华杰和姜贵栋等人开发出一个带有互斥约束的概率 局部解图尚未产生它的全部终叶节点，所以称它为 规划器MPGP.2006年，I.Little和S 局部的).对这个最好的局部解图的非终叶节点之 Thiébaux提出了图框架下的并行概率规划方法 一进行扩展，并把某个费用赋给它的后继节点.算 Paragraph4).实践证明，图规划框架下的不确定 法中的第2个主要运算是一个自下而上的费用修 规划方法在实际应用中具有独特优势 正、连接符标记和solved标记的过程.从刚被扩展 2.5.1 PGraphplan方法 的节点开始，此过程修正其费用值（利用其后继节 Blum和Langford等人将图规划扩展到概率规 点最新计算的费用)，并把外向连接符标记到被估 划中，来处理初始状态确定，而动作结果不确定的 计为达到终节点的最好路径上.仅仅那些经过费用 规划问题，并设计了PG概率规划器] 修正的节点，其祖先才有可能拥有它们的修正值. Pgraphplan算法利用规划图结构求解初始状态 因此，并非所有的祖先都需要进行费用修正，只有 己知、动作结果不确定的概率规划问题.它采用概率 那些具有最好的局部解图而且含有修正费用的后裔 分布描述动作结果的不确定性，动作执行后有若干 的祖先才需要进行费用修正. 个可能结果，每个结果附有相关的概率值.Pgraphp LAO'算法可以看作是AO'算法的泛化.由 lan算法在给定时间限制内产生一个最优规划，得到 于在AO算法中假设一个无循环的解，因而它只 的是从初始状态到目标状态的最优动作序列，其中 能解决具有无循环解的问题.鉴于此，作者认识到 “最优”是指成功概率最大.Pgra即hplan算法主要分 AO`的费用修正步是一个DP算法，适当地一般化 为2个阶段：第1个阶段是在一个给定的时间步内 这个过程，从而得到LAO·算法，使得算法能处理 扩张规划图；第2个阶段是对已创建的规划图进行 解中包含循环的MDPs.LAO`算法包括2个阶段： 前向搜索，求出成功概率最高的有效规划， 在第一阶段，和AO`算法类似，LAO`算法不断扩 PGP的求解过程与图规划类似，只有2点不同 展最优部分解图，并使用一个可纳的启发式函数评 之处：1)在连接动作结点与其添加结果、删除效果 估新扩展出的边缘节点；在第二阶段，LAO·算法 之间的边时一定要标记概率值；2)规划图一直扩 使用价值迭代或策略迭代等动态规划方法更新状态 张到限定时间步Tx,才检查是否所有目标都出现 的评估值.上述2个过程交替执行，直到找到最优 在命题列，若出现则从初始状态开始用自顶向下的 解川.同AO·一样，LAO`的费用修正步也只在 动态规划算法进行解搜索，否则说明在限定时间内 一定的状态集合上执行，即扩展状态和显式图中那 找不到规划解 些可从扩展状态到达的状态.LAO'中，费用修正 图扩张完毕，进行解搜索利用.解搜索过程类 步可以利用VI或PL.运用PI,在有限次迭代后， 似于马尔可夫决策过程且为完全观察的MDP 在对端节点状态进行启发估计的基础上，可以为显 PG以标准的自顶向下动态规划算法作为起点，利 式图中的每一个状态计算一个精确的代价，而运用 用规划图结构所提供的信息来减少搜索范围.PGP VI.状态的精确代价是逐渐逼近的，但是在大规模 算法采用前向链搜索，这时图规划中的互斥信息己 问题上，这一缺点被VI的效率所抵消.不论怎样， 失效，因此PG提出了几种新的有助于减少搜索 通过结合启发式搜索和动态规划的方法，LAO'算 空间的信息类型来加速搜索过程.在PG的搜索 法无需扩展整个状态空间，从而可以快速有效的求 过程中，并没有使用互斥关系，它采用的是深度优 解不确定规划问题 先的状态空间搜索，所以它的速度稍慢一些」 2.5基于Graphplan的方法 2.5.2MPGP方法 图规划方法在智能规划领域取得了巨大的成 PGP采用多项式级别的规划图结构来处理初 功4川.由于其良好的性能，许多研究者扩展图 始状态的确定，而动作结果不确定的规划问题，较 规划，使其能解决不确定规划问题，并取得了很多 同类概率规划器而言，具有较快的速度.但是同时 重大成果.l998年，David E.Smith和Daniel 它也存在一些问题：比如它没有利用互斥约束进行 weld提出了一致图规划2].同年，D.weld,C. 优化、不允许动作的并行执行等.针对这一问题」 Anderson和D.Smith提出了扩展图规划以处理不 2003年，谷文祥、欧华杰和姜贵栋等人在PGP的基 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
算的反复. 首先 , 一个自上而下的图生长运算 , 通 过跟踪有标记的连接符寻找最好的局部解图. 这些 以前计算过的标记指明在搜索图中离开每个节点的 当前的最好局部解图 (在该算法终止之前 , 最好的 局部解图尚未产生它的全部终叶节点 , 所以称它为 局部的) . 对这个最好的局部解图的非终叶节点之 一进行扩展 , 并把某个费用赋给它的后继节点. 算 法中的第 2 个主要运算是一个自下而上的费用修 正、连接符标记和 solved 标记的过程. 从刚被扩展 的节点开始 , 此过程修正其费用值 (利用其后继节 点最新计算的费用) , 并把外向连接符标记到被估 计为达到终节点的最好路径上. 仅仅那些经过费用 修正的节点 , 其祖先才有可能拥有它们的修正值. 因此 , 并非所有的祖先都需要进行费用修正 , 只有 那些具有最好的局部解图而且含有修正费用的后裔 的祖先才需要进行费用修正. LAO 3 算法可以看作是 AO 3 算法的泛化. 由 于在 AO 3 算法中假设一个无循环的解 , 因而它只 能解决具有无循环解的问题. 鉴于此 , 作者认识到 AO 3 的费用修正步是一个 DP 算法 , 适当地一般化 这个过程 , 从而得到 LAO 3 算法 , 使得算法能处理 解中包含循环的 MDPs. LAO 3 算法包括 2 个阶段 : 在第一阶段 , 和 AO 3 算法类似 , LAO 3 算法不断扩 展最优部分解图 , 并使用一个可纳的启发式函数评 估新扩展出的边缘节点 ; 在第二阶段 , LAO 3 算法 使用价值迭代或策略迭代等动态规划方法更新状态 的评估值. 上述 2 个过程交替执行 , 直到找到最优 解[37 ] . 同 AO 3 一样 , LAO 3 的费用修正步也只在 一定的状态集合上执行 , 即扩展状态和显式图中那 些可从扩展状态到达的状态. LAO 3 中 , 费用修正 步可以利用 VI 或 PI. 运用 PI , 在有限次迭代后 , 在对端节点状态进行启发估计的基础上 , 可以为显 式图中的每一个状态计算一个精确的代价 , 而运用 VI , 状态的精确代价是逐渐逼近的 , 但是在大规模 问题上 , 这一缺点被 VI 的效率所抵消. 不论怎样 , 通过结合启发式搜索和动态规划的方法 , LAO 3 算 法无需扩展整个状态空间 , 从而可以快速有效的求 解不确定规划问题. 2. 5 基于 Grap hplan 的方法 图规划方法在智能规划领域取得了巨大的成 功[1 ,38241 ] . 由于其良好的性能 , 许多研究者扩展图 规划 , 使其能解决不确定规划问题 , 并取得了很多 重大 成 果. 1998 年 , David E. Smit h 和 Daniel Weld 提出了一致图规划[42 ] . 同年 , D. Weld , C. Anderson 和 D. Smit h 提出了扩展图规划以处理不 确定 动 作 和 感 知 动 作[6 ] . 1999 年 , Blum 和 J. Langford 提出利用规划图结构来进行概率规划问 题求解的算法 Pgrap hplan [ 43 ] . 2003 年 , 谷文祥、欧 华杰和姜贵栋等人开发出一个带有互斥约束的概率 规 划 器 MPGP [44 ] . 2006 年 , I. Little 和 S. Thiébaux 提出了图框架下的并行概率规划方法 Paragrap h [45 ] . 实践证明 , 图规划框架下的不确定 规划方法在实际应用中具有独特优势. 2. 5. 1 PGrap hplan 方法 Blum 和 Langford 等人将图规划扩展到概率规 划中 , 来处理初始状态确定 , 而动作结果不确定的 规划问题 , 并设计了 PGP 概率规划器[43 ] . Pgraphplan 算法利用规划图结构求解初始状态 已知、动作结果不确定的概率规划问题. 它采用概率 分布描述动作结果的不确定性 , 动作执行后有若干 个可能结果 , 每个结果附有相关的概率值. Pgraphp2 lan 算法在给定时间限制内产生一个最优规划 , 得到 的是从初始状态到目标状态的最优动作序列 , 其中 “最优”是指成功概率最大. Pgraphplan 算法主要分 为 2 个阶段: 第 1 个阶段是在一个给定的时间步内 扩张规划图; 第 2 个阶段是对已创建的规划图进行 前向搜索 , 求出成功概率最高的有效规划. PGP 的求解过程与图规划类似 , 只有 2 点不同 之处 : 1) 在连接动作结点与其添加结果、删除效果 之间的边时一定要标记概率值 ; 2) 规划图一直扩 张到限定时间步 Tmax , 才检查是否所有目标都出现 在命题列 , 若出现则从初始状态开始用自顶向下的 动态规划算法进行解搜索 , 否则说明在限定时间内 找不到规划解. 图扩张完毕 , 进行解搜索利用. 解搜索过程类 似于马尔可夫决策过程且为完全观察的 MDP , PGP 以标准的自顶向下动态规划算法作为起点 , 利 用规划图结构所提供的信息来减少搜索范围. PGP 算法采用前向链搜索 , 这时图规划中的互斥信息已 失效 , 因此 PGP 提出了几种新的有助于减少搜索 空间的信息类型来加速搜索过程. 在 PGP 的搜索 过程中 , 并没有使用互斥关系 , 它采用的是深度优 先的状态空间搜索 , 所以它的速度稍慢一些. 2. 5. 2 MPGP 方法 PGP 采用多项式级别的规划图结构来处理初 始状态的确定 , 而动作结果不确定的规划问题 , 较 同类概率规划器而言 ,具有较快的速度. 但是同时 它也存在一些问题 : 比如它没有利用互斥约束进行 优化、不允许动作的并行执行等. 针对这一问题 , 2003 年 , 谷文祥、欧华杰和姜贵栋等人在 PGP 的基 第 1 期 闫书亚 ,等 :概率规划的研究与发展 · 51 ·
·16 智能系统学报 第3卷 础上成功地开发出一个带有互斥约束并可以快速生 前规划图达到稳定状态.最后，前向遍历搜索空 成有效规划的概率规划器MPGP4!,该规划器引 间，利用贪婪选择策略提取最优随机规划 入命题互斥的思想及不确定环境下全新命题和命题 Paragraph循环规划的生成算法：首先扩展规 互斥的概念，在创建规划图的过程中判定完全实例 划图直到规划图达到稳定状态，然后进行后向搜 化的操作的前提是否互斥，在前提条件不互斥的情 索，采用深度优先搜索或迭代加深搜索算法.深度 况下，才在下一动作列中添加新的动作节点，避免 优先适用于搜索整个搜索空间，但路径被发现的顺 了在各时间步加入不会执行的动作节点，减少了规 序是不可预知的；而迭代加深搜索算法会首先找出 划图扩张过程中创建的节点数，节省了存储空间， 最短路径，当仅能利用搜索空间的一个子集时这种 提高了效率 算法更有效.前向状态模拟与非循环算法类似，代 MPGP算法也主要分为2个阶段：第1个阶段 价值的传递采用贝尔曼方程更新法，对代价函数进 是在一个给定的时间步内扩张规划图，第2个阶段 行更新直到其收敛在给定阈值内.当整个搜索空间 进行解搜索.所不同的是，在第一阶段，MPGP需 都被搜索到时，搜索结束.解的提取与非循环算法 要判断动作的前提条件的互斥关系.MPGP的图扩 相同 张过程和解搜索过程类似PGP Paragraph的优点是它可以充分利用规划图的 MPG可以解决大部分概率规划问题，实验结 的互斥关系和搜索方法来提高求解效率，但它没有 果也表明它在很多方面优于PGP 采用启发式的方法.运用启发式的知识以及将Par 2.5.3 Paragraph方法 agraph扩展到概率时序域上，是值得研究的方向 并行概率规划要解决两方面的问题：动作带有 2.6基于FOALP的方法 概率效果和动作在一定条件下可以并行执行1」 Scott Sanner和Craig Boutilier介绍了一种新 Paragraph规划器s1的主要思想就是将整个图规划 的解决概率规划问题的方法6]，该方法把PPDDL 框架扩展到概率规划问题域中，利用状态信息将由 表示的规划问题转化为一阶MDP(FOMDP),并使 Graphplan目标回溯搜索所找出的所有路径合并在 用FOMDP问题的近似解决技术来得到价值函数 一起生成最优并行随机规划.Paragraph规划器能 以及与之相关的策略，其中价值函数是一阶基础函 生成非循环规划和循环规划，选择性地开发利用问 数(first-order basis functions)的集合.FOMDP方 题潜在的并行性.Paragraph规划器为了能包含非 法线性地表示价值函数，并运用lifted、一阶近似线 循环解和循环解，将规划定义为一个确定的有穷自 性规划(first-order approximate linear program 动机，同时在规划图定义中增加了描述动作多种可 ming,FOALP)和近似策略迭代(first-order ap 能结果的结果结点和结果结点间的互斥关系.根据 proximate policy iteration,FOAPI)计算合适的权 对并行程度的限制级别，管理并行性分为3种模 值 型：不限制并行模型，限制并行模型和非·并行模 运用FOMDP方法求解概率规划问题，首先需 型.Paragraph规划器实现了对非.并行模型和限 要将PPDDL表示的规划转换为FOMDP所使用的 制模型的处理 状态演算表示.初步的转换是将PPDDL的动作概 Paragraph非循环规划的生成算法：l)根据问 要转化为状态演算中效果公式(effect axioms),然 题描述扩展规划图，直到所有目标命题都出现且不 后再将后者转化为后继状态公式(successor-state 互斥或规划图达到稳定状态，假设为前者，2)从规 axioms)I,FOMDP的形式化表示以及算子操作 划图最后一层的目标结点开始进行深度优先搜索， 详见文献[4849].符号A:(x)表示FOMDP中参数 找出从初始状态到目标状态的所有路径；3)从时间 化的动作对每一动作和变量(fluent),假设其后继 步0开始，前向模拟计算每个路径结点可能的世界 状态公式己经定义，Case,vCase和pCase在FO 状态；4)从目标结点开始后向传递代价值，更新当 MDP中分别表示回报值，值和转移函数 前结点/状态的代价.当后向搜索遇到新的结点或 对于FOALP,作者运用带有一阶约束的线 前向状态模拟计算出新的状态时，潜在的路径被搜 性规划linear program(LP)一般化从MDPs转到 索到并且加入到规划中.以上4个步骤交替进行， FOMDPs的过程： 后向搜索，前向状态模拟，后向代价传递，前向图 Variables:w,:i 扩张，直到遇到终止条件.终止条件包括：代价为 Minimize: 0的解被搜索到、超出有限的时间限定和后向搜索 icase,bCase, 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
础上成功地开发出一个带有互斥约束并可以快速生 成有效规划的概率规划器 MPGP [44 ] . 该规划器引 入命题互斥的思想及不确定环境下全新命题和命题 互斥的概念 , 在创建规划图的过程中判定完全实例 化的操作的前提是否互斥 , 在前提条件不互斥的情 况下 , 才在下一动作列中添加新的动作节点 , 避免 了在各时间步加入不会执行的动作节点 , 减少了规 划图扩张过程中创建的节点数 , 节省了存储空间 , 提高了效率. MPGP 算法也主要分为 2 个阶段 : 第 1 个阶段 是在一个给定的时间步内扩张规划图 ; 第 2 个阶段 进行解搜索. 所不同的是 , 在第一阶段 , MPGP 需 要判断动作的前提条件的互斥关系. MPGP 的图扩 张过程和解搜索过程类似 PGP [44 ] . MPGP 可以解决大部分概率规划问题 , 实验结 果也表明它在很多方面优于 PGP. 2. 5. 3 Paragrap h 方法 并行概率规划要解决两方面的问题 : 动作带有 概率效果和动作在一定条件下可以并行执行[45 ] . Paragrap h 规划器[ 45 ]的主要思想就是将整个图规划 框架扩展到概率规划问题域中 , 利用状态信息将由 Grap hplan 目标回溯搜索所找出的所有路径合并在 一起生成最优并行随机规划. Paragrap h 规划器能 生成非循环规划和循环规划 , 选择性地开发利用问 题潜在的并行性. Paragrap h 规划器为了能包含非 循环解和循环解 , 将规划定义为一个确定的有穷自 动机 , 同时在规划图定义中增加了描述动作多种可 能结果的结果结点和结果结点间的互斥关系. 根据 对并行程度的限制级别 , 管理并行性分为 3 种模 型 : 不限制并行模型 , 限制并行模型和非 - 并行模 型. Paragrap h 规划器实现了对非 - 并行模型和限 制模型的处理. Paragrap h 非循环规划的生成算法 :1) 根据问 题描述扩展规划图 , 直到所有目标命题都出现且不 互斥或规划图达到稳定状态 , 假设为前者 ; 2) 从规 划图最后一层的目标结点开始进行深度优先搜索 , 找出从初始状态到目标状态的所有路径 ;3) 从时间 步 0 开始 , 前向模拟计算每个路径结点可能的世界 状态 ;4) 从目标结点开始后向传递代价值 , 更新当 前结点/ 状态的代价. 当后向搜索遇到新的结点或 前向状态模拟计算出新的状态时 , 潜在的路径被搜 索到并且加入到规划中. 以上 4 个步骤交替进行 , 后向搜索 , 前向状态模拟 , 后向代价传递 , 前向图 扩张 , 直到遇到终止条件. 终止条件包括 : 代价为 0 的解被搜索到、超出有限的时间限定和后向搜索 前规划图达到稳定状态. 最后 , 前向遍历搜索空 间 , 利用贪婪选择策略提取最优随机规划. Paragrap h 循环规划的生成算法 : 首先扩展规 划图直到规划图达到稳定状态 , 然后进行后向搜 索 , 采用深度优先搜索或迭代加深搜索算法. 深度 优先适用于搜索整个搜索空间 , 但路径被发现的顺 序是不可预知的 ; 而迭代加深搜索算法会首先找出 最短路径 , 当仅能利用搜索空间的一个子集时这种 算法更有效. 前向状态模拟与非循环算法类似 , 代 价值的传递采用贝尔曼方程更新法 ,对代价函数进 行更新直到其收敛在给定阈值内. 当整个搜索空间 都被搜索到时 , 搜索结束. 解的提取与非循环算法 相同. Paragrap h 的优点是它可以充分利用规划图的 的互斥关系和搜索方法来提高求解效率 ,但它没有 采用启发式的方法. 运用启发式的知识以及将 Par2 agrap h 扩展到概率时序域上 ,是值得研究的方向. 2. 6 基于 FOAL P 的方法 Scott Sanner 和 Craig Boutilier 介绍了一种新 的解决概率规划问题的方法[46 ] , 该方法把 PPDDL 表示的规划问题转化为一阶 MDP(FOMDP) , 并使 用 FOMDP 问题的近似解决技术来得到价值函数 以及与之相关的策略 , 其中价值函数是一阶基础函 数(first2order basis f unctions) 的集合. FOMDP 方 法线性地表示价值函数 ,并运用 lifted、一阶近似线 性规 划 (first2order approximate linear program2 ming , FOAL P) 和近似策略迭代 (first2order ap2 proximate policy iteration , FOAPI) 计算合适的权 值. 运用 FOMDP 方法求解概率规划问题 ,首先需 要将 PPDDL 表示的规划转换为 FOMDP 所使用的 状态演算表示. 初步的转换是将 PPDDL 的动作概 要转化为状态演算中效果公式 (effect axioms) , 然 后再将后者转化为后继状态公式 (successor2state axioms) [47 ] . FOMDP 的形式化表示以及算子操作 详见文献[ 48249 ]. 符号 Ai ( x) 表示 FOMDP 中参数 化的动作对每一动作和变量 (fluent) , 假设其后继 状态公式已经定义 , rCase , vCase 和 pCase 在 FO2 MDP 中分别表示回报值 , 值和转移函数. 对于 FOAL P [ 49 ] , 作者运用带有一阶约束的线 性规划 linear program (L P) 一般化从 MDPs 转到 FOMDPs 的过程 : Variables: wi ; i ≤k Minimize : ∑ k i = 1 wi ∈bCase i t j bCasei · 61 · 智 能 系 统 学 报 第 3 卷
第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.net
Subject 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 ·
·18 智能系统学报 第3卷 函数的近似.然而，在许多域上，尤其是在关系结 的文字.一个赋值是从x到集合{True,False的映 构(first-order)上，间接的表示方法比直接的表示 射 方法更复杂，基于此，作者采用一个新的表示API 随机满足SSAT的关键是引入一个随机变量 表示方法[58]，该API直接将策略表示为状态/动作 牙随机变量将不确定性引入问题中，而不管问题 的映射.该系统的性能主要依赖于以下2点：1)必 是否存在一个可满足的赋值.一个SSAT公式由3 须提供策略表示语言和关联学习者(associated 元组（中Q,9定义，其中中是变量x1,2,xm上 learner),该学习者允许系统找到好的策略的近似； 的合取范式，Q是从变量x1,x2,,x)到量词 2)对于复杂域，需要提供一种引导机制来引导API (存在量词和随机量词9的映射，0∈0,1]是可满 过程.更详细的信息请见文献[5859] 足阈值.定义中[五-是(n-1)-变量CNF公式，它 图2显示了API的核心部件.API的每一个迭 由在r变量CNF公式中中为单一变量x,指定布尔 代包含2个主要步骤：策略评价和策略选择.直观 值b后得到.在量词顺序Q下，中可满足的最大概 地说，策略评价使用模拟来产生一个训练集，该训 率val(中，O定义为量词上的归纳：令x1是与最远 练集描述一个关于当前策略的改进策略.策略选择 的量词相联系的变量， 使用机器学习方法找到基于当前训练集的改进策略 1)如果中包含一个空的子句，则val(中g=0: 的一个近似解.这样，如果给定一个当前策略并顺 2)如果中不包含子句，则val(中，g=1; 序的应用这些步骤(steps),就可以得到一个（近似） 3)如果rx)=3,则val(中，g=max(val(中 的改进策略，系统反复这些步骤直到观察到的策略 i-o,g,val(Φ-1，g): 不再被改进 4)如果(x)=牙则val(中，g)=max(val(中 问题 训练 -0,g+val(φ-1，g)/2 问题 实例 策略 数据 分类 给定中Q、0、(中，Q,)为True当且仅当 生成器 展示 学习 valφ，g≥9 当前最佳策略 解决SSAT问题的算法是EVAL SSA T.给 定任意SSAT的实例（中Q,),算法保证返回一 图2近似策略迭代 个正确的值.EVAL SSAT算法可看作是 Fig.2 Block diagram of approximation policy iteration DPLL6II算法的扩展，DPLL是SSAT求解器的 由于系统的归纳特性，它不保证选择到的策略 基础，它枚举所有可能的赋值，并在任意可能的 的性能.然而，试验结果显示了其良好的性能 时刻简化公式.它的简化方法（或者说是剪枝规 2.9基于随机SAT的方法 则)使得解决整个赋值集合不能被完全枚举的问 除了上述方法以外，S.M.Majercik和M.L. 题是可能的.EVALSSAT算法以0、Q、低阈值A Littman将不确定环境下的随机规划作为随机可满 和高A作为输入.算法返回一个小于（的值，当 足性问题sSAT(stochastic satisfiability)来处 且仅当SSAT公式的值小于A时：算法返回一个 理6®1.他们提出了一种新的规划技术，将概率随机 大于A的值，当且仅当SSAT公式的值大于 规划问题转化为SSAT实例进行求解，首次将可满 时，否则返回SSAT公式的值. 足性规划问题扩展到随机域，并在此基础上设计了 随机可满足SSAT是概率规划技术的核心， 规划器Zander. Zander将随机规划问题转化为sSAT的实例，然 一个确定性的可满足问题要求一个可满足的赋 后进行求解.它首先将随机规划问题编码为SSAT 值，即指定公式中变量的真值，使公式的值为真 问题，转换单元是一个Java程序，它以PPL(一种 令x=是n个布尔变量的集合， 高层动作语言，由动作语言AR62]扩展而来)表示 x)是这些变量上的布尔公式，一个赋值A是可 的规划问题作为输入，并将输入转化为SSAT公 满足的且中(x)是可被满足的，如果在映射A下 式.之后，Zander进行求解.Zander的求解单元是 (x)的值为True.用公式表示为3x1,, C++程序，以SSAT表示的规划问题作为输入， 3xn(Efx)True]=1.0).其中，rx)是带有m 并找到一棵赋值树.求解器为所有可能的赋值构造 个子句的合取范式(CNF),每个子句是文字的析 二叉树.它通过执行DPLL-based算法对树进行 取，一个文字是一个变量或变量的否定.中为True 个深度优先搜索，并通过对每一节点计算到目前为 当且仅当在每个子句中至少存在一个真值为True 止给定的偏序赋值的概率构建一棵子树.求解器通 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
函数的近似. 然而 , 在许多域上 , 尤其是在关系结 构(first2order) 上 , 间接的表示方法比直接的表示 方法更复杂 , 基于此 , 作者采用一个新的表示 API 表示方法[58 ] , 该 A PI 直接将策略表示为状态/ 动作 的映射. 该系统的性能主要依赖于以下 2 点 : 1) 必 须提供策略表示语言和关联学习者 ( associated learner) , 该学习者允许系统找到好的策略的近似 ; 2) 对于复杂域 , 需要提供一种引导机制来引导 API 过程. 更详细的信息请见文献[58259 ]. 图 2 显示了 API 的核心部件. API 的每一个迭 代包含 2 个主要步骤 : 策略评价和策略选择. 直观 地说 , 策略评价使用模拟来产生一个训练集 , 该训 练集描述一个关于当前策略的改进策略. 策略选择 使用机器学习方法找到基于当前训练集的改进策略 的一个近似解. 这样 , 如果给定一个当前策略并顺 序的应用这些步骤(step s) , 就可以得到一个(近似) 的改进策略 , 系统反复这些步骤直到观察到的策略 不再被改进. 图 2 近似策略迭代 Fig. 2 Block diagram of approximation policy iteration 由于系统的归纳特性 , 它不保证选择到的策略 的性能. 然而 , 试验结果显示了其良好的性能. 2. 9 基于随机 SA T 的方法 除了上述方法以外 , S. M. Majercik 和 M. L . Littman 将不确定环境下的随机规划作为随机可满 足性 问 题 SSA T ( stochastic satisfiability ) 来 处 理[60 ] . 他们提出了一种新的规划技术 , 将概率随机 规划问题转化为 SSA T 实例进行求解 , 首次将可满 足性规划问题扩展到随机域 , 并在此基础上设计了 规划器 Zander. 一个确定性的可满足问题要求一个可满足的赋 值 , 即指定公式中变量的真值 , 使公式的值为真. 令 x = 是 n 个布尔变量的集合 , <( x) 是这些变量上的布尔公式 , 一个赋值 A 是可 满足的且 <( x) 是可被满足的 , 如果在映射 A 下 <( x) 的 值 为 True. 用 公 式 表 示 为 ϖ x1 , …, ϖ x n ( E[ <( x) ∴True ] = 110) . 其中 , <( x) 是带有 m 个子句的合取范式 (CN F) , 每个子句是文字的析 取 , 一个文字是一个变量或变量的否定. <为 True 当且仅当在每个子句中至少存在一个真值为 True 的文字. 一个赋值是从 x 到集合{ True , False}的映 射. 随机满足 SSA T 的关键是引入一个随机变量 Я, 随机变量将不确定性引入问题中 , 而不管问题 是否存在一个可满足的赋值. 一个 SSA T 公式由 3 元组( <, Q ,θ) 定义 , 其中 <是变量 x 1 , x2 , …, x n 上 的合取范式 , Q 是从变量 ( x1 , x2 , …, x n ) 到量词 (存在量词和随机量词 Я) 的映射 ,θ∈[0 , 1 ]是可满 足阈值. 定义 <「xi = b是 ( n - 1) 2变量 CNF 公式 , 它 由在 n2变量 CNF 公式 <中为单一变量 x i 指定布尔 值 b 后得到. 在量词顺序 Q 下 , <可满足的最大概 率 val ( <, Q) 定义为量词上的归纳 : 令 x1 是与最远 的量词相联系的变量 , 1) 如果 <包含一个空的子句 , 则val ( <, Q) = 0 ; 2) 如果 <不包含子句 , 则 val ( <, Q) = 1 ; 3) 如果 <( x1 ) = ϖ , 则 val ( <, Q) = max ( val ( < 「x1 = 0 , Q) , val ( <「x1 = 1 , Q) ) ; 4) 如果 <( x1 ) = Я, 则 val ( <, Q) = max ( val ( < 「x1 = 0 , Q) + val ( <「x1 = 1 , Q) ) / 2. 给定 <、Q、θ、( <, Q ,θ) 为 True 当 且 仅 当 val ( <, Q) ≥θ. 解决 SSA T 问题的算法是 EVAL SSA T. 给 定任意 SSA T 的实例 ( <, Q , θ) , 算法保证返回一 个 正 确 的 值. EVAL SSA T 算 法 可 看 作 是 DPLL [ 61 ] 算法的扩展 , DPLL 是 SSA T 求解器的 基础 , 它枚举所有可能的赋值 , 并在任意可能的 时刻简化公式. 它的简化方法 (或者说是剪枝规 则) 使得解决整个赋值集合不能被完全枚举的问 题是可能的. EVAL SSA T 算法以θ、Q、低阈值θl 和高θh 作为输入. 算法返回一个小于θl 的值 , 当 且仅当 SSA T 公式的值小于θl 时 ; 算法返回一个 大于θh 的值 , 当且仅当 SSA T 公式的值大于θh 时 ; 否则返回 SSA T 公式的值. 随机可满足 SSA T 是概率规划技术的核心 , Zander 将随机规划问题转化为 SSA T 的实例 , 然 后进行求解. 它首先将随机规划问题编码为 SSA T 问题 , 转换单元是一个 J ava 程序 , 它以 PPL (一种 高层动作语言 , 由动作语言 AR [ 62 ] 扩展而来) 表示 的规划问题作为输入 , 并将输入转化为 SSA T 公 式. 之后 , Zander 进行求解. Zander 的求解单元是 C + + 程序 , 以 SSA T 表示的规划问题作为输入 , 并找到一棵赋值树. 求解器为所有可能的赋值构造 二叉树. 它通过执行 DPLL2based 算法对树进行一 个深度优先搜索 , 并通过对每一节点计算到目前为 止给定的偏序赋值的概率构建一棵子树. 求解器通 · 81 · 智 能 系 统 学 报 第 3 卷
