Exploiting Problem Symmetries in State-Based Planners

Authors

  • Nir Pochter The Hebrew University of Jerusalem
  • Aviv Zohar Microsoft Research, Silicon Valley
  • Jeffrey Rosenschein The Hebrew University of Jerusalem

Abstract

Previous research in Artificial Intelligence has identified the possibility of simplifying planning problems via the identification and exploitation of symmetries. We advance the state of the art in algorithms that exploit symmetry in planning problems by generalizing previous approaches, and applying symmetry reductions to state-based planners. We suggest several algorithms for symmetry exploitation in state-based search, but also provide a comprehensive view through which additional algorithms can be developed and fine-tuned. We evaluate our approach to symmetry exploitation on instances from previous planning competitions, and demonstrate that our algorithms significantly improve the solution time of instances with symmetries.

Downloads

Published

2011-08-04

How to Cite

Pochter, N., Zohar, A., & Rosenschein, J. (2011). Exploiting Problem Symmetries in State-Based Planners. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1004-1009. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/8014

Issue

Section

Reasoning about Plans, Processes and Actions