Download as iCal file

Symmetry breaking and operator pruning in classical planning and beyond

By Alexander Shleyfman
Location Bloomfield 424
Advisor(s): Carmel Domshlak
Academic Program: Please choose
Tuesday 11 June 2019, 12:30 - 13:30
The idea of identifying and pruning symmetries while reasoning about automorphisms of the
search spaces has been exploited for quite a while already in model checking, constraint
satisfaction, and planning. However, until the work by Pochter et al. (2011), no empirical
successes in this direction have been reported in the scope of cost-optimal planning. 
In our work, we build upon the framework of Pochter et al. (2011) and extend and improve it to
allow for exploiting strictly larger sets of automorphisms, and thus pruning strictly larger parts
of the search space. Our approach is based on exploiting information about the part of the
transition system that is gradually being revealed by forward search algorithms as A∗. This
information allows us to eliminate the requirement of Pochter et al. from the automorphisms
to stabilize the initial state, a requirement that turns out to be quite constraining in terms of
state-space pruning. We introduce an extension of the BrFS algorithms that preserves their core
properties of completeness and optimality.  We also explored the “heuristic” part of the heuristic
search. Several heuristics families were developed over the years to automatically estimate goal 
distance information from problem descriptions. So far, little work has dealt with how the heuristics 
behave under symmetries. We investigate the symmetry properties of existing heuristics and 
reveal that many of them are invariant under symmetries. Moreover,we show that goal-stable 
automorphism groups can be used to improve informativeness of various "non-symmetric" heuristic 
estimates. For last, we prove that the calculation of group automorphisms for planning tasks is 
GI-hard and discuss the presentation of these groups.