Symmetry Breaking in Automated Planning
This is my master thes about exploiting structures in automated planning (through symmetry breaking). You can read it here: Exploiting structures in automated planning. The domains and problems, that were used for testing, are here: Domains.
Several ways of symmetry breaking have been proposed for automated planning in the past. I decided to propose a new set of definitions, which may give a new look at the problem of symmetries in automated planning.
I focused at the relational representation of a planning problem, i.e. the representation, where the state is a set of atoms of specific predicates. Such state can be also viewed as a set of relations, when atoms are "grouped together" by their predicates. This is quite natural way of analyzing a planning problem, since it resembles the PDDL format.
It is shown, that symmetries can be generated by automorphisms of a relational state. Detecting such automorphisms is the key to pruning the state-space search. Instead of making a general automorphism detection, I present a simple algorithm for detecting a specific class T1 (subgroup of the group of automorphisms), which is very frequent in many planning domains. A simple state-space search algorithm can be extended by this method and improve the performance.
At the end, I showed, that such symmetry breaking is less general than Orbit Search, i.e. every relational symmetry, that is generated by a relational automorphism, is also a symmetry of the "standard" SAS+ representation of the same problem and can be detected by algorithms based on the Orbit Search. In my experiments, the Metis planner (based on Orbit Search) always visits the smaller number of states than my experimental planner PLANR. Despite this, PLANR is sometimes faster than Metis.