Constraint Satisfaction (CSP) Task
(Redirected from Constraint satisfaction problem)
Jump to navigation
Jump to search
A Constraint Satisfaction (CSP) Task is a categorical decisioning task for whether a solution exists which satisfies the constraints.
- Context:
- Input: A Search Space, and a Constraint Set.
- output: A Solution that satisfies the Constraints.
- It can require that the Solution be reported.
- It can be solved by a Constraint Satisfaction System (that implements a constraint satisfaction algorithm).
- Example(s):
- a Scheduling Task.
- a n-Queens Task.
- a Boolean Satisfiability Task.
- a Map Coloring Task.
- a Sudoku Task.
- …
- Counter-Example(s):
- See: Function Optimization Task, Automated Planning, Sudoku Solving, Combinatorial Search.
References
2017
- (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/constraint_satisfaction_problem Retrieved:2017-12-30.
- Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. The Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT) and answer set programming (ASP) can be roughly thought of as certain forms of the constraint satisfaction problem.
Examples of simple problems that can be modeled as a constraint satisfaction problem include:
- Eight queens puzzle.
- Map coloring problem.
- Sudoku, Crosswords, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato and many other logic puzzles.
- These are often provided with tutorials of ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems.
"Real life" examples include automated planning [1] and resource allocation. An example for puzzle solution is using a constraint model as a Sudoku solving algorithm.
- Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. The Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT) and answer set programming (ASP) can be roughly thought of as certain forms of the constraint satisfaction problem.
- ↑ Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning, Ian Miguel - slides.
2006
- (Rossi et al., 2006) ⇒ Francesca Rossi, Peter Van Beek, and Toby Walsh. (2006). “Handbook of Constraint Programming." Elsevier Science.
1994
- (Freuder & Mackworth, 1994) ⇒ Eugene C. Freuder, and Alan K. Mackworth, editors. (1994). “Constraint-based Reasoning." MIT Press.