11m ago

3 Views

1 Downloads

1.03 MB

51 Pages

Transcription

Symmetries in CSPSymmetries in CSPElena ShermanUNL, CSEApril 18, 2009

Symmetries in CSPTable of contentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note

Symmetries in CSPWhy Symmetry?ContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note

Symmetries in CSPWhy Symmetry?What is Symmetry?SymmetryIDefined as “patterned self-similarity”.IGenerated by a transformation S of an object O1 into O2 .IS(O1 ) is not distinguishable from O2 .ICommon S are translation, rotation and reflection.

Symmetries in CSPWhy Symmetry?Crafting a Paper SnowflakeHow to cut out a snowflake from a piece of paper?

Symmetries in CSPWhy Symmetry?Crafting a Paper SnowflakeHow to cut out a snowflake from a piece of paper?

Symmetries in CSPWhy Symmetry?Crafting a Paper SnowflakeHow to cut out a snowflake from a piece of paper?In general biological science problems have many geometric symmetries.

Symmetries in CSPWhy Symmetry?Why is Symmetry?ICSP (V , D, C ) NPC , but islands of tractability.IUsing the structure of CSP to reduce complexity, or to reduce theproblem size.ISymmetry can occur in V , D and C ex. All-Diff constraint.CSP’s elements that are symmetric under S create an equivalenceclass.IIProperty detected in one element of an equivalent class can begeneralized to all elements of that class. Ex.D {1, 2, 3, 4, 5, 6, 7} D {[2, 4, 6], [3, 5, 7]}.

Symmetries in CSPSymmetry ExamplesContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note

Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 Rotation

Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIRotate by 180 degrees.

Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIRotate by 180 degrees.

Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIIIIRotate by 180 degrees.x1 exchanges with x5 and x2 with x4 .New domains θ(val) 6 val for each xi .Equivalence classes:IIVariables {x1 , x2 }, {x2 , x4 } and {x3 }.Values {1, 5}, {2, 4}, {3}.

Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIIIIRotate by 180 degrees.x1 exchanges with x5 and x2 with x4 .New domains θ(val) 6 val for each xi .Equivalence classes:IIIVariables {x1 , x2 }, {x2 , x4 } and {x3 }.Values {1, 5}, {2, 4}, {3}.Reflection about the horizontal axis and vertical axis.

Symmetries in CSPSymmetry Examples5-queens Symmetry Example S 180 RotationIIIIRotate by 180 degrees.x1 exchanges with x5 and x2 with x4 .New domains θ(val) 6 val for each xi .Equivalence classes:IIIIVariables {x1 , x2 }, {x2 , x4 } and {x3 }.Values {1, 5}, {2, 4}, {3}.Reflection about the horizontal axis and vertical axis.Rotation by 360? Rotation by 90?

Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?

Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?

Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?

Symmetries in CSPSymmetry Examples5-queens - Different FormulationIX {x1 , x2 , x3 , x4 , x5 }ID {1, 2, . . . , 25}IWhat are the symmetries here? Do they include domains, variablesor both?IAll 8 symmetries.

Symmetries in CSPSymmetry ExamplesFormulation of CSP has Symmetry and not the ProblemIThe definition of the symmetry applies to the definition of CSP andnot to the problem itself.IDifferent CSP’s formulations of the same problem can have differentsymmetries.IWhat symmetry to select?

Symmetries in CSPSymmetry ExamplesFormulation of CSP has Symmetry and not the ProblemIThe definition of the symmetry applies to the definition of CSP andnot to the problem itself.IDifferent CSP’s formulations of the same problem can have differentsymmetries.IWhat symmetry to select? What about one that produces thesmallest number of equivalent classes?

Symmetries in CSPApproaches for Symmetrical CSPsContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note

Symmetries in CSPApproaches for Symmetrical CSPsThree Approaches for Symmetrical CSPsAdding symmetry breaking global constraintsIAdding global constraints to convert it to an asymmetrical CSP.Modify searchIPruning symmetric states as they appear in search.Modify search heuristicsIUsing symmetry-breaking rules to guide search.

Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsRemoving Symmetry from the Problem - Global SymmetryIPuget [93] while developing PECOS tool.ISymmetry can cause a combinatorial explosion of the search space.IArc-consistency AC is not adapted to symmetrical CSPs. Ex.Pigeon Hole problem.In symmetrical CSP a permutation of the variables map one solutiononto another solution.IIRemoving symmetrical solutions by adding a constraint - if C C 0then Sol(P 0 ) Sol(P) - reduction.IAdd static symmetry breaking constraints - an ordering constraintx1 x2 · · · xn - and do AC after that.

Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsCreating a Global ConstraintExampleIV {v0 , v1 , v2 }, D {0, 1, 2}IC : v0 6 v1 v1 6 v2 v2 6 v0IHow many solutions?

Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsCreating a Global ConstraintExampleIV {v0 , v1 , v2 }, D {0, 1, 2}IC : v0 6 v1 v1 6 v2 v2 6 v0IHow many solutions?Has a symmetry (permutation): v0 v1 , v1 v2 , v2 v0I

Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsCreating a Global ConstraintExampleIV {v0 , v1 , v2 }, D {0, 1, 2}IC : v0 6 v1 v1 6 v2 v2 6 v0IIHow many solutions?Has a symmetry (permutation): v0 v1 , v1 v2 , v2 v0IAdding v0 v1 v2 - How many solutions?

Symmetries in CSPApproaches for Symmetrical CSPsAdding symmetry-breaking global constraintsGeneral DirectionIEnforcing GAC on this global constraint reduces the problem.IDepending on the decomposition of a problem GAC propagation canbe NPC .In ”other” constraint paper by Law at al. [CP07].IIIIProposed SigLex global constraint.Its GAC propagation is P.But it prunes only some symmetric values in general cases.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is Dynamic [Meseguer & Torras 2001]ISymmetries holding at the initial states is a global symmetry.IAfter an assignment to vi the global symmetry may break.IYet, new symmetries can appear in some states.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is DynamicISymmetries holding at the initial states is a global symmetry.IAfter an vi assignment the global symmetry can break.IYet, new symmetries can appear in some states.ISymmetries can be broken and restored during the search.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetry is DynamicISymmetries holding at the initial states is a global symmetry.IAfter an vi assignment the global symmetry can break.IYet, new symmetries can appear in some states.ISymmetries can be broken and restored during the search.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationPruning Symmetric States from SearchSymmetric Variables [Brown et al. 1989]IDoes not select vvp if vvp leads to a redundant partial assignment.IDetermines if a current partial assignment X is equivalent to asmaller assignment under a symmetry group G .IHas pseudo code of the Backtracking Algorithm with Symmetries.ISymmetries are given.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationPruning Symmetric States from SearchSymmetric Values [Freuder 1991]IOnly selects one val from equivalence class of values during vvpselection.IValues a and b are neighborhood interchangeable if each vvp isconsistent with their neighborhood.IAlgorithm to determine local value interchangeability is O(n2 d 2 ).ISymmetries are discovered.

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetric Variables and Values [Backofen & Will CP99,Gent & Smith 2000]IDoes not interfere with the heuristic searches (variable ordering).IAdds symmetry breaking constraints to the right branches of searchtree.x1 2, x2 3 - backtracking

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetric Variables and Values [Backofen & Will CP99,Gent & Smith 2000]IDoes not interfere with the heuristic searches (variable ordering).IAdds symmetry breaking constraints to the right branches of searchtree.x1 2, x2 3 - backtrackingx1 2, x2 6 3 - should we consider x4 3?

Symmetries in CSPApproaches for Symmetrical CSPsSearch space modificationSymmetric Variables and Values [Backofen & Will CP99,Gent & Smith 2000]IDoes not interfere with the heuristic searches (variable ordering).IAdds symmetry breaking constraints to the right branches of searchtree.x1 2, x2 3 - backtrackingx1 2, x2 6 3 - should we consider x4 3? Depends if x5 5 or notIf x5 6 5 then x2 3 and x3 3 are not equivalent. Generally it is not known ifx5 5 or x5 6 5.Adding a conditional constraint x1 1 x2 6 3 x5 5 x4 6 3.

Symmetries in CSPApproaches for Symmetrical CSPsHeuristics modificationUse Symmetry to Guide SearchDynamic Variable Ordering [Meseguer & Torras 2001]IIDirect search toward subspaces with many non-symmetric states.Selecting vvp that breaks the most of the symmetries.IIt will lead to more evenly distributed solutions in the CSP’s statespace.IMore about it in my project presentation.

Symmetries in CSPHistorical NoteContentsWhy Symmetry?Symmetry ExamplesApproaches for Symmetrical CSPsAdding symmetry-breaking global contraintsSearch space modificationHeuristics modificationHistorical Note

Symmetries in CSPHistorical NoteIAvoiding symmetric path in search [Glaischer 1874, Brown et al.1989]IValue interchangeability [Freuder 1991]ISymmetry breaking constraints [Puget 93, Backofen & Will 99]Discovering symmetriesIIIIEquivalent to graph isomorphism.Complexity unknown (P? NPC?)Discover symmetry generators with Nauty, Saucy, AUTOM

Symmetries in CSPHistorical NoteBibliography ICynthia A. Brown, Larry Finkelstein, and Paul Walton Purdom, Jr.Backtrack searching in the presence of symmetry.In AAECC-6: Proceedings of the 6th International Conference, onApplied Algebra, Algebraic Algorithms and Error-Correcting Codes,pages 99–110, London, UK, 1989. Springer-Verlag.Rolf Backofen and Sebastian Will.Excluding symmetries in constraint-based search.In CP ’99: Proceedings of the 5th International Conference onPrinciples and Practice of Constraint Programming, pages 73–87,London, UK, 1999. Springer-Verlag.Darga et al.Saucy.http://vlsicad.eecs.umich.edu/BK/SAUCY.

Symmetries in CSPHistorical NoteBibliography IIEugene C. Freuder.Eliminating interchangeable values in constraint satisfactionproblems.In In Proceedings of AAAI-91, pages 227–233, 1991.J.W.L. Glaisher.On the Problem of the Eight Queens.Philosophical Magazine, 48:457–467, 1874.Ian P. Gent and Barbara M. Smith.Symmetry breaking in constraint programming.In Proceedings of ECAI-2000, pages 599–603. IOS Press, 2000.Y. C. Law, J. H. M. Lee, Toby Walsh, and J. Y. K. Yip.Breaking symmetry of interchangeable variables and values.In Principles and Practice of Constraint Programming CP 2007,pages 423–437, London, UK, 2007. Springer-Verlag.

Symmetries in CSPHistorical NoteBibliography IIIBrendan .Pedro Meseguer and Carme Torras.Exploiting symmetries within constraint satisfaction search.Artif. Intell., 129(1-2):133–163, 2001.Jean-Francois Puget.On the satisfiability of symmetrical constrained satisfactionproblems.In ISMIS ’93: Proceedings of the 7th International Symposium onMethodologies for Intelligent Systems, pages 350–361, London, UK,1993. Springer-Verlag.Jean-Francois Puget.Automatic Detection of Variable and Value Symmetries, 2005.

Why Symmetry? Why is Symmetry? I CSP (V;D;C) 2NPC, but 9islands of tractability. I Using the structure of CSP to reduce complexity, or to reduce the problem size. I Symmetry can occur in V, D and C ex. All-Diff constraint. I CSP’s elements that are symmetric under Screate an equiva

Related Documents: