图规划基于距离的目标排序启发式

Study on goal ordering heuristic based on distance

讨论图规划回溯搜索过程中变量和值排序的缺点,并且提出一个基于实现某一子目标的难度的简单策略即获得子目标的困难度,该标准可以通过规划图本身的结构加以量化,特殊的使用子目标在规划图中最早出现用层的下标来表示.结果表明该方法在许多标准的规划问题求解过程中的惊人效果.

This paper discusses the shortcomings of variable and value ordering strategies for Graphplan's backward search phase, and proposes a novel strategy that is based on a notion of the difficulty of achieving the corresponding sub-goal. The difficulty of achievement is quantified in terms of the structure of the planning graph itself-specifically, the earliest level of the planning-graph at which that sub-goal appears. Puts forward the empirical results showed that the surprising effectiveness of this simple heuristic on many problems.