Homomorphisms and Embeddings of STRIPS Planning Models
Open Access
- 10 December 2024
- journal article
- research article
- Published by Wiley in Computational Intelligence
- Vol. 40 (6)
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 and a sub‐instance of another instance . One application of such a mapping is to efficiently produce a compiled form containing all solutions to from a compiled form containing all solutions to . We also introduce the notion of embedding from an instance to another instance , which allows us to deduce that has no solution‐plan if is unsolvable. In this paper, we study the complexity of these problems. We show that the first is GI‐complete and can thus be solved, in theory, in quasi‐polynomial time. While we prove the remaining problems to be NP‐complete, we propose an algorithm to build an isomorphism when possible. We report extensive experimental trials on benchmark problems that demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition SystemsJournal of Artificial Intelligence Research, 2021
- Computational Complexity of Computing Symmetries in Finite-Domain PlanningJournal of Artificial Intelligence Research, 2021
- Counterexample-Guided Cartesian Abstraction Refinement for Classical PlanningJournal of Artificial Intelligence Research, 2018
- State space search nogood learning: Online refinement of critical-path dead-end detectors in planningArtificial Intelligence, 2017
- A Concise Introduction to Models and Methods for Automated Planning2013
- Macro-FF: Improving AI Planning with Automatically Learned Macro-OperatorsJournal of Artificial Intelligence Research, 2005
- The computational complexity of propositional STRIPS planningArtificial Intelligence, 1994
- Graph isomorphism problemJournal of Mathematical Sciences, 1985
- Consistency in networks of relationsArtificial Intelligence, 1977
- An Algorithm for Subgraph IsomorphismJournal of the ACM, 1976