STORING AND INDEXING PLAN DERIVATIONS THROUGH EXPLANATION-BASED ANALYSIS OF RETRIEVAL FAILURES

Case-Based Planning (CBP) provides a way of scaling up domain-independ ent planning to solve large problems in complex domains. It replaces t he detailed and lengthy search for a solution with the retrieval and a daptation of previous planning experiences. In general, CBP has been d emonstrated to improve performance over generative (from-scratch) plan ning. However, the performance improvements it provides are dependent on adequate judgements as to problem similarity. In particular, althou gh CBP may substantially reduce planning effort overall, it; is subjec t to a mis-retrieval problem. The success of CBP depends on these retr ieval errors being relatively rare. This paper describes the design an d implementation of a replay framework for the case-based planner DERS NLP+EBL. DERSNLP+EBL extends current CBP methodology by incorporating explanation-based learning techniques that allow it to explain and lea rn from the retrieval failures it encounters. These techniques are use d to refine judgements about case similarity in response to feedback w hen a wrong decision has been made. The same failure analysis is used in building the case library, through the addition of repairing cases. Large problems are split and stored as single goal subproblems. Multi -goal problems are stored only when these smaller cases fail to be mer ged into a full solution. An empirical evaluation of this approach dem onstrates the advantage of learning from experienced retrieval failure .