Analyzing and Debugging Hierarchies of Multi-Way Local Propagation Constraints

Author: Michael Sannella

In Alan Borning (ed.), Proceedings of the 1994 Workshop on Principles and Practice of Constraint Programming, Springer-Verlag, Lecture Notes in Computer Science No. 874, pages 63-77.

Abstract

Multi-way local propagation constraints are a powerful and flexible tool for implementing applications such as graphical user interfaces. SkyBlue is an incremental constraint solver that uses local propagation to maintain a set of constraints as individual constraints are added and removed. If all of the constraints cannot be satisfied, SkyBlue leaves weaker constraints unsatisfied in order to satisfy stronger constraints (maintaining a constraint hierarchy). Our experience has indicated that large constraint networks can be difficult to construct and understand. To investigate this problem, we have developed the CNV system for interactively constructing constraint-based user interfaces, integrated with tools for displaying and analyzing constraint networks. This paper describes the debugging facilities of CNV, and presents a new algorithm for enumerating all of the ways that SkyBlue could maintain a set of constraints.

full paper (compressed postscript)

Constraints home page