A Transformational Analysis of the EBL Utility Problem

Abstract

Efficiency is a major concern for all problem solving systems. One way of achieving efficiency is the application of learning techniques to speed up problem solving. Accordingly, there has been considerable amount of research on applying explanation-based learning (EBL)(Mitchell, Keller, & Kedar-Cabelli 1986) techniques to problem solving. However, EBL is known to suffer from the utility problem, where the cost of using the learned knowledge overwhelms its benefit. We show that how the cost increase of a learned rule in an EBL system can be analyzed by characterizing the learning process as a sequence of transformations from a problem solving episode to a learned rule. The analysis of how the cost changes through the transformations can be a useful tool for revealing the sources of cost increase in the learning system. We focus on the Soar problem solving system which uses a variant of EBL called chunking(Rosenbloom et al. 1991). The chunking process has been decomposed into a sequence of transformations from the problem solving to a chunk (learned rule). By analyzing these transformations, we have identified a set of sources which can make the output chunk expensive. The set of sources and the proposed solutions are :