·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 卷