Shortening Plans by Local Re-planning

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 for decreasing the plan make span, via substituting parts of the plan by make span-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 make span score than the SASE planner, which is one of the best optimal planners.