基于延迟部分推理的快速前向规划系统

根据动作组件诱发关系的存在和抵制计算的必要性,提出一个计算松弛规划解的新方法——延迟部分推理.该方法在考虑动作删除效果的假定下,构造不包含任何互斥关系的组件规划图,通过定义"松弛诱发"关系预测后续规划过程中可能出现的组件诱发现象,在松弛规划解提取阶段判断动作组件间的"松弛诱发"关系并选择抵制动作避免可能发生的消极作用.基于延迟部分推理方法定义了新的启发式函数和剪枝策略,设计了规划系统FFc并在多个国际通用的测试域上进行实验.结果表明,FFc较之Fast-Forward在求解效率和求解质量方面都有显著的提高.

Fast Forward Planning System Based on Delayed Partly Reasoning

Heuristic based planning becomes the main trend of AI planning and has been proven to be successful in almost every type of planning problems.High quality heuristics and effective pruning methods are two keys to such planning systems.Realizing the two techniques based on relaxed-plans was first used for the Fast-Forward(FF)planning system and is still used by current top-performing planners.Concerning the inconsistent performance of FF in ADL domains,the authors introduce a new method for extracting relaxed plans while considering the inducing relations between components and the necessity of doing confrontations that are common in ADL planning.A relaxed inducing relation between components is proposed to predict possible inducing relations in the actual planning process.Based on actions' delete effects and a simplified components planning graph,confrontations are done in the relaxed-plan-extraction phase to handle negative interactions between components.Both the improved heuristic and the improved pruning technique based on the new relaxed-plan extraction method are implemented in a system called FFc.Experimental results show FFc outperforms FF in several ADL domains in both planning efficiency and planning quality.The authors' work shows the subtleness of state space planning that handles conditional effects partially using an IPP method or factored expansion,and provides an efficient method to deal with such complicacies.