Skyblue: a multi-way local propagation constraint solver for user interface construction

ABSTRACT

Many user interface toolkits use constraint solvers to maintain geometric relationships between graphic objects, or to connect the graphics to the application data structures. One efficient and flexible technique for maintaining constraints is multi-way local propagation, where constraints are represented by sets of method procedures. To satisfy a set of constraints, a local propagation solver executes one method from each constraint.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). SkyBlue is a more general successor to the DeltaBlue algorithm that satisfies cycles of methods by calling external cycle solvers and supports multi-output methods. These features make SkyBlue more useful for constructing user interfaces, since cycles of constraints can occur frequently in user interface applications and multi-output methods are necessary to represent some useful constraints. This paper discusses some of applications that use SkyBlue, presents times for some user interface benchmarks and describes the SkyBlue algorithm in detail.

REFERENCES

• 1: Franz G. Amador, Adam Finkelstein, and Daniel S. Weld. Real-Time Self-Explanatory Simulation. In Proceedings of the Eleventh National Conference on Artificzal intelligence, pages 562-567. AAAI Press/The MIT Press, July 1993.
• 2: Alan Borning , Bjorn Freeman-Benson , Molly Wilson, Constraint hierarchies, Lisp and Symbolic Computation, v.5 n.3, p.223-270, Sept. 1992 [doi>10.1007/BF01807506]
• 3: Conal Elliott , Greg Schechter , Ricky Yeung , Salim Abi-Ezzi, TBAG: a high level framework for interactive, animated 3D graphics applications, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.421-434, July 1994 [doi>10.1145/192161.192276]
• 4: Bjorn Nathan Freeman-Benson, Constraint imperative programming, University of Washington, Seattle, WA, 1992
• 5: Bjorn N. Freeman-Benson, Converting an existing user interface to use constraints, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.207-215, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168663]
• 6: Bjorn N. Freeman-Benson , John Maloney , Alan Borning, An incremental constraint solver, Communications of the ACM, v.33 n.1, p.54-63, Jan. 1990 [doi>10.1145/76372.77531]
• 7: Enrico Gobbetti , Jean-Francis Balaguer , Daniel Thalmann, VB2: an architecture for interaction in synthetic worlds, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.167-178, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168659]
• 8: Ralph D. Hill , Tom Brinck , Steven L. Rohall , John F. Patterson , Wayne Wilner, The Rendezvous architecture and language for constructing multiuser applications, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.81-125, June 1994 [doi>10.1145/180171.180172]
• 9: John Harold Maloney, Using constraints for user interface construction, University of Washington, Seattle, WA, 1992
• 10: Brad A. Myers , Dario A. Giuse , Roger B. Dannenberg , David S. Kosbie , Edward Pervin , Andrew Mickish , Brad Vander Zanden , Philippe Marchal, Garnet: Comprehensive Support for Graphical, Highly Interactive User Interfaces, Computer, v.23 n.11, p.71-85, November 1990 [doi>10.1109/2.60882]
• 11: Michael Sannella, Analyzing and Debugging Hierarchies of Multi-way Local Propagation Constraints, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.63-77, May 02-04, 1994
• 12: Michael John Sannella, Constraint satisfaction and debugging for interactive user interfaces, University of Washington, Seattle, WA, 1994
• 13: Michael Sannella. The SkyBlue Constraint Solver and Its Applications. In Saraswat and van Hentenryck, editors, Proceedings of the 1993 Workshop on Princzples and Practice of Constraint Programmzng. MIT Press, 1994. To appear.
• 14: Michael Sannella and Alan Borning. Multi-Garnet: Integrating Multi-Way Constraints with Garnet. Technical Report 92-07-01, Department of Computer Science and Engineering, University of Washington, September 1992.
• 15: Michael Sannella , John Maloney , Bjorn Freeman-Benson , Alan Borning, Multi-way versus one-way constraints in user interfaces: experience with the DeltaBlue algorithm, Software—Practice & Experience, v.23 n.5, p.529-566, May 1993 [doi>10.1002/spe.4380230507]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: User interface management systems (UIMS)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
SkyBlue, constraint hierarchies, constraints, local propagation, user interface implementation