Introduction

Case-Based Planning improves the efficiency of plan generation by taking advantage of previous problem-solving experiences. It has been shown to be an effective method for scaling up domain-independent planning to solve large problems in complex domains [22,40]. CBP involves storing information about the particular planning episodes in which problems are successfully solved. This information may include the goals that were achieved, the world state conditions which were found to be relevant to their achievement, the final plan and the decisions that were taken in arriving at this plan. Whenever a new problem is encountered, a judgment is made about its similarity to these previous experiences. Similar cases are then reused and extended in the search for a solution to the new problem. For example, the previous plan may be transformed into a skeletal plan which is then further refined into a new solution [10,22,13]. Multiple cases, each corresponding to a small subproblem, may be combined and extended in solving a single larger problem [36,35]. Alternatively, plan derivations may be replayed to provide guidance to a new search process [40,15]. CBP improves problem-solving in that problems are solved in less time in comparison to generative planning.

One of the most challenging tasks in CBP is in determining which cases to store and how to match these cases to a new problem-solving context. In a complex domain, it is unlikely that the same problem will be seen more than once. Moreover, if every problem solved is stored, the library will be large and the cost associated with retrieval may overshadow any gains that it provides [26,9]. Ultimately, we would like to retain in the library a minimum number of cases such that all new problems are solved through the efficient retrieval and adaptation of the cases that are stored [37]. However, in complex domains, the planner's theory of problem similarity is incomplete [1]. It does not have information about all of the relevant features of a new situation which determine if a stored case will be applicable. Sometimes a new problem will contain extra goals and/or changed initial state conditions. These changes may mean that a solution cannot be found which is consistent with the earlier planning decisions made in a stored episode. If the planner cannot predict ahead of time that these previous choices are wrong for the current situation, it will experience a retrieval error.

In this paper, we introduce DERSNLP+EBL (DERivational Systematic NonLinear Planner + Explanation-Based Learning), a CBP system which like PRIAR [22] and SPA [13] is based on a sound and complete domain-independent planner. DERSNLP+EBL deals with the mis-retrieval problem by allowing the planner to learn from its planning failures so that it may anticipate future errors. Failure explanations are automatically generated from the search process which is used in extending the case to the new problem-solving situation. These are used in building the case library through the addition of repairing cases.

Although earlier systems such as CHEF [12] have exploited EBL techniques, their use is restricted to reasoning about the correctness of the plans generated by the case-based planner. In contrast, DERSNLP+EBL starts with a sound and complete plan synthesis strategy. The emphasis here is on improving the performance of the base-level planner through the guidance of the retrieved cases. This guidance is considered to succeed if it leads the planner down a search path leading to a solution to the new problem. A retrieval error occurs when the planner is directed down a wrong path in its search for a solution, that is, a path that does not lead to a solution. DERSNLP+EBL extends current CBP methodology through EBL techniques which are employed in the automatic generation of reasons for a retrieval failure. Analytical failures that occur in the leaf nodes of the search tree are explained in terms of subsets of conflicting plan constraints. These leaf node failure explanations are regressed up the failing search paths to form a reason for the retrieval failure.

DERSNLP+EBL builds and indexes the case library based on this failure analysis. The failure reason is used in the construction of a new repairing case. For example, if a retrieved case fails due to the presence of an extra interacting goal which is not covered in the retrieved episodes, an explanation for the failure is formed which identifies the subset of new input goals which are negatively interacting. The failure reason is used to construct a new case which solves those goals alone. The same failure analysis is also employed in refining the indexing in the case library to both censor the retrieval of the failing case whenever the interacting goals are present again, and to direct the retriever to a new repairing case which avoids the failure.

DERSNLP+EBL's failure-based storage strategy limits the size of the case library. Library size is reduced by splitting problems into single goal subproblems, and storing these separately. Large problems are then solved through the retrieval and adaptation of multiple instances of these smaller cases. Multi-goal problems are stored only when the retrieved cases fail to be merged and extended into a full solution. We will describe empirical studies which demonstrate substantial improvements in performance with this novel approach to multi-case adaptation.

The remainder of the paper is organized as follows: Section 2 describes how DERSNLP+EBL learns from case failure to improve its case retrieval. It also reports some preliminary experiments testing this learning component. Section 3 provides efficient techniques used to store, retrieve and adapt multiple cases. It describes experiments to test DERSNLP+EBL's method of plan merging. Section 4 describes an evaluation of the full DERSNLP+EBLsystem when solving large problems drawn from a complex domain. Section 5 relates our work to previous case-based planners, including CHEF and PRODIGY/ANALOGY. Section 6 provides a summary.