基于Conformant Fast-Forward规划系统的析取目标处理方法  

Extending Conformant Fast-Forward to Deal with Disjunctive Goals

作　　者：杨宇鹏[1,2] 欧阳丹彤[1,2] 蔡敦波[1,2] 吕帅[1,2] 

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

出　　处：《计算机研究与发展》2008年第12期2120-2128,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(607730097);教育部高等学校博士学科点专项科研基金项目(20050183065);吉林大学"九八五"工程研究生创新基金项目(20080233)~~

摘　　要：将规划系统Conformant Fast-Forward从单目标规划扩展到基于析取目标的不确定规划,设计并实现了新的规划系统Conformant-FF-d.Conformant-FF-d的新功能主要包括:目标状态判断、可达性分析和启发函数.提出一种利用SAT技术进行目标状态判断的高效方法;提出析取目标条件下信念状态的可达性分析方法,有效地删除无法到达目标的信念状态,进而缩小了搜索空间的规模;设计了适用于析取目标的启发函数,有效地指导搜索算法向更有希望到达目标的方向进行.在国际规划竞赛的问题域上对Conformant-FF-d和先进的规划系统POND进行测试和对比分析,实验结果表明:Conformant-FF-d的求解效率高而且具有较好的可扩展性.Conformant Fast-Forward that handles certain goals is extended to a new system that can deal with uncertain goals, and the new planning system implemented is called Conformant-FF-d that can deal with disjunctive goals. Disjunctive goals are one of the expressions of uncertain goals, and disjunctive goals are widely used in expressing uncertain goals in planning domains. Some key components of Conformant-FF-d system include goal state recognition, reachability analysis and the heuristic function for disjunctive goals. A method that uses a SAT technique to recognize the goal states efficiently is proposed. In order to do reachability analysis, an algorithm based on relaxed planning graph and implication graph is developed, which prunes the belief states that can never reach the goals. The method of reachability analysis reduces the size of the searching space, so the plan can be found in a relatively small searching space other than the whole space. A new heuristic function suitable for disjunctive goals is defined, and the function guides the search algorithm towards goal states effectively. Conformant-FF-d and the POND system are tested on domains which are used in the international planning competition. Experimental results show that Conformant-FF-d can deal with uncertain goals expressed in disjunctive form and outperforms the POND system in both efficiency and scalability.

关 键 词：Conformant规划 析取目标 松弛规划图 SAT 2-CNF推理 

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