Home | | Artificial Intelligence | Constraint Satisfaction Problems (CSPS)

# Constraint Satisfaction Problems (CSPS)

state is a "black boxâ€ś â€“ any data structure that supports successor function, heuristic function, and goal test

CONSTRAINT SATISFACTION PROBLEMS (CSPS)

â€˘                      Standard search problem:

â€“ state is a "black boxâ€ś â€“ any data structure that supports successor function, heuristic function, and goal test

â€˘                      CSP:

â€“  state is defined by variables Xi with values from domain Di

â€“ goal test is a set of constraints specifying allowable combinations of values for subsets of variables

â€“  Simple example of a formal representation language

â€˘                      Allows useful general-purpose algorithms with more power than standard search algorithms

Arc consistency:

1.                                  Arc refers to a directed arc in the constraint graph.

2.                                  Arc consistency checking can be applied either as a preprocessing. step before the process must be applied repeatedly until no more inconsistency remain.

Path consistency:

Path consistency means that any pair of adjacent variables can always be extended to a third neighboring variable, this is also called path consistency

K-consistency:

Stronger forms of propagation can be defined using the notation called K-consistency. A CSP is K-consistency if for any set of K-1 variables and for any consistent assignment to those variables, a constant value can always be assigned to any variable.

Example: Map-Coloring â€˘                      Variables WA, NT, Q, NSW, V, SA, T

â€˘                      Domains Di = {red,green,blue}

â€˘                      Constraints: adjacent regions must have different colors

e.g., WA â‰  NT, or (WA,NT) in ,(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)} â€˘ Solutions are complete and consistent assignments, e.g., WA = red, NT = green,Q = red,NSW= green,V = red,SA = blue,T = green

Constraint graph

â€˘                      Binary CSP: each constraint relates two variables

â€˘                      Constraint graph: nodes are variables, arcs are constraints Varieties of CSPs

â€˘                     Discrete variables

â€“  finite domains:

â€˘                                                                     n variables, domain size d -O(dn) complete assignments

â€˘                                                                     e.g., Boolean CSPs, incl.~Boolean satisfiability (NP-complete)

â€“  infinite domains:

â€˘                                                                     integers, strings, etc.

â€˘                                                                     e.g., job scheduling, variables are start/end days for each job

â€˘                                                                     need a constraint language, e.g., StartJob1 + 5 â‰¤ StartJob3

â€˘                                                                     Continuous variables

â€“  e.g., start/end times for Hubble Space Telescope observations

â€“  linear constraints solvable in polynomial time by linear programming

Varieties of constraints:

â€˘                     Unary constraints involve a single variable,

â€“  e.g., SA â‰  green

â€˘                     Binary constraints involve pairs of variables,

â€“  e.g., SA â‰  WA

â€“  Higher-order constraints involve 3 or more variables,

â€“  e.g., cryptarithmetic column constraints

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Artificial Intelligence : Constraint Satisfaction Problems (CSPS) |