Generalized Local Propagation: A Framework for Solving Constraint Hierarchies

摘要

'Constraint hierarchy' is a nonmonotonic system that allows programmers to describe over-constrained real-world problems by speci-fying constraints with hierarchical preferences, and has been applied to various areas. An important aspect of constraint hierarchies is the exis-tence of efficient satisfaction algorithms based on local propagation. How-ever, past local-propagation algorithms have been limited to multi-way equality constraints. We overcome this by reformulating constraint hier-archies with a more strict definition, and proposing generalized local prop-agation as a theoretical framework for studying constraint hierarchies and local propagation. Then, we show that global semi-monotonicity in satisfying hierarchies turns out to he a practically useful property in generalized local propagation. Finally, we discuss the relevance of gener-alized local propagation with our previous DETAIL algorithm for solving hierarchies of multi-way equality constraints.