Cost-Optimal External Planning

Abstract

This paper considers strategies for external memory based optimal planning. An external breadth-first search explo-ration algorithm is devised that is guaranteed to find the cost-optimal solution. We contribute a procedure for finding the upper bound on the locality of the search in planning graphs that dictates the number of layers that have to be kept to avoid re-openings. We also discuss an external variant of Enforced Hill Climb-ing. Using relaxed-plan heuristic without helpful-action pruning we have been able to perform large explorations on metric planning problems, providing better plan lengths than have been reported earlier. A novel approach to plan recon-struction in external setting with linear I/O complexity is pro-posed. We provide external exploration results on some re-cently proposed planning domains.