Constraint Satisfaction Problems
Heuristics for Arc-Consistency Algorithms
Introduction
A Constraint Satisfaction Problem is a triple where:
is a set of variables ;
is a set of domains , one for each variable and each of which consists of a set of allowable values ;
is a set of constraints that specify allowable combinations of values.
A CSP is called arc-consistent if every value in the domain of every variable is supported by all the neighbors of the variable while, is called inconsistent, if it has no solutions.
Arc-consistency algorithms remove all unsupported values from the domains of variables making the CSP arc-consistent or decide that a CSP is inconsistent by finding that some variable has no supported values in its domain.
Heuristics significantly enhance the efficiency of the arc-consistency algorithms improving their average performance in terms of consistency-checks which can be considered a standard measure of goodness for such algorithms. Arc-heuristic operate at arc-level and selects the constraint that will be used for the next check, while domain-heuristics operate at domain-level and selects which values will be used for the next support-check.
Domain-Heuristics for Arc-Consistency Algorithms
In
The objective of arc-consistency algorithms is to resolve some uncertainty; it has to be know, for each and for each , whether it is supported.
A single-support check, , is one in which, before the check is done, it is already known that either or are supported.
A double-support check , is one in which there is still, before the check, uncertainty about the support-status of both and .
If a double-support check is successful, two uncertainties are resolved. If a single-support check is successful, only one uncertainty is resolved. A good arc-consistency algorithm, therefore, would always choose to do a double-support check in preference of a single-support check, because the cormer offers the potential higher payback.
The improvement with double-support check is that, where possible, consistency-checks are used to find supports for two values, one value in the domain of each variable, which were previously known to be unsupported. It is motivated by the insight that in order to minimize the number of consistency-checks it is necessary to maximize the number of uncertainties which are resolved per check.
AC-3b: an improved version of AC-3 with Double-Support Checks
As shown in
def AC3(csp, queue=None, removals=None, arc_heuristic=dom_j_up):
"""[Figure 6.3]"""
if queue is None:
queue = {(Xi, Xk) for Xi in csp.variables for Xk in csp.neighbors[Xi]}
csp.support_pruning()
queue = arc_heuristic(csp, queue)
checks = 0
while queue:
(Xi, Xj) = queue.pop()
revised, checks = revise(csp, Xi, Xj, removals, checks)
if revised:
if not csp.curr_domains[Xi]:
return False, checks # CSP is inconsistent
for Xk in csp.neighbors[Xi]:
if Xk != Xj:
queue.add((Xk, Xi))
return True, checks # CSP is satisfiable
def revise(csp, Xi, Xj, removals, checks=0):
"""Return true if we remove a value."""
revised = False
for x in csp.curr_domains[Xi][:]:
# If Xi=x conflicts with Xj=y for every possible y, eliminate Xi=x
# if all(not csp.constraints(Xi, x, Xj, y) for y in csp.curr_domains[Xj]):
conflict = True
for y in csp.curr_domains[Xj]:
if csp.constraints(Xi, x, Xj, y):
conflict = False
checks += 1
if not conflict:
break
if conflict:
csp.prune(Xi, x, removals)
revised = True
return revised, checks
At any stage in the process of making 2-variable CSP arc-consistent in AC3b:
there is a set whose values are all known to be supported by ;
there is a set whose values are unknown, as yet, to be supported by .
The same holds if the roles for and are exchanged.
In order to establish support for a value it seems better to try to find a support among the values in first, because for each the check is a double-support check and it is just as likely that any supports than it is that any does. Only if no support can be found among the elements in , should the elements in be used for single-support checks . After it has been decided for each value in whether it is supported or not, either and the 2-variable CSP is inconsistent, or and the CSP is satisfiable. In the latter case, the elements from which are supported by are given by . The elements in which are supported by are given by the union of with the set of those elements of which further processing will show to be supported by some .
def AC3b(csp, queue=None, removals=None, arc_heuristic=dom_j_up):
if queue is None:
queue = {(Xi, Xk) for Xi in csp.variables for Xk in csp.neighbors[Xi]}
csp.support_pruning()
queue = arc_heuristic(csp, queue)
checks = 0
while queue:
(Xi, Xj) = queue.pop()
# Si_p values are all known to be supported by Xj
# Sj_p values are all known to be supported by Xi
# Dj - Sj_p = Sj_u values are unknown, as yet, to be supported by Xi
Si_p, Sj_p, Sj_u, checks = partition(csp, Xi, Xj, checks)
if not Si_p:
return False, checks # CSP is inconsistent
revised = False
for x in set(csp.curr_domains[Xi]) - Si_p:
csp.prune(Xi, x, removals)
revised = True
if revised:
for Xk in csp.neighbors[Xi]:
if Xk != Xj:
queue.add((Xk, Xi))
if (Xj, Xi) in queue:
if isinstance(queue, set):
# or queue -= {(Xj, Xi)} or queue.remove((Xj, Xi))
queue.difference_update({(Xj, Xi)})
else:
queue.difference_update((Xj, Xi))
# the elements in D_j which are supported by Xi are given by the union of Sj_p with the set of those
# elements of Sj_u which further processing will show to be supported by some vi_p in Si_p
for vj_p in Sj_u:
for vi_p in Si_p:
conflict = True
if csp.constraints(Xj, vj_p, Xi, vi_p):
conflict = False
Sj_p.add(vj_p)
checks += 1
if not conflict:
break
revised = False
for x in set(csp.curr_domains[Xj]) - Sj_p:
csp.prune(Xj, x, removals)
revised = True
if revised:
for Xk in csp.neighbors[Xj]:
if Xk != Xi:
queue.add((Xk, Xj))
return True, checks # CSP is satisfiable
def partition(csp, Xi, Xj, checks=0):
Si_p = set()
Sj_p = set()
Sj_u = set(csp.curr_domains[Xj])
for vi_u in csp.curr_domains[Xi]:
conflict = True
# now, in order to establish support for a value vi_u in Di it seems better to try to find a support among
# the values in Sj_u first, because for each vj_u in Sj_u the check (vi_u, vj_u) is a double-support check
# and it is just as likely that any vj_u in Sj_u supports vi_u than it is that any vj_p in Sj_p does...
for vj_u in Sj_u - Sj_p:
# double-support check
if csp.constraints(Xi, vi_u, Xj, vj_u):
conflict = False
Si_p.add(vi_u)
Sj_p.add(vj_u)
checks += 1
if not conflict:
break
# ... and only if no support can be found among the elements in Sj_u, should the elements vj_p in Sj_p be used
# for single-support checks (vi_u, vj_p)
if conflict:
for vj_p in Sj_p:
# single-support check
if csp.constraints(Xi, vi_u, Xj, vj_p):
conflict = False
Si_p.add(vi_u)
checks += 1
if not conflict:
break
return Si_p, Sj_p, Sj_u - Sj_p, checks
AC3b is a refinement of the AC3 algorithm which consists of the fact that if, when arc is being processed and the reverse arc is also in the queue, then consistency-checks can be saved because only support for the elements in has to be found (as opposed to support for all the elements in in the AC3 algorithm).
AC3b inherits all its properties like time-complexity and space-complexity fron AC3 and where denotes the number of variables in the CSP, denotes the number of binary constraints and denotes the maximum domain-size of the variables.
Arc-Heuristics for Arc-Consistency Algorithms
Many arc-heuristics can be devised, based on three major features of CSPs:
the number of acceptable pairs in each constraint (the constraint size or satisfiability);
the domain size;
the number of binary constraints that each variable participates in, equal to the degree of the node of that variable in the constraint graph.
Simple examples of heuristics that might be expected to improve the efficiency of relaxation are:
ordering the list of variable pairs by increasing relative satisfiability;
ordering by increasing size of the domain of the variable relaxed against ;
ordering by descending degree of node of the variable relaxed.
In
def dom_j_up(csp, queue):
return SortedSet(queue, key=lambda t: neg(len(csp.curr_domains[t[1]])))
def sat_up(to_do):
return SortedSet(to_do, key=lambda t: 1 / len([var for var in t[1].scope]))
Experimental Results
For the experiments below on binary CSPs, in addition to the two arc-consistency algorithms already cited above, AC3 and AC3b, the AC4 algorithm was used.
The AC4 algorithm runs in worst-case time but can be slower than AC3 on average cases.
def AC4(csp, queue=None, removals=None, arc_heuristic=dom_j_up):
if queue is None:
queue = {(Xi, Xk) for Xi in csp.variables for Xk in csp.neighbors[Xi]}
csp.support_pruning()
queue = arc_heuristic(csp, queue)
support_counter = Counter()
variable_value_pairs_supported = defaultdict(set)
unsupported_variable_value_pairs = []
checks = 0
# construction and initialization of support sets
while queue:
(Xi, Xj) = queue.pop()
revised = False
for x in csp.curr_domains[Xi][:]:
for y in csp.curr_domains[Xj]:
if csp.constraints(Xi, x, Xj, y):
support_counter[(Xi, x, Xj)] += 1
variable_value_pairs_supported[(Xj, y)].add((Xi, x))
checks += 1
if support_counter[(Xi, x, Xj)] == 0:
csp.prune(Xi, x, removals)
revised = True
unsupported_variable_value_pairs.append((Xi, x))
if revised:
if not csp.curr_domains[Xi]:
return False, checks # CSP is inconsistent
# propagation of removed values
while unsupported_variable_value_pairs:
Xj, y = unsupported_variable_value_pairs.pop()
for Xi, x in variable_value_pairs_supported[(Xj, y)]:
revised = False
if x in csp.curr_domains[Xi][:]:
support_counter[(Xi, x, Xj)] -= 1
if support_counter[(Xi, x, Xj)] == 0:
csp.prune(Xi, x, removals)
revised = True
unsupported_variable_value_pairs.append((Xi, x))
if revised:
if not csp.curr_domains[Xi]:
return False, checks # CSP is inconsistent
return True, checks # CSP is satisfiable
Sudoku
Easy Sudoku
Harder Sudoku
8 Queens
For the experiments below on n-ary CSPs, due to the n-ary constraints, the GAC algorithm was used.
The GAC algorithm has time-complexity and space-complexity where denotes the number of n-ary constraints, denotes the constraint arity and denotes the maximum domain-size of the variables.
def GAC(self, orig_domains=None, to_do=None, arc_heuristic=sat_up):
"""Makes this CSP arc-consistent using Generalized Arc Consistency
orig_domains is the original domains
to_do is a set of (variable,constraint) pairs
returns the reduced domains (an arc-consistent variable:domain dictionary)
"""
if orig_domains is None:
orig_domains = self.csp.domains
if to_do is None:
to_do = {(var, const) for const in self.csp.constraints for var in const.scope}
else:
to_do = to_do.copy()
domains = orig_domains.copy()
to_do = arc_heuristic(to_do)
checks = 0
while to_do:
var, const = to_do.pop()
other_vars = [ov for ov in const.scope if ov != var]
new_domain = set()
if len(other_vars) == 0:
for val in domains[var]:
if const.holds({var: val}):
new_domain.add(val)
checks += 1
# new_domain = {val for val in domains[var]
# if const.holds({var: val})}
elif len(other_vars) == 1:
other = other_vars[0]
for val in domains[var]:
for other_val in domains[other]:
checks += 1
if const.holds({var: val, other: other_val}):
new_domain.add(val)
break
# new_domain = {val for val in domains[var]
# if any(const.holds({var: val, other: other_val})
# for other_val in domains[other])}
else: # general case
for val in domains[var]:
holds, checks = self.any_holds(domains, const, {var: val}, other_vars, checks=checks)
if holds:
new_domain.add(val)
# new_domain = {val for val in domains[var]
# if self.any_holds(domains, const, {var: val}, other_vars)}
if new_domain != domains[var]:
domains[var] = new_domain
if not new_domain:
return False, domains, checks
add_to_do = self.new_to_do(var, const).difference(to_do)
to_do |= add_to_do
return True, domains, checks