Plan repair as an extension of planning

Abstract

In dynamic environments, agents have to deal with changing situations. In these cases, repairing a plan is often more efficient than planning from scratch, but existing planning techniques are more advanced than existing plan repair techniques. Therefore, we propose a straightforward method to extend planning techniques such that they are able to repair plans. This is possible, because plan repair consists of two different operations: (i) removing actions, and (ii) adding actions. Adding actions is similar to planning, but planning heuristics can also be used for removing actions, which we call unrefinement. We present a plan repair template that reflects these two operations, and we present a heuristic for unrefinement that uses arbitrary existing planning techniques. We show that the resulting method is much better than replanning from scratch, and also significantly better than another plan repair method (GPG). Furthermore, we show that the plan repair template is a generalisation of existing plan repair methods.