L12: Graphical Representations, Constraint Propagation

Question 1

Why is it useful to view a CSP as a graph?

Answer 1

To guide Heuristics.

To guide Propagation

Question 2

What is a binary constraint graph

Answer 2

Each node represents a variable.
Constraints are represented by edges.
An edge only contains 2 nodes.
There is one node on the graph per variable.

The crystal maze is an example of a constraint graph with the addition of a hyper edge.

Question 3

What is a hyper edge?

Answer 3

A hyper edge is a constraint that involves more than 2 nodes (draw a circle around the relevant nodes).

Question 4

What is dual representation?

Answer 4

A means of transforming non-binary instances into binary instances.

There is a lot of work on algorithms for binary CSP- this is a way of applying it to non-binary CSPs.

Question 5

How do we convert non-binary constraints into dual representation?

Answer 5

1. Transform each constraint into a dual variable. Has an associated domain of the allowed tuples for the pair of variables for that constraint.
2. Add binary constraints between any two dual variables that share an original variable. tConstraint insists that the assignments to the two nodes that it connects agree for the shared original variables.

Question 6

Can tuples be domain elements?

Answer 6

No: for the purposes of this module, we think of domain values as atomic (indivisible).
But we can transform each tuple into an atomic value and relabel the domains.

Question 7

What is a dual graph?

Answer 7

Each node represents a dual variable (i.e. an original constraint).

There are edges between nodes that share an original variable.

Corresponding to the new binary constraints.

Constraints become nodes in the graph, essentially become the variables in an equivalent CSP. Domains are tuples (or atomic equivalents).

Question 8

What is constraint propagation?

Answer 8

Deduction via a subset of the constraints.

Deduced information recorded as changes to the CSP instance.

Most often: pruning values from domains (i.e. unary constraints).

Sometimes: higher arity constraints.

Question 9

What is propagation?

Answer 9

Local changes form the basis for further deductions.

Hence the result of a change is gradually propagated through the constraint network.

Question 10

What can we use that is better than backtracking?

Answer 10

Constraint Propagation?

Question 11

What is a consistency property?

Answer 11

A consistency property holds when constraint propagation of a certain kind reaches a fixpoint. We can deduce nothing new.

Consistency may be:
local: one (or a subset of) constraint/arc/variable
global: all constraints/arcs/variables.

Question 12

What is local node consistency?

Answer 12

Given a unary constraint c(xi), local node consistency holds if:

For every d in Di, c(xi) is satisfied when xi = d.

Question 13

What is global node consistency?

Answer 13

For global node consistency to hold, it requires that this local consistency is met for all unary constraints. A unary constraint involves a single variable.

Any variable can be assigned a value from its reduced domain without violating any constraints. For example, if a variable ‘X’ can only take values from 1 to 5 after applying the constraints, any value within that range can be chosen for ‘X’ without causing conflicts with the other constraints.

Can be enforced simply by enforcing node consistency for each unary constraint once. Node consistency for a unary constraint involves reducing the variable’s domain based solely on that individual constraint.

Question 14

What is arc consistency?

Answer 14

In arc consistency, for every pair of variables connected by a constraint (an “arc”), the values in one variable’s domain are systematically reduced based on the values in the other variable’s domain, ensuring that the constraint between the variables is satisfied.

This process continues until no more reductions can be made, making the problem easier to solve by narrowing down the possibilities for each variable while respecting the constraints.

Question 15

What is local arc consistency?

Answer 15

Given arc (xi, xj), local arc consistency holds if:
- c(xi) and c(xj) are both node consistent.
- For each di in Di, there is at least one corresponding dj in Dj, such that c(xi, xj) is satisfied when xi = di and xj = dj.

Local arc consistency is focused on pairs of variables connected by a constraint (an “arc”). It systematically reduces the domain of one variable based on the values of the other variable’s domain, ensuring that the specific constraint between the two variables is satisfied.

Question 16

What is support?

Answer 16

Support is a concept used in constraint propagation generally (not just arc revision). A support is evidence that a domain value is consistent, and therefore should not be removed.

For an arc(x1, x2), a support of a value in x1 is a compatible value in x2.

Question 17

Why do we split a constraint into 2 arcs?

Answer 17

Efficiency.

Question 18

What is global arc consistency?

Answer 18

Holds if local arc consistency holds for all arcs. If local arc consistency is established for all these pairs of variables, it leads to global arc consistency for the entire problem.

Any assignment to a single variable can be extended to an assignment to two variables consistently. Any valid assignment made to one variable can be consistently extended to other related variables, ensuring that the constraint relationships are preserved.

Remember that global node consistency is a precondition.

Cannot be enforced in general simply by enforcing local arc consistency for all arcs once. In ensuring arc consistency for one constraint, it may change the consistency of another constraint.