Intelligent Backtracking Algorithms Foundations of Constraint Processing CSCE421/821, Spring 2019 www.cse.unl.edu/~choueiry/S19-421-821 Berthe Y. Choueiry (Shu-we-ri) Avery Hall, Room 360 Foundations of Constraint Processing Intelligent Backtracking Algorithms 1 Reading Required reading Hybrid Algorithms for the Constraint Satisfaction Probl em [Prosser, CI 93] Recommended reading Chapters 5 and 6 of Dechters textbook Tsang, Chapter 5 Foundations of Constraint Processing Intelligent Backtracking Algorithms

2 Outline Review of terminology of search Hybrid backtracking algorithms Foundations of Constraint Processing Intelligent Backtracking Algorithms 3 Backtrack search (BT) Variable/value ordering S Variable instantiation (Current) path Var 1 v2 v1 Current variable

Past variables Future variables Shallow/deep levels /nodes Search space / search tree Back-checking Backtracking Foundations of Constraint Processing Intelligent Backtracking Algorithms 4 Outline Review of terminology of search Hybrid backtracking algorithms Vanilla: BT Improving back steps: {BJ, CBJ} Improving forward step: {BM, FC} Foundations of Constraint Processing Intelligent Backtracking Algorithms 5 Two main mechanisms in BT

1. Backtracking: To recover from dead-ends To go back 2. Consistency checking: To expand consistent paths To move forward Foundations of Constraint Processing Intelligent Backtracking Algorithms 6 Backtracking To recover from dead-ends 1. Chronological (BT) 2. Intelligent Backjumping (BJ) Conflict directed backjumping (CBJ) With learning algorithms (Dechter Chapt 6.4) Etc.

Foundations of Constraint Processing Intelligent Backtracking Algorithms 7 Consistency checking To expand consistent paths 1. Back-checking: against past variables Backmarking (BM) 2. Look-ahead: against future variables Forward checking (FC) (partial look-ahead) Directional Arc-Consistency (DAC) (partial lo ok-ahead) Maintaining Arc-Consistency (MAC) (full loo k-ahead) Foundations of Constraint Processing

Intelligent Backtracking Algorithms 8 Hybrid algorithms Backtracking + checking = new hybrids BT BJ CBJ BM BMJ BM-CBJ FC FC-BJ FC-CBJ Evaluation: Empirical: Prosser 93. 450 instances of Zebra Theoretical: Kondrak & Van Beek 95

Foundations of Constraint Processing Intelligent Backtracking Algorithms 9 Notations (in Prossers paper) Variables: Vi, i in [1, n] Domain: Di = {vi1, vi2, ,viMi} Constraint between Vi and Vj: Ci,j Constraint graph: G Arcs of G: Arc(G) Instantiation order (static or dynamic) Language primitives: list, push, pushnew, rem ove, set-difference, union, max-list Foundations of Constraint Processing Intelligent Backtracking Algorithms

10 Main data structures v: a (1xn) array to store assignments v[i] gives the value assigned to ith variable v[0]: pseudo variable (root of tree), backtracking to v [0] indicates insolvability domain[i]: a (1xn) array to store the original dom ains of variables current-domain[i]: a (1xn) array to store the curre nt domains of variables Upon backtracking, current-domain[i] of future variabl es must be refreshed check(i,j): a function that checks whether the val ues assigned to v[i] and v[j] are consistent Foundations of Constraint Processing Intelligent Backtracking Algorithms 11 Generic search: bcssp 1. 2. 3.

4. 5. 6. Procedure bcssp (n, status) Forward move: x-label Begin consistent true Backward move: x-unlabel status unknown Input: i: current variable, i1 consistent: Boolean While status = unknown Return: i: new current variable 7. Do Begin 8. If consistent 9. Then i label (i, consistent) 10. Else i unlabel (i, consistent) 11. If i > n 12. Then status solutionsolution 13. Else If i=0 then status solutionimpossible 14. End 15. End

Foundations of Constraint Processing Intelligent Backtracking Algorithms 12 Chronological backtracking (BT) Uses bt-label and bt-unlabel bt-label: When v[i] is assigned a value from current-domain[i], we perform back-checking against past variables (check(i,k)) If back-checking succeeds, bt-label returns i+1 If back-checking fails, we remove the assigned value from curren t-domain[i], assign the next value in current-domain[i], etc. If no other value exists, consistent nil (bt-unlabel will be called) bt-unlabel Current level is set to i-1 (notation for current variable: v[h]) For all future variables j: current-domain[j] domain[j] If domain[h] is not empty, consistent true (bt-label will be called) Note: for all past variables g, current-domain[g] domain[g]

Foundations of Constraint Processing Intelligent Backtracking Algorithms 13 BT-label 1. 2. 3. 4. Function bt-label(i,consistent): INTEGER BEGIN consistent false For v[i] each element of current-domain[i] while not consistent 5. Do Begin Terminates: 6. consistent true consistent=true, return i+1 7. For h 1 to (i-1) While consistent consistent=false, current8. Do consistent check(i,h) domain[i]=nil, returns i 9. If not consistent 10. Then current-domain[i] remove(v[i], current-domain[i]) 11. End 12. If consistent then return(i+1) ELSE return(i)

13. END Foundations of Constraint Processing Intelligent Backtracking Algorithms 14 BT-unlabel 1. 2. FUNCTION bt-unlabel(i,consistent):INTEGER BEGIN 3. h i -1 4. current-domain[i] domain[i] 5. current-domain[h] remove(v[h],current-domain[h]) 6. consistent current-domain[h] nil 7. return(h) Is called when consistent=false and current-domain[i]=nil 8. END Selects vh to backtrack to (Uninstantiates all variables between v h and vi) Uninstantiates v[h]: removes v[h] from current-domain [h]: Sets consistent to true if current-domain[h] 0 Returns h Foundations of Constraint Processing

Intelligent Backtracking Algorithms 15 Example: BT (the dumbest example ever) {1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} V1 V2 V3 v[0] - v[1] 1 v[2] 1 v[3]

1 CV3,V4={(V3=1,V4=3)} {1,2,3,4,5} V4 v[4] 1 2 3 4 etc 4 5 CV2,V5={(V2=5,V5=1),(V2=5,V5=4)} {1,2,3,4,5}

V5 v[5] 1 2 3 Foundations of Constraint Processing Intelligent Backtracking Algorithms 16 Outline Review of terminology of search Hybrid backtracking algorithms Vanilla: BT Improving back steps: BJ, CBJ Improving forward step: BM, FC Foundations of Constraint Processing Intelligent Backtracking Algorithms

17 Danger of BT: thrashing BT assumes that the instantiation of v[i] w as prevented by a bad choice at (i-1). It tries to change the assignment of v[i-1] When this assumption is wrong, we suffer from thrashing (exploring barren parts of solution space) Backjumping (BT) tries to avoid that Jumps to the reason of failure Then proceeds as BT Foundations of Constraint Processing Intelligent Backtracking Algorithms 18 Backjumping (BJ) Tries to reduce thrashing by saving some backtracking effort When v[i] is instantiated, BJ remembers v [h], the deepest node of past variables tha t v[i] has checked against. Uses: max-check[i], global, initialized to 0 At level i, when check(i,h) succeeds

1 2 3 0 1 2 3 h-1 h h-2 i h 0 0 h-1 max-check[i] max(max-check[i], h) If current-domain[h] is getting empty, simp le chronological backtracking is performed from h

BJ jumps then steps! Past variable Current variable 0 Foundations of Constraint Processing Intelligent Backtracking Algorithms 19 BJ: label/unlabel bj-label: same as bt-label, but updates max-check[i] bj-unlabel, same as bt-unlabel but Backtracks to h = max-check[i] Resets max-check[j] 0 for j in [h+1,i] Important: max-check is the deepest l evel we checked against, could have been success or could have been fail ure 1 2

3 0 1 2 3 h-1 h h-2 i h 0 0 h-1 0 Foundations of Constraint Processing Intelligent Backtracking Algorithms 20

Example: BJ v[0] = 0 {1,2,3,4,5} V1 {1,2,3,4,5} V2 - v[1] 1 v[2] 1 v[3] 1 Max-check[1] = 0

2 Max-check[2] = 1 CV2,V5={(V2=5,V5=1)} {1,2,3,4,5} V3 CV2,V4={(V2=1,V4=3)} {1,2,3,4,5} V4=1, fails for V2, mc=2 V4=2, fails for V2, mc=2 V4=3, succeeds max-check[4] = 3 v[4] V4 V5=1, fails for V1, mc=1 V5=2, fails for V2, mc=2 V5=3, fails for V1 V5=4, fails for V1 v[5] V5=5, fails for V1 max-check[5] = 2 CV1,V5={(V1=1,V5=2)}

{1,2,3,4,5} V5 1 1 2 2 3 3 4 4 5 Foundations of Constraint Processing Intelligent Backtracking Algorithms 21

Conflict-directed backjumping (CBJ) Backjumping jumps from v[i] to v[h], but then, it steps back from v[h] to v[h-1] CBJ improves on BJ Jumps from v[i] to v[h] And jumps back again, across conflicts involvi ng both v[i] and v[h] To maintain completeness, we jump back to th e level of deepest conflict Foundations of Constraint Processing Backtracking Intelligent Backtracking Algorithms 22 CBJ: data structure 0 1 conf-set 2

Maintains a conflict set: conf-set g conf-set[i] are first initialized to {0} h-1 At any point, conf-set[i] is a subset of h past variables that are in conflict with i i conf-set[g] {0} conf-set[h] {0} conf-set[i] {0} {0} {0} {0} Foundations of Constraint Processing Intelligent Backtracking Algorithms 23

CBJ: conflict-set 1 2 3 conf-set[i] conf-set[i] {h} When current-domain[i] empty 1. Jumps to deepest past variable h in conf-set[i] Past variables When a check(i,h) fails g conf-set[g] {x} {x, 3,1} h-1 h conf-set[h] {3} {3,1, g}

Current variable i conf-set[i] {1, g, h} 2. Updates conf-set[h] conf-set[h] (conf-set[i] \{h}) Primitive form of learning (while searching) {0} {0} {0} Foundations of Constraint Processing Intelligent Backtracking Algorithms 24 Example CBJ V1 V2 V3 v[0] = 0

{1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} {(V2=1, V4=3), (V2=4, V4=5)} V4 V5 {1,2,3,4,5} 1 conf-set[1] = {0} v[2] 1 conf-set[2] = {0} v[3] 1 conf-set[3] = {0}

{(V1=1, V5=3)} v[5] 1 conf-set[5] = {1} v[6] 1 {(V4=5, V6=3)} V6 v[1] v[4] 1 2 conf-set[4] = {2} {1,2,3,4,5} {1,2,3,4,5} - {(V1=1, 2 2 3

conf-set[4] = {1, 2} 3 3 4 5 conf-set[6] = {1} conf-set[6] = {1} conf-set[6] = {1,4} V6=3)} conf-set[6] = {1,4} conf-set[6] = {1,4} Foundations of Constraint Processing Intelligent Backtracking Algorithms 25 CBJ for finding all solutions After finding a solution, if we jump from this last variable, then we may miss some solutions and l ose completeness Two solutions, proposed by Chris Thiel (S08)

1. Using conflict sets 2. Using cbf of Kondrak, a clear pseudo-code Rationale by Rahul Purandare (S08) We cannot skip any variable without chronologically backtracking to it at least once In fact, exactly once Foundations of Constraint Processing Intelligent Backtracking Algorithms 26 CBJ/All solutions without cbf When a solution is found, force the last variable, N, to conflict with everything before it conf-set[N] {1, 2, ..., N-1}. This operation, in turn, forces some chronologic al backtracking as the conf-sets are propagated backward Foundations of Constraint Processing

Intelligent Backtracking Algorithms 27 CBJ/All solutions with cbf Kondrak proposed to fix the problem using cbf (flag), a 1xn vector i, cbf[i] 0 When you find a solution, i, cbf[i] 1 In unlabel if (cbf[i]=1) Then h i-1; cbf[i] 0 Else h max-list (conf-set[i]) Foundations of Constraint Processing Intelligent Backtracking Algorithms 28 Backtracking: summary Chronological backtracking Steps back to previous level No extra data structures required

Backjumping Jumps to deepest checked-against variable, then step s back Uses array of integers: max-check[i] Conflict-directed backjumping Jumps across deepest conflicting variables Uses array of sets: conf-set[i] Foundations of Constraint Processing Intelligent Backtracking Algorithms 29 Outline Review of terminology of search Hybrid backtracking algorithms Vanilla: BT Improving back steps: BJ, CBJ Improving forward step: BM, FC Foundations of Constraint Processing Intelligent Backtracking Algorithms 30

Backmarking: goal Tries to reduce amount of consistency che cking Situation: v[i] about to be re-assigned k v[i]k was checked against v[h]g v[h] = g v[h] has not been modified v[i] k k Foundations of Constraint Processing Intelligent Backtracking Algorithms 31 BM: motivation Two situations 1. Either (v[i]=k,v[h]=g) has failed it will fail again 2. Or, (v[i]=k,v[h]=g) was founded consistent it will

remain consistent v[h] = g v[i] v[h] = g k k v[i] k k In either case, back-checking effort against v[h] can be saved! Foundations of Constraint Processing Intelligent Backtracking Algorithms 32

Data structures for BM: 2 arrays maximum checking level: mcl (n x m) Minimum backup level: mbl (n x 1) 0 0 0 0 0 0 0 0 0 0 0 0 0 Number of variables n Number of variables n max domain size m Foundations of Constraint Processing 33

Maximum checking level Number of variables n mcl[i,k] stores the deepest variable that v[i]k checked against mcl[i,k] is a finer version of max-check[i] max domain size m 0 0 0 0 0 0 0 0 0 0 0 0 0 Foundations of Constraint Processing 34

Minimum backup level mbl[i] gives the shallowest past variable whose value has changed since v[i] was the current variable BM (and all its hybrid) do not allow dynamic variable ordering Number of variables n Foundations of Constraint Processing 35 When mcl[i,k]=mbl[i]=j BM is aware that The deepest variable that (v[i] k) checked against is v[j] Values of variables in the past of v [j] (h

We do need to check (v[i] k) agai nst the values of the variables bet ween v[j] and v[i] We do not need to check (v[i] k) against the values of the variables in the past of v[j] v[j] v[i] k k mbl[i] = j Foundations of Constraint Processing Intelligent Backtracking Algorithms 36 Type a savings When mcl[i,k] < mbl[i], do not check v[i] k because it will fail v[h] v[j]

v[i] k k mcl[i,k]=h mcl[i,k] < mbl[i]=j Foundations of Constraint Processing Intelligent Backtracking Algorithms 37 Type b savings When mcl[i,k] mbl[i], do not check (i,h

k mcl[i,k]=g k mcl[i,k]mbl[i] mbl[i] = j Foundations of Constraint Processing Intelligent Backtracking Algorithms 38 Hybrids of BM mcl can be used to allow backjumping in B J Mixing BJ & BM yields BMJ avoids redundant consistency checking (types a+b savings) and reduces the number of nodes visited during s earch (by jumping) Mixing BM & CBJ yields BM-CBJ Foundations of Constraint Processing Intelligent Backtracking Algorithms

39 Problem of BM and its hybrids: warning BMJ enjoys only some of the advantages of BM Assume: mbl[h] = m and max-check[i]=max(mcl[i,x])=g Backjumping from v[i]: v[i] backjumps up to v[g] v[m] v[m] v[m] v[f] Backmarking of v[h]: When reconsidering v[h], v[h] will be checked against all f [m,g) effort could be saved Phenomenon will worsen with CBJ Problem fixed by Kondrak & v an Beek 95 v[g]

v[g] v[g] v[h] v[h] v[h] v[i] v[i] v[i] v[h] Foundations of Constraint Processing Intelligent Backtracking Algorithms 40 Forward checking (FC) Looking ahead: from current variable, consider all future

variables and clear from their domains the values that ar e not consistent with current partial solution FC makes more work at every instantiation, but will expa nd fewer nodes When FC moves forward, the values in current-domain o f future variables are all compatible with past assignment , thus saving backchecking FC may solutionwipe out the domain of a future variable (aka, domain annihilation) and thus discover conflicts early on. FC then backtracks chronologically Goal of FC is to fail early (avoid expanding fruitless subtr ees) Foundations of Constraint Processing Intelligent Backtracking Algorithms 41 FC: data structures When v[i] is instantiated, current-domain[j] are filter ed for all j connected to i and I < j n reduction[j] store sets of values remove from curren t-domain[j] by some variable before v[j] v[i] reductions[j] = {{a, b}, {c, d, e}, {f, g, h}}

v[k] future-fc[i]: subset of the future variables that v[i] ch ecks against (redundant) v[m] future-fc[i] = {k, j, n} past-fc[i]: past variables that checked against v[i] v[j] v[l] All these sets are treated like stacks v[n] Foundations of Constraint Processing Intelligent Backtracking Algorithms 42 Forward Checking: functions

check-forward undo-reductions update-current-domain fc-label fc-unlabel Foundations of Constraint Processing Intelligent Backtracking Algorithms 43 FC: functions Check-Forward(i,j) is called when instantiating v[i] It performs Revise(j,i) Returns false if current-domain[j] is empty, true otherw ise Values removed from current-domain[j] are pushed, a s a set, into reductions[j] These values will be popped back if we have to backtrack over v[i] (undo-reductions) Foundations of Constraint Processing

Intelligent Backtracking Algorithms 44 FC: functions update-current-domain current-domain[i] domain[i] \ reductions[i] actually, we have to iterate over reductions, which is a set of sets fc-label Attempts to instantiate current-variable Then filters domains of all future variables (push into r eductions) Whenever current-domain of a future variable is wipe d-out: v[i] is un-instantiated and domain filtering is undone (pop reductions) Foundations of Constraint Processing Intelligent Backtracking Algorithms 45 Hybrids of FC FC suffers from thrashing: it is based on BT

FC-BJ: max-check is integrated in fc-bj-label and fc-bj-unlabel Enjoys advantages of FC and BJ but suffers malad y of BJ (first jumps, then steps back) FC-CBJ: Best algorithm so far fc-cbj-label and fc-cbj-unlabel Foundations of Constraint Processing Intelligent Backtracking Algorithms 46 Consistency checking: summary Chronological backtracking Uses back-checking No extra data structures Backmarking Uses mcl and mbl Two types of consistency-checking savings Forward-checking Works more at every instantiation, but expands fewer subtrees

Uses: reductions[i], future-fc[i], past-fc[i] Foundations of Constraint Processing Intelligent Backtracking Algorithms 47 Experiments Empirical evaluations on Zebra Representative of design/scheduling problems 25 variables, 122 binary constraints Permutation of variable ordering yields new search sp aces Variable ordering: different bandwidth/induced width o f graph 450 problem instances were generated Each algorithm was applied to each instance Experiments were carried out under static variable ordering Foundations of Constraint Processing Intelligent Backtracking Algorithms 48 Analysis of experiments Algorithms compared with respect to:

1. Number of consistency checks (average) FC-CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B FC-BJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ BBM-CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B FC FC-BJ BM-CBJ FC CBJ BMJ BM BJ B CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BMJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BM FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B B T 2. Number of nodes visited (average) FC-CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B FC-BJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B FC FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BM-CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BMJ=BJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BM=BT 3. CPU time (average) FC-CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B FC-BJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B FC FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BM-CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B CBJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BMJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BJ FC-BJ BM-CBJ FC CBJ BMJ BM BJ B BT FC-BJ BM-CBJ FC CBJ BMJ BM BJ B B M FC-CBJ apparently the champion Foundations of Constraint Processing Intelligent Backtracking Algorithms 49 Additional developments Other backtracking algorithms exist: Graph-based backjumping (GBJ), etc. Pseudo-trees [Freuder 85] [Dechter] Other look-ahead techniques exist DAC, MAC, etc.

More empirical evaluations over randomly generated problems Theoretical comparisons [Kondrak & van Beek IJCAI95] Foundations of Constraint Processing Intelligent Backtracking Algorithms 50 Implementing BT-based algorithms Preprocessing Enforce NC, do not include in #CC (e.g., Zebra) Normalize all constraints (fapp01-0200-0) Check for empty relations (bqwh-15-106-0_ext) Interrupt as soon as you detect domain wipe out Dynamic variable ordering Apply domino effect Foundations of Constraint Processing Intelligent Backtracking Algorithms

51