Abstract
There exist planning algorithms that can quickly find sub-optimal plans even for large problems and planning algorithms finding optimal plans but only for smaller problems. In this paper we attempt to integrate both approaches.
We present an anytime technique for improving plan quality, in particular decreasing the plan makespan, via substituting parts of the plan by makespan-optimal sub-plans. The technique guarantees optimality though it is primarily intended to quickly improve plan quality.
We experimentally compare various approaches to local improvements and we show that our method has significantly better makespan score than the SASE planner, which is one of the best optimal planners.