Abstract

Many Artificial Intelligence problems, such as theorem proving, computer vision, and expert systems, can be seen as constraint satisfaction problems^1,2,3. In such problems, constraints are given on any possible solution. Most often, the problem is either explicitly stated in terms of allowed partial solutions or can be converted to such a representation. The objective is to find one or more solutions satisfying all constraints simultaneously, or the determination that no such solution exists. A simplistic approach to solving constraint satisfaction problems is to generate all possible solutions, then test each against the constraints to see if indeed they are satisfied. The process of backtracking provides a marginal improvement by testing increasingly larger partial solutions. Consistent Labelling is a more efficient procedure which eliminates allowed partial solutions that conflict with one another ². A problem is represented in a constraint network. Arc and path Consistent Labelling eliminate allowed partial solutions that are inconsistent over the smallest closed loops. The remaining allowed partial solutions can then be used in an efficient backtracking search. Using Consistent Labelling on larger loops, it is possible to obtain solutions to constraint satisfaction problems without backtracking⁴.

© 1989 Optical Society of America