סמינר המחלקה להנדסת תעשייה
Symmetry breaking and operator pruning in classical planning
Alexander Shleyfman is a postdoctoral fellow at the Department of Mechanical & Industrial Engineering in the University of Toronto, Ontario, Canada
The Lecture will be held on Tuesday , 17 November 2020, at 14:00
Via Zoom – https://us02web.zoom.us/j/85690788388?pwd=K0d1QlpXWWpMVEo3SHg1WTZSbERDQT...
Abstract: 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. Finally, we prove that the calculation of an automorphism group for a given planning task is GI-complete.
Short biography: Alexander Shleyfman was recently a postdoctoral fellow at the Department of Mechanical & Industrial Engineering in the University of Toronto, Ontario, Canada. Alex completed both his PhD and MSc degrees at the Faculty of Industrial Engineering and Management at the Technion. His current research looks at integration of classical planning and learning techniques into real world application and resource management, as well as in the theoretical properties of such techniques. Prior to being a postdoc at UofT, Alex worked as a course instructor at the Technion, teaching such courses as "Introduction to AI" and "Software Engineering" for the Data Science and Engineering BSc program. While working on his PhD Alex was part of the Adams fellowship program, and received a Wolf Prize for PhD students.
