Catalogue of Artificial Intelligence Techniques
Constraint Satisfaction and Propagation
Aliases: CSP, Consistent-labelling, Satisfaction Assignment
Keywords: backjumping, backtracking, databases, graph isomorphism, matching
Categories: Inference and Reasoning , Problem Solving
Author(s): Rina Dechter
Constraint satisfaction is a class of problems in which knowledge is expressed declaratively as a collection of explicit, categorical constraints over a set of possibilities. These include, for example, scene labelling, scene matching, space planning problems, database consistency-maintenance, query-answering, graph isomorphism detection, the Graph Colouring problem, and many puzzles such as crypto-arithmetic. The Constraint-Satisfaction Problem consists of a set of variables,
, each represented by its domain values (not necessarily numerical),
, and a set of constraints. A constraint is a subset of the Cartesian product
that specifies which values of the variables are compatible with each other. A solution is an assignment of values to all the variables which simultaneously satisfy all the constraints, and the most common task associated with these problems is to find one or all solutions. In practice, the constraints may be specified either as truth-tables, or as lists of the satisfying tuples or, more concisely, in analytic form as expressions (such as ) in some `constraint languages', algebraic or otherwise. See also the entry on Relaxation Labelling. The common algorithm for solving CSPs is the backtrack search algorithm. In its primitive version, called Chronological Backtracking, the algorithm traverses the variables in a predetermined order, provisionally assigning consistent values to a subsequence ( ) of variables and attempting to append to it a new instantiation of such that the whole set is consistent. If no consistent assignment can be found for the next variable , a dead-end situation occurs, the algorithm `backtracks' to the most recent variable, changes its assignment and continues from there. Chronological backtracking suffers from many maladies and several cures have been offered and analysed in the AI literature. These can be classified into look-ahead schemes, and look-back schemes. The former are concerned with the decision of what variable to instantiate (e.g., dynamic search rearrangement, max-cardinality search, minimum width), or what value to assign next among all the consistent choices available (e.g., forward-checking, full-lookahead, partial look-ahead, constraint propagation). Look-back schemes concern the decision of where and how to backtrack in case of a dead-end situation. The two fundamental ideas in look-back schemes are go-back to source of failure, and constraint recording or learning. The former detect and change decisions that caused the dead-end while skipping irrelevant decisions (e.g., selective backtracking, backjumping), while constraint-recording schemes identify the conflict-sets representing the reasons for the dead-end and record them as explicit constraints to disable the same conflicts from occurring in the future (e.g., Dependency Directed Backtracking).
- Kumar, V., Algorithms for constraint-satisfaction problems: a survey AI Magazine 13 (1992) no.1, 32--44.