Proceedings

Exploiting Symmetries by Planning for a Descriptive Quotient

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1479-1485.

© 2015 International Joint Conferences on Artificial Intelligence

Abstract

We eliminate symmetry from a problem before searching for a plan. The planning problem with symmetries is decomposed into a set of isomorphic subproblems. One plan is computed for a small planning problem posed by a descriptive quotient, a description of any such subproblem. A concrete plan is synthesized by concatenating instantiations of that one plan for each subproblem. Our approach is sound.

  1. [Amir and Engelhardt, 2003] Eyal Amir and Barbara Engel- hardt. Factored planning. In IJCAI, volume 3, pages 929- 935. Citeseer, 2003.
  2. [Brafman and Domshlak, 2006] Ronen I Brafman and Carmel Domshlak. Factored planning: How, when, and when not. In AAAI, volume 6, pages 809-814, 2006.
  3. [Brown et al., 1996] Cynthia A. Brown, Larry Finkelstein, and Paul Walton Purdom Jr. Backtrack searching in the presence of symmetry. Nord. J. Comput., 3(3):203-219, 1996.
  4. [Clarke et al., 1998] Edmund M Clarke, E Allen Emerson, Somesh Jha, and A Prasad Sistla. Symmetry reductions in model checking. In Computer Aided Verification, pages 147-158. Springer, 1998.
  5. [Crawford et al., 1996] James Crawford, Matthew Ginsberg, Eugene Luks, and Amitabha Roy. Symmetry-breaking predicates for search problems. KR, 96:148-159, 1996.
  6. [de Moura and Bjørner, 2008] Leonardo de Moura and Nikolaj Bjørner. Z3: An efficient SMT solver, 2008.
  7. [Domshlak et al., 2012] Carmel Domshlak, Michael Katz, and Alexander Shleyfman. Enhanced symmetry break- ing in cost-optimal planning as forward search. In ICAPS, 2012.
  8. [Domshlak et al., 2013] Carmel Domshlak, Michael Katz, and Alexander Shleyfman. Symmetry breaking: Satisfic- ing planning and landmark heuristics. In ICAPS, 2013.
  9. [Eugene, 1993] M Eugene. Permutation groups and polynomial-time computation. In Groups and Computa- tion: Workshop on Groups and Computation, October 7- 10, 1991, volume 11, page 139. American Mathematical Soc., 1993.
  10. [Fox and Long, 1999] Maria Fox and Derek Long. The de- tection and exploitation of symmetry in planning prob- lems. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stock- holm, Sweden, July 31 -August 6, 1999. 2 Volumes, 1450 pages, pages 956-961, 1999. IJCAI
  11. [Fox and Long, 2002] Maria Fox and Derek Long. Extend- ing the exploitation of symmetries in planning. In Pro- ceedings of the Sixth International Conference on Arti- ficial Intelligence Planning Systems, April 23-27, 2002, Toulouse, France, pages 83-91, 2002.
  12. [Guere and Alami, 2001] Emmanuel Guere and Rachid Alami. One action is enough to plan. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001, pages 439-444, 2001.
  13. [Helmert et al., 2014] Malte Helmert, Patrik Haslum, Jörg Hoffmann, and Raz Nissim. Merge-and-shrink abstrac- tion: A method for generating lower bounds in factored state spaces. Journal of the ACM (JACM), 61(3):16, 2014.
  14. [Joslin and Roy, 1997] David Joslin and Amitabha Roy. Ex- ploiting symmetry in lifted CSPs. In Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-31, 1997, Provi- dence, Rhode Island., pages 197-202, 1997.
  15. [Kelareva et al., 2007] Elena Kelareva, Olivier Buffet, Jinbo Huang, and Sylvie Thiébaux. Factored planning using de- composition trees. In IJCAI, pages 1942-1947, 2007. IJCAI
  16. [McKay and Piperno, 2014] Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, {II}. Journal of Symbolic Computation, 60(0):94 -112, 2014.
  17. [Miguel, 2001] Ian Miguel. Symmetry-breaking in planning: Schematic constraints. In Proceedings of the CP01 Work- shop on Symmetry in Constraints, pages 17-24, 2001.
  18. [Pochter et al., 2011] Nir Pochter, Aviv Zohar, and Jeffrey S Rosenschein. Exploiting problem symmetries in state- based planners. In AAAI, 2011.
  19. [Porco et al., 2013] Aldo Porco, Alejandro Machado, and Blai Bonet. Automatic reductions from PH into STRIPS or how to generate short problems with very long solutions. In ICAPS, 2013.
  20. [Richter and Westphal, 2010] Silvia Richter and Matthias Westphal. The LAMA planner: Guiding cost-based any- time planning with landmarks. Journal of Artificial Intel- ligence Research, 39(1):127-177, 2010.
  21. [Rintanen and Gretton, 2013] Jussi Rintanen and Charles Gretton. Computing upper bounds on lengths of transition sequences. In IJCAI, 2013. IJCAI
  22. [Rintanen, 2003] Jussi Rintanen. Symmetry reduction for SAT representations of transition systems. In ICAPS, pages 32-41, 2003.
  23. [Shleyfman et al., 2015] Alexander Shleyfman, Michael Katz, Malte Helmert, Silvan Sievers, and Martin Wehrle. Heuristics and symmetries in classical planning. In AAAI, 2015.
  24. [Sievers et al., 2015] Silvan Sievers, Martin Wehrle, Malte Helmert, Alexander Shleyfman, and Michael Katz. Fac- tored symmetries for merge-and-shrink abstractions. In Proc. 29th National Conf. on Artificial Intelligence. AAAI Press, 2015.
  25. [Wahl and Donaldson, 2010] Thomas Wahl and Alastair F. Donaldson. Replication and abstraction: Symmetry in automated formal verification. Symmetry, 2(2):799-847, 2010.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards