JLU-RLAO和JLU-QLAO:两个不确定智能规划求解系统  

JLU-RLAO and JLU-QLAO:Two Non-Deterministic Planners

作　　者：孙吉贵[1,2] 殷明浩[3] 吕帅[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学教育部符号计算与知识工程重点实验室,长春130012 [3]东北师范大学计算机学院,长春130117

出　　处：《计算机研究与发展》2009年第4期667-675,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金重大项目(6049321);国家自然科学基金项目(60473042;60573067;60803102);高等学校博士学科点专项科研基金项目(20050183065);东北师范大学青年自然科学基金项目(20070601)~~

摘　　要：不确定环境下的智能规划问题往往假设世界状态的转移概率是确切可知的,然而规划建模专家有时只能在信息不完备的条件下进行建模,从而只能通过猜测或者不完全统计的方法来获取不完备的有关状态转移不确定性的定量信息,有时甚至只能获取相关的定性信息.在2004年概率规划比赛冠军LAO系统的基础上设计了JLU-RLAO系统和JLU-QLAO系统.它们可以在无法获得精确的状态转移概率条件下,依然保证规划求解的健壮性.实验结果表明,JLU-RLAO系统和JLU-QLAO系统可以快速高效地解决上述不确定智能规划问题.Classical decision-theoretic planning methods assume that the probabilistic model of the domain is always accurate. Unfortunately, for lack of information, sometimes planning modeling experts can only obtain incomplete quantitative information, or even ordinal, qualitative information for modeling the uncertainty about the world transition. Recently, LAO^＊ has been proved to be one of the most efficient planners for solving probabilistic planning problems. Two algorithms, namely rLAO^＊ algorithm and qLAO^＊ algorithm, are introduced to solve non-deterministic planning problems without complete information based on LAO^＊. Specifically, rLAO^＊ algorithm can solve planning problems under uncertainty with incomplete quantitative information, and qLAO^＊ algorithm can solve planning problems under uncertainty with qualitative information. Both these two algorithms are proved to be sound and complete. Both algorithms have been implemented in the framework of two un-deterministie planners ＂JLU-RLAO＂ and ＂JLU-QLAO＂, and compared with LAO^＊ using a lot of benchmark problems. Experimental results show that both systems inherit the merits of excellent performance of LAO^＊ for solving planning problems under uncertainty. Because JLU-RLAO and JLU- QLAO planners can solve planning problems under uncertainty with incomplete information, they can be regarded as complementary planners to LAO^＊.

关 键 词：智能规划 不确定规划 最坏模型 最好模型 定性决策 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]