Foundations of Constraint Processing: Global Consistency Properties
Dive into the world of constraint processing with a focus on global consistency properties such as minimality and decomposability. Explore the concepts of n-consistency, strong consistency, and the extendability to non-binary CSPs. Uncover the essence of every constraint being as tight as possible and the ability for consistent partial solutions to be terminated backtrack free. Delve into graphical illustrations depicting arc consistency, path consistency, and more, providing a visual understanding of these fundamental concepts.
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
More on Constraint Consistency Properties & Algorithms Foundations of Constraint Processing CSCE421/821, Spring 2022 www.cse.unl.edu/~choueiry/S22-421-821/ All questions to Piazza Berthe Y. Choueiry (Shu-we-ri) Avery Hall, Room 259 Tel: +1(402)472-5444 Foundations of Constraint Processing 1 More on Constraint Consistency
Summary 1. Global properties 2. Local properties Binary CSPs Non-Binary CSPs 3. Effects of Consistency Algorithms Domain filtering Constraint filtering Constraint synthesis 4. Beyond finite, crisp CSPs Continuous domains Weighted CSPs Foundations of Constraint Processing 2 More on Constraint Consistency
Outline 1. Global properties 2. Local properties Binary CSPs Dechter Sections 3.1, 3.2, 3.3, 3.4 Non-Binary CSPs 3. Effects of Consistency Algorithms Domain filtering Constraint filtering Constraint synthesis 4. Beyond finite, crisp CSPs Continuous domains Weighted CSPs Dechter Sections 3.5.1, 8.1 Dechter Sections 3.5.3 Foundations of Constraint Processing 3 More on Constraint Consistency
Global Consistency Properties Minimality & Decomposability Originally defined for binary CSPs Easily extendable to non-binary CSPs Minimality Dechter Definition 2.6 Every constraint is as tight as it can be Minimality n-consistency A.k.a. strong consistency (strongly consistent) in the literature In DB, the relations are said to join completely Decomposability Every consistent partial solution can be terminated backtrack free Decomposability strong n-consistency Foundations of Constraint Processing 4 More on Constraint Consistency
Graphical Illustration Minimality tuple n-2 variables Decomposability any consistent assignment of length k n-k variables Arc consistency (1,1)-consistency vvp (2,1)-consistency Path consistency tuple (k-1,1)-consistency k-consistency kthvariables any consistent assignment of length k-1 (i,j)-consistency any consistent assignment of length i j variables (1,j)-consistency inverse consistency vvp j variables NIC vvp deg variables Foundations of Constraint Processing 5 More on Constraint Consistency
Outline 1. Global properties 2. Local properties Binary CSPs Non-Binary CSPs 3. Effects Domain filtering Constraint filtering Constraint synthesis 4. Beyond finite, crisp CSPs Continuous domains Weighted CSPs Foundations of Constraint Processing 6 More on Constraint Consistency
Local Properties: Binary CSPs Classical ones Based on variations of (i,j)-consistency More recently Singleton Arc Consistency Inverse Consistency Neighborhood Inverse Consistency (Conservative) Dual consistency Special Constraints Foundations of Constraint Processing 7 More on Constraint Consistency
Classical Local Consistency: Properties Arc consistency Every vvp can be extended to a partial solution of length 2 Path consistency Every partial solution of length 2 can be extended to a partial solution of length 3 i-consistency Every partial solution of length (i-1) can be extended to a partial solution of length i (i,j)-consistency Every partial solution of length i can be extended to a partial solution of length i+j Foundations of Constraint Processing 8 More on Constraint Consistency
Classical Local Consistency: Algorithms Arc consistency: AC-1, 2, 3, , 7, AC-2001, AC-*, Effect: domain filtering Complexity: in n2 Path consistency PC-1, 2, 3, , 8, PC2001, PPC, Effect: adds binary constraints, modifies the width of network Complexity: in n3 i-consistency Dechter Figure 3.14 & 3.15 Effect: adds constraints of arity i-1, modifies the arity of network Complexity: in ni Foundations of Constraint Processing 9 More on Constraint Consistency
Local Properties: Binary CSPs Classical ones Based on variations of (i,j)-consistency More recently Singleton Arc Consistency Inverse Consistency Neighborhood Inverse Consistency (Conservative) Dual consistency Special Constraints Foundations of Constraint Processing 10 More on Constraint Consistency
Singleton Arc Consistency (SAC) Property: The CSP is AC for every vvp (Sketchy) Algorithm Repeat for each variable Repeat for each value in domain Assign this value to this variable. If the CSP is AC, keep the value. Otherwise, remove it. Effect: domain filtering Note Proposed by Debruyne & Bessi re, IJCAI 97 Quite expensive, but can be quite effective Foundations of Constraint Processing 11 More on Constraint Consistency
POAC SAC Partition-One AC SAC Keep a counter for all vvps on For every singleton test on domain of Update the counter if value appears If counter is zero, remove vvp Foundations of Constraint Processing 12 More on Constraint Consistency
Inverse Consistency Path Inverse Consistency (PIC) Equivalent to (1,2)-consistency Inverse m-consistency Equivalent to (1,m)-consistency Neighborhood Inverse Consistency (NIC) Every vvp participates in a solution in the CSP induced by its neighborhood Global Inverse Consistency (GIC) Domain minimality Foundations of Constraint Processing 13 More on Constraint Consistency
Neighborhood Inverse Consistency (NIC): Algorithm Repeat until no change occurs Repeat for each variable Consider only the neighborhood of the variable Repeat for each value for the variable If the value appears in a complete solution for the neighborhood, then keep it. Otherwise, remove it. Effect: domain filtering Note Proposed by Freuder & Elfe, AAAI 96 Very effective, very expensive Foundations of Constraint Processing 14 More on Constraint Consistency
Summary: Binary CSPs (i,j)-consistency j=1 Arc consistency: (1,1)-consistency Path consistency: (2,1)-consistency i-consistency: (i-1,1)-consistency Strong i-consistency: k-consistency for all k i i=1, inverse consistency Path Inverse Consistency (PIC): (1,2)-consistency Global Inverse Consistency (GIC): (1,n-1) consistency (minimal domains) Neighborhood Inverse Consistency (NIC) Foundations of Constraint Processing 15 More on Constraint Consistency
Local Properties: Binary CSPs More recently Singleton Arc Consistency Partial Path Consistency (PPC) (Conservative) Dual consistency Conservative Path Consistency Debruyene ICTAI 99 Special Constraints Foundations of Constraint Processing 16 More on Constraint Consistency
Special Constraints: AC [Van Hentenryck et al. AIJ 92] Specialized AC algorithms exist for special constraints Functional A constraint C is functional with respect to a domain D iff for all v D (respectively w D) there exists at most one w D (respectively v D) such that C(v,w) Anti-functional A constraint C is anti-functional with respect to a domain D iff C is functional with respect to D Monotonic A constraint C is monotonic with respect to a domain D iff there exists a total ordering on D such that, for all v and w D, C(v,w) holds implies C(v ,w) holds for all values all v and w D such that v v and w w Foundations of Constraint Processing 17 More on Constraint Consistency
Outline 1. Global properties 2. Local properties Binary CSPs Non-Binary CSPs 3. Effects of Consistency Algorithms Domain filtering Constraint filtering Constraint synthesis 4. Beyond finite, crisp CSPs Continuous domains Weighted CSPs Foundations of Constraint Processing 18 More on Constraint Consistency
How about Non-binary CSPs? (Almost) all properties (& algorithms) discussed so far were restricted to binary CSPs Consistency properties for non-binary CSPs are the topic of current research Mainly, properties and algorithms for: 1. Domain filtering techniques (a.k.a. domain reduction, domain propagation) Do not change topology of network (width/arity) Do not modify constraints definitions 2. Relational m-consistency Add constraints/change constraint definitions [Dechter, Chap 8] Foundations of Constraint Processing 19 More on Constraint Consistency
Non-Binary CSPs 1. Domain filtering Generalized Arc Consistency (GAC) Dechter 3.5.1 Singleton Generalized Arc Consistency (SGAC) maxRPWC, rPIC, RPWC, etc. [Bessiere et al., 08] 2. Relational consistency (strong) Relational m-consistency Relational Arc-Consistency (R1C) Relational Path-Consistency (R2C) Relational (i,m)-consistency i = 1, Relational (1,m)-consistency is a domain filtering technique i=1 and m=2, Relational (1,m)-consistency is known as rPIC Relational (*,m)-consistency (m-wise consistency) Foundations of Constraint Processing 20 More on Constraint Consistency
Generalized Arc-Consistency: Property First introduced by [Mohr & Masini, ECAI 88] Every value in the domain of every variable has a support in every constraint in the problem In every constraint, every vvp participates in a consistent tuple (can be extended to all other variables in the scope of the constraint) Foundations of Constraint Processing 21 More on Constraint Consistency
Generalized Arc-Consistency: Algorithm1 (Sketchy) Algorithm Project the constraint on each of the variables in its scope to tighten the domain of the variable. As domains are filtered, filter the constraint Repeat the above until quiescence When constraint is not defined in extension, GAC may be problematic (e.g., NP-hard in TCSP) Foundations of Constraint Processing 22 More on Constraint Consistency
Generalized Arc-Consistency: Algorithm2 Another (Sketchy) Algorithm Iterate over every combination of a variable and a constraint where it appears (Vx, Ci) For every value for Vx, identify a support for this value in Ci, where a support is a tuple where all vvps in the tuple are alive Repeat the above until quiescence Does not filter the constraints Check GAC2001 [Bessi re et al., AIJ05] When constraint is not defined in extension, GAC may be problematic (e.g., NP-hard in TCSP) Foundations of Constraint Processing 23 More on Constraint Consistency
SGAC Idea: Similar to SAC (Sketchy) Algorithm Repeat until quiescence For each vvp Assign the vvp; Enforce GAC on the CSP; If CSP is GAC, keep the vvp, else remove it Note Costly in practice, but polynomial as long as GAC is polynomial SGAC has been empirically shown to solve every known 9x9 Sudoku puzzle Foundations of Constraint Processing 24 More on Constraint Consistency
Relational Consistency Dechter generalizes consistency Dechter 8.1.1 properties to non-binary constraints Relational m-consistency Relational 1-consistency relational arc-consistency Relational 2-consistency relational path-consistency Relational (i,m)-consistency Relational (1,1)consistency GAC m-wise consistency (Databases) Relational (*,m)-consistency Foundations of Constraint Processing 25 More on Constraint Consistency
Relational 1-Consistency Dechter Def 8.1 Property For every constraint C Let k be the arity of C Every consistent partial solution of length k-1 Can be extended to a consistent partial solution of length k (Sketchy) Algorithm Dechter Equation (8.2), (8.3) For each C, generate k constraints, each of arity k-1 by Joining C with the domain of each variable x in scope of C and Projecting result on remaining variables (possibly intersecting with existing constraints) Effect: For each constraint, it adds k constraints Complexity: polynomial in the largest scope Foundations of Constraint Processing 26 More on Constraint Consistency
Relational 2-Consistency Dechter Def 8.2 Property For every two constraints C1and C2 ,every consistent partial solution over can be extended to (Sketchy) Algorithm Dechter Equation (8.4) generate all constraints of arity |u|-1 by Joining C1, C2, (and the domain of variables u) and Projecting the result on Effect: adds |s| new constraints Complexity: polynomial in |u| a1 ai as C1 s C2 Foundations of Constraint Processing 27 More on Constraint Consistency
Relational m-Consistency Dechter Def 8.3 Property For m constraints C1, C2, , Cm ,every consistent partial solution over can be extended to (Sketchy) Algorithm Dechter Equation (8.5) generate all constraints of arity |u|-1 by (and the domain of variables u) Projecting the result on Effect: adds |s| new constraints Complexity: polynomial in |u| a1 ai as C1 s C2 Cm Foundations of Constraint Processing 28 More on Constraint Consistency
Relational m-Consistency Dechter Def 8.3 Property For every m constraints C1, C2, .., Cm Let s = i mscope(Ci) Every consistent partial solution of length |s|-1 Can be extended to a consistent partial solution of length |s| (Sketchy) Algorithm Dechter Equation (8.5) For each m constraints, generate all constraints of arity |s| -1 by Joining the m constraints and the domain of a variable (at the intersection of their scopes) and Projecting the result on remaining variables Effect: Adds a huge number of new constraints Complexity: polynomial in the sum of largest 2 scopes Foundations of Constraint Processing 29 More on Constraint Consistency
Relational (i,m)-Consistency Dechter Def 8.4 Property For every m constraints C1, C2, .., Cm Let s = i mscope(Ci) Every consistent partial solution of length i Can be extended to a consistent partial solution of length |s| Algorithm Dechter Fig 8.1 For each m constraints, generate all constraints of arity i by Joining the m constraints and the domain of a variable (at the intersection of their scopes) and Projecting the result on every combination of i variables Effect: Adds a huge number of new constraints, except for i=1 Complexity: exponential in s (largest union of scope of m constraints) in time and space Foundations of Constraint Processing 30 More on Constraint Consistency
m-wise consistency Property For every set of m constraints, Every tuple in each constraint appears in a consistent solution to the m constraints That is, each constraint is as tight as it can be for the set of m constraints tuple .. relation m-1 relations (Sketch of) Algorithm: PerTuple, AllSol, etc. Effect: Filters the constraints, w/o introducing new constraints Note: Defined in DB: pairwise consistency, relations join completely First defined as R(*,m)C, now recast as m-wise consistency Foundations of Constraint Processing 31 More on Constraint Consistency
Summary: Non-Binary CSPs 1. Domain filtering Generalized Arc Consistency (GAC) Singleton Generalized Arc Consistency (SGAC) maxRPWC, rPIC, RPWC, etc. [Bessiere et al., 08] 2. Relational consistency (strong) Relational m-consistency Relational Arc-Consistency (R1C) Relational Path-Consistency (R2C) Relational (i,m)-consistency i = 1, Relational (1,m)-consistency is a domain filtering technique i=1 and m=2, Relational (1,m)-consistency is known as rPIC Relational (*,m)-consistency (m-wise consistency) Foundations of Constraint Processing 32 More on Constraint Consistency
Outline 1. Global properties 2. Local properties Binary CSPs Non-Binary CSPs 3. Effects of Consistency Algorithms Domain filtering Constraint filtering Constraint synthesis 4. Beyond finite, crisp CSPs Continuous domains Weighted CSPs Foundations of Constraint Processing 33 More on Constraint Consistency
Effects of Consistency Algorithms Filter the domains Old algorithms: AC-*, GAC-*, etc. New algorithms: maxRPWC, R(1,m)C, etc. Filter the constraints New algorithms: R(*,m)C Add new constraints to the problem Old algorithms: PC-2, etc. i-consistency (i > 2), (i,j)-C, RmC, R(i,m)C Example: Solving the CSPs by Constraint Synthesis Foundations of Constraint Processing 34 More on Constraint Consistency
Solving CSPs by Constraint Synthesis [Freuder 78] From i=2 to i=n, achieve i-consistency by using (i -1)-arity constraints to synthesize i-arity constraints, then use the i-ary constraints to filter constraints of arity i-1, i-2, etc. Process ends with a unique n-ary constraint whose tuples are all the solutions to the CSP Foundations of Constraint Processing 35 More on Constraint Consistency
Outline 1. Global properties 2. Local properties Binary CSPs Non-Binary CSPs 3. Effects of Consistency Algorithms Domain filtering Constraint filtering Constraint synthesis 4. Beyond finite, crisp CSPs Continuous domains Weighted CSPs Foundations of Constraint Processing 36 More on Constraint Consistency
Box Consistency (on interval constraints) Domains are (continuous) intervals Historically also called: continuous CSPs, continuous domains Domains are infinite: We cannot enumerate consistent values/tuples [Davis, AIJ 87] (see recommended reading) showed that even AC may be incomplete or not terminate We apply consistency (usually, arc-consistency) on the boundaries of the interval Sometimes, domains are split, so that boundaries can be further filtered Foundations of Constraint Processing 37 More on Constraint Consistency
Weighted CSPs Weighted CSPs Tuples have weights in [0,m], m: intolerable cost Costs are added a b=min{m,a+b} Soft Arc Consistency (Cooper, de Givry, Schiex, etc.) VAC: Virtual Arc Consistency EDAC: Existential Directional Arc Consistency OSAC: Optimal Soft Arc Consistency Foundations of Constraint Processing 38 More on Constraint Consistency
Summary 1. Global properties 2. Local properties Binary CSPs Non-Binary CSPs 3. Effects of Consistency Algorithms Domain filtering Constraint filtering Constraint synthesis 4. Beyond finite, crisp CSPs Continuous domains Weighted CSPs Foundations of Constraint Processing 39 More on Constraint Consistency
Global Decomposability Minimality (global consistency) Consistency Foundations of Constraint Processing 40 More on Constraint Consistency
Local AC, GAC PPC, DPC, CDC, sCDC1 (original), DC2 (completes the graph) SAC, POAC, NIC, RNIC (i,j)-consistency, (1,j)-consistency PW-AC, m-wise consistency maxRPWC, rPIC, RPWC Relational m-consistency, Relational (i,m)-consistency Box consistency Foundations of Constraint Processing 41 More on Constraint Consistency
