Publication
Plan Reuse versus Plan Generation: A theoretical and empirical Analysis
Bernhard Nebel; Jana Koehler
In: Artificial Intelligence (AIJ), Vol. 76, No. 1-2, Pages 427-454, ELSEVIER, Amsterdam, 7/1995.
Abstract
The ability of a planner to reuse parts of old plans is hypothesized to be a valuable tool for improving effciency of planning by avoiding the repetition of the same planning effort. We test this hypothesis from an analytical and empirical point of view. A comparative worst case complexity analysis of generation and reuse under different assumptions reveals that it is not possible to achieve a provable effciency gain of reuse over generation. Further, assuming "conservative" plan modifcation, plan reuse can actually be strictly more difficult than plan generation. While these plan may present a serious bottleneck for plan reuse systems, as we will show. Finally we present the results of an empirical study of two different plan reuse systems, pointing out possible pitfalls one should be aware of when attempting to employ reuse methods.