In this paper we have described the design and implementation of the case-based planner, DERSNLP+EBL. The DERSNLP+EBL framework represents an integration of eager case adaptation with failure-based EBL. EBL techniques are employed in building the case library on the basis of experienced retrieval failures. This approach improves on earlier treatments of case retrieval [1,22,15,42]. As a partial-order case-based planner, DERSNLP has the ability to solve large problems by retrieving multiple instances of smaller subproblems and merging these cases through sequenced replay [15]. The DERSNLP+EBL framework extends this approach through the use of new EBL techniques which are employed in the construction of the case library. These techniques are used to explain a plan merging failure and to identify a set of negatively interacting goals. The library is then augmented with a new repairing case covering these interacting goals.
DERSNLP+EBL's method of storing multi-goal cases only when goals are negatively interacting results in a small library size and low retrieval costs. However, multi-case adaptation also involves a tradeoff since effort is expended in merging multiple instances of stored cases. DERSNLP+EBL accomplishes this merging by increasing the justification for replay of step addition decisions. This strategy avoids the addition of redundant steps when goals positively interact. DERSNLP+EBL is therefore aimed at domains such as the Logistics Transportation domain where there is a significant amount positive interaction. It is also aimed at domains where there is negative interaction. It is of course futile to spend effort in explaining case failure if none are encountered.
Section 4 describes an evaluation of the overall efficiency of this storage and retrieval strategy when solving large problems in a complex domain. DERSNLP+EBL shows an improvement in planning performance which more than offsets the added cost entailed in retrieving on failure conditions. The amount of improvement provided by replay shown in these experiments should be seen as a lower bound since a random problem distribution may mean less problem similarity than is found in real world problems.
In conclusion, this paper has described a novel approach to integrating explanation-based learning techniques into case-based planning. This approach has been aimed at issues associated with both pure case-based planning, and with rule-based EBL. In particular, it addresses the mis-retrieval problem of CBP, as well as the utility problem. The results demonstrate that eager case adaptation when combined with DERSNLP+EBL's dynamic case retrieval is an effective method of improving planning performance.