L19: K-Consistency Flashcards
What is k-consistency?
Holds if:
- Given assignments to k-1 variables satisfying all constraints among them.
- Can choose an assignment to any kth variable such that constraints among all k variables are satisfied.
What is strong K consistency?
j-consistency for all 1 <= j <= k
This includes node, arc and path consistency.
What does ‘constraints among them’ mean?
All the variables in a scope are assigned.
We dont look ‘inside’ constraints with unassigned variables.
Explain the levels of consistency for CSPs/COPs.
Node: 1-consistency
Arc: strong 2-consistency
Path: 3-consistency
Strong Path: strong 3-consistency
BUT
K-consistency does not require binary CSPs.
What does enforcing k-consistency do in general?
Makes ‘nogoods’ of arity k-1 explicit.
2-consistency: add unary ocnstraints to remove vales that cannot participate in any solutions.
3-consistency: write down binary tuples that cannot participate in any solution (by modifying constraints/’adding’ new constraints)
What if the CSP is strongly n-consistent?
Where n is the number of variables.
- Any individual variable can be assigned consistently
- A consistent assignment to 1 variable can be extended to a consistent assignment to 2 variables
- …
- A consistent assignment to n-1 variables can be extended to a consistent assignment to n variables
Meaning we will never have to backtrack.
What is the cost of enforcing k-consistency?
Cooper’s algorithm enforces K-consistency in O((n^k)(d^k)).
This gets very expensive very quickly.
What is a sufficient condition for a backtrack free search?
“Given a CSP that is already strong k-consistent, and a variable ordering with width k-1, we can solve the problem with d-way branching with constraint checking at each node) backtrack-free.”
A variable ordering is backtrack-free if the level of strong consistency exceeds the width of the corresponding ordered constraint graph.
Do we perform backtrack-free search in practice?
Level of k-consistency is typically still to great to enforce in practice.
E.g. crystal maze, sudoku
We can spot when the graph becomes tree structured (through assignment).
What is generalised arc consistency?
A constraint is generalised arc consistent if:
- For every variable, for every element in the domain of those variables, there is a supporting tuple.
How is General Arc Consistency enforced?
GAC2001/3.1
GAC-schema
Specialised propagation algorithms
What is the complexity of GAC2001/3.1?
O(e(r^2)(d^r))
- e is the number of constraints in the network
- r is the maximum constraint arity
- d is the maximum domain size
(not cheap)
Is GAC used in practice?
Yes
GCC, AllDifferent, Lexicographic ordering, Multiset ordering
