A mathematical framework for a general purpose constraint management system

The use of constraints in engineering for designing complex models is very popular. Current constraint solvers are divided into two broad classes: general and domain specific. Those that are general can handle very general constraint problems but are typically slow; while those that are domain specific can handle only a specific type of problem but are typically fast. For example, numerical algorithms are slow but general, whilst local propagation techniques are fast but limited to simple problems.

It is generally acknowledged that there is a close coupling between engineering constraints and geometric constraints in the design process and so the solution of constraint problems consisting of engineering and geometric constraints is an important research issue. Some authors attempt to overcome the expressive limitations of domain specific solvers by using hybrid systems which try to find a balance between the speed of domain specific solvers and the generality of general solvers.

Previous research at the University of Leeds has led to the development of a number of domain specific solvers that are capable of solving geometric and engineering constraint problems separately. In particular, the Leeds solvers are incremental and can find solutions when a new constraint is added very quickly. This thesis investigates the use of a hybrid of the various Leeds solvers with an aim to interactively solving constraint problems in engineering design, This Hybrid would have the speed advantages of the domain specific solvers and the expressiveness of a more general solver. In order for the hybrid to be constructed, commonalties of existing engineering constraints solvers must be identified. A characterisation of existing constraint solvers leads to the identification of a number of issues that need to be addressed before the hybrid can be built.

In order to examine these issues, a framework for the constraint satisfaction process is presented that allows abstractions of constraint definition, constraint representation and constraint satisfaction. Using the constraint satisfaction framework, it is possible to study the quality of solution of constraint solvers. This leads to the identification of important problems in current constraint solvers.

The constraint process framework leads to a study of the use of various paradigms of collaboration within the hybrid, such as sequential, parallel and concurrent. The study of the quality of solution allows concrete statements to be made about the hybrid collaborations. A new incremental constraint solver is presented that uses the hybrid collaboration paradigms and provides a first step towards a powerful engineering constraint solver.