Constraint Processing Foundations in Lookahead Schemas
Explore the fundamentals of Lookahead Schemas in Constraint Processing including techniques like Forward Checking and Directional Arc Consistency. Learn how to revise variable domains to make efficient decisions and avoid expanding unnecessary parts of the problem tree.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lookahead Schemas Foundations of Constraint Processing CSCE421/821, Spring 2019 www.cse.unl.edu/~choueiry/S19-421-821/ All questions to Piazza Berthe Y. Choueiry (Shu-we-ri) Avery Hall, Room 360 Tel: +1(402)472-5444 Foundations of Constraint Processing 1 Lookahead Schemas
Outline: Lookahead Schemas Forward checking (FC) Directional Arc Consistency (DAC) Maintaining Arc Consistency (a.k.a. full arc-consistency) Foundations of Constraint Processing 2 Lookahead Schemas
Looking ahead: Rationale As decisions are made (conditioning) Revise the domain of future variables to propagate the effects of decisions (instantiations) i.e., eliminate inconsistent choices in future sub- problem Domain annihilation of a future variable avoids expansion of useless portions of the tree Foundations of Constraint Processing 3 Lookahead Schemas
Looking ahead: Techniques Partial forward-checking (FC) directional arc-consistency (DAC) Full Maintaining arc-consistency (MAC) a.k.a. Real Full Lookahead (RFL) Initialize the queue with the set of (Vf,Vc) REVISE(Vf,Vc), Vffuture variable, Vccurrent variable Foundations of Constraint Processing 4 Lookahead Schemas
Revise the domain of Vi Revising the domain of Vigiven a constraint CVi,Vjon Vi(i.e., Vi scope(C)) General notation: REVISE(Vi,CVi,Vj) In a binary CSP: REVISE(Vi,CVi,Vj)= REVISE(Vi,Vj) Foundations of Constraint Processing 5 Lookahead Schemas
Revise Revise(Vi, Vj) Revise(Vi, Vj) 1. revised nil 2. x Dvi 3. 4. 5. 6. 7. Return revised NOTE: only DVi may be updated y DVj If Check((Vi,x),(Vj,y)) Then break revised t DVi DVi \ {x} Simpler, equivalent code but not as obvious as the previous one Foundations of Constraint Processing 6 Lookahead Schemas
Domain filtering in lookahead Vccurrent variable Vffuture variable {Vf} all future variables Revise(Vf, Vc) FC(Vc): 1. Vf {Vf} connected to Vc 2. Revise(Vf,Vc) 3. If DVf ={} then break false Foundations of Constraint Processing 7 Lookahead Schemas
Directional Arc Consistency Choose an ordering d, stick to it After instantiating a variable at level i, do the following 1. For k from i to (n-1) in the ordering d Do 2. If FC(Vk)= false then break false Foundations of Constraint Processing 8 Lookahead Schemas
Real Full Lookahead (RFL) AC-3 Set Q {(Vf,Vc) | Vcis the current variable, Vf Neigh(Vf)} Run AC-3(Q) AC-1 does too many checks First revise all the tuples in {(Vf,Vc)} Then, call AC-1 ({(Vi,Vj), Vi,Vj are future variables}}) Foundations of Constraint Processing 9 Lookahead Schemas
Look-ahead techniques: FC, DAC, RFL FC: DAC: FC(Vc) FC(Vc); While not failure: For the next Vf in the ordering d, FC(Vf) assumes a fixed variable ordering d RFL: FC(Vc); AC-3({Vf}) FC(Vc); Repeat until quiescence or failure Vf1,Vf2 {Vf}, Revise(Vf1,Vf2) does more pruning (search may visit fewer nodes) at the cost of more consistency checks Foundations of Constraint Processing 10 Lookahead Schemas
Terminology overload alert: FC FC is used to denote one of the following: a partial look-ahead schema a specific chronological backtrack search algorithm that uses the partial look-ahead schema Meaning is inferred from context Not a healthy situation, but a fact of reality Advice: state upfront the meaning of your terms and stick to them throughout your paper Foundations of Constraint Processing 11 Lookahead Schemas
(BT Search +) RFL vs. FC Reference: [Sabin & Freuder, ECAI94], [Bessi re & R gin, CP97], [Sabin & Freuder, CP97], [Gent & Prosser, APES-20-2000], [Experiments by Lin XU, 2001], [Yang, MS thesis 2003] Results: (sketchy) Low tightness High tightness FC RFL Low density (sparse) High density (dense) FC FC Note: Results depend on Variable ordering (static vs. dynamic) Problem difficulty (positive relative to crossover point) Foundations of Constraint Processing 12 Lookahead Schemas
Alert: Terminology Distinguish between Real Full Lookahead (RFL) Maintaining Arc Consistency (MAC) MAC assumes binary branching Foundations of Constraint Processing 13 Lookahead Schemas
