A Generalized Framework for Constraint Planning 1

Constraint hierarchies have been proposed to solve over-constrained systems of constraints by specifying constraints with hierarchical preferences. They are widely used in HCLP, CIP and graphical user interfaces. A declarative expression of preferred constraints and the existence of efficient satisfaction algorithms are the advantages of constraint hierarchies. At present, there exists a lot of relatively independent constraint hierarchy solvers/satisfaction algorithms that could be classified into two categories as refining and local propagation algorithms. While the local propagation algorithms are fast but limited to equality (functional) constraints the more general refining algorithms are not incremental. In this paper we propose a generalized framework for solving constraint hierarchies, in particular, for constraint planning stage. Our approach is based on ideas of local propagation, however, it suppresses local propagation limits, i.e., restriction to LPB comparator and functional constraints. We introduce a new notion of a constraint cell and we generalize the concept of constraint network here. We also show that the proposed framework covers the refining method as well. Finally, we informally present an algorithm for constraint planning that is an instance of our framework. The proposed algorithm fits in our other concept of plug-in architecture of constraint hierarchy solvers