Generalized Local Propagation:

A Framework for Solving Constraint Hierarchies

Hiroshi Hosobe,1 Satoshi Matsuoka,2 and Akinori Yonezawa1

1 Department of Information Science
2 Department of Mathematical Engineering
University of Tokyo
3-1, Hongo 7-chome, Bunkyo-ku, Tokyo 113, JAPAN
fdetail@is.s, matsu@ipl.t, yonezawa@is.sg.u-tokyo.ac.jp

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

Keywords: constraint hierarchies, nonmonotonicity, local propagation, multi-way constraints.

1 Introduction

Constraint hierarchies allow programmers to describe over-constrained realworld problems by specifying constraints with hierarchical strengths or preferences [1, 2], and have been applied to various research areas such as constraint logic programming [11, 13], constraint imperative programming [3], and graphical user interfaces [8, 9]. Intuitively, in a constraint hierarchy, the stronger a constraint is, the more it influences the solutions of the hierarchy. For example, the hierarchy of the constraints strong x = and weak x = 1 yields the solution
x 0. This property enables programmers to specify preferential or default constraints that may be used in case the set of required or non-default constraints are under-constrained. Moreover, constraint hierarchies are general enough to handle powerful constraint systems such as arithmetic equations and inequalities over reals. Additionally, they allow `relaxing' of constraints with the same strength by applying, e.g., the least-squares method.