constraint satsfaction problem Flashcards
what is planning
a sequence of actions
what do we care about in planning
We care about the path to the goal
what is identification
an assignment
what do we care about in identification
We care about the goal itself, not the path
what is constraint satisfaction problem
: Identification problems have
constraints to be satisfied; there is no preference in CSPs
what is constraints
refers to hard constraints which a legal solution cannot violate
what are preferences referring too
Preferences sometimes are referred to as soft constraints (or objectives),
where we need to optimise, e.g., to minimise cost.
Search -> Identification -> CSP
what does a csp consists of
A set of variables
A domain for each variable
A set of constraints
In csp when is an assignment complete
if every variable has a
value,
in csp if some variables do not have a value, what is the assignment referred too
partial
what is a partial assignment in csp
not every variable has a value
what is an assigment called in csp when every variable has a value
complete
describe standard search problem
State is a “black-box”: arbitrary data structure
◆ Goal test can be any function over state
describe csp states
State is defined by variables 𝑋1, 𝑋2,… with values from domains
𝐷1, 𝐷2, …
describe csp goal test
Goal test is a set of constraints specifying allowable combinations
of values of variables
give example of csp
An example of a formal representation language, in which many
search problems can be abstracted. This allows useful general-
purpose algorithms with more power than standard search
algorithms.
Standard Search Problems vs CSPs
what is a constraint graph
Constraint graphs are used to represent relations among
constraints in CSPs, where nodes correspond to the variables
and arcs reflect the constraints
How to draw a constraint graph when a constraint
relates to more than two variables? e.g like in soduku
Use a square to represent a constraint, and connect all the
variables involved in that constraint
formalise minesweeper as a csp (please check slides to find out what a mindsweeper is )
Variables:
◆ All squares to be uncovered
◆ 𝑋1, 𝑋2, 𝑋3, 𝑋4
Domain:
◆ 𝐷 = {0, 1}, where 0 denotes not
a mine and 1 denotes a mine
Constraints:
◆ The number on a square is the
sum of its neighbour’s values.
◆ 𝑋1 = 1
◆ 𝑋1 + 𝑋2 = 1
◆ 𝑋1 + 𝑋2 + 𝑋3 + 𝑋4 = 3
◆ 𝑋4 = 1
◆ …
different types of variables and domains in csp
◆ Finite domains (discrete), e.g. all the above examples.
◆ Infinite domains (discrete or continuous), e.g., variables involving
time
different types of constraints in csp
Unary, binary and high-order constraints; i.e., how many variables
involved in a constraint
why are CSPs are difficult search problems
◆ If a CSP has 𝑛 variables, the size of each domain is 𝑑, then there
are 𝑂(𝑑𝑛) complete assignments.
◆ For the previous Sudoku problem, there are 951 complete
assignments
exapmles of csps in the real world
Assignment problems, e.g. who teaches which class
◆ Timetabling problems, e.g. which class is offered when and
where
◆ Hardware configuration
◆ Transportation scheduling
◆ Factory scheduling
◆ Circuit layout
◆ Fault diagnosis
Many of CSP problems can also consider the preferences
(i.e., objectives), in which case they turn into constrained
optimisation problems.
what is the difference between planning and identification
planning –> we care about the path to the goal
identification –> we only care about the goal itself
