Homomorphisms and Embeddings of STRIPS Planning Models

Arnaud Lequen, Martin C. Cooper, Frédéric Maris·June 24, 2024

Summary

This paper investigates isomorphisms and embeddings in STRIPS planning models, focusing on the complexity of determining if two instances are equivalent or can be embedded within each other. The main points are: 1. Isomorphism detection between identical-sized STRIPS instances is GI-complete, with a quasi-polynomial solution. 2. Subinstance isomorphisms (SSI) are NP-complete, and the paper presents an algorithm using constraint propagation and SAT reduction to identify isomorphisms or prove their absence. 3. Embeddings help infer solvability by showing that an unsolvable instance can be embedded in a larger solvable one, with embeddings being NP-complete to decide. 4. The study highlights the importance of transferring knowledge between planning instances with shared structure, like Rubik's cubes of different sizes. 5. The paper proposes algorithms for detecting isomorphisms and embeddings, with applications in explainable AI and plan compilation. 6. Experiments evaluate the algorithm's performance, showing the benefits of preprocessing for efficiency, even in challenging domains. In conclusion, the research contributes to understanding the complexity of isomorphisms and embeddings in planning, providing tools for analyzing and transferring knowledge between similar tasks, and improving solver efficiency through preprocessing.

Key findings

2

Paper digest

What problem does the paper attempt to solve? Is this a new problem?

The paper addresses the problem of determining isomorphisms between STRIPS planning instances, specifically focusing on finding an isomorphism between a planning instance and a sub-instance of another instance . This problem is not new, as the paper introduces the notions of subinstance isomorphism and embedding, along with associated problems, to study the complexity of these problems . The paper also proposes an algorithm based on constraint propagation techniques and a reduction to SAT to address this problem .


What scientific hypothesis does this paper seek to validate?

This paper aims to validate the scientific hypothesis related to finding an isomorphism between two planning problems and the associated complexity. It introduces the problem of finding an isomorphism between planning problems and demonstrates that it is GI-complete. Additionally, it explores subinstance isomorphism, embedding, and related problems, proving their NP-completeness and proposing a generic algorithm based on constraint propagation techniques and a reduction to SAT . The study also delves into the experimental evaluation of the algorithm, highlighting the efficiency of SAT solvers with traditional constraint propagation and the impact of symmetries on planning instances . Furthermore, the paper discusses the computational complexity of computing symmetries in finite-domain planning and the role of heuristics and symmetries in classical planning .


What new ideas, methods, or models does the paper propose? What are the characteristics and advantages compared to previous methods?

The paper introduces several novel ideas, methods, and models in the field of planning models:

  • Problem SI and Associated Notions: The paper introduces the problem SI, which involves finding an isomorphism between two planning problems, and demonstrates that it is GI-complete. It also introduces subinstance isomorphism, embedding, and associated problems SSI, SSI-H, and SE. The paper proves the NP-completeness of these problems and proposes a generic algorithm based on constraint propagation techniques and reduction to SAT .
  • Experimental Evaluation: The paper conducts an experimental evaluation of the algorithm proposed, showing that traditional constraint propagation in a preprocessing step significantly enhances the efficiency of SAT solvers. The study reveals that planning domains with a significant amount of symmetries may benefit from this approach. The paper highlights the importance of identifying characteristics of problems in NP that are suitable for a hybrid CP-SAT approach .
  • Symmetry Analysis and Abstractions: The paper delves into the study of symmetries in planning problems and the potential benefits of leveraging symmetries to optimize grounding by pruning irrelevant operators through a relaxed reachability analysis. It discusses the use of abstractions to create equivalence classes between states of LTS to build an abstract LTS where desirable properties of the original LTS are preserved. The work also explores the connection between FDR endomorphisms and LTS endomorphisms to remove redundant operators .
  • Compilation Maps and Synthesis of Plans: The paper discusses the concept of storing all solutions to a CSP or SAT instance in a compact compiled form, which can be used to synthesize plans for similar problems. It explores the synthesis of plans for a problem P from a compiled form representing all shortest solution-plans to a similar problem P'. The study emphasizes the importance of finding isomorphisms between subproblems and the implications of embedding unsolvable planning instances into other instances as a proof of unsolvability . The paper introduces novel characteristics and advantages compared to previous methods in planning models:
  • Problem SI and Associated Notions: The paper introduces the problem SI, which involves finding an isomorphism between two planning problems, and demonstrates its GI-completeness. It also introduces subinstance isomorphism, embedding, and associated problems SSI, SSI-H, and SE, proving their NP-completeness. The proposed generic algorithm utilizes constraint propagation techniques and SAT reduction, enhancing efficiency .
  • Symmetry Analysis and Abstractions: The study delves into symmetries in planning problems, optimizing grounding by pruning irrelevant operators through relaxed reachability analysis. It explores abstractions to create equivalence classes between states, preserving desirable properties. The work connects FDR endomorphisms and LTS endomorphisms to eliminate redundant operators, offering a unique approach to symmetry utilization .
  • Compilation Maps and Synthesis of Plans: The paper discusses storing all solutions to a CSP or SAT instance in a compact compiled form for synthesizing plans for similar problems. It explores plan synthesis from compiled forms representing all shortest solution-plans to similar problems. The importance of finding isomorphisms between subproblems and embedding unsolvable planning instances into others as proof of unsolvability is highlighted .

Do any related researches exist? Who are the noteworthy researchers on this topic in this field?What is the key to the solution mentioned in the paper?

Several related researches exist in the field of STRIPS planning models. Noteworthy researchers in this field include J´erˆome Amilhastre, H´el`ene Fargier, Pierre Marquis , Malte Helmert , Rostislav Horˇc´ık, Daniel Fiˇser , Henry A Kautz, Bart Selman , Richard E. Korf , Nir Lipovetzky, Christian J. Muise, Hector Geffner , Alexander Shleyfman, Peter Jonsson , and many others mentioned in the provided contexts.

The key to the solution mentioned in the paper involves determining whether two STRIPS planning instances are isomorphic, which is the simplest form of comparison between planning instances. It also involves finding an isomorphism between a planning instance and a sub-instance of another instance, as well as introducing the notion of embedding from one instance to another. This embedding allows deducing that the target instance has no solution-plan if the source instance is unsolvable . The paper discusses the complexity of these problems, showing that finding an isomorphism is GI-complete and can be solved in quasi-polynomial time, while proposing an algorithm to build an isomorphism when possible .


How were the experiments in the paper designed?

The experiments in the paper were designed to evaluate the efficiency and effectiveness of the algorithm proposed for solving the problems related to finding isomorphisms between planning instances. The experiments aimed to demonstrate the feasibility of finding subinstance isomorphisms and embeddings in the context of planning models . The experiments utilized a set of benchmarks derived from previous International Planning Competitions, including domains like Barman, Blocks, Ferry, Gripper, Hanoi, Rovers, Satellite, Sokoban, TSP, and Visitall. These benchmarks were used to create STRIPS matching instances for evaluation . The experiments focused on solving instances where at least one solution could be found, and the results were reported based on the outcomes of the experiments . The goal of the experiments was to showcase the practical application of the algorithm in finding solutions to planning instances efficiently within a specified time cutoff, using a machine with specific hardware specifications .


What is the dataset used for quantitative evaluation? Is the code open source?

The dataset used for quantitative evaluation in the study is formed from ten sets found in previous International Planning Competitions, including domains like Barman, Blocks, Ferry, Gripper, Hanoi, Rovers, Satellite, Sokoban, TSP, and Visitall . The code, sets of benchmarks, and full results are available online .


Do the experiments and results in the paper provide good support for the scientific hypotheses that need to be verified? Please analyze.

The experiments and results presented in the paper provide strong support for the scientific hypotheses that needed to be verified. The paper introduces the problem of finding isomorphisms between planning instances and demonstrates that it is GI-complete, indicating the theoretical feasibility of solving it in quasi-polynomial time . Additionally, the paper proves the NP-completeness of related problems and proposes an algorithm to construct an isomorphism when possible, showcasing a practical approach to addressing these complex problems . The extensive experimental trials conducted on benchmark problems illustrate that applying constraint propagation in preprocessing significantly enhances the efficiency of SAT solvers, highlighting the effectiveness of the proposed methodology . These findings validate the scientific hypotheses put forth in the paper and demonstrate the robustness of the approach in tackling challenging planning problems.


What are the contributions of this paper?

The paper makes several contributions:

  • It introduces the problem of finding an isomorphism between two planning problems, showing that it is GI-complete, and proposes algorithms for related problems like subinstance isomorphism and embedding .
  • The paper discusses the experimental evaluation of an algorithm based on constraint propagation techniques and SAT reduction, highlighting the efficiency of traditional constraint propagation in improving SAT solver performance .
  • It explores the identification of characteristics of NP problems amenable to a hybrid CP-SAT approach, indicating a promising avenue for future research .
  • The study defines subinstance isomorphism and embedding, establishing distinct partial orders between STRIPS instances, which can help reveal hidden structures in the space of all planning instances .

What work can be continued in depth?

Further research in the field of planning models can be expanded in several directions based on the existing work:

  • Formal Explanations of (Un)solvability: Future research could focus on defining formal explanations of (un)solvability through minimal solvable isomorphic subinstances or minimal unsolvable embedded subinstances .
  • Symmetries in Planning Instances: Exploring the characteristics of problems in NP that make them suitable for a hybrid CP-SAT approach could be an interesting avenue for further investigation .
  • Identification of Problem Characteristics: It remains an open question to identify the specific characteristics of problems in NP that make them amenable to the hybrid CP-SAT approach, which could be a promising area for future research .
  • Hidden Structure in Planning Instances: Defining subinstance isomorphism and embedding as two distinct partial orders between STRIPS instances could help reveal hidden structures in the space of all planning instances, suggesting a potential direction for further exploration .

Introduction
Background
Overview of STRIPS planning models
Importance of isomorphisms and embeddings in planning
Objective
Main research question: Complexity of isomorphism detection and embedding decision
Applications: Explainable AI, plan compilation, and solver efficiency
Complexity Analysis
Isomorphism Detection
GI-Completeness (Identical-Sized Instances)
Proof of GI-completeness
Quasi-polynomial algorithm for isomorphism detection
Subinstance Isomorphisms (SSI)
NP-Completeness
Algorithm using constraint propagation and SAT reduction
Proving isomorphism or absence of isomorphism
Embeddings
Solvability Inference
NP-completeness of deciding embeddings
Embedding as a tool for transferring solvability
Rubik's Cube Analogy
Shared structure between instances and its implications
Algorithms and Techniques
Detection Algorithms
Isomorphism detection algorithm
Embedding detection algorithm
Preprocessing and Efficiency
Importance of preprocessing for improved performance
Challenges and benefits in complex domains
Experimental Evaluation
Performance analysis of the algorithms
Real-world and synthetic domain experiments
Effectiveness of preprocessing on solver efficiency
Conclusion
Summary of main findings
Contributions to planning theory and practice
Future directions and potential applications
Basic info
papers
artificial intelligence
Advanced features
Insights
How difficult is the problem of deciding subinstance isomorphisms (SSI) according to the paper?
What is the complexity of determining if an instance can be embedded within a larger solvable one?
How do isomorphisms and embeddings contribute to the field of explainable AI and plan compilation, as mentioned in the paper?
What is the main complexity result for isomorphism detection in identical-sized STRIPS instances?

Homomorphisms and Embeddings of STRIPS Planning Models

Arnaud Lequen, Martin C. Cooper, Frédéric Maris·June 24, 2024

Summary

This paper investigates isomorphisms and embeddings in STRIPS planning models, focusing on the complexity of determining if two instances are equivalent or can be embedded within each other. The main points are: 1. Isomorphism detection between identical-sized STRIPS instances is GI-complete, with a quasi-polynomial solution. 2. Subinstance isomorphisms (SSI) are NP-complete, and the paper presents an algorithm using constraint propagation and SAT reduction to identify isomorphisms or prove their absence. 3. Embeddings help infer solvability by showing that an unsolvable instance can be embedded in a larger solvable one, with embeddings being NP-complete to decide. 4. The study highlights the importance of transferring knowledge between planning instances with shared structure, like Rubik's cubes of different sizes. 5. The paper proposes algorithms for detecting isomorphisms and embeddings, with applications in explainable AI and plan compilation. 6. Experiments evaluate the algorithm's performance, showing the benefits of preprocessing for efficiency, even in challenging domains. In conclusion, the research contributes to understanding the complexity of isomorphisms and embeddings in planning, providing tools for analyzing and transferring knowledge between similar tasks, and improving solver efficiency through preprocessing.
Mind map
Embedding as a tool for transferring solvability
NP-completeness of deciding embeddings
Proving isomorphism or absence of isomorphism
Algorithm using constraint propagation and SAT reduction
Quasi-polynomial algorithm for isomorphism detection
Proof of GI-completeness
Challenges and benefits in complex domains
Importance of preprocessing for improved performance
Embedding detection algorithm
Isomorphism detection algorithm
Shared structure between instances and its implications
Solvability Inference
NP-Completeness
GI-Completeness (Identical-Sized Instances)
Applications: Explainable AI, plan compilation, and solver efficiency
Main research question: Complexity of isomorphism detection and embedding decision
Importance of isomorphisms and embeddings in planning
Overview of STRIPS planning models
Future directions and potential applications
Contributions to planning theory and practice
Summary of main findings
Effectiveness of preprocessing on solver efficiency
Real-world and synthetic domain experiments
Performance analysis of the algorithms
Preprocessing and Efficiency
Detection Algorithms
Rubik's Cube Analogy
Embeddings
Subinstance Isomorphisms (SSI)
Isomorphism Detection
Objective
Background
Conclusion
Experimental Evaluation
Algorithms and Techniques
Complexity Analysis
Introduction
Outline
Introduction
Background
Overview of STRIPS planning models
Importance of isomorphisms and embeddings in planning
Objective
Main research question: Complexity of isomorphism detection and embedding decision
Applications: Explainable AI, plan compilation, and solver efficiency
Complexity Analysis
Isomorphism Detection
GI-Completeness (Identical-Sized Instances)
Proof of GI-completeness
Quasi-polynomial algorithm for isomorphism detection
Subinstance Isomorphisms (SSI)
NP-Completeness
Algorithm using constraint propagation and SAT reduction
Proving isomorphism or absence of isomorphism
Embeddings
Solvability Inference
NP-completeness of deciding embeddings
Embedding as a tool for transferring solvability
Rubik's Cube Analogy
Shared structure between instances and its implications
Algorithms and Techniques
Detection Algorithms
Isomorphism detection algorithm
Embedding detection algorithm
Preprocessing and Efficiency
Importance of preprocessing for improved performance
Challenges and benefits in complex domains
Experimental Evaluation
Performance analysis of the algorithms
Real-world and synthetic domain experiments
Effectiveness of preprocessing on solver efficiency
Conclusion
Summary of main findings
Contributions to planning theory and practice
Future directions and potential applications
Key findings
2

Paper digest

What problem does the paper attempt to solve? Is this a new problem?

The paper addresses the problem of determining isomorphisms between STRIPS planning instances, specifically focusing on finding an isomorphism between a planning instance and a sub-instance of another instance . This problem is not new, as the paper introduces the notions of subinstance isomorphism and embedding, along with associated problems, to study the complexity of these problems . The paper also proposes an algorithm based on constraint propagation techniques and a reduction to SAT to address this problem .


What scientific hypothesis does this paper seek to validate?

This paper aims to validate the scientific hypothesis related to finding an isomorphism between two planning problems and the associated complexity. It introduces the problem of finding an isomorphism between planning problems and demonstrates that it is GI-complete. Additionally, it explores subinstance isomorphism, embedding, and related problems, proving their NP-completeness and proposing a generic algorithm based on constraint propagation techniques and a reduction to SAT . The study also delves into the experimental evaluation of the algorithm, highlighting the efficiency of SAT solvers with traditional constraint propagation and the impact of symmetries on planning instances . Furthermore, the paper discusses the computational complexity of computing symmetries in finite-domain planning and the role of heuristics and symmetries in classical planning .


What new ideas, methods, or models does the paper propose? What are the characteristics and advantages compared to previous methods?

The paper introduces several novel ideas, methods, and models in the field of planning models:

  • Problem SI and Associated Notions: The paper introduces the problem SI, which involves finding an isomorphism between two planning problems, and demonstrates that it is GI-complete. It also introduces subinstance isomorphism, embedding, and associated problems SSI, SSI-H, and SE. The paper proves the NP-completeness of these problems and proposes a generic algorithm based on constraint propagation techniques and reduction to SAT .
  • Experimental Evaluation: The paper conducts an experimental evaluation of the algorithm proposed, showing that traditional constraint propagation in a preprocessing step significantly enhances the efficiency of SAT solvers. The study reveals that planning domains with a significant amount of symmetries may benefit from this approach. The paper highlights the importance of identifying characteristics of problems in NP that are suitable for a hybrid CP-SAT approach .
  • Symmetry Analysis and Abstractions: The paper delves into the study of symmetries in planning problems and the potential benefits of leveraging symmetries to optimize grounding by pruning irrelevant operators through a relaxed reachability analysis. It discusses the use of abstractions to create equivalence classes between states of LTS to build an abstract LTS where desirable properties of the original LTS are preserved. The work also explores the connection between FDR endomorphisms and LTS endomorphisms to remove redundant operators .
  • Compilation Maps and Synthesis of Plans: The paper discusses the concept of storing all solutions to a CSP or SAT instance in a compact compiled form, which can be used to synthesize plans for similar problems. It explores the synthesis of plans for a problem P from a compiled form representing all shortest solution-plans to a similar problem P'. The study emphasizes the importance of finding isomorphisms between subproblems and the implications of embedding unsolvable planning instances into other instances as a proof of unsolvability . The paper introduces novel characteristics and advantages compared to previous methods in planning models:
  • Problem SI and Associated Notions: The paper introduces the problem SI, which involves finding an isomorphism between two planning problems, and demonstrates its GI-completeness. It also introduces subinstance isomorphism, embedding, and associated problems SSI, SSI-H, and SE, proving their NP-completeness. The proposed generic algorithm utilizes constraint propagation techniques and SAT reduction, enhancing efficiency .
  • Symmetry Analysis and Abstractions: The study delves into symmetries in planning problems, optimizing grounding by pruning irrelevant operators through relaxed reachability analysis. It explores abstractions to create equivalence classes between states, preserving desirable properties. The work connects FDR endomorphisms and LTS endomorphisms to eliminate redundant operators, offering a unique approach to symmetry utilization .
  • Compilation Maps and Synthesis of Plans: The paper discusses storing all solutions to a CSP or SAT instance in a compact compiled form for synthesizing plans for similar problems. It explores plan synthesis from compiled forms representing all shortest solution-plans to similar problems. The importance of finding isomorphisms between subproblems and embedding unsolvable planning instances into others as proof of unsolvability is highlighted .

Do any related researches exist? Who are the noteworthy researchers on this topic in this field?What is the key to the solution mentioned in the paper?

Several related researches exist in the field of STRIPS planning models. Noteworthy researchers in this field include J´erˆome Amilhastre, H´el`ene Fargier, Pierre Marquis , Malte Helmert , Rostislav Horˇc´ık, Daniel Fiˇser , Henry A Kautz, Bart Selman , Richard E. Korf , Nir Lipovetzky, Christian J. Muise, Hector Geffner , Alexander Shleyfman, Peter Jonsson , and many others mentioned in the provided contexts.

The key to the solution mentioned in the paper involves determining whether two STRIPS planning instances are isomorphic, which is the simplest form of comparison between planning instances. It also involves finding an isomorphism between a planning instance and a sub-instance of another instance, as well as introducing the notion of embedding from one instance to another. This embedding allows deducing that the target instance has no solution-plan if the source instance is unsolvable . The paper discusses the complexity of these problems, showing that finding an isomorphism is GI-complete and can be solved in quasi-polynomial time, while proposing an algorithm to build an isomorphism when possible .


How were the experiments in the paper designed?

The experiments in the paper were designed to evaluate the efficiency and effectiveness of the algorithm proposed for solving the problems related to finding isomorphisms between planning instances. The experiments aimed to demonstrate the feasibility of finding subinstance isomorphisms and embeddings in the context of planning models . The experiments utilized a set of benchmarks derived from previous International Planning Competitions, including domains like Barman, Blocks, Ferry, Gripper, Hanoi, Rovers, Satellite, Sokoban, TSP, and Visitall. These benchmarks were used to create STRIPS matching instances for evaluation . The experiments focused on solving instances where at least one solution could be found, and the results were reported based on the outcomes of the experiments . The goal of the experiments was to showcase the practical application of the algorithm in finding solutions to planning instances efficiently within a specified time cutoff, using a machine with specific hardware specifications .


What is the dataset used for quantitative evaluation? Is the code open source?

The dataset used for quantitative evaluation in the study is formed from ten sets found in previous International Planning Competitions, including domains like Barman, Blocks, Ferry, Gripper, Hanoi, Rovers, Satellite, Sokoban, TSP, and Visitall . The code, sets of benchmarks, and full results are available online .


Do the experiments and results in the paper provide good support for the scientific hypotheses that need to be verified? Please analyze.

The experiments and results presented in the paper provide strong support for the scientific hypotheses that needed to be verified. The paper introduces the problem of finding isomorphisms between planning instances and demonstrates that it is GI-complete, indicating the theoretical feasibility of solving it in quasi-polynomial time . Additionally, the paper proves the NP-completeness of related problems and proposes an algorithm to construct an isomorphism when possible, showcasing a practical approach to addressing these complex problems . The extensive experimental trials conducted on benchmark problems illustrate that applying constraint propagation in preprocessing significantly enhances the efficiency of SAT solvers, highlighting the effectiveness of the proposed methodology . These findings validate the scientific hypotheses put forth in the paper and demonstrate the robustness of the approach in tackling challenging planning problems.


What are the contributions of this paper?

The paper makes several contributions:

  • It introduces the problem of finding an isomorphism between two planning problems, showing that it is GI-complete, and proposes algorithms for related problems like subinstance isomorphism and embedding .
  • The paper discusses the experimental evaluation of an algorithm based on constraint propagation techniques and SAT reduction, highlighting the efficiency of traditional constraint propagation in improving SAT solver performance .
  • It explores the identification of characteristics of NP problems amenable to a hybrid CP-SAT approach, indicating a promising avenue for future research .
  • The study defines subinstance isomorphism and embedding, establishing distinct partial orders between STRIPS instances, which can help reveal hidden structures in the space of all planning instances .

What work can be continued in depth?

Further research in the field of planning models can be expanded in several directions based on the existing work:

  • Formal Explanations of (Un)solvability: Future research could focus on defining formal explanations of (un)solvability through minimal solvable isomorphic subinstances or minimal unsolvable embedded subinstances .
  • Symmetries in Planning Instances: Exploring the characteristics of problems in NP that make them suitable for a hybrid CP-SAT approach could be an interesting avenue for further investigation .
  • Identification of Problem Characteristics: It remains an open question to identify the specific characteristics of problems in NP that make them amenable to the hybrid CP-SAT approach, which could be a promising area for future research .
  • Hidden Structure in Planning Instances: Defining subinstance isomorphism and embedding as two distinct partial orders between STRIPS instances could help reveal hidden structures in the space of all planning instances, suggesting a potential direction for further exploration .
Scan the QR code to ask more questions about the paper
© 2025 Powerdrill. All rights reserved.