View Related Documents

Abstract

Many research works on symmetry in CSPs appeared recently. But, most of them deal only with the global symmetry of the studied problem and give no strategy that can be used to detect and eliminate local symmetry. Eliminating global symmetry is shown to be useful, but exploiting only these symmetries could not be sufficient to solve some hard locally symmetrical problems. That is, a problem can have few or no initial symmetries and become very symmetrical at some nodes during the search. In this paper we study a general principle of semantic symmetry and define a syntactic symmetry which is a sufficient condition for semantic symmetry. We define a weakened form of this syntactic symmetry, and show how to detect and how to eliminate it locally to increase CSP tree search methods efficiency. Experiments confirm that local symmetry breaking is profitable for CSP solving.

Fulltext Preview

Image of the first page of the fulltext document