path consistency, constraint problem solving strategies, and constraint propagation

Question 1

Path consistency (PC)

Answer 1

How to strengthen the consistency level
require consistency over more than one constraint
-Path(V0,V1,…,Vm) is path consistent iff for every pair of values xED0 and yEDm satisfying all the binary constraints on V0,Vm there exists an assignment of variables V1,…,Vm-1 such that all the binary constraints between the neighboring variables Vi,Vi+1 are satisfied

-only guarantees paths between neighboring variables are satisfied

Question 2

when is a CSP path consistent?

Answer 2

iff every path is consistent

Question 3

path consistency drawbacks

Answer 3

• memory consumption
• Bad ratio strength/efficiency
• modifies the constraint network
• still not a complete technique

Question 4

PC memory consumption

Answer 4

because PC eliminates pairs of values, we need to keep all compatible pairs extensionally, e.g. using {0,1} matrix

Question 5

PC bad ratio strength/efficiency

Answer 5

PC removes more or same inconsistencies than AC, but the strength/efficiency ratio is much worse than for AC

Question 6

PC constraint network modification

Answer 6

• adds redundant arcs (constraints) and thus it changes connectivity of the constraint network
• complicates using heuristics derived from the structure of the original constraint network

Question 7

How to solve constraint problems

Answer 7

depth first search
consistency techniques
combination of approaches

Question 8

CSP depth-first search

Answer 8

depth-first search

-complete but too slow (exponential) explores visibly wrong valuations

Question 9

CSP consistency techniques

Answer 9

consistency techniques

• usually incomplete(inconsistent values stay in domains)
• pretty fast(polynomial)

Question 10

CSP DFS and consistency combo

Answer 10

combinations of approaches

• combines advantages of approaches
• label variables step by step(backtracking)
• maintain consistency after assigning a value

Question 11

CSP solving techniques

Answer 11

core procedure DFS
Look Back
forward checking
partial look ahead
look ahead
MAC
MCk

Question 12

CSP core DFS

Answer 12

assign variables one by one

ensure consistency after each assignment

Question 13

CSP Look Back

Answer 13

• maintain consistency among already assigned variables
• look back= look to already assigned variables
• if the consistency test returns a conflict (+ explanation)
• -backtrack (basic) or
• -backjump

Question 14

CSP forward checking:

Answer 14

prevention technique

• removes values from future variables which are incompatible with current assignments
• check only future variables connected to some assigned variables by some constraint

Question 15

CSP partial look ahead

Answer 15

• propagate the value assigned to the current variable to all future variables
• if DAC is maintained in reverse order w.r.t. the labeling order (aka known as DAC look ahead)
• it is not necessary to consider constraints involving past variables other than the current one

Question 16

CSP look ahead

Answer 16

like partial look ahead but with AC instead of DAC

Question 17

CSP MAC

Answer 17

AC performed initially

maintained after each assignment

Question 18

CSP MCk

Answer 18

maintain strong-k-consistency

chronological backtracking