基于缩减信念状态的Conformant规划方法  

Conformant Planning Based on Reducing Belief States

作　　者：魏唯[1,2] 欧阳丹彤[1,2] 吕帅[1,2] 

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

出　　处：《软件学报》2013年第7期1557-1570,共14页Journal of Software

基　　金：国家自然科学基金(61133011;60973089;61003101;61170092;61272208);国家教育部博士点专项基金(20100061110031);吉林省科技发展计划(20101501;20100185;201101039);浙江师范大学计算机软件与理论省级重中之重学科开放基金(ZSDZZZZXK12);浙江省自然科学基金(Y1100191)

摘　　要：Conformant规划问题通常转化为信念状态空间的搜索问题来求解.提出了通过降低信念状态的不确定性来提高规划求解效率的方法.首先给出缩减信念状态的增强爬山算法,在此基础上,提出了基于缩减信念状态的Conformant规划方法,设计了CFF-Lite规划系统.该规划器的求解过程包括两次增强爬山过程,分别用于缩减信念状态和搜索目标.首先对初始信念状态作最大程度的缩减,提高启发函数的准确性;然后从缩减后的信念状态开始执行启发式搜索.实验结果表明,CFF-Lite规划系统通过快速缩减信念状态降低了问题的求解难度,在大多数问题上,求解效率和规划解质量与Conformant-FF相比,都有显著的提高.Conformant planning is usually transformed into a search problem in the space of belief states. In this paper, a method which can improve efficiency of planning by reducing the nondeterministic degree of belief states is proposed. An enforced hill-climbing algorithm for reducing belief states is presented first. Then, the method of Conformant planning based on reducing belief states is proposed. A planner named CFF-Lite implements this idea and is designed. The planner includes two phases of enforced hill-climbing which are used to reduce belief states and search the goal respectively. Before the search phase, the initial belief state is reduced furthest to an intermediate state which is much more deterministic. Next, the precision of heuristic information is improved and the heuristic search phase is performed. Experimental results show that the CFF-Lite planner can decrease the difficulty of Conformant planning problems by reducing belief states and with most of the test problems this method outperforms Conformant-FF in both planning efficiency and planning quality.

关 键 词：Conformant规划问题 信念状态 增强爬山 启发式搜索 

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