Catalogue of Artificial Intelligence Techniques
Keywords: Adaptive Consistency, Cycle Cutset, Tree Clustering, backjumping, backtracking
Categories: Knowledge Representation
Author(s): Rina Dechter
Constraint networks offer a graphical representation of Constraint Satisfaction problems that can be used to control search efficiently. A constraint network is a graph (or hypergraph) in which nodes represent variables and arcs represent pairs (or sets) of variables which are included in a common constraint. The topology of this network uncovers opportunities for problem decomposition techniques and provides estimates of the problem complexity prior to actually performing the search. The following are typical network-based techniques.
- Cycle Cutset is a method based on preferentially instantiating variables which intercept cycles in the constraint graph. Once all cycles are intercepted, the rest of the problem becomes tree-structured and can be solved in linear time. The complexity of this scheme is exponential in the size of the cutset found.
- Adaptive Consistency is a method based on enforcing local consistency with adjustable scope. Variables are called sequentially, and local consistency is enforced recursively among their uncalled neighbours. Each such operation would normally result in connecting the neighbours with extra links, called `induced constraints'. When all variables are called, a backtrack-free solution can be found by instantiating the variables in the reverse order.
- Tree Clustering is a method of systematic regrouping constraints into hierarchical structures capable of supporting search without backtracking. The complexity of this transformation is exponential in the size of the largest cluster generated and its main advantage is that, once the clusters are structured, queries can be answered in linear time.
- Freuder, E.C., A sufficient condition for backtrack-bounded search JACM 32 (1985) no.4, 755--761.