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 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 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.