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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Borning, A., R. Duisberg, B. Freeman-Benson, A. Kramer, and M. Woolf, “Constraint Hierarchies,” in OOPSLA '87, ACM, Oct. 1987, pp. 48–60.
Borning, A., B. Freeman-Benson, and M. Wilson, “Constraint Hierarchies,” Lisp and Symbolic Computation, vol. 5, 1992, pp. 221–268.
Freeman-Benson, B. N. and A. Borning, “Integrating Constraints with an ObjectOriented Language,” in ECOOP'92, no. 615 in LNCS, Springer-Verlag, June/July 1992, pp. 268–286.
Freeman-Benson, B. N., J. Maloney, and A. Borning, “An Incremental Constraint Solver,” Comm. ACM, vol. 33, no. 1, Jan. 1990, pp. 54–63.
Freuder, E. C. and R. J. Wallace, “Partial Constraint Satisfaction,” Artificial Intelligence, vol. 58, 1992, pp. 21–70.
Hosobe, H., K. Miyashita, S. Takahashi, S. Matsuoka, and A. Yonezawa, “Locally Simultaneous Constraint Satisfaction,” in PPCP'94, no. 874 in LNCS, Springer-Verlag, Oct. 1994, pp. 51–62.
Jampel, M., “A Compositional Theory of Constraint Hierarchies (Operational Semantics),” in Proc. Workshop on Over-Constrained Systems at CP'95, Sept. 1995.
Maloney, J. H., A. Borning, and B. N. Freeman-Benson, “Constraint Technology for User-Interface Construction in ThingLab II,” in OOPSLA '89, ACM, Oct. 1989, pp. 381–388.
Sannella, M., “SkyBlue: A Multi-Way Local Propagation Constraint Solver for User Interface Construction,” in UIST'94, ACM, Nov. 1994, pp. 137–146.
Satoh, K. and A. Aiba, “Computing Soft Constraints by Hierarchical Constraint Logic Programming,” Tech. Rep. TR-610, ICOT, Japan, Jan. 1991.
Wilson, M., “Hierarchical Constraint Logic Programming (Ph.D. Dissertation),” Tech. Rep. 93-05-01, Dept. of Computer Science and Engineering, University of Washington, May 1993.
Wilson, M. and A. Borning, “Extending Hierarchical Constraint Logic Programming: Nonmonotonicity and Inter-Hierarchy Comparison,” in Proc. North American Conference on Logic Programming, 1989.
Wilson, M. and A. Borning, “Hierarchical Constraint Logic Programming,” J. Logic Programming, vol. 16, no. 3/4, July/Aug. 1993, pp. 277–319.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hosobe, H., Matsuoka, S., Yonezawa, A. (1996). Generalized local propagation: A framework for solving constraint hierarchies. In: Freuder, E.C. (eds) Principles and Practice of Constraint Programming — CP96. CP 1996. Lecture Notes in Computer Science, vol 1118. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61551-2_78
Download citation
DOI: https://doi.org/10.1007/3-540-61551-2_78
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61551-4
Online ISBN: 978-3-540-70620-5
eBook Packages: Springer Book Archive