第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 年也组织了一期专刊用于介绍和推广