Eliminating Expensive Chunks by Restricting Expressiveness

Abstract

Cltunking , an experience based-learning mechanism, improves Soar's perfonnance a great deal when viewed in terms of the number of su bproblem s required and the number of steps within a subproblem. This high-level view of the impact of chunking on performance is based on an ideal computational model, which says that the time per step is constant. However, if the chunks created by chunking are expensive, then they coosume a large amount of processing in the match, i.e, indexing the knowledge -base, distorting Soar's constant time-per-step model. In these situations , the gain in number of steps does not reflect an improvement in perfonnance ; in fact there may be degradation in the total run time of the sy stem . Su ch chunks form a major problem for the system, since absolutely no guarantees can be given about its behavior. This article presents a solution to the problem of expensive chunks. The solution is based on the notion of restricting the expressiveness of Soar's representational language to guarantee that chunks formed will require only a limited amount of matching effort. We analyze the tradeoffs involved in restricting expressiveness and present some empirical evidence to support our analysis.