Operator Decomposability: A New Type of Problem Structure

Richard E. Korf

This paper describes a structural property of problems that allows an efficient strategy for solving a large number of problem instances to be based on a small amount of knowledge. Specifically, the property of operator decomposability is shown to be a sufficient condition for the effective application of the Macro Problem Solver, a method that represents its knowledge of a problem by a small number of operator sequences. Roughly, operator decomposability exists in a problem to the extent that the effect of an operator on each component of a state can be expressed as a function of only a subset of the components, independent of the remaining state components.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.