What Are Constraint Satisfaction Problems?(slides5)

Question 1

CSP state

Answer 1

defined by variables Xi with values from domain Di

Question 2

CSP goal test

Answer 2

a set of constraints specifying allowable combinations of values for subsets of variables

Question 3

Constraint Satisfaction Problems

Answer 3

give a standard factorization of the state
general purpose heuristics
the main idea is to reduce the search space by identifying constraint violations

Question 4

CSP sets and domains

Answer 4

set or variables X= {X1, X2, …., Xn}
set of domains D={D1,D2,…,Dn}
-variable Xi takes value from domain Di
-Domain can also be same for all variables

Question 5

CSP constraint sets

Answer 5

C={ci=(scopei,reli) | i=1,…,h}

• scopei: subset of X, the variables that are constrained by ci
• reli: is a relations and tells us which simultaneous assignments to variables in scopei are allowed or not allowed

Question 6

CSP Varieties of constraints

Answer 6

Unary
Binary
Higher-order

Question 7

CSP Unary constraints

Answer 7

constraints that involve a single variable

-eg, SA != green

Question 8

CSP Binary Constraints

Answer 8

constraints that involve pairs of variables

-eg, SA != WA

Question 9

CSP Higher Order constraints

Answer 9

involve 3 or more variables

-e.g., cryptarithmetic column constraints

Question 10

Binary CSP

Answer 10

each constraint relates two variables

Question 11

constraint graph

Answer 11

nodes are variables, arcs are constraints (only works with Binary CSP)

Question 12

CSP binary conversion

Answer 12

Any CSP can be converted into one with only binary constraints
2 known techniques:
-dual graph method
-hidden variable method
translations are polynomial if constraints are represented extensionally

Question 13

Varieties of CSP variables

Answer 13

Discrete Variables

continuous variables

Question 14

CSP Discrete Variables

Answer 14

finite domains

infinite domains

Question 15

CSP finite domains

Answer 15

• n variabls, domain size d –> O(d^n) complete assignments

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

Question 16

CSP infinite Domains

Answer 16

integers, strings, etc.

• e.g., job scheduling, variables are start/end days for each job
• need a constraint language, e.g., startJob1 + 5 <= StartJob3

Question 17

CSP continuous variables

Answer 17

e.g., start/end times for hubble space telescope observations
linear constraints solvable in polynomial time by linear programming

Question 18

Simple Temporal Problems

Answer 18

Variables X,Y--> timepoints
Temporal constraints
-binary: defined on 2 variables
-intervals[a,b] meaning a<=b
  -temporal interval: all allowed values for y-x