Publication Details
Title: Dynamic Constraints
Author: H. W. Guesgen and J. Hertzberg
Group: ICSI Technical Reports
Date: April 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-14.pdf
Overview:
Usually, a constraint describes a relation on variables, and networks of constraints are obtained by sharing variables among constraints. Manipulating a constraint or a constraint network means manipulating the variables until a consistent assignment is found. There are, however, deviations from this classical view, e.g., manipulating the constraints themselves to make the computation of consistent assignments more efficient, or relaxing constraints to make an overspecified constraint problem solvable. In this paper, we present a formalism that subsumes classical constraint satisfaction, constraint manipulation, and constraint relaxation. The idea is that the constraints in a network are not static but that their relations can and must be manipulated and that manipulating relations subsumes manipulating variable values. We clarify the relation between classical constraint networks and the newly developed dynamical ones; we prove termination properties of dynamic constraint networks in the special case of filtering; and we show by examples how to express constraint manipulation and constraint relaxation in the new formalism.
Bibliographic Information:
ICSI Technical Report TR-90-014
Bibliographic Reference:
H. W. Guesgen and J. Hertzberg. Dynamic Constraints. ICSI Technical Report TR-90-014, April 1990
Author: H. W. Guesgen and J. Hertzberg
Group: ICSI Technical Reports
Date: April 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-14.pdf
Overview:
Usually, a constraint describes a relation on variables, and networks of constraints are obtained by sharing variables among constraints. Manipulating a constraint or a constraint network means manipulating the variables until a consistent assignment is found. There are, however, deviations from this classical view, e.g., manipulating the constraints themselves to make the computation of consistent assignments more efficient, or relaxing constraints to make an overspecified constraint problem solvable. In this paper, we present a formalism that subsumes classical constraint satisfaction, constraint manipulation, and constraint relaxation. The idea is that the constraints in a network are not static but that their relations can and must be manipulated and that manipulating relations subsumes manipulating variable values. We clarify the relation between classical constraint networks and the newly developed dynamical ones; we prove termination properties of dynamic constraint networks in the special case of filtering; and we show by examples how to express constraint manipulation and constraint relaxation in the new formalism.
Bibliographic Information:
ICSI Technical Report TR-90-014
Bibliographic Reference:
H. W. Guesgen and J. Hertzberg. Dynamic Constraints. ICSI Technical Report TR-90-014, April 1990