The Adaptive Constraint Satisfaction Project, 1992-98

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

Motivation:
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.

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

• Mapping has been developed for, but was limited to, binary constraint satisfaction problems. Mapping for general problems depends on problem formulation (modelling), which was where the emphasis laid in the project.
• Adaptive Search: An effective chain of algorithms was developed, in which search performance is monitored. When the current algorithm fails to achieve what it is designed for (e.g. when a lookahead algorithm was found to fail in pruning future branches), the search switches to the next search algorithm in the chain.

• Adaptive search:
  The idea of monitoring the performance of a search algorithm and switch to another algorithsm was new.
• Ahead of "No Free Lunch":
  The philosophy in this project was: no signle algorithm is good for all problems. Different problems are better served by different algorithms. This idea was developed in 1992. Funding was sought in 1993, well before the "No Free Lunch Theorem" was published.
• First in Modelling:
  In this project, James Borrett developed a framework for automating problem transformation. This was the first project on modelling in constraint satisfaction. Modelling is now high on the agenda of constraint satisfaction research.

Funding:
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 Page