Search Problems
Planning
Search
Identifica tion
CSPs (i.e., without preferences)
Constraint Satisfaction Problems (CSPs): Identification problems have constraints to be satisfied; there is no preference in CSPs.
Constraints refer to hard constraints which a legal solution cannot violate.
Preferences sometimes are referred to as soft constraints (or objectives), where we need to optimise, e.g., to minimise cost.
Identification
Standard Search Problems vs CSPs
Standard Search problems
State is a “black‐box”: arbitrary data structure
Goal test can be any function over states Constraint Satisfaction Problems (CSPs)
State is defined by variable with values from a domain ( may depend on ).
Goal test is a set of constraints specifying allowable combinations of values for subsets of variables.
An example of a formal representation language.
This allows useful general‐purpose algorithms with more power
than standard search algorithms.
CSP
A constraint satisfaction problem consists of A set of variables
A domain for each variable A set of constraints
In a CSP, an assignment is complete if every variable has a value, otherwise it is partial.
Solutions are complete assignments satisfying all the constraints.
Example: Course scheduling problem
Variables – courses: AI1, Data Structure, Software Engineering, OOP,
AI2, Neural Computation…
Domain ‐ year‐term: {1‐1, 1‐2, 2‐1, 2‐2, 3‐1, 3‐2}
Constraints ‐ pre‐requisites: {AI1 < AI2, OOP < SE...}
Solutions ‐ e.g.: (AI1=1‐2, OOP=1‐1, AI2=2‐2, SE=2‐1...)
Example: Map Colouring
Problem: Map colouring problem is to paint a map in such a way that none of adjacent regions can have the same colour.
Variables: WA, NT, Q, NSW, V, SA, T
Domain: D = {red, green, blue}
Constraints: adjacent regions must have different colours
Implicit:WA≠NT
Explicit:(WA,NT)∈{(red,green),(red,blue),...}
Solutions: e.g. {WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=green}
Example: Sudoku
Problem: Sudoku is to fill a 9×9 grid with digits so that each column, each row, and each of the regions contain all of the digits from 1 to 9.
Variables:eachopencell
Domain:D={1,2,3,...,9}
Constraints:
Each row contains different numbers
Each column contains different numbers Each region contains different numbers
Example: N‐Queens
Problem: N‐queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.
Variables:
Domain:D={0,1}
Constraints:
∀,,, ∈ 0,0,0,1,1,0 ∀,,, ∈ 0,0,0,1,1,0
∀,, , , ∈ 0,0 , 0,1 , 1,0 ∀,, , , ∈ 0,0 , 0,1 , 1,0 ∑
Constraint Graphs
Constraintgraphsareusedtorepresent relations among constraints in CSPs, where nodes correspond to the variables and arcs reflect the constraints.
Theyaredifferentfromstatespacegraphs since variables in CSPs correspond to multiple states.
BinaryCSP:Eachconstraintinvolvesat most two variables.
Generalpurpose:CSPalgorithmsusethe graph structure to speed up the search.
When a constraint relates more than two variables
Useasquaretorepresentaconstraint(circlesforvariables)
Thesquareconnectsallthevariablesinvolvedinthatconstraint.
Variety of CSPs
Variables
Finite domains (discrete), e.g. all the preceding examples.
Infinite domains (discrete or continuous), e.g., variables involving time.
Constraints
Unary (single variable having reducing domains), binary and high‐
order constraints.
CSPsaredifficultsearchproblems
If a CSP has variables, the size of each domain is , then there are complete assignments.
For the preceding representation of the 4 × 4 queens puzzle, there are 2 complete assignments.
Real‐world CSPs
Assignmentproblems,e.g.whoteacheswhichclass
Timetablingproblems,e.g.whichclassisofferedwhenand
where
Hardwareconfiguration
Transportationscheduling
Factoryscheduling
Circuitlayout
Faultdiagnosis ...
Many of CSP problems can also consider the preferences (i.e., objectives), in which case they turn into constraint optimisation problems.