On the Complexity
of Plan Adaptation by Derivational Analogy
in a Universal Classical Planning Framework

Tsz-Chiu Au1, Hctor Muoz-Avila2, and Dana S. Nau1

1 Department of Computer Science and Institute for System Research
University of Maryland, College Park, MD 20742, USA
{chiu, nau}@cs.umd.edu
2 Department of Computer Science and Engineering
Lehigh University, Bethlehem, PA 18015, USA
munoz@cse.lehigh.edu



Abstract. In this paper we present an algorithm called DerUCP, which
can be regarded as a general model for plan adaptation using Derivational 
Analogy. Using DerUCP, we show that previous results on the
complexity of plan adaptation do not apply to Derivational Analogy. We
also show that Derivational Analogy can potentially produce exponential 
reductions in the size of the search space generated by a planning
system.
References

1.	Veloso, M., Garbonell, J.: Derivational analogy in PRODIGY: Automating case
acquisition, Storage and Utilization. Machine Learning (1993) 249278
2.	Ihrig, L., Kambhampati, S.: Plan-space vs. State-space planning in reuse and
replay. Technical report, Arizona State University (1996)
3.	Muoz-Avila, H.: Case-Base Maintenance by Integrating Case Index Revision
and Case Retention Policies in a Derivational Replay Framework. Computational
Intelligence 17 (2001)
4.	Nebel, B., Koehier, J.: Plan reuse versus plan generation: a theoretical and empirical 
analysis. Artificial Intelligence 76 (1995) 427454
5.	Kambhampati, S., Srivastava, B.: Unifying Classical Planning Approaches. Technical 
report, Arizona State University (1996)
6.	Fikes, R., Hart, P., Nilsson, N.: Learning and executing generalized robot plans.
Artificial Intelligence 3 (1972) 251288
7.	Carbonell, J.G.: Derivational analogy: A theory of reconstructive problem solving
and expertise acquisition. Machine Learning (1986)
8.	Bhansali, S., IIarandi, M.T.: When (not) to Use Derivational Analogy: Lessons
Learned Using APU. In Aha, D., ed.: Proceeding of AAM-94 Workshop: Case-
based Reasoning. (1994)
9.	Blumenthal, B., Porter, B.: Analysis and Empirical Studies of Derivational Analogy. 
Artificial Intelligence 67 (1994) 287328
10.	Finn, D., Slattery, S., Cunningham, P.: Modelling of Engineering Thermal Problems - 
An implementation using CBR with Derivational Analogy. In: Proceedings
of EWCBR93, Springer-Verlag (1993)
11.	Ihrig, L., Kambhampati, S.: Derivation Replay for Partial-Order Planning. AAAI-
1994 (1994)
12.	Muoz-Avila, H., Weberskirch, F.: Planning for Manufacturing Workpieces by
Storing, Indexing and Replaying Planning Decisions. Proc. 3rd Int. Conference on
Al Planning Systems (AIPS-96) (1996)
13.	Muoz-Avila, H., Paulokat, J., Wess, S.: Controlling Nonlinear Hierarchical Planning 
by Case Replay. In: Proceedings the 2nd European Workshop on Case-Based
Reasoning (EWCBR-94). (1994) 195203
14.	Bylander, T.: The Computational Complexity of Propositional STRIPS Planning.
Artificial Intelligence 69 (1994) 165204
15.	Kambhampati, S.: Exploiting causal structure to control retrieval and refitting
during plan reuse. Computational Intelligence 10 (1994) 213244
16.	Hanks, S., Weld, D.S.: A Domain-Independent Algorithm for Plan Adaptation.
Journal of Artificial Intelligence Research 2 (1995) 319360
17.	Korf, R.: Planning as Search: A Quantitative Approach. Artificial Intelligence 33
(1987) 6588
