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