基于路标隐式分解的前向搜索规划方法

摘要

A planning algorithm that implicitly decomposes the forward search procedure with landmark information is proposed.The original planning task is decomposed into several smaller sub-tasks according to the estimation of the landmark counting heuristic.Whenever the search visits a state with lower heuristic value,a sub-task is completed.The procedure is iterated until the estimation of the landmark-counting heuristic reduces to zero.The plan fragments of all the sub-tasks are connected into the final solution.The experimental results show the superiority of the proposed algorithm.The implicit task decomposition is introduced by the landmark counting heuristic.Therefore,compared with the existing decomposition methods that treat landmarks as mandatory subgoals,the proposed algorithm guides the forward search procedure faster,cuts down the search space dramatically and makes considerable improvement in both planning efficiency and planning quality.%提出一种利用路标信息隐式分解前向搜索过程的规划算法.以路标计数启发式估值的降低作为分界点,将规划任务分解成多个规模更小的子任务,当访问到估值更低的状态时,表明搜索过程完成一个子任务的求解,反复执行这一过程直到路标计数启发式估值降低为零.与其它将路标具体指定为中间目标的分解方法相比,基于路标计数启发式的隐式分解方法能指导前向搜索过程快速向目标方向推进,实现搜索空间的大规模压缩,在求解效率和规划解质量上都有较大提高.