Mechanical Generation of Heuristics for Intractable Theories

A domain independent mechanism for generating heuristics for intractable theories has been implemented in the POLLYANNA program. Heuristics are generated by a process of systematically applying generic simplifying assumptions to an initial intractable theory. Such assumptions sacrifice the accuracy of an intractable theory to gain efficiency in return. Truth preserving reformulations are also used to enhance the power of generic simplifying assumptions. This paper describes a framework for generating heuristics using these basic types of knowledge. Examples and representations of each are presented along with an architecture within which they interact to generate heuristic theories. Results from testing this technique in the hearts card domain are presented as well. This work is pan of a system combining analytic and empirical methods for learning heuristics. In the analytic phase, a set of candidate heuristics is generated from an intractable theory. In the empirical phase, heuristic theories are evaluated against teacher-provided training examples. This paper concentrates on the analytic process of generating heuristics