Publication
Plan Modification versus Plan Generation: A Complexity-Theoretic Perspective
Bernhard Nebel; Jana Koehler
In: Ruzena Bajcsy (Hrsg.). Proceedings of the 13th International Joint Conference on Artificial Intelligence. International Joint Conference on Artificial Intelligence (IJCAI-1993), August 28 - September 3, Chambéry, France, Pages 1436-1441, Vol. 2, ISBN 155860300X, 9781558603004, Morgan Kaufmann, 1993.
Abstract
The ability of a planner to modify a plan is considered as a valuable tool for improving efficiency of planning by avoiding the repetition of the same planning effort. From a computational complexity point of view, however, it is by no means obvious that modifying a plan is computationally as easy as planning from scratch if the modication has to follow the principle of "conservatism," i.e. to reuse as much of the old plan as possible. Indeed considering propositional STRIPS planning it turns out that conservative plan modifcation is as hard as planning and can sometimes be harder than plan generation. Furthermore this holds even if we consider modication problems where the old and the new goal specication are similar. We put these results into perspective and discuss the relationship to existing plan modication systems.