高级检索
    杨宇鹏 欧阳丹彤 蔡敦波 吕 帅. 基于Conformant Fast-Forward规划系统的析取目标处理方法[J]. 计算机研究与发展, 2008, 45(12): 2120-2128.
    引用本文: 杨宇鹏 欧阳丹彤 蔡敦波 吕 帅. 基于Conformant Fast-Forward规划系统的析取目标处理方法[J]. 计算机研究与发展, 2008, 45(12): 2120-2128.
    Yang Yupeng, Ouyang Dantong, Cai Dunbo, and Lü Shuai. Extending Conformant Fast-Forward to Deal with Disjunctive Goals[J]. Journal of Computer Research and Development, 2008, 45(12): 2120-2128.
    Citation: Yang Yupeng, Ouyang Dantong, Cai Dunbo, and Lü Shuai. Extending Conformant Fast-Forward to Deal with Disjunctive Goals[J]. Journal of Computer Research and Development, 2008, 45(12): 2120-2128.

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

    Extending Conformant Fast-Forward to Deal with Disjunctive Goals

    • 摘要: 将规划系统Conformant Fast-Forward从单目标规划扩展到基于析取目标的不确定规划,设计并实现了新的规划系统Conformant-FF-d.Conformant-FF-d的新功能主要包括:目标状态判断、可达性分析和启发函数.提出一种利用SAT技术进行目标状态判断的高效方法;提出析取目标条件下信念状态的可达性分析方法,有效地删除无法到达目标的信念状态,进而缩小了搜索空间的规模;设计了适用于析取目标的启发函数,有效地指导搜索算法向更有希望到达目标的方向进行.在国际规划竞赛的问题域上对Conformant-FF-d和先进的规划系统POND进行测试和对比分析,实验结果表明:Conformant-FF-d的求解效率高而且具有较好的可扩展性.

       

      Abstract: 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.

       

    /

    返回文章
    返回