The Adaptive Constraint Satisfaction Project, 1992-98

Researchers involved:
Edward Tsang, Jim Doran, James Borrett, Alvin Kwan, Natasha Walsh

Constraint Satisfaction is the core of many problems tackled in AI; one important application in which it plays a significant role is scheduling. The importance of constraint satisfaction has led to active research and the development of commercially available constraint satisfaction systems e.g. CHIP, ECLiPSe and ILOG Solver, in recent years. Basically, these commercial systems use a long established general strategy for all problems. Although they are efficient for some applications, they are inefficient for others.

Mapping problems to algorithms:
Specialized algorithms which exploit certain problem characteristics have been developed in the last decade. Some of the algorithms are extremelly efficient, but correspondingly limited in their applicability. Unfortunately, no one has systematically mapped problems to algorithms according to the problems' requirements and characteristics. Therefore, these specialized algorithms have not been fully utilized in applications.

Objectives of the project:
There were two main objectives in this project. Firstly, we aimed to systematically to map problems (according to their characteristics) to algorithms and heuristics whilst problem-solving is in progress, so that effort can be switched to more effective algorithms when appropriate. Secondly, we aimed to develop a unified adaptive constraint satisfaction strategy in this project, which could help researchers in the constraint satisfaction community to bring effective algorithms to applications. It was a major step towards the development of a new generation of constraint satisfaction systems which could significantly outperform existing ones in speed.

The project was an ambitious one. Following are some of our achievements:

Ahead of time:
This project has made the first steps towards modelling and adaptive constraint satisfaction.

This project was funded by EPSRC grant GR/J42878 between March 1994 and February 1997. Visit our papers section for reports on this project and demos section for demonstration software.

Constraint Satisfaction Home Logo Constraint Satisfaction Home Page