Document Open Access Logo

Isomorphisms Between STRIPS Problems and Sub-Problems

Authors Martin C. Cooper , Arnaud Lequen , Frédéric Maris

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.13.pdf
  • Filesize: 0.82 MB
  • 16 pages

Document Identifiers

Author Details

Martin C. Cooper
  • IRIT, University of Toulouse, France
Arnaud Lequen
  • IRIT, University of Toulouse, France
Frédéric Maris
  • IRIT, University of Toulouse, France

Funding

This work was supported by the AI Interdisciplinary Institute ANITI, funded by the French program "Investing for the Future – PIA3" under Grant agreement no. ANR-19-PI3A-0004.

Acknowledgements

The authors would like to thank the anonymous reviewers, whose insightful comments helped improve this paper.

Cite As Get BibTex

Martin C. Cooper, Arnaud Lequen, and Frédéric Maris. Isomorphisms Between STRIPS Problems and Sub-Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CP.2022.13

Abstract

Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance P and a sub-instance of another instance P'. One application of such an isomorphism is to efficiently produce a compiled form containing all solutions to P from a compiled form containing all solutions to P'. In this paper, we study the complexity of both problems. We show that the former is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the latter to be NP-complete, we propose an algorithm to build an isomorphism, when possible. We report extensive experimental trials on benchmark problems which demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning for deterministic actions
  • Mathematics of computing → Matchings and factors
Keywords
  • planning
  • isomorphism
  • complexity
  • constraint propagation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Jérôme Amilhastre, Hélène Fargier, and Pierre Marquis. Consistency restoration and explanations in dynamic csps application to configuration. Artif. Intell., 135(1-2):199-234, 2002. URL: https://doi.org/10.1016/S0004-3702(01)00162-X.
  2. László Babai. Group, graphs, algorithms: the graph isomorphism problem. In Proceedings of the International Congress of Mathematicians, pages 3319-3336. World Scientific, 2018. Google Scholar
  3. Djamila Baroudi, Maël Valais, and Frédéric Maris. Touistplan. URL: https://github.com/touist/touistplan.
  4. Tom Bylander. The computational complexity of propositional strips planning. Artificial Intelligence, 69(1-2):165-204, 1994. Google Scholar
  5. Stephen A. Cook. The complexity of theorem-proving procedures. In Michael A. Harrison, Ranan B. Banerji, and Jeffrey D. Ullman, editors, 3rd Annual ACM Symposium on Theory of Computing, pages 151-158. ACM, 1971. URL: https://doi.org/10.1145/800157.805047.
  6. Adnan Darwiche and Pierre Marquis. A knowledge compilation map. J. Artif. Intell. Res., 17:229-264, 2002. URL: https://doi.org/10.1613/jair.989.
  7. Richard Fikes and Nils J. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artif. Intell., 2(3/4):189-208, 1971. URL: https://doi.org/10.1016/0004-3702(71)90010-5.
  8. Malte Helmert. Complexity results for standard benchmark domains in planning. Artificial Intelligence, 143(2):219-262, 2003. URL: https://doi.org/10.1016/S0004-3702(02)00364-8.
  9. Henry A. Kautz and Bart Selman. Planning as satisfiability. In Bernd Neumann, editor, ECAI 92, pages 359-363. John Wiley and Sons, 1992. Google Scholar
  10. Songtuan Lin and Pascal Bercher. Change the world - how hard can that be? On the computational complexity of fixing planning models. In Zhi-Hua Zhou, editor, IJCAI-21, pages 4152-4159, August 2021. URL: https://doi.org/10.24963/ijcai.2021/571.
  11. Mao Luo, Chu-Min Li, Fan Xiao, Felip Manyà, and Zhipeng Lü. An effective learnt clause minimization approach for cdcl sat solvers. In IJCAI-17, pages 703-711, 2017. URL: https://doi.org/10.24963/ijcai.2017/98.
  12. Alan K Mackworth. Consistency in networks of relations. Artificial intelligence, 8(1):99-118, 1977. Google Scholar
  13. Peter Nightingale, Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, and Patrick Spracklen. Automatically improving constraint models in savile row. Artif. Intell., 251:35-61, 2017. URL: https://doi.org/10.1016/j.artint.2017.07.001.
  14. Francesca Rossi, Peter Van Beek, and Toby Walsh. Handbook of Constraint Programming. Elsevier, 2006. Google Scholar
  15. Viktor N Zemlyachenko, Nickolay M Korneenko, and Regina I Tyshkevich. Graph isomorphism problem. Journal of Soviet Mathematics, 29(4):1426-1481, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact