Cost-Optimal External Planning

This paper considers strategies for external memory based optimal planning. An external breadth-first search exploration algorithm is devised that is guaranteed to find the costoptimal 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 Climbing. 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 reconstruction in external setting with linear I/O complexity is proposed. We provide external exploration results on some recently proposed planning domains.

Authors

• Stefan Edelkamp Faculty of Mathematics and Physics, Charles University
• Shahid Jabbar

Keywords

No keywords are indexed for this paper.