第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)表示； (<additive-op><reward fluent <f-exp > 2)若b∈是一个布尔型状态变量，则b和7b 式中：<additive-op>为增加回报算子或减少回报 是其效果： 算子；<fep>是不包括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 来表示 动作或规划的回报值 , 其基本语法表示为 ( < additive2op > < reward fluent > < f2exp > ) . 式中 : < additive2op > 为增加回报算子或减少回报 算子 ; < f2exp > 是不包括 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 =〈<a , ea〉定义了一个转移概率矩阵 Pa 和转移回报矩阵 Ra , p a ij 表示在状态 i 上运用动作 a , 转移到状态 j 时的概率; r a ij表示在状态 i 上运用 动作 a , 转移到状态 j 时得到的回报. 效果 c þ e 定 义了一组状态转移 , 其中 e 是简单效果的合取. 计 算 Pa 和 Ra 时 , 可首先将 ea 转化为 p1 e1 | … | pne n , 其中 ei 是确定效果. 具体的转化方法见文献 [18 ]. 当结果为多个效果 p1 e1 | …| pne n 时 , 具有同 样的转移 , 这时要求一个特定转移的回报与结果是 一致的. 2 概率规划求解方法 2. 1 动态规划算法 一个概率规划问题通常可以模型化为随机最短 路 径 问 题 ( stochastic shortest path problems , SSPs) [ 20 ] . 随机最短路径问题是一类特殊的马尔可 夫决策问题 (Markov decision problems , MDPs) . SSPs 为一个六元组〈: S , A , T , c , G, S0 〉, 其中 , S 是一组有限状态的集合; A 是有限动作的集合 , 对任一 s ∈S , A (s) 表示在状态 s′上的可用动作的集 合; T 是转移模型 , 即对在每个可能状态中的每种 行动的结果概率的详细说明. 对于 s, s’∈S , T (s, a , s’) 表示在状态 s 上执行动作 a 时到达状态 s’的 概率; c 是代价函数 , 对任一 s ∈S , a ∈A ( s) , c( a , s) 表示在状态 s 上执行动作 a 的立即代价; G 是目标集 , G ΑS ; S0 ∈S 是初始状态. 这时 , 求解概率规划问题即转换为求解下述不 动点方程[21 ] : f (s) = min a∈A (s) [ c( a ,s) + s′∑∈S T (s, a ,s′) f (s′) ]. (1) 显然价值迭代算法和策略迭代算法可以用于求 解上述问题. 2. 1. 1 价值迭代算法 价值迭代算法 ( value iteration , VI) 是求解 MDP 问题的一种经典的动态规划算法 , 它从任意 的初始评估值开始 , 通过迭代来求解方程. 令 f i (s) 为状态 s 在第 i 次迭代中的评估值 , 那么价值迭代 执行下述更新 : f i+1 (s) = min a∈A (s) [ c( a ,s) + s′∑∈S T (s, a ,s′) f (s′) ]. (2) 如果无限地应用贝尔曼更新方程 , 价值迭代最终会 收敛在贝尔曼方程组的惟一解上. 在这种情况下 , 对应的策略是最优的. π(s) = arg min a ∈A (s) [ c( a ,s) + s′∑∈S T (s, a ,s′) f (s′) ]. (3) 对于 Πs ∈S , 当| f i (s) - f i - 1 (s) | ≤ε, 价值迭 代算法停止 , 其中ε> 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 ·