Adaptive search through constraint violations

Abstract

Abstract We describe HS, a production system that learns control knowledge through adaptive search. Unlike most other psychological models of skill acquisition, HS is a model of analytical, or knowledge-based, learning. HS encodes general domain knowledge in state constraints, patterns that describe those search states that are consistent with the principles of the problem domain. When HS encounters a search state that violates a state constraint it revises the production rule that generated that state. The appropriate revisions are computed by regressing the constraint through the action of the production rule. HS can learn to solve problems that it cannot solve without learning. We present a Blocks World example of a rule revision, empirical results from both initial learning experiments and transfer experiments in the domain of counting, and an informal analysis of the conditions under which this learning technique is likely to be useful.