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_0$ . One application of
such a mapping is to efficiently produce a compiled form containing all
solutions to P from a compiled form containing all solutions to $P_0$. We also
introduce the notion of embedding from an instance $P$ to another instance
$P_0$, which allows us to deduce that $P_0$ has no solution-plan if $P$ 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 which demonstrate
conclusively that applying constraint propagation in preprocessing can greatly
improve the efficiency of a SAT solver.

研究了 STRIPS 规划实例之间的同构性，引入了嵌入的概念，并研究了相关问题的复杂性，证明了第一个问题是 GI-complete 的，提出了一种构建同构的算法，并通过实验表明预处理中应用约束传播可以大大提高 SAT 求解器的效率。