Symmetry
Human artifacts from chess boards to airplanes exhibit
symmetries. From the highly regular patterns of circuitry on a
microchip, to the interchangeable pistons in a car engine, or seats in
a commercial aircraft, we are drawn aesthetically and organizationally
to symmetric designs. Part of the appeal of regular or symmetric
designs is that they allows us to reason about and understand larger and
more complex structures than we could otherwise handle. It follows
that if we are to build computer systems that configure, schedule,
diagnose, or otherwise reason about human artifacts, we need to endow
these reasoning systems with the ability to exploit structure in
general and symmetries in particular.
CIRL
CIRL has developed algorithms that detect symmetries in optimization
problems, and compile these symmetries into axioms that restrict the
search. These "symmetry breaking" axioms are not sound deductions
from the constraints in the problem, but do have the property that
they neither increase or decrease the optimal value of the objective
function.
Pointers
-
Exploiting Symmetry in Lifted CSPs
-
Previous work has show how to exploit symmetries in propositional
encodings of constraint satisfaction problems. In this paper,
problems in more compact lifted (quantified) descriptions are
considered. By David Joslin and Amitabha Roy. It appeared in
Proc. AAAI in 1997. Compressed Postscript document.
-
Symmetry Breaking Predicates for Search Problems
-
Many reasoning and optimization problems exhibit symmetries. In
this paper, a general scheme whereby symmetries are exploited by
adding "symmetry-breaking" predicates to the theory is presented.
The new theory is then solved and experimental results show that in
at least two problems, the symmetry-breaking predicates help in
solving the problem faster. By James Crawford, Gene Luks, Matt
Ginsberg, and Amitabha Roy. It appeared in Proc. KR in 1996.
Postscript document.
- Parent areas:
- Solution structure
Back to the CIRL Overview Page.