路标计数启发式引导的分解规划方法

路标信息能够准确描述智能规划问题解空间的基本形态.提出由路标信息引导的分解规划方法,求解过程由路标计数启发式引导增强爬山算法向目标方向进行,根据路标的完成情况分段求出规划解.从全局范围上看,爬山过程逐渐实现更多的路标,路标计数启发式估值的降低引发规划任务的分解,当搜索过程遇到估值更低的状态时,提取一段爬山路径.如此反复执行“搜索-提取”过程,直至路标计数启发式的估值降低为0,各段爬山路径构成最终的规划解.采用最新国际通用的标准测试问题进行实验测试,结果表明:由路标计数启发式引导的分解规划方法能够更好地发挥路标信息的优势,实现了搜索范围的压缩,可更快地生成规划解.

Decomposed Planning Guided by Landmark Counting Heuristic

Landmarks can capture the features of the solution space of planning tasks precisely. In this paper, a decomposed planning method guided by landmark information is proposed. The method executes an enforced hill-climbing procedure guided by the landmark-counting heuristic towards the goal, searching for a plan along with completions of the landmarks. Globally the hill-climbing procedure achieves the landmarks one after another. A decrease in the landmark counting heuristic estimation causes task decomposition and whenever the search encounters a state with a lower estimation, a hill-climbing fragment is extracted. Such "search-extract" procedure is repeated until the estimation of the landmark counting heuristic decreases to zero eventually, and then all the extracted fragments are connected into the final plan. Experiment results show that the decomposed planning method guided by landmark-counting heuristic makes use of the landmark information in a more flexible way, usually cutting down the search space dramatically and find the plan much faster.