Information Technology Reference
In-Depth Information
New Developments in Symmetry Breaking
in Search Using Computational Group Theory
Tom Kelsey, Steve Linton, and Colva Roney-Dougal
School of Computer Science, University of St Andrews, Fife, Scotland
{
tom,sal,colva
}
@dcs.st-and.ac.uk
Abstract.
Symmetry-breaking in constraint satisfaction problems is a
well-established area of AI research which has recently developed strong
interactions with symbolic computation, in the form of computational
group theory. GE-trees are a new conceptual abstraction, providing low-
degree polynomial time methods for breaking value symmetries in con-
straint satisfication problems. In this paper we analyse the structure
of symmetry groups of constraint satisfaction problems, and implement
several combinations of GE-trees and the classical SBDD method for
breaking all symmetries. We prove the ecacy of our techniques, and
present preliminary experimental evidence of their practical eciency.
1
Introduction
Constraint systems are a generalization of the Boolean satisfiability problems
that play a central role in theoretical computer science. Solving constraint sat-
isfaction problems (CSPs) in general is thus NP-complete; but effective solving
of constraint systems arising from real problems, such as airline scheduling, is of
enormous industrial importance.
There has been a great deal of research interest in dealing with symmetries
in CSPs in recent years. CSPs are often solved using AI search techniques in-
volving backtrack search and propagation. Many approaches to dealing with
symmetries (constraints and/or solutions that are interchangeable in terms of
the structure of the problem) are themselves based on refinements of AI search
techniques. These include imposing some sort of ordering (before search) on oth-
erwise interchangeable elements, posting constraints at backtracks that rule out
search in symmetric parts of the tree, and checking that nodes in the search tree
are not symmetrically equivalent to an already-visited state. These approaches
are collectively known as lexicographic ordering [1], symmetry breaking during
search (SBDS) [2,3], and symmetry breaking by dominance detection (SBDD)
[4,5]. Methods can be, and are, optimised for either finding the first solution or
finding all solutions. In this paper we consider only the problem of finding all
solutions.
A promising recent approach has been to consider the symmetries of a given
CSP as a group of permutations. It then becomes possible to pose and answer
questions about symmetry using computational group theory. In effect, the AI
Search WWH ::
Custom Search