A HIGH-PERFORMANCE EXPLANATION-BASED LEARNING ALGORITHM

The main contribution of this paper is a new domain-independent explan ation-based learning (EBL) algorithm. The new EBLDI algorithm signifi cantly outperforms traditional EBL algorithms both by learning in situ ations where traditional algorithms cannot learn as well as by providi ng greater problem-solving performance improvement in general. The sup eriority of the EBLDI algorithm is demonstrated with experiments in t hree different application domains. The EBL''DI algorithm is developed using a novel formal framework in which traditional EBL techniques ar e reconstructed as the structured application of three explanation-tra nsformation operators. We extend this basic framework by introducing t wo additional operators that, when combined with the first three opera tors, allow us to prove a completeness result: in the formal framework , every EBL algorithm is equivalent to the application of the five tra nsformation operators according to some control strategy. The EBLDI a lgorithm employs all five proof-transformation operators guided by fiv e domain-independent control heuristics.