Enhanced Symmetry Breaking in Cost-Optimal Planning as Forward Search

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Volume

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Short Papers

In heuristic search planning, state-space symmetries are mostly ignored by both the search algorithm and the heuristic guidance. Recently, Pochter, Zohar, and Rosenschein (2011) introduced an effective framework for detecting and accounting for state symmetries within A∗ cost-optimal planning. We extend this framework to allow for exploiting strictly larger symmetry classes, 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 A∗. An extensive empirical evaluation shows that our approach allows for substantial reductions in search effort overall, and in particular, allows for more problems being solved.

10.1609/icaps.v22i1.13531