A Connectionist Approach to Constraint Satisfaction

Researchers involved (in chronological order):
Edward Tsang, Chang Wang, Jim Doran, James Borrett, Andrew Davenport, Kangmin Zhu, Chris Voudouris

Constraint Satisfaction is a core of many problems tackled in AI, such as scheduling and temporal reasoning. The importance of constraint satisfaction has led to the development of commercially available constraint satisfaction programming languages and systems, such as CHIP, ECLiPSe and ILOG Solver. However, these are too slow for applications in which rapid solutions are critical or vital, for instance, in interactive systems and problems in which one would like to examine many variables and constraints combinations. Moreover, many real world problems are so tightly constrained that not all the constraints are satisfiable. In such problems near optimal solutions are called for. Complete algorithms are unlikely to be suitable for such problems.

Connectionist approaches have shown good potential in meeting the requirements of the above applications. A connectionist approach has been pursued by our group under the GENET project. The GENET Binary Model, which was first reported in 1990, was designed for handling problems with binary constraints. We have also developed a number of other GENET models for handling non-binary constraints and find near optimal solutions. It has been applied to:

In the future, we would like to investigate the potential of employing current VLSI or parallel processing technology to support GENET implementations.

GENET has been extended to Guided Local Search (GLS) which has been proved to be efficient, effective and have wide scope of applications.

GENET models have been extended by researchers outside our group. Some of the publications known to us can be found in our GENET-related work page.

This project was funded by EPSRC grant GR/H75275 from 1st January 1993 to 30th September 1995.

Publications by our group Publications by other groups

Constraint Satisfaction Home Logo Constraint Satisfaction Home Page