Date: Tue, 10 Dec 1996 03:25:53 GMT Server: NCSA/1.4.2 Content-type: text/html The SkyBlue Constraint Solver and Its Applications

The SkyBlue Constraint Solver and Its Applications

Author: Michael Sannella

To appear in Vijay Saraswat and Pascal van Hentenryck (eds), Proceedings of the 1993 Workshop on Principles and Practice of Constraint Programming, MIT Press, 1994.


Abstract

The SkyBlue constraint solver uses multi-way local propagation to efficiently maintain constraints organized in a constraint hierarchy. As individual constraints are added and removed, SkyBlue executes method procedures associated with each constraint to incrementally resatisfy the constraints. SkyBlue is a successor to the DeltaBlue algorithm, which has two significant limitations: cycles of constraints are prohibited, and constraint methods can only have a single output variable. SkyBlue relaxes these restrictions, satisfying cycles of constraints by calling external solvers and supporting multi-output methods.

This paper compares SkyBlue to other constraint solvers, describes the SkyBlue algorithm and discusses several applications that have been built using SkyBlue. The SkyBlue algorithm description introduces several new concepts including method vines (used to select which methods to execute) and walkbounds (a generalization of DeltaBlue's walkabout strengths).


Click here to get the postscript file.

Return to Constraints home page