Constraint Processing

By R. Barták. Encyclopedia of Artificial Intelligence, 2009

976 citations recorded by the source corpus.

INTRODUCTION Constraints appear in many areas of human endeavour starting from puzzles like crosswords (the words can only overlap at the same letter) and recently popular Sudoku (no number appears twice in a row) through everyday problems such as planning a meeting (the meeting room must accommodate all participants) till solving hard optimization problems for example in manufacturing scheduling (a job must finish before another job). Though all these problems look like being from completely different worlds, they all share a similar base – the task is to find values of decision variables, such as the start time of the job or the position of the number at a board, respecting given constraints. This problem is called a Constraint Satisfaction Problem (CSP). Constraint processing emerged from AI research in 1970s (Montanary, 1974) when problems such as scene labelling were studied (Waltz, 1975). The goal of scene labelling was to recognize a type of line (and then a type of object) in the 2D picture of a 3D scene. The possible types were convex, concave, and occlud-ing lines and the combination of types was restricted at junctions of lines to be physically feasible. This scene labelling problem is probably the first problem formalised as a CSP and some techniques developed for solving this problem, namely arc consistency, are still in the core of constraint processing. Systematic use of constraints in programming systems has started in 1980s when researchers identified a similarity between unification in logic programming and constraint satisfaction (Gallaire, 1985) (Jaffar & Lassez, 1987). Constraint Logic Programming was born. Today Constraint Programming is a separate subject independent of the underlying programming language, though constraint logic programming still plays a prominent role thanks to natural integration of constraints into a logic programming framework. This article presents mainstream techniques for solving constraint satisfaction problems. These techniques stay behind the existing constraint solvers and their understanding is important to exploit fully the available technology.

View Paper: https://www.semanticscholar.org/paper/39775860ff0702974844049fca907cf756b98596

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Constraint programming systems for modeling music theories and composition (2011, methodology): “Constraint programming [Apt 2003; Dechter 2003] is a programming paradigm that introduces techniques to solve constraint satisfaction problems.”
Using Expectation Maximization to Find Likely Assignments for Solving CSP's (2007, background): “Further, it characterizes BP’s poorly-understood dynamics as a special case of primal/dual optimization on the search and inference formulations of a constraint problem [5].”
Potassco: The Potsdam Answer Set Solving Collection (2011, unknown): “This is addressed by the hybrid ASP solver clingcon [52], combining the Boolean modeling capacities of ASP with Constraint Processing (CP; [19, 89]).”
Bounded approximate decentralised coordination via the max-sum algorithm (2009, background): “Another interesting possibility would be to investigate the use of cutset schemes to obtain tree-structured network [25].”
Dependency Parsing by Belief Propagation (2008, background): “In that case, loopy BP reduces to an algorithm for generalized arc consistency (Mackworth, 1977; Bessière and Régin, 1997; Dechter, 2003), and updating a factor’s outgoing messages is known as constraint propagation.”
Learning Dependency-Based Compositional Semantics (2011, background): “In general, finding the solution to a CSP is NP-hard, but for trees, we can exploit dynamic programming (Dechter 2003).”
Conflict-Driven Answer Set Solving (2007, background): “But despite the close relationship to SAT and, more generally, constraint processing (CSP; [Dechter, 2003]), state-of-the-art look-back techniques from these areas, like backjumping, conﬂict-driven learning, and restarts, are not yet established in genuine ASP solvers.”
Conflict-driven answer set solving: From theory to practice (2012, background): “Nonetheless, state-of-the-art look-back techniques from SAT, or more generally, Constraint Programming (CP; [26,113]), such as backjumping and conflict-driven learning, were not yet established in native ASP solvers.”
Concise finite-domain representations for PDDL planning tasks (2009, methodology): “closely related to a technique called forward checking in the CSP literature [10], generalized to constraints on more than two”
Integrated Task and Motion Planning (2020, unknown): “Figure 9 compresses the plan skeleton in Figure 8 into a constraint network , a bipartite graph from parameters to constraints, by removing redundant constraints, constants, and parameters (54).”
Model-free, Model-based, and General Intelligence (2018, background): “…and stochastic planning problems (FONDPs, PONDPs, MDPs, and POMDPs), general game playing, and answer set programming among others [Dechter, 2003; Biere et al., 2009; Pearl, 1988; Geffner and Bonet, 2013; Bertsekas, 1995; Kaelbling et al., 1998; Genesereth et al., 2005; Gebser et…”