Related Work and Discussion

  DERSNLP+EBL's storage strategy relies on the capability of the case-based planner to replay multiple cases, each covering a small subset of goals, and then add step orderings to interleave their respective plans. This strategy differs from earlier approaches such as PRIAR [22], PRODIGY/ANALOGY [40], PARIS [3], and CAPLAN [32], in that the division into goal subsets is not based on the structure of the final plan alone, but on the sequence of events making up the problem-solving episode. Retrieval failures are treated as an opportunity by which the planner stores a new repairing case. In this aspect it is similar to Hammond's CHEF [12] which also learns to improve its retrieval strategy based on failures. Despite this surface similarity, there are important differences in our approach. DERSNLP+EBL learns from case extension failures, whereas CHEF concentrates on learning from execution failures. Specifically, CHEF assumes an incomplete domain model, consisting of stored cases, and a domain-specific modification theory of patches. Given a new problem, CHEF retrieves a previous case, and modifies the retrieved plan using domain specific modification rules to generate a candidate solution for the current problem. The correctness of this solution is then tested with respect to an external causal simulator of the domain. If the solution is found to be incorrect, the explanation of incorrectness (supplied by the simulator) is used to modify the case-library to censor the retrieval of the case in similar situations in the future. This in effect improves the correctness of CHEF's domain theory. In contrast, DERSNLP+EBL assumes complete knowledge of the domain, in the form of domain operators. It also has access to a sound and complete plan synthesis strategy. The aim of case-based reasoning in DERSNLP+EBL is to improve the performance of the base-level planner. To this end, DERSNLP+EBL analyzes case extension failures to predict when a case cannot be extended to solve a new problem.

  

Figure 23: Some different approaches to case-based planning where case adaptation is accomplished by an underlying generative planner.

Fox and Leake [8] have taken an approach similar to that of CHEF, but use introspective reasoning to explain failures and find repairing cases. Similar to CHEF, introspective reasoning is used to revise indexing in the case library [8,34]. Other approaches employ domain-specific techniques to improve storage and retrieval from a case library [32,37]. DERSNLP+EBL differs in that it automatically generates new indices through a well defined and domain-independent methodology [24] which is incorporated into the underlying planning strategy.

Since EBL is employed in explaining case failure as well as success, DERSNLP+EBL complements and extends earlier approaches to case retrieval [1,22,14,40,3,32,35]. Although it exhibits low retrieval and match cost, as with any CBP system, this efficiency may degrade with larger domain size. DERSNLP+EBL's approach is compatible with others aimed at improving match cost [6,35,14]. For example, MPA [35] is built around a retrieval engine which performs asynchronous memory retrieval. CAPER [14] uses a structure matching algorithm which parallelizes the process by which the plan's success conditions represented as a retrieval probe are matched with a large knowledge base of world facts. This process expands binary predicates which match the success conditions into a larger structure containing implicitly specified relations in the knowledge base. This structure acts as a filter, eliminating matches which fail to line up with the probe.

DERSNLP+EBL is similar to case-based systems which employ a complete and correct domain-independent planner to generate cases to be stored [13,22,26,40,35]. In surveying this literature, it is possible to distinguish these approaches on two orthogonal scales as shown in Figure 23. In the horizontal direction, the CBP frameworks are ranked as to how the underlying planning strategy falls on a continuum whose end extremes represent the state-space vs plan-space dichotomy. Towards the state-space end of the spectrum is PRODIGY/ANALOGY, which employs the means-ends analysis (MEA) planner, NOLIMIT, to extend a previous case. NOLIMIT is here classed as a state-space planner since it applies actions to the plan based on the current world state and thereby advances the world state.

The PRIAR framework [22,20] is based within NONLIN [39]. NONLIN creates its plans through hierarchical task reduction. It is also a partial-order (plan-space) planner which constructs plans by protecting their underlying causal structure. Like DERSNLP+EBL, it extends a case through the normal course of plan refinement defined by an underlying plan-space strategy. However, DERSNLP+EBL is implemented within the partial-order, causal-link planner, SNLP [28,2]. In this aspect it is similar to the SPA system developed by Hanks and Weld [13].

The different CBP systems may also be distinguished according to their case adaptation strategy. These can be roughly categorized as either transformational or derivational [4,43], according to whether they transform a previous plan or replay a previous plan derivation. In the transformational strategies of PRIAR and SPA, the final plan which is the product of the planning episode is stored in the case library. When a case is retrieved this plan is fitted to adapt to the new problem-solving situation by retracting the irrelevant or redundant subparts. Early CBP systems [4,12] also employ transformational techniques to adapt a previous solution. Causal-link planners such as SNLP are ready-made for plan reuse since the causal structure which is employed in plan adaptation is a part of the plan itself. PRIAR and SPA use the plan's causal structure both in fitting the plan to the new problem context, and in extending the fitted plan to solve the new problem. PRIAR differs from SPA in that it employs an extension-first strategy. The skeletal plan is first refined through the addition of plan constraints before undertaking any further retraction of constraints. SPA, on the other hand, alternates the retraction of the plan constraints with the further addition of new constraints. MPA [35] extends SPA's transformational strategy to accomplish multi-case retrieval and adaptation.

As mentioned earlier, derivational analogy is a case-based planning technique which was introduced by Carbonell [43]. This model was developed by Veloso in PRODIGY/ANALOGY [40], which employed the case fitting strategy called derivational replay. Case fitting based on replay is similar to fitting in plan reuse, in that it is based on the plan's underlying causal structure. The justification for each planning decision which is stored in the derivation trace reflects the causal dependencies between plan steps. Only justified choices are replayed in solving the new problem. Replay thus serves the same purpose as retraction in plan reuse. Replay may have an advantage in multi-case reuse since it allows the planner to readily merge small subplans to solve large problems.

DERSNLP can be contrasted to PRODIGY/ANALOGY in that it employs a case fitting methodology called eager derivation replay [15,17]. With this replay strategy, the applicable cases are replayed in sequence before returning to from-scratch planning. Eager replay simplifies the replay process by avoiding the decision as to how to alternate replay of multiple cases. The effectiveness of this approach is dependent on the underlying plan-space planning strategy [15]. DERSNLP's eager case adaptation strategy allows case failure to be defined in terms of the failure of a single node in the search tree. In particular, case failure is defined as the failure of the skeletal plan, which contains all of the constraints that have been adopted on the advice of the previous cases. Eager case adaptation means that explanations of case failure may be constructed through the use of EBL techniques which have been developed to explain analytical failures occurring in the planner's search space.