# endomorphisms_of_classical_planning_tasks__32a2c102.pdf Endomorphisms of Classical Planning Tasks Rostislav Horˇc ık1, Daniel Fiˇser1,2 1 Czech Technical University in Prague, Faculty of Electrical Engineering, Prague, Czech Republic 2 Saarland University, Saarland Informatics Campus, Saarbr ucken, Germany xhorcik@fel.cvut.cz, danfis@danfis.cz Detection of redundant operators that can be safely removed from the planning task is an essential technique allowing to greatly improve performance of planners. In this paper, we employ structure-preserving maps on labeled transition systems (LTSs), namely endomorphisms that are well known from model theory, in order to detect redundancy. Computing endomorphisms of an LTS induced by a planning task is typically infeasible, so we show how to compute some of them on concise representations of planning tasks such as finite domain representations and factored LTSs. We formulate the computation of endomorphisms as a constraint satisfaction problem (CSP) that can be solved by an off-the-shelf CSP solver. Finally, we experimentally verify that the proposed method can find a sizable number of redundant operators on the standard benchmark set. Introduction One way to improve performance of classical planners (regardless of the employed planning technique) is by reducing the size of the input planning task by removing operators and facts so that at least one (optimal) plan is preserved. The most commonly used method for the reduction of planning tasks is a reachability analysis in forward and backward direction using hm heuristics (Haslum and Geffner 2000; Alc azar and Torralba 2015). This method prunes operators that are either unreachable or that lead to a dead-end state. Nevertheless, even if we successfully remove all unreachable and dead-end operators, the remaining planning task may still be unnecessarily large because of many alternative plans it may contain. Recently, Fiˇser, Torralba, and Shleyfman (2019) proposed a technique combining so-called operator mutexes (op-mutexes) and symmetries in such a way that allows to identify operators that are redundant in a sense that removing them still preserves at least one (optimal) plan. The main idea behind this technique is based on the observation that if two operators cannot occur simultaneously in an optimal plan and there is a symmetry mapping one operator to another, then one of the operators can be safely removed. This method works only on planning tasks exhibiting non-trivial symmetries. Copyright c 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Figure 1: Examples of transition systems with redundant states. The dashed arrows show where to map redundant states. In this paper, we develop a new pruning method allowing to detect redundant parts of the state space which cannot be detected by a reachability analysis. Although it can, in some cases, detect the same redundant operators as the method based on op-mutexes and symmetries, our method does not depend on the existence of symmetries. Consider a simple transition system depicted in Fig. 1 (left) where the cost of o1 and o2 is less than the cost of o3 and o4, respectively, and o5 has a unit cost. It is obvious that the plan going through the state s2 is sub-optimal and we can safely omit the state s2 and operators o3 and o4. However, the transition system has no symmetries due to different costs of actions and the operator o5. Moreover, all states are reachable and there are no dead-ends. Our solution to detect such a redundancy is to look for a structure-preserving self-map on the transition system which maps plans to (possibly cheaper) plans. In the situation described above, such mapping could map the state s2 to s1, o3 to o1, o4 to o2, and fix the remaining states and operators. More precisely, since transition systems can be understood as first-order structures, we just employ standard structure-preserving maps from model theory, namely homomorphisms (see, e.g., Hodges 1997). In particular, we are interested in endomorphisms which are homomorphisms having the same domain and co-domain. It is well known that homomorphisms preserve existential-positive formulas (e.g. Hodges 1997, Section 2.4). As the existence of a plan of a certain length can be expressed by such a formula, it follows that an endomorphism maps plans to plans. Consequently, if we find an endomorphism whose image is strictly smaller than the original transition system, then the states and operators which are not in its image are necessarily redundant. The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21) Another example depicted in Fig. 1 (right) shows a transition system having no non-trivial symmetries due to the operator o5 and the goal state. Moreover, all states are reachable and there are no dead-ends. Still, the state s1 and operators o1, o2 are redundant. However, there is an endomorphism mapping s1 to s2 and operators o1, o2 to o3, o4, respectively, provided o3 (resp. o4) is not more expensive than o1 (resp. o2). The endomorphisms are closely related to symmetries of transition systems. Unlike the symmetries, the endomorphisms need not be bijective. Note that none of the endomorphisms shown in Fig. 1 is bijective. Once we know we look for endomorphisms, the necessary second step is to describe algorithms computing them. Since classical planning tasks are described in concise representations and it is infeasible to construct their whole state space, we cannot hope for computing all existing endomorphisms. However, we can find at least some of them on concise representations. We propose two methods. The first one uses a set of abstract transition systems (e.g., projections) whose synchronized product is the whole state space. The second method uses the finite domain representation. In both methods, the actual endomorphisms are expressed as solutions to a constraint satisfaction problem (CSP) and solved by a standard CSP solver. The computation itself can be seen as constraint optimization because some of the solutions are better than others. An FDR planning task Π is specified by a tuple Π = V, O, I, G . V is a finite set of variables, each variable V V has a finite domain dom(V ). A fact V, v is a pair of a variable V V and one of its values v dom(V ). The set of all facts is denoted by F = { V, v | V V, v dom(V )}, and the set of facts of variable V is denoted by FV = { V, v | v dom(V )}. A partial state p is a variable assignment over some variables vars(p) V. We write p[V ] for the value assigned to the variable V vars(p) in the partial state p. We also identify p with the set of facts contained in p, i.e., p = { V, p[V ] | V vars(p)}. A partial state s is a state if vars(s) = V. I is an initial state. G is a partial state called goal, and a state s is a goal state iff G s. The set of all states is denoted by SΠ. O is a finite set of operators, each operator o O has a precondition pre(o) and effect eff(o), which are partial states over V, and a cost c(o) R+ 0 . An operator o is applicable in a state s iff pre(o) s. The resulting state of applying an applicable operator o in a state s is another state o Js K such that o Js K[V ] = eff(o)[V ] for every V vars(eff(o)), and o Js K[V ] = s[V ] for every V V \ vars(eff(o)). A sequence of operators π = o1, . . . , on is applicable in a state s0 if there are states s1, . . . , sn such that oi is applicable in si 1 and si = oi Jsi 1K for i {1, . . . , n}. The resulting state of this application is πJs0K = sn and c(π) = Pn i=1 c(oi) denotes the cost of this sequence of operators. A sequence of operators π is called a plan iff π is applicable in I and πJs K is a goal state, π is called an opti- mal plan if its cost is minimal among all plans. A labeled transition system (LTS) is a tuple Θ = S, L, T , s I, S , where S is a finite set of states, L is a finite set of labels with associated cost c(l) R+ 0 to each label l L, T S L S is a set of transitions, s I S is the initial state, and S S is a set of goal states. We write s l s to refer to a transition from s to s with the label l. A sequence of labels π = l1, . . . , ln is called a plan in Θ if there exist si 1 li si T for every i {1, . . . , n} such that s0 = s I and sn S . The cost of the plan π is c(π) = Pn i=1 c(li). A plan π is called optimal plan if the cost of π is minimal among all plans. The state space of a planning task Π = V, O, I, G is the LTS ΘΠ = S, L, T , s I, S , where S := SΠ, s I := I, s S iff G s, the labels L are the operators O with the given costs, and s o s is a transition in T if o is applicable in s and o Js K = s . Given two transition systems Θ = S, L, T , s I, S and Θ = S , L, T , s I, S with a common set of labels L, a synchronized product of Θ and Θ is another transition system Θ Θ = S , L, T , s I , S , where S = S S , s I = s I, s I , S = S S , and T = { s, s , l, t, t | s, l, t T , s , l, t T }. A factored LTS of a planning task Π = V, O, I, G is a tuple Θ1, . . . , Θn of LTSs (also called factors) with a common set of labels such that Θ1 Θn = ΘΠ. Let V = {V1, . . . , Vn} denote the set of variables of Π. An atomic factored LTS ΘV1, . . . , ΘVn is a factored LTS where ΘVi, for every i {1, . . . , n}, is an atomic projection of Π to the variable Vi, i.e., ΘVi = S, L, T , s I, S , where S = dom(Vi); L = O; s I = I[Vi]; S = {G[Vi]} if Vi vars(G) or S = S otherwise; and the set of transitions T consists of transitions s o t for the state s = pre(o)[Vi] if Vi vars(pre(o)) or s dom(Vi) otherwise, and for the state t = eff(o)[Vi] if Vi vars(eff(o)) or t = s otherwise. We have to also recall the Constraint Satisfaction Problem (CSP) (for details see, e.g., Russell and Norvig 2010, Chapter 6). Suppose we are given a set X of variables, a finite domain D where the variables can take values, and a set of constraints C. The problem is whether there exists an assignment h: X D of values D to variables X that satisfies all the constraints. Each constraint C C is specified as a pair C = x, R where x is a tuple of variables from X of length n, and R is an n-ary relation on D. The assignment h satisfies the constraint C = x, R if h( x) R. CSPs are often formulated in such a way that each variable x X has its domain of allowed values Dx D. Note that each such restriction can be equivalently expressed as a unary constraint x , Dx . For notational convenience, we will sometimes abuse the notation for sequences by referring to a sequence as a set. Endomorphisms of Transition Systems Labeled transition systems can be viewed as first-order relational structures used in logic and model theory. More precisely, given an LTS Θ = S, L, T , s I, S , one can simply understand Θ as a first-order structure defined on S L endowed with unary predicates defining states and labels, a ternary relation T , a constant s I, and unary predicate S . The following definition is nothing else than the usual definition of homomorphism used in model theory (see, e.g., Hodges 1997; Libkin 2004).1 Definition 1. Let Θ = S, L, T , s I, S and Θ = S , L , T , s I, S denote two LTSs. A mapping α: S L S L is an LTS homomorphism from Θ to Θ if the following conditions are satisfied: (L1) α(s) S for every s S, and (L2) α(l) L for every l L, and (L3) α(s) α(l) α(s ) T for every s l s T , and (L4) c(α(l)) c(l) for every l L, and (L5) α(s I) = s I, and (L6) α(s) S for every s S . An LTS homomorphism from Θ to Θ is called an LTS endomorphism of Θ. For notational convenience, we extend the mapping α to sequences α( x1, . . . , xn ) = α(x1), . . . , α(xn) and sets α({x1, . . . , xn}) = {α(x1), . . . , α(xn)}. A bijective LTS homomorphism α whose inverse is an LTS homomorphism as well is called an LTS isomorphism. If, in addition, α is an LTS endomorphism then α is called an LTS automorphism. Note that LTS automorphisms are structural symmetries stabilized for the initial state and goals as described by Shleyfman et al. (2015). Homomorphisms are important because they preserve existential-positive formulas. In fact, every formula preserved by homomorphisms on all finite structures is equivalent to an existential-positive formula (see Rossman 2008). Consequently, they have to preserve plans. Thus the following theorem follows immediately but we provide an elementary proof for the sake of the reader. Theorem 2. Let α denote an LTS endomorphism of Θ. If π is a plan in Θ, then α(π) is a plan in Θ. Proof. Let Θ = S, L, T , s I, S and let π = s0 l1 s1 l2 ln 1 sn 1 ln sn, where s0 = s I and sn S . It follows directly from Definition 1 that (L5) s0 = s I = α(s I) = α(s0), and (L6) sn S implies α(sn) S , and (L3) si 1 li si T implies α(si 1) α(li) α(si) T for every i {1, . . . , n}. Therefore, α(π) is a plan in Θ. Corollary 3. Let α denote an LTS endomorphism of Θ. If π is an optimal plan in Θ, then α(π) is an optimal plan in Θ. Proof. It follows from (L4) that c(π) c(α(π)). Since c(π) is minimal among all plans, it follows that c(π) = c(α(π)). The rest follows from Theorem 2. 1The only subtlety is hidden in the cost function. One can regard it as a sort of fuzzy predicate which has to be preserved by the homomorphism like other crisp predicates. Alternatively, it is possible to encode the condition (L4) as preservation of unary predicates Cl = {l L | c(l ) c(l)} for each label l. Note that the condition (L4) is required only for the preservation of optimal plans. So, it is possible to weaken the definition of LTS endomorphisms by removing this condition, which could be useful for satisficing planning where we are interested in any plans and not necessarily in the optimal ones. However, we leave this for future work. The fact that LTS endomorphisms preserve (optimal) plans means that once we have an endomorphism α of an LTS, we can prune the planning task by keeping only its image {α(x) | x S L} and throwing away everything else. Formally, we define redundant labels as labels that can be removed as long as there is at least one optimal plan left. Definition 4. Let Θ denote an LTS with labels L, and let X L denote a set of labels. We say that X is redundant in Θ if there exists an optimal plan π in Θ such that π X = . Theorem 5. Let α denote an LTS endomorphism of Θ with labels L. Then X = {l L | l L : α(l ) = l} is redundant in Θ. Proof. It follows from Corollary 3 that for every optimal plan π such that π X = it holds that α(π) is also an optimal plan. And from the definition of X it follows that α(π) X = . In practice, we would like to find the largest possible set of redundant labels, which means that we would like to find an LTS endomorphism with the smallest image. Interestingly, the smallest image is unique (up to an isomorphism) and it is called a core of the structure. This notion originally comes from graph theory (Hell and Neˇsetˇril 1992), but it turned out that it works also for finite relational structures (e.g., Rossman 2008). The only endomorphisms of the core are automorphisms. Therefore, in theory, there is a unique optimal endomorphism. Unfortunately, it is an NP-complete problem to test whether a finite structure is a core or not. Nevertheless, any non-trivial endomorphism (i.e., endomorphism whose image is smaller than its preimage) allows to prune the LTS. Now we have come to the question of how to actually compute endomorphisms of an LTS. It is well known that homomorphisms between finite first-order structures can be viewed as solutions to a CSP (e.g., Libkin 2004, Section 14.3). For the case of LTSs the CSP formulation has two kinds of variables: a variable Xs for every state s S, and a variable Xl for every label l L. The constraints directly corresponds to the conditions (L1) (L6) from Definition 1. The domain of each Xs is the set of states (L1), and the domain of Xl is the set of all labels whose cost is less than or equal to c(l) (L2, L4). There is a constraint Xs I , {s I} for the initial state s I (L5), and Xs G , S for every goal state s G S (L6). Finally, there is a constraint Xs, Xl, Xt , T for each transition s l t (L3). A solution to such CSP with the minimum number of values assigned to the label variables Xl allows to prune the largest possible amount of labels. Of course, the above formulation is not practical because we would need to construct the whole state space (LTS) in order to construct the CSP formulation. However, we show in the next section that we can use a similar approach on factored transition systems. Endomorphisms of Factored LTSs We start by showing that endomorphisms of multiple LTSs naturally extend over their synchronized product as long as the mapping of labels is the same for all LTSs. Definition 6. Given two sets of states S and S , a set of labels L, and two mappings α: S L S L and α : S L S L such that α(l) = α (l) for every l L, β = α α denotes a new mapping β : (S S ) L (S S ) L such that β(l) = α(l) = α (l) for every l L and β(s, s ) = α(s), α (s ) for every s S and every s S . Theorem 7. Let Θ = S, L, T , s I, S , and Θ = S , L, T , s I, S denote two LTSs with a common set of labels, and let α and α denote LTS endomorphisms of Θ and Θ , respectively. If α(l) = α (l) for every l L, then β = α α is an LTS endomorphism of Θ Θ . Proof. (L1), (L2) and (L4 6) follow trivially from the construction of β and Θ Θ . For (L3), let s, s l t, t be a transition in Θ Θ . By the definition of transitions in Θ Θ , we have s l t in Θ and s l t in Θ . Thus α(s) α(l) α(t) T and similarly α (s ) α(l) α (t ) T as α(l) = α (l). By Definition 6 we have β(s, s ) = α(s), α (s ) , β(t, t ) = α(t), α (t ) , and β(l) = α(l). Hence β(s, s ) β(l) β(t, t ) is a transition in Θ Θ . Let Θ1, . . . , Θn denote a factored LTS of a planning task Π. It follows from Theorem 7 that if we find an LTS endomorphism αi for each individual factor Θi and all these endomorphisms agree on the common set of labels, then α1 αn is an LTS endomorphism of the whole state space ΘΠ (i.e., Θ1 Θn). Therefore, we can use this mapping for the inference of redundant labels (operators) according to Theorem 5. The construction of CSP for the factored LTS follows the same construction laid out in the previous section: Each factor Θi is encoded individually, but all encodings for all factors share the same set of variables for labels. This way, every solution to such CSP will produce the same mapping over the set of labels in all factors. The size of the resulting CSP is polynomial in the size of the factored LTS. Assume we have F many factors each having at most M states, i.e., for an atomic factored LTS F = |V|, and M is the size of the largest domain. Since LTSs corresponding to planning problems are deterministic, each label l can induce at most M many transitions on each factor. So there are at most |L| M F transitions to be encoded into constraints. Moreover, there are at most |L| M admissible triples of values for each such constraint. Thus the size of constraints encoding the condition (L3) is bounded by 3 |L|2 M 2 F. The sizes of all other constraints are negligible in comparison to (L3). Example 8. Fig. 2 shows an example of a planning task. It is easy to see that the factor ΘV1 has an endomorphism α such that α(v1) = α(v2) = α(v3) = v3, α(o1) = O pre(o) eff(o) o1 V1=v0, V2=va V1=v1, V2=vb o2 V1=v0, V2=va V1=v2, V2=vc o3 V1=v0 V1=v3 p1 V1=v1, V2=vb V1=v4, V2=va p2 V1=v2, V2=vb V1=v4, V2=va p3 V1=v3 V1=v4 V = {V1, V2} dom(V1) = {v0, v1, v2, v3, v4} dom(V2) = {va, vb, vc} I = {V1=v0, V2=va} G = {V1=v4} ΘV1 : ΘV2 : v0 o3, p3 o3, p3 Figure 2: Example planning task with atomic factored LTS ΘV1, ΘV2 . All operators have a unit cost. α(o2) = α(o3) = o3, α(p1) = α(p2) = α(p3) = p3, and α(v0) = v0 and α(v4) = v4. The factor ΘV2 has an endomorphism α such that α (o) = α(o) for all operators o {o1, o2, o3, p1, p2, p3} and α (vb) = α (vc) = α (va) = va. By Theorem 7, α α is an endomorphism on the synchronized product of both factors. Therefore, the labels (operators) o1, o2, p1, p2 are redundant by Theorem 5. Endomorphisms of Finite Domain Representations The size of the CSP formulation for the factored LTSs can be still computationally prohibitive in practice, because the number of transitions even on relatively small factors may be too large. In this section, we define endomorphisms directly on FDR and show how to formulate a CSP for finding such endomorphisms that is smaller than the CSP for the endomorphisms of the corresponding atomic factored LTS. The price for the smaller CSP is that there can be solutions to the CSP for the atomic factored LTS that are not FDR endomorphisms. Definition 9. Let Π = V, O, I, G be an FDR planning task with facts F. A mapping φ: F O F O is an FDR endomorphism of Π if the following conditions are satisfied2: (F1) φ(FV ) FV for every V V, and (F2) φ(O) O, and (F3) φ(pre(o)) pre(φ(o)) for every o O, and (F4) φ(eff(o)) = eff(φ(o)) for every o O, and (F5) c(φ(o)) c(o) for every o O, and (F6) φ(I) = I, and (F7) φ(G) = G. Theorem 10. Every FDR endomorphism of Π induces an LTS endomorphism of ΘΠ. Proof. Let φ denote an FDR endomorphism of Π. Note that each fact can be mapped only to facts from the same variable (F1). Therefore, vars(p) = vars(φ(p)) holds for every 2As in the case of the LTS endomorphism, we extend φ to sequences and sets. In particular, we can apply φ to partial states. (partial) state p. So, it is easy to see that φ(s) SΠ for every state s (so (L1) holds); and the initial state is preserved (L5); and the goal states are preserved (L6). It is also easy to see that (L2) and (L4) hold because φ maps operators to operators (F2) with possibly smaller costs (F5). What remains to show is that the conditions (F3) and (F4) preserve transitions within ΘΠ (L3). Let s o o Js K denote a transition in ΘΠ. Now, we need to show that φ(s) φ(o) φ(o Js K) is also a transition in ΘΠ. We already showed that φ(s), φ(o Js K) SΠ and φ(o) O, so what remains to show is that (i) φ(o) is applicable in φ(s) and (ii) φ(o)Jφ(s)K = φ(o Js K). By the definition of transitions in ΘΠ we have pre(o) s, and from (F3) we have pre(φ(o)) φ(pre(o)) φ(s). Therefore, φ(o) is applicable in φ(s). For (ii), note that vars(eff(o)) = vars(φ(eff(o))) = vars(eff(φ(o))). Further observe that p[V ] = p [V ] implies φ(p)[V ] = φ(p )[V ] for any partial states p, p and any variable V V. Therefore, for every V vars(eff(o)) it holds that φ(o Js K)[V ] = φ(eff(o))[V ] = eff(φ(o))[V ] = φ(o)Jφ(s)K[V ], and for every V V \ vars(eff(o)) it holds that φ(o Js K)[V ] = φ(s)[V ] = φ(o)Jφ(s)K[V ]. Each FDR endomorphism induces endomorphisms on its respective variable projections and all these endomorphisms agree on labels. So, every FDR endomorphism is an endomorphism of the atomic factored LTS of the same FDR planning task. On the other hand, there are endomorphisms of the atomic factored LTS that are not FDR endomorphisms. Example 11. In the example planning task in Fig. 2, there is an FDR endomorphism φ such that φ(o2) = o1, φ(p2) = p1, φ(v2) = v1, and φ(vc) = vb (the rest of the mapping is identity, i.e., φ(x) = x for x {o2, p2, v2, vc}). Note that in the definition of φ we tacitly identified facts with their values, e.g. V1, v2 was identified with v2. Therefore, the operators (labels) o2, p2 are redundant. However, the LTS endomorphism α α from Example 8 is not an FDR endomorphism. For instance, we cannot map o1 to o3 because vars(eff(o1)) = vars(eff(o3)) which is required for the condition (F4) to hold. To formulate an FDR endomorphism as a CSP we strengthen the condition (F3) as φ(pre(o)) = pre(φ(o)) for all operators o O to simplify the CSP formulation, and we directly encode the conditions (F1) (F7) as constraints. For every variable V V and every value v dom(V ) we define a CSP variable Xv with the domain dom(V ) (F1) (we assume w.l.o.g. that variable domains are pairwise disjoint), and for every operator o O we define a CSP variable Xo with the domain Do = {o O | c(o ) c(o)} (F2, F5). The initial state I = { V1, v1 , . . . , Vn, vn } is encoded as the constraint Xv1, . . . , Xvn , { v1, . . . , vn } (F6), and the goal G = { Vi1, vi1 , . . . , Vik, vik } as the the constraint Xvi1 , . . . , Xvik , { vi1, . . . , vik } (F7). Finally, every operator o is encoded with two constraints Cpre(o) and Ceff(o) as follows. Let o O denote an operator with pre(o) = { Vi1, vi1 , . . . , Vik, vik }. The strengthened condition (F3) is encoded with Cpre(o) = Xo, Xvi1 , . . . , Xvik , Uo where Uo = { o , pre(o )[Vi1], . . . , pre(o )[Vik] | o Do, vars(pre(o )) = vars(pre(o))}. The condition (F4) is encoded with Ceff(o) constructed analogously to Cpre(o) but from eff(o). The size of the CSP formulation is polynomial in the size of FDR and, again, the size of operator constraints Cpre(o) and Ceff(o) is the most critical. For each operator o O there are 2 |O| constraints Cpre(o) and Ceff(o) altogether. The arities of these constraints are bounded by the number of variables V. For each of them, there are at most |O| many |V|-tuples of allowed values. Thus the size of these constraints is bounded by 2 |O|2 |V|. Nevertheless, this bound is often too pessimistic because the domains of preconditions and effects are often much smaller than |V| and operators are rarely allowed to be mapped to all operators. If we rewrite the bound for factored LTS 3 |L|2 M 2 F for the case of an atomic factored LTS of the FDR planning task, we get 3 |O|2 d2 max |V|, where dmax is the size of the largest domain. So, it is easy to see that for a given FDR planning tasks, the FDR endomorphism has a smaller CSP formulation then the corresponding LTS endomorphism (even if we consider the too pessimistic bound for the FDR endomorphism). Related Work The investigated endomorphisms are related to the already studied notion of structural symmetry (e.g., Pochter, Zohar, and Rosenschein 2011; Shleyfman et al. 2015), which is nothing else than an automorphism of the transition system in terms of model theory. Moreover, the homomorphisms are related to abstractions. In particular, abstractions form a certain subclass of homomorphisms because they always act as identity on the labels and are always surjective. However, abstractions were used mainly for computing heuristics and not for a detection of redundant operators. The most commonly used method for removing redundant operators is reachability analysis using hm heuristic, usually for m = 2, in forward and backward direction (Alc azar and Torralba 2015). This method can, however, find only the redundant operators that are either unreachable or lead to a dead-end state, i.e., they can never be part of any plan. Our proposed method via endomorphisms is therefore complementary it can, in some cases, prune unreachable or dead-end states/operators, but it does not dominate hmbased methods. Consider, for example, an LTS with an unreachable part which cannot be mapped into the reachable part by an endomorphism. Conversely, our method finds redundant operators in situations where hm pruning fails. Consider for instance the examples in Fig. 1 as there are neither unreachable states nor dead-ends. Another related method is the combination of operator mutexes (op-mutexes) and symmetries proposed by Fiˇser, Torralba, and Shleyfman (2019). The main idea behind this technique is based on the observation that if two operators cannot co-occur in the same optimal plan (i.e., they form an op-mutex) and there is a symmetry (stabilized for both the initial state and goals) mapping one operator to another, then one of the operators can be safely removed. So, as our Figure 3: (a) an example of a symmetric LTS; (b) a factored LTS Θ, Θ . method, this method can prune operators that can be part of some plan, but it requires an existence of a non-trivial symmetry, whereas our method does not need any symmetries. Again, consider the LTS depicted in Fig. 1 (right) having no non-trivial symmetry. Conversely, there are symmetric transition systems where the method employing op-mutexes finds redundant operators but our method fails. Consider the LTS depicted in Fig. 3 (a). All labels have a unit cost. The shown LTS is in fact a core. The operators l1 and l2 form an op-mutex and there is a symmetry mapping l1 to l2, which means that l1 (or l2) can be removed as redundant. Our method is also tightly related to methods applying a dominance relation to prune states and operators during search. Torralba and Hoffmann (2015) used cost-simulations which are dominance relations respecting transitions. A binary relation S S is said to be goal-respecting if s t, s S implies t S , and is called a costsimulation for Θ if, whenever s t, for every transition s l s there is a transition t l t such that s t and c(l ) c(l). Lemma 12. An LTS endomorphism α (viewed as a relation) is a goal-respecting cost-simulation. Proof. An endomorphism α induces a binary relation on states consisting of pairs of the form s, α(s) , i.e., we define s t iff t = α(s). Since α(S ) S , we have α(s) S provided that s S , i.e., is goal-respecting. Next, we have to prove that is a cost-simulation. Assume s t and s l s . We have to find t and l such that t l t , s t , and c(l ) c(l). By definition of we have t = α(s). As α is an endomorphism, it follows that t = α(s) α(l) α(s ) and c(α(l)) c(l). Since s α(s ), α(s ) is the witnessing state t and α(l) is the witnessing label l . Therefore, LTS endomorphisms are just functional goalrespecting cost-simulations. Similarly, as it is infeasible to search for endomorphisms directly on the LTS induced by a planning task, cost-simulations have to be computed on the factored LTS as well. Thus Torralba and Hoffmann (2015) defined a label-dominance (LD) simulation. Given a factored LTS Θ1, . . . , Θn , a tuple 1, . . . , n of relations, each i being a goal-respecting relation on Θi, is called label-dominance simulation if, whenever s i t in Θi, for every transition s l s in Θi there is a transition t l t in Θi such that s i t and c(l ) c(l) and for all j = i the label l dominates l in Θj given j. We say that l dominates l in Θj given j if for all s l t in Θj there exists s l t in Θj such that t j t . Note that particular relations i in the LD simulation are goal-respecting cost-simulations. Thus it is reasonable to ask whether the endomorphism obtained by Theorem 7 forms an LD simulation. The answer is negative as shown in the following example. Thus we get a separation of endomorphisms from LD simulations. Consider the factored LTS consisting of two factors Θ and Θ depicted in Fig. 3 (b). Assume that c(l1) c(l2) and c(l3) c(l4). There are clearly non-trivial endomorphisms on both LTSs such that l2 7 l1, l4 7 l3, s2 7 s1, sc 7 sb, and se 7 sd. Consequently, by Theorem 7 there is a non-trivial endomorphism on the synchronized product Θ Θ mapping s2, sc to s1, sb . Nevertheless, there is no LD simulation which would allow to prune state s2, sc . Indeed, suppose there are costsimulations and respectively on Θ and Θ such that s2 s1 and sc sb. For the transition s2 l4 s3 there has to be a transition going from s1. The only one is s1 l3 s3. Consequently, l3 has to dominate l4 in Θ by the definition of LD-simulation. However, this is not the case because l3 is not applicable in the state sc. Experimental Evaluation The inference of endomorphisms and pruning of redundant operators was implemented3 in C and experimentally evaluated on a cluster of computing nodes with Intel Xeon Scalable Gold 6146 processors. We used all planning domains from the optimal tracks of International Planning Competitions (IPCs) from 1998 to 2018 excluding the ones containing conditional effects after translation (leaving 65 domains). We used fact-alternating mutex groups (Fiˇser and Komenda 2018; Fiˇser 2020) for the construction of FDR variables and for removing unreachable and dead-end facts and operators. For comparison, we used pruning using h2 heuristic in forward and backward direction (Alc azar and Torralba 2015) which we refer to as h2 pruning. For solving CSPs, we used CP Optimizer from IBM ILOG CPLEX Optimization Studio v12.9. This solver contains an objective function that returns the number of different values assigned to a specified set of variables. We use the minimization of such objective function over operator (label) variables to obtain optimal solutions. Moreover, CP Optimizer is able to report all sub-optimal solutions found during the search for the optimal solution we use this feature to obtain a sub-optimal solution for tasks where the search terminates prematurely because of a time or memory limit. In the first set of experiments we aimed at (i) finding which domains contain non-trivial (i.e., non-identity) endomorphisms; (ii) how many operators can be identified as redundant by endomorphisms; (iii) how often can we find an optimal solution and how often the search for the op- 3https://gitlab.com/danfis/cpddl, branch aaai21-endomorphism domain fdr without h2 ts without h2 h2 fdr with h2 ts with h2 red fail sym %avg red fail sym %avg %avg red fail sym %avg %avg2 red fail sym %avg %avg2 airport04 (50) 0 29 0 0.00 16 29 0 2.00 73.41 0 29 0 73.41 0.00 0 29 0 73.41 0.00 blocks00 (35) 0 0 0 0.00 35 0 35 70.24 0.00 0 0 0 0.00 0.00 35 0 35 70.24 70.24 caldera18 (20) 0 0 0 0.00 (5) 8 12 0 28.44 55.35 0 0 0 55.35 0.00 (5) 11 9 0 74.53 34.09 cavediving14 (20) 8 0 5 13.66 3 13 1 6.24 0.54 8 0 5 14.20 13.72 3 13 1 6.79 6.29 data-network18 (20) 0 0 0 0.00 19 1 0 2.81 0.00 0 0 0 0.00 0.00 19 1 0 2.81 2.81 mystery98 (30) 4 3 8 1.10 8 16 10 6.28 46.39 3 12 2 46.79 0.87 1 21 1 46.64 0.42 organic-synthesis18 (20) 0 14 0 0.00 6 14 0 55.42 89.96 0 14 0 89.96 0.00 3 14 0 92.89 27.78 parcprinter08 (30) 26 0 8 5.23 28 0 17 20.38 44.87 0 0 0 44.87 0.00 20 0 16 57.46 22.35 parcprinter11 (20) 18 0 8 5.57 19 0 13 17.64 44.20 0 0 0 44.20 0.00 12 0 10 55.96 20.25 pathways06 (30) 0 0 0 0.00 5 10 0 0.05 3.94 0 0 0 3.94 0.00 5 10 0 3.98 0.05 pegsol08 (30) 2 0 0 0.30 3 0 0 0.38 19.14 0 0 0 19.14 0.00 0 0 0 19.14 0.00 pipesworld-notank04 (50) 0 0 0 0.00 12 18 4 1.51 6.12 0 0 0 6.12 0.00 0 14 0 6.12 0.00 psr-small04 (50) 0 0 0 0.00 38 0 0 2.49 23.51 0 0 0 23.51 0.00 11 0 0 23.75 0.25 rovers06 (40) 38 0 5 21.74 17 21 5 8.82 46.68 38 0 5 57.99 21.74 17 21 5 51.61 8.82 spider18 (20) 0 1 0 0.00 3 17 0 0.43 13.26 0 2 0 13.26 0.00 0 17 0 13.26 0.00 storage06 (30) 0 0 0 0.00 2 13 1 1.37 0.00 0 0 0 0.00 0.00 2 13 1 1.37 1.37 tidybot11 (20) 0 0 0 0.00 9 11 0 14.70 52.16 0 0 0 52.16 0.00 0 8 0 52.16 0.00 tpp06 (30) 10 2 0 7.69 (2) 6 14 0 2.53 39.74 10 2 0 43.50 7.76 4 12 0 41.60 3.32 transport08 (30) 13 0 12 2.69 1 21 1 0.29 0.00 13 0 12 2.69 2.69 1 21 1 0.29 0.29 transport11 (20) 11 0 11 5.10 1 16 1 0.43 0.00 11 0 11 5.10 5.10 1 16 1 0.43 0.43 transport14 (20) 15 0 14 6.44 1 17 1 0.99 0.00 15 0 14 6.44 6.44 1 17 1 0.99 0.99 trucks06 (30) 0 14 0 0.00 12 18 0 1.19 29.46 0 0 0 29.46 0.00 0 16 0 29.46 0.00 visitall11 (20) 6 0 6 5.19 6 0 6 5.19 0.00 6 0 6 5.19 5.19 6 0 6 5.19 5.19 visitall14 (20) 6 0 6 1.28 6 0 6 1.28 0.00 6 0 6 1.28 1.28 6 0 6 1.28 1.28 woodworking08 (30) 0 0 0 0.00 30 0 0 21.52 48.54 0 0 0 48.54 0.00 23 0 0 49.94 2.61 woodworking11 (20) 0 0 0 0.00 20 0 0 21.08 49.01 0 0 0 49.01 0.00 18 0 0 50.54 2.95 overall from above (735) 157 63 83 3.13 314 261 101 10.34 24.10 110 59 61 25.97 2.69 199 252 84 30.22 7.94 Table 1: red: number of tasks with at least one redundant operator (all non-trivial endomorphisms were optimal, except in caldera18 and tpp06, where the number of optimal solutions is given in parenthesis); fail: number of tasks where the inference failed due to a time or memory limit; sym: number of tasks in which symmetries appear after pruning; %avg: average percentage of removed operators per task within the whole domain; %avg2: same as %avg but the basis is the number of operators after h2 pruning, i.e., it measures the number of removed operators on top of those already removed by h2; overall is a sum for red, fail, and sym, and it is the average percentage of removed operators over all tasks for %avg and %avg2. timal solution fails because it requires too many computational resources; and (iv) whether the theoretical dominance of the LTS endomorphism over the FDR endomorphism can be actually measured on the standard benchmark set. To that end, we compared the FDR endomorphism (denoted by fdr) with the LTS endomorphism of the factored LTS constructed from projections to the found mutex groups (denoted by ts). Table 1 shows the results where the time limit for the inference of endomorphisms was set to 90 seconds and the memory limit was set to 16 GB. The table shows only the domains in which at least one variant found at least one redundant operator (or in other words, where at least one variant found a non-trivial endomorphism). The left side of the table shows results without the h2 pruning and the right side show the behaviour of our pruning when used after the tasks were already pruned using h2. Even with h2 pruning, we were able to find non-trivial FDR endomorphisms in 9 domains (out of 65) and in most of other domains, we were able to prove that there exist only identity FDR endomorphisms. Non-trivial LTS endomorphisms after h2 pruning were found in 20 domains, but the inference failed on a memory limit much more frequently (the time limit was an issue in a very few tasks). For example, we were not able to find out whether there is an LTS endomorphism in domains such as agricola18, airport04, park- ing11/14, or petri-net-alignment18. The relative number of pruned operators varied greatly depending on the domain, which is an expected behaviour. The comparison between the variants with and without h2 pruning clearly demonstrate that, on one hand, endomorphisms can sometimes prune a subset of unreachable operators found by h2 (e.g., in airport04, pegsol08, pipesworldnotankage04, spider18, tidybot11, and trucks06). And on the other hand, endomorphisms are able to prune operators that are reachable and thus undetectable by h2, e.g., blocks00, transport08/11/14, and visitall08/11 are domains without unreachable or dead-end operators and endomorphisms were able to detect redundant operators there. As we already described in the section on endomorphisms of transition systems, the only non-identity endomorphisms of a core are automorphisms, i.e., symmetries. So, we were also wondering whether removing redundant operators using endomorphisms can expose symmetries (on the so-called Problem Description Graph (Pochter, Zohar, and Rosenschein 2011)) that could not be found otherwise. As can be seen in Table 1, this behaviour is actually quite common, which is a promising result considering other planning methods depending on structural symmetries of planning tasks (e.g., Sievers et al. 2015; Shleyfman et al. 2015; Gnad et al. 2017; Fiˇser, Torralba, and Shleyfman 2019). domain lmc pot ms symba scrp B E B E B E B E B E blocks00 (35) 28 35 29 35 21 35 31 35 28 35 cavediving14 (20) 7 7 7 7 7 7 8 10 7 7 hiking14 (20) 11 11 14 14 14 14 16 15 16 16 parcprinter08 (30) 23 24 28 28 25 26 22 24 30 30 parcprinter11 (20) 18 19 20 20 19 19 17 18 20 20 rovers06 (40) 9 9 8 8 8 8 14 14 10 11 tetris14 (17) 9 9 17 17 13 13 11 11 14 13 transport14 (20) 6 6 7 8 7 8 9 9 10 10 visitall14 (20) 6 6 13 13 13 13 6 7 13 13 woodworking08 (30) 24 25 19 19 17 17 28 28 30 30 woodworking11 (20) 16 17 14 14 12 12 20 20 20 20 overall (1697) 885 896 1 025 1 032 935 951 1 002 1 011 1 113 1 120 Table 2: Number of solved tasks per domain and over all 65 domains. B: base variant with h2 and without endomorphisms, E: pruning with h2 and endomorphisms. In the second set of experiments, we applied the pruning using endomorphisms in various planners and counted the number of solved tasks under 30 minutes time limit and 16 GB memory limit. Since FDR endomorphisms are easier to infer and LTS endomorphisms can be found in more domains, we decided to combine both methods. We run the inference of FDR endomorphisms and after that the inference of LTS endomorphisms both with 90 seconds time limit. However, if the inference of FDR endomorphisms fails on a memory limit, we skip the inference of LTS endomorphisms, because the previous data showed that it is also very likely to fail. Moreover, we combined our proposed pruning with the h2 pruning, because the previous set of experiment showed that the combination of the two is able to prune more operators. We used the heuristic search planner Fast Downward (Helmert 2006) with A and the LM-Cut (lmc) heuristic (Helmert and Domshlak 2009); the merge-and-shrink (ms) heuristic with SCC-DFP merge strategy and non-greedy bisimulation shrink strategy (Helmert et al. 2014; Sievers, Wehrle, and Helmert 2016); the potential (pot) heuristic enhanced with disambiguations and optimized for all syntactic states with added constraint for the initial state (Seipp, Pommerening, and Helmert 2015; Fiˇser, Horˇc ık, and Komenda 2020); and the Scorpion planner (scrp) (Seipp 2018; Seipp and Helmert 2018) that performed very well in the last IPC 2018; and the symbolic planner Symb A (symba) (Torralba et al. 2017) used as a baseline in IPC 2018. Table 2 shows that the number of solved tasks is moderately increased due to the pruning, and the extra time spent in the inference of endomorphisms impacts the results negatively only in a very few cases. The table shows only the domains in which the pruning with endomorphisms resulted in a different number of solved tasks than in the case without endomorphisms for at least one of the planners. To demonstrate that the pruning has a positive effect even on tasks that were solved by both variants within the time limit, we show the number of expanded states (excluding the last f layer) as scatter plots for lmc, pot, and ms in Fig. 4. One can clearly see, that, on one hand, the number of expanded states is rarely higher with pruning (due to a differently constructed heuristic function). And on the other hand, pruning 10 102103104105106107108 B 10 102 103 104 105 106 107 108 10 102103104105106107108 B 10 102103104105106107108 B Figure 4: Number of expansions before the last f layer for tasks solved both with and without pruning using endomorphisms where at least one operator was pruned. B and E as in Table 2. using endomorphisms can greatly reduce the number of expanded states. Conclusions We introduced the notion of endomorphism into classical planning and we showed how to use it for detection of redundant operators. We proposed two methods for computing endomorphisms via a CSP solver. Experimental evaluation showed that a substantial number of IPC domains exhibit non-trivial endomorphisms. Nevertheless, it is necessary to further explore efficient methods for computing them, because, on one hand, our method for factored LTSs might produce too large CSP instances. And on the other hand, FDR endomorphisms are maybe too weak as only a few domains contain non-trivial FDR endomorphisms. Acknowledgements This work was funded by the Czech Science Foundation (grant no. 18-24965Y) and by DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science). The experimental evaluation was supported by the OP VVV funded project CZ.02.1.01/0.0/0.0/16 019/0000765 Research Center for Informatics . References Alc azar, V.; and Torralba, A. 2015. A Reminder about the Importance of Computing and Exploiting Invariants in Plan- ning. In Proc. ICAPS 15, 2 6. Fiˇser, D. 2020. Lifted Fact-Alternating Mutex Groups and Pruned Grounding of Classical Planning Problems. In Proc. AAAI 20, 9835 9842. Fiˇser, D.; Horˇc ık, R.; and Komenda, A. 2020. Strengthening Potential Heuristics with Mutexes and Disambiguations. In Proc. ICAPS 20, 124 133. Fiˇser, D.; and Komenda, A. 2018. Fact-Alternating Mutex Groups for Classical Planning. Journal of Artificial Intelligence Research 61: 475 521. Fiˇser, D.; Torralba, A.; and Shleyfman, A. 2019. Operator Mutexes and Symmetries for Simplifying Planning Tasks. In Proc. AAAI 19, 7586 7593. Gnad, D.; Torralba, A.; Shleyfman, A.; and Hoffmann, J. 2017. Symmetry Breaking in Star-Topology Decoupled Search. In Proc. ICAPS 17, 125 134. Haslum, P.; and Geffner, H. 2000. Admissible Heuristics for Optimal Planning. In Proc. AIPS 00, 140 149. Hell, P.; and Neˇsetˇril, J. 1992. The core of a graph. Discrete Mathematics 109(1-3): 117 126. Helmert, M. 2006. The Fast Downward Planning System. Journal of Artificial Intelligence Research 26: 191 246. Helmert, M.; and Domshlak, C. 2009. Landmarks, Critical Paths and Abstractions: What s the Difference Anyway? In Proc. ICAPS 09, 162 169. Helmert, M.; Haslum, P.; Hoffmann, J.; and Nissim, R. 2014. Merge & Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces. Journal of the Association for Computing Machinery 61(3): 16.1 16.63. Hodges, W. 1997. A Shorter Model Theory. Cambridge University Press. ISBN 978-0-521-58713-6. Libkin, L. 2004. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer. ISBN 978-3-540-21202-7. Pochter, N.; Zohar, A.; and Rosenschein, J. S. 2011. Exploiting Problem Symmetries in State-Based Planners. In Proc. AAAI 11. Rossman, B. 2008. Homomorphism preservation theorems. Journal of the Association for Computing Machinery 55(3): 15:1 15:53. Russell, S.; and Norvig, P. 2010. Artificial Intelligence: A Modern Approach (Third Edition). Englewood Cliffs, NJ: Prentice-Hall. ISBN 0-13-103805-3. Seipp, J. 2018. Fast Downward Scorpion. In IPC 2018 planner abstracts, 77 79. Seipp, J.; and Helmert, M. 2018. Counterexample-Guided Cartesian Abstraction Refinement for Classical Planning. Journal of Artificial Intelligence Research 62: 535 577. Seipp, J.; Pommerening, F.; and Helmert, M. 2015. New Optimization Functions for Potential Heuristics. In Proc. ICAPS 15, 193 201. Shleyfman, A.; Katz, M.; Helmert, M.; Sievers, S.; and Wehrle, M. 2015. Heuristics and Symmetries in Classical Planning. In Proc. AAAI 15, 3371 3377. Sievers, S.; Wehrle, M.; and Helmert, M. 2016. An Analysis of Merge Strategies for Merge-and-Shrink Heuristics. In Proc. ICAPS 16, 294 298. Sievers, S.; Wehrle, M.; Helmert, M.; Shleyfman, A.; and Katz, M. 2015. Factored Symmetries for Merge-and-Shrink Abstractions. In Proc. AAAI 15, 3378 3385. Torralba, A.; Alc azar, V.; Kissmann, P.; and Edelkamp, S. 2017. Efficient symbolic search for cost-optimal planning. Artificial Intelligence 242: 52 79. Torralba, A.; and Hoffmann, J. 2015. Simulation-Based Admissible Dominance Pruning. In Proc. IJCAI 15, 1689 1695.