Notes - Artificial Intelligence MT24, Constraint satisfaction problems

[[Course - Artificial Intelligence MT24]]^U

Flashcards

@Define a constraint satisfaction problem and what a solution looks like.

A 3-tuple $P = \langle X, D, C \rangle$ where:

$X$ is a set of variables $X = \langle x _ 1, \ldots, x _ n \rangle$
$D$ is a set of domains for each variable $D = \langle D _ 1, \ldots, D _ n \rangle$
- $D _ i$ is a set of values $x _ i$ could take
$C$ is a set of constraints $C = \langle C _ 1, \ldots, C _ t \rangle$
- $C _ i = \langle S _ i, R _ i \rangle$ a pair of a set containing the variables involved and a relation between them
- $S _ i = \langle x _ {i _ 1}, \ldots, x _ {i _ m}\rangle$
- $R _ i \subseteq D _ {i _ 1} \times \cdots \times D _ {i _ m}$

A solution is an assignment/valuations $v \in D _ 1 \times \cdots \times D _ n$ that satisfies all $C _ i$.

In what sense are CSPs a special case of search problems?

Search problems:
- State: can be any data structure
- Goal test: Domain-dependent
- Successor: Domain-dependent
Constraint satisfaction problems:
- State: assignment of values to variables
- Goal test: Every variable is assigned and it fits within constraints

Suppose $P$ is a CSP consisting of only binary constraints. @Define the corresponding constraint graph $G _ P$.

Every variable corresponds to a vertex
There is an edge between $x _ i$ and $x _ j$ is there is a binary constraint over variables $x _ i$ and $x _ j$

Suppose $P$ is a CSP. @Define the corresponding hypergraph and Gaifman graph.

Hypergraph:
- Each variable corresponds to a vertex
- For every constraint over variables $x _ {i _ 1}, \ldots, x _ {i _ m}$ there is a hyperedge $\{x _ {i _ 1}, \ldots, x _ {i _ m}\}$
Gaifman graph:
- Each variable corresponds to a vertex
- For every constraint over variables $x _ {i _ 1}, \ldots, x _ {i _ m}$, there is an edge for each $x _ {i _ k}$ and $x _ {i _ \ell}$.

@Justify why the decision version of CSP is $\mathbf{NP}$-complete in the discrete case.

It is $\mathbf{NP}$-hard since $\mathbf{3SAT} \le \mathbf{CSP}$
It is in $\mathbf{NP}$ since a simple nondeterministic algorithm just guesses assignments

@Justify why CSP is not $\mathbf{NP}$ when infinite domains are allowed.

You can encode Diophantine equations (Hilbert’s 10th problem), which is actually undecidable.

@Define a constrained optimisation problem.

A CSP $P$ and an objective function $f : D _ 1 \times \cdots \times D _ n \to \mathbb R$.
A solution satisfies $P$ and also minimises (or maximises) $f$.

@Define a weighted constraint satisfaction problem.

A CSP $P$ and a weight $w _ i$ for each constraint $C _ i$
Find the assignment that maximises the total weight of the satisfied constraints

Describe the backtracking search @algorithm for CSPs, and relate it to standard search algorithms.

Backtracking search is DFS where each depth assigns just one variable (rather than considering all possible next assignments).

function BacktrackingSearch(csp) returns (solution/failure):
	return Backtrack(empty, csp)

function Backtrack(assignment, csp) return s(soltuion/failure):
	if assignment is complete then return assignment

	var = SelectUnassignedVariable(csp, assignment, assignment)

	for each value in the domain of var:
		if the value is consistent with the assignement, then:
			add {var = value} to assignment
			inferences = Inference(csp, var, value)
			
			if inferences ≠ failure, then
				add inferences to assignment
				result = Backtrack(assignment, csp)

				if result ≠ failure:
					return result
			
			remove {var = value } and inferences from assignment

	return failure

where $\mathbf{Inference}$ is some technique for checking whether the assignment is or will be consistent with constraints (e.g. forward checking, constraint propagation).

The basic backtracking algorithm for solving CSPs looks like:

function BacktrackingSearch(csp) returns (solution/failure):
	return Backtrack(empty, csp)

function Backtrack(assignment, csp) return s(soltuion/failure):
	if assignment is complete then return assignment

	var = SelectUnassignedVariable(csp, assignment, assignment)

	for each value in the domain of var:
		if the value is consistent with the assignement, then:
			add {var = value} to assignment
			inferences = Inference(csp, var, value)
			
			if inferences ≠ failure, then
				add inferences to assignment
				result = Backtrack(assignment, csp)

				if result ≠ failure:
					return result
			
			remove {var = value } and inferences from assignment

	return failure

In this context, @define the minimum remaining value heuristic.

Choose the variable with the fewest legal values.

The basic backtracking algorithm for solving CSPs looks like:

function BacktrackingSearch(csp) returns (solution/failure):
	return Backtrack(empty, csp)

function Backtrack(assignment, csp) return s(soltuion/failure):
	if assignment is complete then return assignment

	var = SelectUnassignedVariable(csp, assignment, assignment)

	for each value in the domain of var:
		if the value is consistent with the assignement, then:
			add {var = value} to assignment
			inferences = Inference(csp, var, value)
			
			if inferences ≠ failure, then
				add inferences to assignment
				result = Backtrack(assignment, csp)

				if result ≠ failure:
					return result
			
			remove {var = value } and inferences from assignment

	return failure

In this context, @define the degree heuristic.

Choose the variable that is involved in the largest number of constraints on unassigned variables.

The basic backtracking algorithm for solving CSPs looks like:

function BacktrackingSearch(csp) returns (solution/failure):
	return Backtrack(empty, csp)

function Backtrack(assignment, csp) return s(soltuion/failure):
	if assignment is complete then return assignment

	var = SelectUnassignedVariable(csp, assignment, assignment)

	for each value in the domain of var:
		if the value is consistent with the assignement, then:
			add {var = value} to assignment
			inferences = Inference(csp, var, value)
			
			if inferences ≠ failure, then
				add inferences to assignment
				result = Backtrack(assignment, csp)

				if result ≠ failure:
					return result
			
			remove {var = value } and inferences from assignment

	return failure

In this context, @define the least constraining value heuristic.

Once a variable has been chosen to assign to, choose the value that rules out the fewest values in the neighbouring variables.

The basic backtracking algorithm for solving CSPs looks like:

function BacktrackingSearch(csp) returns (solution/failure):
	return Backtrack(empty, csp)

function Backtrack(assignment, csp) return s(soltuion/failure):
	if assignment is complete then return assignment

	var = SelectUnassignedVariable(csp, assignment, assignment)

	for each value in the domain of var:
		if the value is consistent with the assignement, then:
			add {var = value} to assignment
			inferences = Inference(csp, var, value)
			
			if inferences ≠ failure, then
				add inferences to assignment
				result = Backtrack(assignment, csp)

				if result ≠ failure:
					return result
			
			remove {var = value } and inferences from assignment

	return failure

In this context, @define the forward checking inference approach.

When a value $d$ is assigned to a variable $x$, delete values incompatible with $d$ from other variables’ domains.

@Define what it means for a variable $x _ i$ with domain $D _ i$ to be node-consistent.

All values in $D _ i$ satisfy the unary constraints on $x _ i$.

Suppose:

$C = \big\langle \langle x, y\rangle, R \big\rangle$ is a binary constraint in a CSP
$x$ is a variable

@Define what it means for $x$ to be consistent with respect to $C$.

For each $d _ x \in D _ x$, there exists some $d _ y \in D _ y$ such that $\langle d _ x, d _ y \rangle \in R$.

@Define what it means for a CSP to be arc-consistent.

All variables are consistent with respect to all binary constraints (i.e. for each $d _ x \in D _ x$, there exists some $d _ y \in D _ y$ such that $\langle d _ x, d _ y \rangle \in R$).

What’s the high-level idea behind AC-3, the arc consistency algorithm?

Make sure each edge is arc-consistent, and make sure that making one edge arc-consistent doesn’t make another inconsistent.

Describe AC-3, the arc consistency @algorithm.

function AC3(csp) returns whether CSP is consistent
	inputs: csp, a binary CSP with components X, D, C
	local variables: queue, a queue of directed arcs, initially containing every arc

	while queue is not empty:
		(x_i, x_j) = RemoveFirst(queue)

		if Revise(csp, x_i, x_j):
			if D_i is empty:
				return false
			for each x_k in x_i.Neighbours \ { x_j }:
				add (x_k, x_i) to queue
	
	return true

function Revise(csp, x_i, x_j) returns true iff D_i gets revised:
	revised = false
	for each d in D_i:
		if no value d' in D_j allows (d, d') to satisfy constraints between x_i and x_j:
			delete d from D_i
			revised = true

	return revised

AC-3 is an algorithm for ensuring the arc consistency of a binary CSP and can be implemented as follows:

function AC3(csp) returns whether CSP is consistent
	inputs: csp, a binary CSP with components X, D, C
	local variables: queue, a queue of directed arcs, initially containing every arc

	while queue is not empty:
		(x_i, x_j) = RemoveFirst(queue)

		if Revise(csp, x_i, x_j):
			if D_i is empty:
				return false
			for each x_k in x_i.Neighbours \ { x_j }:
				add (x_k, x_i) to queue
	
	return true

function Revise(csp, x_i, x_j) returns true iff D_i gets revised:
	revised = false
	for each d in D_i:
		if no value d' in D_j allows (d, d') to satisfy constraints between x_i and x_j:
			delete d from D_i
			revised = true

	return revised

What is the time complexity of AC-3?

\[O(cd^3)\]

where:

$c$ is the number of binary constraints
$d$ is the maximum size of a domain

AC-3 is an algorithm for ensuring the arc consistency of a binary CSP and can be implemented as follows:

function AC3(csp) returns whether CSP is consistent
	inputs: csp, a binary CSP with components X, D, C
	local variables: queue, a queue of directed arcs, initially containing every arc

	while queue is not empty:
		(x_i, x_j) = RemoveFirst(queue)

		if Revise(csp, x_i, x_j):
			if D_i is empty:
				return false
			for each x_k in x_i.Neighbours \ { x_j }:
				add (x_k, x_i) to queue
	
	return true

function Revise(csp, x_i, x_j) returns true iff D_i gets revised:
	revised = false
	for each d in D_i:
		if no value d' in D_j allows (d, d') to satisfy constraints between x_i and x_j:
			delete d from D_i
			revised = true

	return revised

@Justify that the time complexity of AC-3 is $O(cd^3)$, where $c$ is the number of binary constraints and $d$ is the maximum size of a domain.

Each arc can be inserted into the queue at most $d$ times
An arc $(x _ k, x _ i)$ gets added back to the queue when some value is deleted from the domain of $x _ i$
Revise takes $O(d^2)$

Suppose:

$C = \big\langle \langle x _ 1, \ldots, x _ m\rangle, R \big\rangle$ is a constraint in a CSP
$x$ is a variable

@Define generalised arc consistency in this context.

For each $d \in D _ i$, there exists some $\langle d _ 1, \ldots, d _ m \rangle \in R$ such that $d _ i = d$ and $d _ j \in D _ j$ for each $1 \le j \le n$.

@Define what it means for a CSP to be $k$-consistent.

For each set of $k-1$ variables and each consistent assignment to those variables, a consistent value exists for each $k$-th variable.

@Define what it means for a CSP to be strongly $k$-consistent.

It is $i$-consistent for all $i = 1, \ldots, k$.

How can you identify independent subproblems from the constraint graph?

Look at the connected components.

Suppose the constraint graph of a CSP is a tree (i.e. it contains no loops). Describe an @algorithm which can solve CSPs like this more efficiently.

function TreeCSPSolver(csp) returns solution/failure
	inputs: csp, a CSP with components X, D and C
	
	n = number of variables in X
	assignment = the empty assignment
	root = any variable in X
	X = TopologicalSort(x, root)
	for j = n down to 2:
		isConsistent = Revise(csp, Parent(x_j), x_j)
		if not isConsistent:
			return failure
	for i = 1 to n:
		assignment[x_i] = any value from D_i consistent with current assignment
		if there is no consistent value:
			return failure
	
	return assignment

What’s the high-level idea behind the TreeCSPSolver algorithm?

function TreeCSPSolver(csp) returns solution/failure
	inputs: csp, a CSP with components X, D and C
	
	n = number of variables in X
	assignment = the empty assignment
	root = any variable in X
	X = TopologicalSort(x, root)
	for j = n down to 2:
		isConsistent = Revise(csp, Parent(x_j), x_j)
		if not isConsistent:
			return failure
	for i = 1 to n:
		assignment[x_i] = any value from D_i consistent with current assignment
		if there is no consistent value:
			return failure
	
	return assignment

Compute a topological ordering; an ordering of nodes so that every node’s parent precedes it in the order
Revise the domains of each variable in reverse order by deleting values that would cause inconsistencies
Pick a value from each of the domains

The $\mathbf{TreeCSPSolver}$ algorithm works on CSPs where the constraint graph is a tree. Sometimes the constraint graph is almost a tree, but not quite. In this context, describe the cycle conditioning @algorithm.

Calculate the constraint graph
Choose a cycle cutset, a subset $S$ of $X$ such that, after removing $S$, the constraint graph becomes a tree
For each possible consistent assignment of variables in $S$:
- Prune the domain of each variable in $X \setminus S$ that has a neighbour of $S$
- Solve the remaining CSP using $\mathbf{TreeCSPSolver}$

The $\mathbf{TreeCSPSolver}$ algorithm works on CSPs where the constraint graph is a tree. Sometimes the constraint graph is almost a tree, but not quite. In this context, the cycle conditioning algorithm finds a cutset which

Calculate the constraint graph
Choose a cycle cutset, a subset $S$ of $X$ such that, after removing $S$, the constraint graph becomes a tree
For each possible consistent assignment of variables in $S$:
- Prune the domain of each variable in $X \setminus S$ that has a neighbour of $S$
- Solve the remaining CSP using $\mathbf{TreeCSPSolver}$

What is the time complexity of this algorithm?

\[O(d^c \cdot (n-c)d^2)\]

where:

$c$ is the cycle cutset size
$d$ is the domain size
$n$ is the number of variables

The $\mathbf{TreeCSPSolver}$ algorithm works on CSPs where the constraint graph is a tree. @Define a corresponding tree decomposition $T$ of $P$.

Each variable $x \in X$ occurs in some node of $T$
For each $C _ i$, some node of $T$ contains all variables of $C _ i$
If a variable $x$ appears in two nodes of $T$, then $x$ appears in all nodes along the path connecting these two nodes
Edges are @todo

The $\mathbf{TreeCSPSolver}$ algorithm works on CSPs where the constraint graph is a tree. A tree decomposition converts a CSP $P$ into a corresponding tree $T$ where:

Each variable $x \in X$ occurs in some node of $T$
For each $C _ i$, some node of $T$ contains all variables of $C _ i$
If a variable $x$ appears in two nodes of $T$, then $x$ appears in all nodes along the path connecting these two nodes

Describe an @algorithm for solving a CSP given a tree decomposition.

For each node of $T$, compute all assignments that satisfy the constraints between variables in the node
Make each node $t _ 1$ of $T$ consistent with its parent $t _ 2$. This can be done by eliminating each assignment $v _ 2$ in $t _ 2$ for which no compatible assignment $v _ 1$ in $t _ 1$ exists (the same as $\mathbf{TreeCSPSolver}$).

The $\mathbf{TreeCSPSolver}$ algorithm works on CSPs where the constraint graph is a tree. A tree decomposition converts a CSP $P$ into a corresponding tree $T$ where:

Each variable $x \in X$ occurs in some node of $T$
For each $C _ i$, some node of $T$ contains all variables of $C _ i$
If a variable $x$ appears in two nodes of $T$, then $x$ appears in all nodes along the path connecting these two nodes

An algorithm for solving a CSP given a tree decomposition is given by:

For each node of $T$, compute all assignments that satisfy the constraints between variables in the node
Make each node $t _ 1$ of $T$ consistent with its parent $t _ 2$. This can be done by eliminating each assignment $v _ 2$ in $t _ 2$ for which no compatible assignment $v _ 1$ in $t _ 1$ exists (the same as $\mathbf{TreeCSPSolver}$).

What is the time complexity of this algorithm?

\[O(nd^{w+1})\]

where:

$w$ is the width of $T$
$d$ is the maximum domain size of the original CSP
$n$ is the number of nodes in $T$

The $\mathbf{TreeCSPSolver}$ algorithm works on CSPs where the constraint graph is a tree. A tree decomposition converts a CSP $P$ into a corresponding tree $T$ where:

Each variable $x \in X$ occurs in some node of $T$
For each $C _ i$, some node of $T$ contains all variables of $C _ i$
If a variable $x$ appears in two nodes of $T$, then $x$ appears in all nodes along the path connecting these two nodes

@Define the width of the tree $T$.

The maximum number of variables in a node of $T$, minus one.

The $\mathbf{TreeCSPSolver}$ algorithm works on CSPs where the constraint graph is a tree. A tree decomposition converts a CSP $P$ into a corresponding tree $T$ where:

Each variable $x \in X$ occurs in some node of $T$
For each $C _ i$, some node of $T$ contains all variables of $C _ i$
If a variable $x$ appears in two nodes of $T$, then $x$ appears in all nodes along the path connecting these two nodes

@Define the treewidth of $P$.

The smallest width of a tree decomposition of $P$.

Flashcards

Related posts