Systematic Approach to the Design of Representation-Changing Algorithms

The performance of all problem-solving systems depends crucially on problem representation. The same problem may be easy or difficult to solve depending on the way we describe it. Researchers have designed a variety of learning algorithms that deduce important information from the description of the problem domain and use the deduced information to improve the representation. Examples of these representation improvements include generating abstraction hierarchies, replacing operators with macros, decomposing a problem into subproblems, and selecting primary effects of operators. There has, however, been little research on the common principles underlying the representation-improving algorithms and the notion of useful representation changes has remained at an informal level. We present preliminary results on a systematic approach to the design of algorithms for automatically improving representations. We identify the main desirable properties of such algorithms, present a framework for formally specifying these properties, and show how to implement a representation-improving algorithm based on the specification of its properties. We illustrate the use of this approach by developing two novel algorithms that improve problem representations