On non-conservative plan modification

The problem of minimally modifying a plan in response to changes in the specification of the planning problem has already been investigated in the literature. In this paper we consider the problem of non-minimal modification of plans from a computational point of view. We prove that while the general problem is intractable (that is, replanning from scratch is equally hard), there are scenarios in which the new plan can be built more efficiently (in polynomial time).