###
Journal of Software:2013.24(7):1557-1570

基于缩减信念状态的Conformant 规划方法
魏唯,欧阳丹彤,吕帅
(吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012)
Conformant Planning Based on Reducing Belief States
WEI Wei,OUYANG Dan-Tong,LÜ Shuai
(College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering, Ministry of Education (Jilin University), Changchun 130012, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2015   Download 1936
Received:July 20, 2011    Revised:May 18, 2012
> 中文摘要: Conformant 规划问题通常转化为信念状态空间的搜索问题来求解.提出了通过降低信念状态的不确定性来提高规划求解效率的方法.首先给出缩减信念状态的增强爬山算法,在此基础上,提出了基于缩减信念状态的Conformant 规划方法,设计了CFF-Lite 规划系统.该规划器的求解过程包括两次增强爬山过程,分别用于缩减信念状态和搜索目标.首先对初始信念状态作最大程度的缩减,提高启发函数的准确性;然后从缩减后的信念状态开始执行启发式搜索.实验结果表明,CFF-Lite 规划系统通过快速缩减信念状态降低了问题的求解难度,在大多数问题上,求解效率和规划解质量与Conformant-FF 相比,都有显著的提高.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61133011, 60973089, 61003101, 61170092, 61272208); 国家教育部博士点专项基金(20100061110031); 吉林省科技发展计划(20101501, 20100185, 201101039); 浙江师范大学计算机软件与理论省级重中之重学科开放基金(ZSDZZZZXK12); 浙江省自然科学基金(Y1100191) 国家自然科学基金(61133011, 60973089, 61003101, 61170092, 61272208); 国家教育部博士点专项基金(20100061110031); 吉林省科技发展计划(20101501, 20100185, 201101039); 浙江师范大学计算机软件与理论省级重中之重学科开放基金(ZSDZZZZXK12); 浙江省自然科学基金(Y1100191)
Foundation items:
Reference text:

魏唯,欧阳丹彤,吕帅.基于缩减信念状态的Conformant 规划方法.软件学报,2013,24(7):1557-1570

WEI Wei,OUYANG Dan-Tong,LÜ Shuai.Conformant Planning Based on Reducing Belief States.Journal of Software,2013,24(7):1557-1570