License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.13
URN: urn:nbn:de:0030-drops-166426
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16642/
Go to the corresponding LIPIcs Volume Portal

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

Isomorphisms Between STRIPS Problems and Sub-Problems

pdf-format:
LIPIcs-CP-2022-13.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{cooper_et_al:LIPIcs.CP.2022.13,
  author =	{Cooper, Martin C. and Lequen, Arnaud and Maris, Fr\'{e}d\'{e}ric},
  title =	{{Isomorphisms Between STRIPS Problems and Sub-Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16642},
  URN =		{urn:nbn:de:0030-drops-166426},
  doi =		{10.4230/LIPIcs.CP.2022.13},
  annote =	{Keywords: planning, isomorphism, complexity, constraint propagation}
}

Keywords: planning, isomorphism, complexity, constraint propagation
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022
Supplementary Material: The material to reproduce the experiments can be found here:
Software (Source Code): https://github.com/arnaudlequen/PDDLIsomorphismFinder

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI