Abstract
Constraint hierarchies provide a framework for soft constraints, and have been applied to areas such as artificial intelligence, logic programming, and user interfaces. In this framework, constraints are associated with hierarchical preferences or priorities called strengths, and may be relaxed if they conflict with stronger constraints. To utilize constraint hierarchies, researchers have designed and implemented various practical constraint satisfaction algorithms. Although existing algorithms can be categorized into several approaches, what kinds of algorithms are possible has been unclear from a more general viewpoint. In this paper, we propose a novel theory called generalized local propagation as a foundation of algorithms for solving constraint hierarchies. This theory formalizes a way to express algorithms as constraint scheduling, and presents theorems that support possible approaches. A benefit of this theory is that it covers algorithms using constraint hierarchy solution criteria known as global comparators, for which only a small number of algorithms have been implemented. With this theory, we provide a new classification of solution criteria based on their difficulties in constraint satisfaction. We also discuss how existing algorithms are related to our theory, which will be helpful in designing new algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Badros, G.J., & Borning, A.(1998).The Cassowary linear arithmetic constraint solving algorithm: Interface and implementation.Technical Report 98-06-04, Dept.of Computer Science and Engineering, University of Washington.
Bistarelli, S., Gennari, R., & Rossi, F. (2000). Constraint propagation for soft constraints: Generalization and termination conditions.In Principles and Practice of Constraint Programming-CP2000, Vol.1894 of LNCS, pages 83–97, Springer.
Borning, A., Anderson, R., & Freeman-Benson, B. (1996). Indigo: A local propagation algorithm for inequality constraints.In Proc. ACM UIST, pages 129–136.
Borning, A., Duisberg, R., Freeman-Benson, B., Kramer, A., & Woolf, M. (1987). Constraint hierarchies. In Proc. ACM OOPSLA, pages 48–60.
Borning, A., & Freeman-Benson, B.(1998).Ultra violet: A constraint satisfaction algorithm for interactive graphics. Constraints J., 3(1): 9–32.
Borning, A., Freeman-Benson, B., & Wilson, M. (1992). Constraint hierarchies. Lisp and Symbolic Comput., 5(3): 223–270.
Borning, A., Marriott, K., Stuckey, P., & Xiao, Y. (1997). Solving linear arithmetic constraints for user interface applications.In Proc. ACM UIST, pages 87–96.
Freeman-Benson, B., Wilson, M., & Borning, A. (1992). DeltaStar: A general algorithm for incremental satisfaction of constraint hierarchies.In Proc. IEEE IPCCC, pages 561–568.
Freeman-Benson, B.N., Maloney, J., & Borning, A.(1990).An incremental constraint solver. Commun. ACM, 33(1): 54–63.
Freuder, E.C., & Wallace, R.J.(1992).Partial constraint satisfaction. Artif. Intell., 58: 21–70.
Harvey, W., Stuckey, P., & Borning, A.(1997).Compiling constraint solving using projection.In Principles and Practice of Constraint Programming—CP97, Vol.1330 of LNCS, pages 491–505, Springer.
Hosobe, H.(2000).A scalable linear constraint solver for user interface construction.In Principles and Practice of Constraint Programming—CP2000, Vol.1894 of LNCS, pages 218–232.Springer.
Hosobe, H.(2001).A modular geometric constraint solver for user interface applications.In Proc. ACM UIST, pages 91–100.
Hosobe, H., Matsuoka, S., & Yonezawa, A. (1996). Generalized local propagation: A framework for solving constraint hierarchies.In Principles and Practice of Constraint Programming—CP96, Vol.1118 of LNCS, pages 237–251.Springer.
Hosobe, H., Miyashita, K., Takahashi, S., Matsuoka, S., & Yonezawa, A. (1994). Locally simultaneous constraint satisfaction.In Principles and Practice of Constraint Programming—PPCP'94, Vol.874 of LNCS, pages 51–62.Springer.
Jampel, M.(1996).A compositional theory of constraint hierarchies (operational semantics).In Over-Constrained Systems, Vol.1106 of LNCS, pages 189–206.Springer.
Maloney, J.H., Borning, A., & Freeman-Benson, B.N.(1989).Constraint technology for user-interface construction in ThingLab II.In Proc. ACM OOPSLA, pages 381–388.
Marriott, K.& Stuckey, P.J.(1998). Programming with Constraints: An Introduction.MIT Press.
Ryu, Y.U.(1999).A hierarchical constraint satisfaction approach to product selection for electronic shopping support. IEEE Trans. Syst., Man, Cybern. A, 29(6): 525–532.
Sannella, M.(1994).Sk yBlue: A multi-way local propagation constraint solver for user interface construction. In Proc. ACM UIST, pages 137–146.
Satoh, K., & Aiba, A.(1991).Computing soft constraints by hierarchical constraint logic programming. Technical Report TR-610, ICOT, Japan.
Schiex, T.(2000).Arc consistency for soft constraints.In Principles and Practice of Constraint Programming—CP2000, Vol.1894 of LNCS, pages 411–424.Springer.
Wilson, M.(1993).Hierarchical constraint logic programming (Ph.d.Dissertation).T echnical Report 93-05-01, Dept.of Computer Science and Engineering, University of Washington.
Wilson, M., & Borning, A.(1989).Extending hierarchical constraint logic programming: Nonmonotonicity and inter-hierarchy comparison.In Proc. North American Conf. on Logic Programming, pages 3–19.
Wilson, M., & Borning, A.(1993).Hierarchical constraint logic programming. J. Logic Prog., 16(3&4): 277–319.
Wolf, A.(1996).Transforming ordered constraint hierarchies into ordinary constraint systems.In Over-Constrained Systems, Vol.1106 of LNCS, pages 171–187.Springer.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hosobe, H., Matsuoka, S. A Foundation of Solution Methods for Constraint Hierarchies. Constraints 8, 41–59 (2003). https://doi.org/10.1023/A:1021946627805
Issue Date:
DOI: https://doi.org/10.1023/A:1021946627805