Fast Solutions to CSP’s Based on PROSSER, P. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence 9 (1993), 268--299 Outline ? Motivation ? Methods of advancing CSP search – Backmarking – Forward Checking ? Hybrid algorithms ? Conclusion Problem to be solved Given a set of n variables where the i th variable, 1<= i<=n, has a discrete domain of values it can take, domain[i], and a set of binary relations C = {C 1,1 … C 1,n C 2,1 … C 2,n … C n,n }, find the first consistent instantiation of these variables which satisfies all the relations. Notation: Current variable is indexed with i, V i Past variables will be variables that have already been instantiated (those whose index is <i ) Future variables will be those yet to be instantiated (those whose index is >i ) Why Binary CSP’s Every higher order (multiple variables) , finite domain constraint can be reduced to a set of binary constraints if enough auxillary variables are introduced. What is the forward move and why change it? Forward move – the procedure that determines what actions to take (consistency checks, bookkeeping, etc) when the next variable is instantiated. Goal : avoid unnecessary computation ?Backmarking (BM) – remembers consistency checks it already performed ?Forward Checking (FC) – doesn’t expand nodes it knows aren’t feasible Go Backwards Go Forwards BT BM FC BJ CBJ More informed styles Different styles The 5 Base styles of search Hybrid Algorithms Generally Faster Outline ? Motivation ? Methods of advancing CSP search – Backmarking – Forward Checking ? Hybrid algorithms ? Conclusion What does BM do? ? Objective : BM prevents redundant consistency checks when – The current variable is known to fail with its current value because of some variable in the past still has the value that made the current variable fail. – The current variable is known to succeed with its current value in a check against a past value that still has the same value that made the current variable succeed. ? Tradeoff : must spend time doing, and allot space for, bookkeeping. What does BM do? ? Maximum checking level (mcl) array – Size = Number of variables x domain size – mcl[i,k] holds the index of the deepest variable that v[i] = k, k ? D i , was checked against ? Minimum backup level (mbl) array – Size = Number of variables x 1 – mbl[i] the index of the shallowest past variable that has changed value since v[i] was the current variable What does BM do? ? mcl[i,k] < mbl[i] means the previous consistency check between v[I] = k and some variable in the past of mcl[i,k] failed and will still fail because mcl[i,k] hasn’t been changed ? mcl[I,k] >= mbl[i] means v[i] = k passed consistency checking for all variables in the past of mbl[i]. V[i] only needs to be checked for consistency with the new variables, those in the future of mbl[i] Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 imblGR 000 000 000 000 000 Remaining domain Suppose no element of the domain of the 5 th variable is consistent with the first element of the domain of the first variable Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 imblGR 000 000 000 001 000 Remaining domain Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 imblGR 000 003 002 001 000 Remaining domain Skipping a step Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 imblGR 001 003 002 001 000 Remaining domain X X Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 imblGR 011 003 002 001 000 Remaining domain X XX Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 imblGR 411 003 002 001 000 Remaining domain X X X X Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 imblGR 411 003 002 001 000 Remaining domain X X Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 imblGR 411 033 002 001 000 Remaining domain X Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 imblGR 411 033 002 001 000 Remaining domain X No consistency checks at level 5 will be performed until the value of the first variable is changed X X Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 imblGR 411 033 002 001 000 Remaining domain X X Eventually variable 4 also encounters DWO X XX X Backmarking example Variable # 1 2 3 4 5 1 3 0 0 0 B 5 4 3 2 1 imblGR 411 333 002 001 000 Remaining domain X X X Eventually variable 4 also encounters DWO X Backmarking example Variable # 1 2 3 4 5 1 3 0 0 0 B 5 4 3 2 1 imblGR 411 333 022 001 000 Remaining domain The algorithm does not recognize that no instantiation of variable 4 works while variable 1 is red, it does however save on consistency checks between variable 4 and all variables previous to the shallowest change since variable 4 was last tested X Forward Checking ?Objective : look ahead to find impossible combinations as soon as possible; “fail early” ?Remove inconsistent values from the domains of all future variables ?If domain of future variable is null, then backtrack ?Trade off : perform speculative checks hoping they will reduce the total number of checks you must perform Suppose no element of the domain of the 5 th variable is consistent with the first element of the domain of the first variable Remaining domain 1 2 3 4 5 Variable # This entire sub-tree would be impossible. FC detects this in 12 checks, BT detects this in 426 checks Forward checking example 5 variables to be instantiated, each has domain {red,green,blue} Remaining domain Variable # 1 2 3 4 5 Forward checking example X X Variable # 1 2 3 4 5 First step does 3 x 4 consistency checks In general, n th step can require up to (N-n) x max domain size consistency checks, N = total number of variables Remaining domain Forward checking example X X Variable # 1 2 3 4 5 XX Remaining domain Forward checking example X X X Variable # 1 2 3 4 5 XX Domain wipe out (DWO) occurs, must backtrack Remaining domain Forward checking example X X X X Variable # 1 2 3 4 5 X Remaining domain Forward checking example X X X X X Variable # 1 2 3 4 5 X Remaining domain Forward checking example X X X X X Variable # 1 2 3 4 5 X Solution Found Remaining domain Example when FC is beat by BT BT would pick the first element in each variable’s domain and find the solution while performing the minimum possible number of consistency checks (4+3+2+1 = 10 consistency checks) FC would propagate the domain reductions downward which would be fruitless effort (4x3 + 3x3 + 2x3 + 1x3 = 30 consistency checks) A problem with 5 variables, each with domain of size = 3 Outline ? Motivation ? Methods of advancing CSP search – Backmarking – Forward Checking ? Hybrid algorithms ? Conclusion Why create a hybrid algorithm? ?Objective : create better CSP algorithms by mixing forward and backward algorithms ?Requires that the backward and forward algorithms be compatible : information stored by the forward algorithm won’t be corrupted by the actions of the backward algorithm and vice versa How do you create a hybrid algorithm? ?Implement each algorithm iteratively instead of recursively ?Two functions : move-forward( ) and move-backward( ) ?WHILE (!solution and !impossible) { IF consistent then move-forward( ) ELSE move-backward( ) } ?Maintain the information required by each algorithm in the forward and backward move Hybrid Algorithms Implemented by Prosser Backmark Jumping (BMJ) Backmarking and Conflict Directed Backjumping (BM-CBJ) Forward Checking and Backjumping (FC-BJ) Forward Checking and Conflict Directed Backjumping (FC- CBJ) He compared these with the base algorithms BT, BJ, CBJ, BM, FC on the ZEBRA problem Results: Consistency checks (from Prosser) 119,76726216,38310,361FC-CBJ 280,30226229,97716,839FC-BJ 802,06926271,01235,582FC 1,237,28329772,00425,470BM-CBJ 5,214,608300361,595125,474BMJ 18,405,5144011,276,415396,945BM 19,324,081339193,84663,212CBJ 19,324,0813581,524,193503,324BJ 102,267,38317739,616,4073,858,989BT MaxMinStd. Dev.meanAlgorithm Consistency checks and Nodes visited are two possible, implementation independent metrics for algorithm efficiency. FC’s performance is unfairly enhanced by the Nodes Visited metric since it prunes the tree. Also, consistency checks could possibly be computationally intense for more difficult problems and therefore is the preferable metric How Often One Algorithm (Row) Bettered Another (Column) (from Prosser) -----------388440415447448445450450FC-CBJ 0-----------438333443445415450450FC-BJ 00-----------163421437320450450FC 35117286-----------433442450450450BM-CBJ 372917-----------419170450450BMJ 2513831-----------80318450BM 5351300280370-----------450450CBJ 000001320-----------450BJ 00000000-----------BT FC-CBJFC-BJFCBM-CBJBMJBMCBJBJBT If (i,j) does not equal (j,i) then there were ties Go Backwards Go Forwards BT BM FC BJ CBJ More informed styles Different styles The 5 Base styles of search Generally Faster BMJ FC-BJ BM-CBJ FC-CBJ Beware ? If one part of the hybrid performs poorly on a problem, then its possible that the hybrid will perform poorly as well. – CBJ is usually better than BM, but when BM beats CBJ, its possible that BM might out perform BM-CBJ ? In jumping back you change some past variable further up the tree than you would with BM alone. This causes you to forget about the previous consistency checks that have been performed since mbl[i] < mcl[i,k] Why do BM schemes sometimes outperform FC-CBJ? ? FC performs speculative consistency checks, these may pare down the tree (detect DWO) or they may just be a waste of time ? Can you detect DWO without performing excess consistency checks? – No, but Minimal Forward Checking (MFC) will reduce the number of excess consistency checks MFC ? To detect DWO you only need to check for existence of a single consistent instantiation for a variable – Use lazy evaluation for all consistency checks beyond those necessary to find the first consistent instantiation ? MFC = adding DWO detection to BM with lazy evaluation of consistency checks (hybrid of FC and BM) ? Results : MFC usually performs better than BM, FC, and FC-CBJ Outline ? Motivation ? Methods of advancing CSP search – Backmarking – Forward Checking ? Hybrid algorithms ? Conclusion Conclusion ? BM and FC are powerful in their ability to reduce consistency checks ? Hybrids generally perform better than their constituent parts – Poor performance of one algorithm in the hybrid might mean poor hybrid performance ? Can even make hybrids within the forward move (MFC) Information on MFC from Bacchus, F. & Grove, A. On the Forward Checking Algorithm. In Proceedings the First International Conference on Principle and Practice of Constraint Programming, 292- 309, 1995 Framework for the iterative Constraint Satisfaction Search Problem PROCEDURE bcssp(n,status) BEGIN consistent = true status = “unknown” i = 1 WHILE status == “unknown” DO BEGIN IF consistent THEN i=label(i,consistent) ELSE i = unlabel(i,consistent) IF i>n THEN status = “solution” ELSE IF i=0 THEN status = “impossible” END END 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 FUNCTION bm-label(I,consistent) return INTEGER BEGIN consistent = false FOR k = EACH ELEMENT OF current-domain[I] WHILE not consistent DO BEGIN consistent = mcl[I,k] >= mbl[I] FOR h=mbl[I] TO I-1 WHILE consistent DO BEGIN v[I] = k consistent = check(I,h) mcl[I,k] = h END IF not consistent THEN current-domain[I] = remove(v[I],current-domain[I]) END IF consistent THEN return(I+1) ELSE return(I) END 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 FUNCTION bm-unlabel(I,consistent) return INTEGER BEGIN h = I-1 current-domain[I] = domain[I] mbl[I] = h FOR j = h+1 TO n DO mbl[j] = min(mbl[j],h) current-domain[h] = remove(v[h],current-domain[h]) consistent = current-domain[h] != null return(h) END 1 2 3 4 5 6 7 8 9 10 FUNCTION check-forward(I,j) returns BOOLEAN BEGIN reduction = null FOR v[j] = EACH ELEMENT OF current-domain[j] DO IF not check(I,j) THEN push(v[j],reduction) IF reduction != null THEN BEGIN current-domain[j] = set-difference(current-domain[j],reduction) push(reduction,reductions[j] push(j,future-fc[I]) push(I,past-fc[j]) END return (current-domain[j] != null) END 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 PROCEDURE update-current-domain(I) BEGIN current-domain[I] = domain[I] FOR reduction = EACH ELEMENT OF reductions[I] DO current-domain[i] = set-difference(current-domain[I],reduction) END 1 2 3 4 5 6 FUNCTION fc-label(I,consistent) returns INTEGER BEGIN consistent = false FOR k = EACH ELEMENT OF current-domain[I] WHILE not consistent DO BEGIN consistent = true FOR j = I+1 TO n WHILE consistent DO consistent = check-forward(I,j) IF not consistent THEN BEGIN current-domain[I] = remove(v[I],current-domain[I]) undo-reductions(I) END END IF consistent THEN return(I+1) ELSE return(I) END 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 FUNCTION fc-unlabel(I,consistent) returns INTEGER BEGIN h = I-1 Undo-reductions(h) Update-current-domain(I) current-domain[h] = remove(v[h],current-domain[h]) consistent = current-domain[h] != null return(h) END 1 2 3 4 5 6 7 8 9