Towards Feasible Higher-Dimensional Potential Heuristics

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 14:48:42

Abstract: Potential heuristics assign numerical values
(potentials) to state features, where each feature is a conjunction of
facts. It was previously shown that the informativeness of potential
heuristics can be significantly improved
by considering complex features,
but computing potentials over all pairs of facts
is already too costly in practice.
In this paper, we investigate whether using just a few high-dimensional
features instead of all conjunctions up to dimension $n$ can result in
improved heuristics while keeping the computational cost at bay. We focus on (a)
establishing a framework for studying this kind of potential heuristics, and
(b) whether it is reasonable to expect improvement with just a few
conjunctions. For (a), we propose two compilations that encode each
conjunction explicitly as a new fact so that we can compute
potentials over conjunctions in the original task as one-dimensional
potentials in the compilation.
Regarding (b), we provide evidence that informativeness of potential
heuristics can be significantly increased with a small set of conjunctions,
and these improvements have positive impact on the number of solved tasks.

Main paper: 
 introduction 20: 
 In classical optimal planning, potential heuristics (Pommerening et al. 2015; Pommerening, Helmert, and Bonet 2017) are a family of admissible (and consistent) heuristics computed as sums of potentials (numerical values) over state features that are sets of facts (conjunctions). Potentials ensuring admissibility and consistency can be found by solving a certain linear program with any optimization criteria that can be designed to emphasize different properties of the resulting heuristics (Seipp, Pommerening, and Helmert 2015; Fišer, Horčík, and Komenda 2020) . It was shown that increasing the size of conjunctions can eventually lead to optimal heuristics (Pommerening, Helmert, and Bonet 2017) . Computation of potential heuristics over single facts and pairs of facts is polynomial. However, computing the heuristics over all pairs of facts is already too computationally costly in practice, and for conjunctions of size 3 or more, it becomes coNP-hard to decide heuristic consistency.Here, we focus on the question whether computing potential heuristics over just a few conjunctions can lead to a significantly more informed heuristic that can be successfully used in practice. We leverage prior work of Steinmetz and Hoffmann (2018) showing that potential heuristics over conjunctions can be computed via the so-called Π C compilation (Haslum 2012) where conjunctions C are explicitly represented as facts. Potential heuristics over conjunctions C can be computed as single-fact potential heuristics in Π C , but the price we pay is the worst-case exponential blow-up in |C| of the Π C encoding. Since Π C does not preserve state space of the original task perfectly and thus does not preserve all (potential) heuristics, we introduce a new compilation Π C exact that remedies this pitfall. This allows us to plug-in a set of conjunctions C as input, and obtain a potential heuristic over C as output, while exchanging computational complexity for blow-up in the task encoding. Moreover, we use prior work on mutual exclusion state invariants to mitigate the blow-up (Keyder, Hoffmann, and Haslum 2014; Fišer and Komenda 2018; Fišer, Horčík, and Komenda 2020) .To test whether it is possible to increase informativeness of potential heuristics with only few conjunctions, we use a simple greedy uninformed algorithm to obtain improving conjunctions. We show in our experiments that it is, indeed, often the case that a small number of conjunctions leads to better heuristic estimates. We test this approach with explicit-state search, but also with symbolic search where potential heuristics can be used via so-called operatorpotential heuristics (Fišer, Torralba, and Hoffmann 2022a,b) . We show that even in this simple setting, we are able to increase the number of solved tasks in some domains. We leave the question how to intelligently find the improving conjunctions to future work. 
background: 
 We consider the finite domain representation (FDR) of planning tasks (Bäckström and Nebel 1995) . An FDR planning task is a tuple Π = ⟨V, O, I, G⟩. V is a finite set of variables, each v ∈ V has a finite domain dom(v). A fact ⟨v, x⟩ is a pair of a variable v ∈ V and one of its values x ∈ dom(V ). The set of all facts is denoted byF = {⟨v, x⟩ | v ∈ V, x ∈ dom(V )}, the set of facts of variable v is denoted by F v = {⟨v, x⟩ | x ∈ dom(v)},and similarly for sets of facts V : F V = v∈V F v . Given p ⊆ F, V(p)i = o i s i-1 for i ∈ {1, . . . , n}. The resulting state is π s 0 = s n and cost(π) = n i=1 cost(o i ) 105denotes the cost of π. A sequence of operators π is called an s-plan iff π is applicable in a state s and π s is a goal state, I-plan is called simply plan. An s-plan π is called optimal if its cost is minimal among all s-plans. A sequence of operators is called path if it is applicable in the initial state.A state s is reachable if there exists an operator sequence π applicable in I such that π I = s. R(Π) denotes the set of all reachable states in Π. An operator o is reachable if it is applicable in some reachable state. A state s is a dead-end if G ̸ ⊆ s and there is no s-plan.A heuristic h : R(Π) → R ∪ {∞} estimates the cost of optimal s-plans. The optimal heuristic h ⋆ (s) maps each reachable state s to the cost of the optimal s-plan or to ∞ if s is a dead-end. A heuristic h is called (a) admissible iff h(s) ≤ h ⋆ (s) for every reachable state s ∈ R(Π); (b) goalaware iff h(s) ≤ 0 for every reachable goal state s; and (c) consistent iff h(s) ≤ h(o s ) + cost(o) for all reachable states s ∈ R(Π) and operators o ∈ O applicable in s.Note that we define heuristics over the reachable states (instead of all states) because we intend to use heuristics in a (forward) heuristic search and because we use state invariants describing the reachable state space for improving the heuristic values (h-values). Also note that we allow negative heuristic values as is usual in literature on potential heuristics (the standard interpretation is that during the search, negative heuristic values are interpreted as zero). It is well-known that goal-aware and consistent heuristics are also admissible. 
mutexes and disambiguation: 
 It was previously shown that utilizing mutual exclusion in-135 variants (mutexes) significantly improves informativeness of potential heuristics (Fišer, Horčík, and Komenda 2020) . A mutex is a set of facts that is not part of any reachable state, i.e., M ⊆ F is a mutex if M ̸ ⊆ s for every s ∈ R(Π).The most obvious mutex in an FDR task is a set of facts 140 containing two facts of the same variable, but more mutexes can be inferred by the h m heuristic (Bonet and Geffner 2001; Alcázar and Torralba 2015) or by inference of so called fam-groups on lifted (Helmert 2009; Fišer 2020 Fišer , 2023) ) or ground (Fišer and Komenda 2018) level. Clearly, every superset of a mutex is also a mutex. For notational convenience, we use the notion of a mutex-set.Definition 1. A set of sets of facts M ⊆ 2 F is called a mutex-set if (a) every M ∈ M is a mutex, and (b) for every M ∈ M and every f ∈ F it holds that M ∪ {f } ∈ M, and (c) for every variable v ∈ V and every pair of factsf, f ′ ∈ F v , f ̸ = f ′ , it holds that {f, f ′ } ∈ M.In other words, a mutex-set is an upper set of a set of mutexes (a,b) and it always contains all mutexes that can be inferred directly from task's variables (c). This allows us to write p ∈ M if we want to express that the set of facts p is not a partial state (i.e., it contains two facts of the same variable), or that all states extending p are not reachable. Note also that p ̸ ∈ M implies p is a partial state.Mutexes can also be used for inference of disambiguations (Fišer, Horčík, and Komenda 2020) . A disambiguation of a variable v for a partial state p is a set of facts X ⊆ F v from the same variable v such that every reachable state extending p contains one fact from X. In other words, disambiguation of v for p allows us to filter out facts of the variable v that cannot be part of any reachable state extending p.Definition 2. Let v ∈ V denote a variable, and let p denote a partial state.X ⊆ F v is called a disambiguation of v for p if for every s ∈ R(Π) s.t. p ⊆ s it holds that X ∩ s ̸ = ∅.Disambiguations can also be used for finding unreachable operators and determining unsolvability of tasks. If, for some operator o ∈ O, a disambiguation of some v ∈ V for pre(o) is empty, then o is unreachable; and if a disambiguation of some v ∈ V for G is empty, the task is unsolvable. So, from now on, we will consider only tasks for which we have non-empty disambiguations of the goal and operators' preconditions. We use the following disambiguation maps D. Given a variable v ∈ V, D(v) denotes a disambiguation of v for G. Given an operator o ∈ O and v ∈ V(eff(o)), D(o, v) denotes a disambiguation of v for pre(o). 
potential heuristics: 
 Potential heuristics (Pommerening et al. 2015) were introduced as admissible and consistent heuristics that assign a numerical value (potential) to each fact, and the h-value for a state s is a sum of the potentials of all facts in s. It was shown that potentials can be computed by solving a linear program (LP) with constraints expressing goal-awareness and consistency of the resulting heuristic. Pommerening, Helmert, and Bonet (2017) showed that this concept can be extended to larger sets of facts (higher-dimensional features/conjunctions) so that a potential is associated with each conjunction, and the h-value for a state s is a sum over the potentials corresponding to conjunctions that are true in s.Increasing the size of conjunctions allows to distinguish between more states, eventually leading to a potential heuristic that is optimal. However, the computation of potentials becomes significantly more difficult as the size of conjunctions grows. Pommerening, Helmert, and Bonet (2017) showed that deciding consistency of a potential heuristic is coNP-hard in general if we consider all conjunctions of size 3 or more. They were however able to identify conditions when the construction of an admissible potential heuristic is tractable, depending on the interactions between the conjunctions. Steinmetz and Hoffmann (2018) showed that admissible higher-dimensional potential heuristics can be 205 computed via a detour to a single-fact potential heuristics in the Π C compilation, which we build upon here. The size of Π C grows worst-case exponentially in |C|, yielding an alternative tractability condition-when Π C does not explode.Since we plan to compute potential heuristics via compilations where each conjunction is explicitly represented as a fact, we formally use only a single-fact potential heuristics. Definition 3. A potential function is a function P : F → R.A potential heuristic for P maps each state s ∈ R(Π) to the sum of potentials of facts in s, i.e., h P (s) = f ∈s P(f ).Potential functions inducing admissible potential heuristics can be found by solving LPs, and it was shown by Fišer, Horčík, and Komenda (2020) that, if restricted to the reachable states, potential heuristics can be strengthened by taking disambiguations into account. So, given a disambiguation map D, we can find potential functions P by solving the following LP: The LP has a variable P(f ) for each fact f ∈ F, the constraintV ∈V max f ∈D(V ) P(f ) ≤ 0ensuring goal-awareness, and the constraintV ∈V(eff(o)) max f ∈D(o,V ) P(f ) - f ∈eff(o) P(f ) ≤ cost(o)for each operator o ∈ O ensuring consistency. Note that the maximization can be easily implemented with auxiliary variables as described by Pommerening et al. (2015) . Since the aforementioned constraints ensure goal-awareness and consistency (and therefore admissibility), the objective function of the LP can be freely chosen (Seipp, Pommerening, and Helmert 2015; Fišer, Horčík, and Komenda 2020) , e.g., maximization of f ∈I P(f ) will result in a potential heuristic with the maximum possible h-value for the initial state. 
π c compilation: 
 The first compilation we use for computing potentials over conjunctions is the Π C compilation introduced by Haslum (2012) in the context of strengthening delete-relaxation heuristics. Since then, it proved to be useful in different contexts too (e.g., Keyder, Hoffmann, and Haslum 2014; Fickert, Hoffmann, and Steinmetz 2016; Steinmetz and Hoffmann 2018) . In particular, Steinmetz and Hoffmann (2018) already showed that potential heuristics over Π C provide consistent and admissible estimates for the original task. We follow up on their work in that we use the Π C compilation in the FDR formalism (Haslum (2012) used STRIPS), but we also fully utilize mutexes to prune unreachable operators, as it was already pointed out by Keyder, Hoffmann, and Haslum (2014) that mutexes are effective in preventing the compilation to blow-up in practice as the size of Π C is worst-case exponential in |C|. Another subtle difference to the work of Steinmetz and Hoffmann is that we consider heuristics defined over reachable states only. For these reasons, we provide full proofs showing that the compilation preserves admissibility and consistency of heuristics (moved to the technical report for space reasons). Moreover, we show that Π C has some disadvantages. Namely, it can induce superfluous paths in the state space. For the rest of this section, let Π = ⟨V, O, I, G⟩ denote a task with facts F, let M be a mutex-set, and let C ⊆ 2 F be a set of conjunctions consisting of at least two facts (i.e., |c| ≥ 2 for every c ∈ C).The idea of the Π C compilation is following. First, we encode each conjunction c ∈ C as a binary variable v c : If c is true in a state s (c ⊆ s), v c is set to 1, otherwise it is set to 0. Second, we set the initial state and goal accordingly. Finally, we construct multiple operators for each input operator o ∈ O so that application of at least one of them maintain the intended values of the v c variables-this is where the worst-case exponential blow-up comes from as we need to enumerate possible contexts in which each operator can be applied. Now, we introduce some auxiliary notation that will be helpful in the construction of operators.Clearly, o ∈ O can make c ∈ C true or false only if eff(o) and c share some variables: C eff (o) = {c ∈ C | V(c) ∩ V(eff(o)) ̸ = ∅}.C a (o) = {c ∈ C eff (o) | c ∪ pre(o) ̸ ∈ M, c ∪ app(o) ∈ M} ∪ {c ∈ C eff (o) | c ∪ app(o) ̸ ∈ M}. C a (o)C f (o) = {c ∈ C a (o) | c ∪ app(o) ∈ M},and the set of conjunctions potentially made true by o depending on the state where o is applied:C p (o) = {c ∈ C a (o) | c ∪ app(o) ̸ ∈ M, c ̸ ⊆ app(o)}.Lastly, for every subset X ⊆ C, we define the extension of the precondition of o by parts of conjunctions from X unaffected by o (i.e., facts from X that if true before the application, are true also after the operator's application): (1) V C extends V with a fresh binary variable v c for each conjunction c ∈ C, i.e.,ext-pre(o, X) = pre(o) ∪ c∈X (c \ eff(o)).V C = V ∪ {v c | c ∈ C}, and, for each c ∈ C, v c ̸ ∈ V, dom(v c ) = {0, 1}.(2) The initial state is extended with the correct truth values of v c variables, i.e.,I C = I ∪ {⟨v c , 1⟩ | c ∈ C, c ⊆ I} ∪ {⟨v c , 0⟩ | c ∈ C, c ̸ ⊆ I}.(3) The goal is extended with v c set to1 whenever c is true in G, i.e., G C = G ∪ {⟨v c , 1⟩ | c ∈ C, c ⊆ G}.(4) For every operator o ∈ O and every subset of conjunctions X ⊆ C p (o) potentially made true by o such that (i) ext-pre(o, X) ̸ ∈ M, and (ii) X is downward closed onC p (o) (i.e., for every c ∈ C p (o) such that there exists c ′ ∈ X such that c ⊆ c ′ it holds that c ∈ X), O C has the operator o X with cost(o X ) = cost(o), pre(o X ) = ext-pre(o, X) ∪ {⟨v c , 1⟩ | c ∈ C, c ⊆ ext-pre(o, X)}, eff(o X ) = (eff(o) ∪ {⟨v c , 1⟩ | c ∈ C t (o) ∪ X} ∪ {⟨v c , 0⟩ | c ∈ C f (o)}) \ pre(o X ).Π C is well-defined as all variables have finite domains, I C is defined over all variables, and pre(oX ) ∩ eff(o X ) = ∅ for all o X ∈ O C .Note that the blow-up of the compilation comes from enumerating all possible combinations of conjunctions that are potentially made true by an operator (4). It is, however, mitigated by skipping operators that can be proved to be unreachable (4i), and by considering only downward closed sets (4ii). The later comes from a simple observation that having c, c ′ ∈ C such that c ′ ⊆ c and c is true, then c ′ is also necessarily true and therefore there is no reason for splitting the context where c is true, c ′ is true, and both are true.325 Given a state s from Π, we define the shorthandC[s] = s ∪ {⟨v c , 1⟩ | c ∈ C, c ⊆ s} ∪ {⟨v c , 0⟩ | c ∈ C, c ̸ ⊆ s}that can be used for translating a state s from Π to a state in Π C where all variables v c have assigned the correct values. Every path in Π C corresponds to a path in Π, i.e., Π C preserves applicability of the original operators from Π:Proposition 5. Let π = ⟨o X1 1 , . . . , o Xn n ⟩ denote a path in Π C . Then π ′ = ⟨o 1 , . . . , o n ⟩ is a path in Π and π ′ I = π I C ∩ F.Every path π in Π has its corresponding path π ′ in Π C with exactly the same length, cost, and it leads to a state inΠ C with correctly set variables v c , i.e., π ′ I C = C[π I ]. Proposition 6. Let π = ⟨o 1 , . . . , o n ⟩ denote a path in Π. Then there exists a path π ′ = ⟨o X1 1 , . . . , o Xn n ⟩ in Π C such that π ′ I C = C[π I ].Propositions 5 and 6 are enough to show that Π C preserves consistency and admissibility of heuristics. To be precise, we show that if we have an admissible (consistent) heuristic h C for Π C , then we can cast any state s reachable in Π to another state C[s] in Π C and use h C (C[s]) as an admissible (consistent) estimate for s in Π.Theorem 7. Let h C : R(Π C ) → R + 0 be a heuristic for Π C , let h : R(Π) → R + 0 be a function s.t. h(s) = h C (C[s]) for every s ∈ R(Π). If h C is admissible (consistent) heuristic for Π C , then h is an admissible (consistent) heuristic for Π.Proof. From Proposition 6 it follows that h is well-defined, because C[s] ∈ R(Π C ) for every s ∈ R(Π). Every plan in Π C has its corresponding plan in Π with the same cost (Proposition 5), and every plan in Π has its corresponding plan in Π C with the same cost (Proposition 6). So, admissibility and consistency follows.Π C also has some pitfalls. Consider a task with a plan π = ⟨o 1 , . . . , o n ⟩ and C = {c} such that c ̸ ⊆ I and c ⊆ G and c ̸ ⊆ eff(o i ) for every i ∈ {1, . . . , n}. From the construction of Π C it follows that for everyo i ∈ O there is o ∅ i ∈ O C constructed from the empty subset of C p (o i ), and the se- quence π ′ = ⟨o ∅ 1 , . . . , o ∅ n ⟩ is applicable in I C .Therefore, the resulting state s = π ′ I C contains all goal facts from Π, i.e., G ⊆ s, but v c is set to zero in s, i.e., ⟨v c , 0⟩ ∈ s, even though c ⊆ G ⊆ s. In other words, we have thats = π ′ I C ̸ = C[π I ].This does not contradict the propositions above. There still is another sequence of operatorsπ ′′ ̸ = π ′ from Π C s.t. π ′′ I C = C[π s ] (Proposition 6),and it, indeed, holds that π ′ I C ∩F = π I (Proposition 5). However, it shows that the construction of Π C can induce superfluous paths in the state space. These paths cannot be shortcuts, but they can be detours or lead to dead-ends. 
π c: 
 exact CompilationHere, we introduce a new compilation Π C exact that, in contrast to Π C , preserves the reachable part of the state space exactly. Π C exact follows Π C in that it also encodes each c ∈ C as a binary variable v c , but it differs from Π C in the way operators are encoded. Each operator o in Π C exact explicitly encodes truth values of all conjunctions potentially affected by o in both precondition and effect. This can lead to even larger blow-up than in Π C , but allows us to prove that not only all paths from Π are preserved in Π C exact , but also that every reachable state s in Π C exact is of a form s = C[s ∩ F], i.e., in every reachable state, every v c is set to 1 whenever c ⊆ s, and it is set to 0 otherwise. Therefore, the reachable parts of state spaces of Π and Π C exact are isomorphic: There is one-to-one mapping between reachable states in Π and Π C exact , one-to-one mapping between paths preserving costs, and therefore also one-to-one mapping between heuristics. From now on, let Π = ⟨V, O, I, G⟩, F, M, and C ⊆ 2 C be as in the previous section. We use some auxiliary notation:We use the same set C a (o) ⊆ C of conjunctions possibly affected by o ∈ O. Moreover, we use total functions f : C a (o) → {0, 1} for generating possible assignments to variables v c for all c ∈ C a (o). So, given o ∈ O and a total function f : C a (o) → {0, 1}, we define sets of conjunctions affected by o mapped by f to 1 and 0, respectively:C f,1 (o) = {c ∈ C a (o) | f (c) = 1}, C f,0 (o) = {c ∈ C a (o) | f (c) = 0},and the set of variables from C f,0 (o) that are not part of the precondition or effect of o:V f,0 (o) = c∈C f,0 (o) V(c) \ V(pre(o) ∪ eff(o)).For every partial state p s.t.V(p) = V f,0 (o), we define expre(o, f, p) = pre(o) ∪ p ∪ c∈C f,1 (o) c, exapp(o, f, p) = (expre(o, f, p) \ F eff(o) ) ∪ eff(o).The idea of the construction of operators is that for every operator o ∈ O, we consider all possible assignments to variables v c corresponding to possibly affected conjunctions c ∈ C a (o). In other words, o makes c true depending on the additional context which is not explicitly specified in its precondition. Therefore, the construction iterates over all possible contexts of variables V f,0 (o) so that we are able to exactly determine when the variables v c change their values from 0 to 1.exact compilation is worst-case exponential in |C| and |V|, but we can mitigate it by using mutexes as we need to consider only contexts that can cooccur with operator's precondition. Definition 8. Given a planning task Π, a mutex-set M, and a set of conjunctions C ⊆ 2 F s.t. |c| ≥ 2 for every c ∈ C, the planning task Π C exact = ⟨V C , O C exact , I C , G C ⟩ is defined as follows. V C , I C ,V f,0 (o) such that (i) expre(o, f, p) ̸ ∈ M and (ii) for every c ∈ C f,0 (o) it holds that c ̸ ⊆ expre(o, f, p), O C exact has the operator o f,p such that cost(o f,p ) = cost(o), pre(o f,p ) = expre(o, f, p) ∪ {⟨v c , f (c)⟩ | c ∈ C a (o)}, eff(o f,p ) = eff(o) \ pre(o f,p ) ∪ {⟨v c , 0⟩ | c ∈ C f,1 (o), c ∪ app(o) ∈ M} ∪ {⟨v c , 1⟩ | c ∈ C f,0 (o), c ⊆ exapp(o, f, p)}.As for Π C , it is easy to see that Π C exact is well-defined.Note that the condition (ii) makes sure that we consider only compatible (downward closed) assignments to variables, i.e., whenever we have two conjunctions c, c ′ ∈ C such that c ′ ⊆ c and f (v c ) = 1, then the compilation considers only the functions f where also f (v c ′ ) = 1. Also note that effects set v c to 1 only if v c is set to 0 in the precondition and vice versa ⟨v c , 0⟩ ∈ eff(o ′ i = s i ∩ F.From the definition of Π C exact we have thatI C ∩ F = I = s ′ 0 . Since, for every i ∈ {1, . . . , n}, it holds that pre(o i ) ⊆ expre(o i , f i , p i ) ⊆ pre(o fi,pi i ) ⊆ s i-1 , it fol- lows that pre(o i ) ⊆ s ′ i-1 , i.e., o i is applicable in s ′ i-1 . Since eff(o fi,pi i )∩F = eff(o)\pre(o fi,pi i ) it follows that for every f ∈ eff(o) it holds that either f ∈ pre(o fi,pi i ) (and therefore also f ∈ s ′ i-1 and f ∈ s ′ i ) or f ∈ eff(o fi,pi i ) (and there- fore f ∈ s ′ i ). Finally, since eff(o fi,pi i ) ∩ F ⊆ eff(o) we have o fi,pi i s i-1 ∩ F = o i s ′ i-1 = s ′ i .Next, we show that for every reachable state s in Π C exact it holds that v c is set to 1 whenever c is true in s, and v c is set to 0 whenever c is false in s. In other words, in contrast to Π C , all paths in Π C lead to states with correctly set v c values.Proposition 10. Let s ∈ R(Π C exact ) denote a reachable state in Π C exact . Then s = C[s ∩ F].Proof. Since I C = C[I C ∩ F] by construction, it follows that if there exists a reachable state s ∈ R(Π C exact ) such that s ̸ = C[s ∩ F], then there also exist a reachable states ′ ∈ R(Π C exact ) and an operator o f,p ∈ O C exact applicable in s ′ such that s ′ = C[s ′ ∩ F] and o f,p s ′ = s.We need to investigate four cases: (iv) There exists c ∈ C such that c ̸ ⊆ s ′ and ⟨v c , 0⟩ ∈ s ′ and c ⊆ s and ⟨v c , 0⟩ ∈ s: From c ̸ ⊆ s ′ and c ⊆ s and Proposition 9 it follows that c \ s ′ ⊆ eff(o), and from the construction expre(o, f, p) we have thatV(c \ eff(o)) ⊆ V(expre(o, f, p)), therefore V(c) ⊆ V(exapp(o, f, p)), therefore c ⊆ exapp(o, f, p) because exapp(o, f, p) ⊆ s, therefore ⟨v c , 1⟩ ∈ s which contradicts ⟨v c , 0⟩ ∈ s.Next, we show that for every path in Π there is a corresponding path in Π C exact with exactly the same cost. Proposition 11. Let π = ⟨o 1 , . . . , o n ⟩ denote a path in Π. Then there exists a path π ′ = ⟨o f1,p1 Proof. Let s 0 , s 1 , . . . , s n denote the intermediate states of π applied on I, i.e., s 0 = I and for every i ∈ {1, . . . , n} it holds that o i s i-1 = s i . Moreover, let s ′ i = C[s i ] for every i ∈ {0, 1, . . . , n}. From Definition 8 it follows that s ′ 0 = I C . Let assume that there exists a sequence of operatorsπ ′ = ⟨o f1,p1 1 , . . . , o fi-1,pi-1 i-1 ⟩, for some i < n, such that π ′ is applicable in s ′ 0 and π ′ s ′ 0 = s ′ i-1 . Now, we show that there exists o fi,pi i such that o fi,pi i is applicable in s ′ i-1 and o fi,pi i s ′ i-1 = s ′ i . From Proposition 9 we have that pre(o i ) ⊆ s i-1 = s ′ i-1 ∩ F. Let f i : C a (o) → {0, 1}denote a total function such that for every c ∈ C a (o) it holds that ⟨v c , f (c)⟩ ∈ s ′ i-1 , and letp i = s ′ i-1 ∩ F V f i ,0 (oi) . It is easy to see that f i is well-defined because V(s ′ i-1 ) = V.It is also easy to see that p i is a partial state, and since we have that pre(o i ) ⊆ s ′ i-1 and p ⊆ s ′ i-1 and, for everyc ∈ C fi,1 (o i ), c ⊆ s ′ i-1 , it follows that expre(o i ) ̸ ∈ M and therefore o fi,pi i ∈ O Cexact , and for the same reasons we have that pre(o fi,pi i) ⊆ s ′ i-1 . Therefore o fi,pi i is applicable in s ′i-1 and the rest follows from Proposition 10. Finally, we show that there is a one-to-one correspondence between heuristics in Π and Π C exact preserving admissibility and consistency. It is because every path in Π can be mapped to a path in Π C exact (Proposition 11), every path in Π C exact can be mapped back to a path in Π (Proposition 9), and there is a bijective mapping between all intermediate states of all paths in Π and Π C exact (Proposition 10).Theorem 12. (A) If h C ex : R(Π C exact ) → R + 0 is an admissible (consistent) heuristic for Π C exact , then h : R(Π) → R + 0 such that h(s) = h C ex (C[s]) for every s ∈ R(Π) is an admissible (consistent) heuristic for Π. (B) If h : R(Π) → R + 0 is an admissible (consistent) heuristic for Π, then h C ex : R(Π C exact ) → R + 0 such that h C ex (s) = h(s ∩ F) for every s ∈ R(Π C exact ) is admissible (consistent) heuristic for Π Cexact . Proof. Let T (Π) denote the set of all paths in Π, and let T (Π C exact ) denote the set of all paths in Π C exact . From Propositions 9, 10, and 11, it follows there are bijective functionsf t : T (Π) → T (Π C exact ) and f s : R(Π) → R(Π C exact ) such that cost(π) = cost(f t (π)) for every π ∈ T (Π).Theorem 12, the construction of Π C exact can result in having unreachable operators (as the input Π can have unreachable operators too). Therefore, inferring potential heuristics Co ← C; P ← P ′ ; 9 go to 2; 10 return Co as described in Section 4 does not guarantee we are able to find all possible potential heuristics (as it is not guaranteed 550 in general even for Π). 
potential heuristics over conjunctions: 
 Using potential heuristics over conjunctions in explicit-state search is straightforward. Given a set of conjunctions C, we construct either Π C or Π C exact compilation of the input plan-555 ning task Π, compute a potential heuristic h C in Π C or Π C exact as described in Section 4, and finally use the heuristic h such that h(s) = h C (C[s]) for all reachable states s ∈ R(Π) when running search in Π. Theorems 7 and 12 show that such heuristic h is admissible and consistent.Moreover, Π C and Π C exact compilations are ordinary FDR tasks that preserve all optimal plans (and do not induce any shortcuts), therefore we can plan directly in them. Such approach does not offer many benefits for explicit-state search as the larger number of operators makes generating succes-565 sor states slower, more variables lead to larger memory consumption for storing generated states, and the state space of Π C is possibly larger than the state space of Π (although this is not the case for Π C exact ). However, there are planning techniques that might benefit from this approach. 570 Fišer, Torralba, and Hoffmann (2022a,b) showed that potential heuristics can be transformed into operator-potential heuristics associating each operator o with the change of heuristic value of the corresponding potential heuristic induced by o. Consequently, operator-potential heuristics can 575 be used to significantly improve performance of symbolic search that searches over sets of states (represented as binary decision diagrams (Bryant 1986 )) rather than individual states. So, we can run this planning technique directly on Π C and Π C exact where the increased informativeness of 580 potential heuristics automatically translates into operatorpotential heuristics. This, of course, does not mean that the symbolic search will not suffer from using larger planning tasks. Also note that different variants of operators o X in Π C (o f,p in Π C exact ) corresponding to the same operator o from 585 Π can induce a different change of heuristic values. Therefore, we cannot directly translate potential heuristics over conjunctions obtained via compilations to operator-potential heuristics in the original task Π.Next question is how to obtain conjunctions C improv-590 ing potential heuristics. As we already indicated before, we do not attempt do design an efficient way to do it here. Instead, we aim at gathering evidence that it is, indeed, common that there are small sets of conjunctions that can significantly improve potential heuristics. So, here we use a simple greedy algorithm (Algorithm 1) that systematically tries to test conjunctions one by one starting from the smallest ones (lines 2 and 3). For each tested conjunction and all its subsets (line 5), a compilation is constructed and the corresponding potential heuristic inferred using the LP described in Section 4 (line 6). Finally, if the potential heuristic is improvement over the current one, we extend the set of conjunctions (lines 7 and 8) and restart the whole process (line 9). Potential heuristics can be computed by maximizing different optimization criteria-in our experiments we focus on the maximization of the h-value for the initial state only. The improvement of the resulting heuristics can also be measured in different ways. Here, we simply compare objective values of the corresponding LPs-since we maximize, higher values indicate a better heuristic. However, note that the inference using LP cannot guarantee dominance between potential heuristics in a general sense (one upper-bounds the other in all reachable states). It can only ensure dominance with respect to the optimization criteria (e.g., h-value for the initial state, or average h-value over all syntactic states). 
experimental evaluation: 
 The proposed method was implemented in C (source codes and data will be released) and evaluated on a cluster with Intel Xeon E5-2650v3 processors and 4 GB memory limit for each process. We used all planning domains from the optimal track of International Planning Competitions (IPCs) from 1998 to 2023 excluding the ones containing conditional effects after translation. We merged, for each domain, all benchmark from different IPCs leaving 54 domains and 1 806 tasks overall. Operators and facts are pruned with the h 2 heuristic in forward and backward direction (Alcázar and Torralba 2015) , and the translation from PDDL to FDR uses the mutex groups inference proposed by Fišer (2020 Fišer ( , 2023)) .For explicit-state search, we ran A ⋆ algorithm (Hart, Nilsson, and Raphael 1968 ) with two variants of potential heuristics: I denotes maximization of the h-value of the initial state (Pommerening et al. 2015) , and A denotes maximization for the average (syntactic) state while enforcing the maximum h-value for the initial state (Seipp, Pommerening, and Helmert 2015; Fišer, Horčík, and Komenda 2020) .We also evaluated symbolic search with operator-potential heuristics (Fišer, Torralba, and Hoffmann 2022a,b) : We used forward search with A (denoted by -→ A ), backward search with I ( ← -I ) and the combination of the two in the bidirectional search ( -→ A -← -I ). We use 30 minutes time limit for all search variants (not counting the inference of conjunctions). Since A ⋆ with potential heuristics tend to terminate quickly, we also consider simple portfolios P C and P C ex : We run A ⋆ with I or A in Π until it terminates. Then, in the remainder of the 30 minutes time budget, we run Algorithm 1 for 5 minutes to infer conjunctions C, and then run A ⋆ again this time with potential heuristics over C using Π C (P C ) or exact is compared over the same set of conjunctions inferred using Π C exact .Π C exact (P C ex ). These portfolios count the time spent in the inference of conjunctions into the whole time limit.To obtain conjunctions C, we ran Algorithm 1 for 5 min-650 utes for each task, and we set the optimization criteria to the maximization of the h-value for the initial state. Improving conjunctions were found with Π C (Π C exact ) in 47 (50) domains and 794 (844) tasks. So, Π C exact seems to be slightly more successful in this respect. The maximum size of the 655 found conjunction per task ranged from 2 to 8 for Π C and from 2 to 5 for Π C exact . The average (median) was 2.5 (2) for Π C and 2.6 (2) for Π C exact meaning most of the improvement comes from pairs of facts which is not surprising given Algorithm 1 tests all pairs first. The minimum, maximum, 660 average and median size of the resulting C was, respectively, 1, 28, 3.9 and 3 for Π C , and 1, 38, 3.8 and 3 for Π C exact . This indicates that both compilations used small sets of conjunctions in most cases. Fig. 1 compares h-values for initial states as ratios to the optimal heuristic on tasks where we knew h ⋆ 665 (1 333 tasks). These results show that it, indeed, is possible to obtain significantly more informative potential heuristics via Π C and Π C exact with just few additional conjunctions. To get some indication which compilation tends to lead to more informative heuristics, the comparison between Π C 670 and Π C exact in Fig. 1 is done with the same C (inferred with Π C exact ) in each task for both. It seems Π C exact is more successful than Π C in this respect too. However, Π C exact also tends to generate larger task representations than Π C : The minimum, maximum, average and median ratio between the 675 number of operators in the compilation and in the original planning task was 1, 7.9, 1.2 and 1 for Π C , and 1, 46.4, 2.8 and 1.4 for Π C exact . This is also reflected in the speed of computing potential heuristics. We were able to evaluate on average 64.4 conjunctions per second in case of Π C (median 680 was 32.7), and 55.3 with Π C exact (median 27.6). Table 1 shows the number of solved tasks (coverage) by the explicit-state search configurations. We are able to increase the coverage in some domains even with a small set of conjunctions inferred with a simple greedy uninformed algo-685 rithm. (Note that A ⋆ with I over all pairs of facts solves only 451 tasks.) Π C and Π C exact perform similarly, and the baseline (Π) rarely solves more tasks. The biggest difference between Π C and Π C exact seems to be in A and the woodworking domain where Π C managed to obtain more informed heuris-690 tics mainly due to the fact that Algorithm 1 with Π C was able to test larger number of conjunctions within the time limit.Portfolio results (P C , P C ex ) show that 30 minutes time bud- exact tends to consume more memory because all binary decision diagrams (BDDs) grow as the task grows, therefore also manipulating BDDs is slower. In some tasks, there is also an issue with the ordering of BDD variables (corresponding to facts in the task) causing significant blow-up of the BDD encodings. This, unfortunately, makes it harder to apply potential heuristics over conjunction in this setting, because we would need to consider conjunctions that not only improve the informativeness of the 715 heuristics, but also induce a good ordering of BDD variables.Nevertheless, at least the symbolic backward search ← -I seems to benefit from the compilations (more often from Π C exact than from Π C ). The main reason is that the backward search usually generates a smaller number of BDDs representing sets of states than the forward direction, but they typically encapsulate larger number of states. So, it seems having more informative heuristics is able to push this method a little bit further, but enough to see a difference in coverage.In this work, we focus on higher-dimensional potential heuristics computed via a small number of conjunctions explicitly represented as facts in compilations of the input planning tasks. We propose to use two variants of compilations: a well known Π C compilation (Haslum 2012) heuristics over conjunctions as single-fact potential heuristics in the compilations. Instead of trying to figure out how to find "good" conjunctions guaranteeing increased informativeness of the resulting heuristics, we focus on a basic ques-735 tion whether heuristic estimates can be improved with just few conjunctions and without significantly increasing computational cost in practice. To this end, we use a very simple greedy algorithm that blindly tries small conjunctions one by one, accepting the conjunction if its addition increases h-740 value for the initial state. We conclude that even in this simple setting, we can, indeed, increase informativeness of potential heuristics with just few conjunctions. Moreover, we provide a machinery for computing potential heuristics over conjunctions requiring only conjunctions to be plugged-in. 745We leave many questions unanswered for future work. The first one is how to determine which conjunctions lead to an improvement. Possible directions for answering this question might be previous works on the selection of improving conjunctions for delete-relaxed heuristics (Fickert 750 and Hoffmann 2017) or for learning no-goods using stateequation heuristics (Steinmetz and Hoffmann 2018) . Selection of patterns for pattern databases might also be relevant (Edelkamp 2006; Haslum et al. 2007; Franco et al. 2017; Rovner, Sievers, and Helmert 2019) . Another question is 755 the exact relationship between Π C and Π C exact compilations with respect to the possible potential heuristics that they can express via linear programs (LPs). It would also be interesting to know their relationship to the direct encoding in LP described by Pommerening, Helmert, and Bonet (2017) . 760 Lastly, it is not entirely clear how to successfully transfer the increased informativeness of potential heuristics to operatorpotential heuristics in the context of symbolic search (Fišer, Torralba, and Hoffmann 2022a,b) . 
: 
 is already too costly in practice. In this paper, we investigate whether using just a few high-dimensional features instead of all conjunctions up to a dimension n can result in improved heuristics while keeping the computational cost at bay. We focus on (a) establishing a framework for studying this kind of potential heuristics, and (b) whether it is reasonable to expect improvement with just a few conjunctions. For (a), we propose two compilations that encode each conjunction explicitly as a new fact so that we can compute potentials over conjunctions in the original task as one-dimensional potentials in the compilation. Regarding (b), we provide evidence that informativeness of potential heuristics can be significantly increased with a small set of conjunctions, and these improvements have positive impact on the number of solved tasks. 
 
 Appendix:  


Decision: The paper computes potential heuristics over conjunctive features via compilation. For this purpose, the authors consider a variation of the $\Pi^C$ compilation ($\Pi^C_\textup{exact}$) that guarantees an isomorphic reachable state-space. The reviewers are happy with the quality, originality and significance of the work.

One reviewer had a question regarding the soundness of one proof that was satisfactory resolved in the rebuttal.

Pros:
- interesting contribution
- paper is rigorous and mostly well-written
- experiments are well-designed

Cons:
- some parts of the paper hard to follow
- $\Pi^C_\textup{exact}$ compilation is somewhat incremental (based on ideas behind $\Pi^C$) and does not have an outstanding experimental impact

Reviews: review: strength_weakness: strength_weakness: I have a some minor points to mention here but all are easily fixable. The main one is about a possible gap in two proofs; the remaining ones are about improving clarity, and some related work. If the proofs are correct or can be fixed, the other points are not that critical. I reduced my score for soundness until this point can be cleared up, even if the description of the second-highest score doesn't really reflect my opinion.

Proofs for Theorems 7 and 12, rely on the fact that there is a bijection between plans and intermediate steps. (Side note: in the proof of Theorem 12, the function f_s is never used.) I don't think this is sufficient (at least for consistency) as consistency also has to hold between reachable dead ends which cannot lie on plans. Pi^C can also introduce detours, and I'm not quite convinced that properties hold along those detours. (They probably are as the detour is part of some other plan for which we again can make the original argument but it would be good to spell this out in the paper.)

In the section on the exact Pi^C compilation, it is hard to follow the case distinction of whether a conjunction is added, removed, or stays true/false. In all 4 cases, some of the conditions mentioned are necessary, some sufficient, and some both necessary and sufficient. Making this more explicit would improve readability.

The terms "admissible", "goal-aware" and "consistent" are re-defined to require the property only for reachable states. I don't think this is good practice, as in some contexts, the distinction between being admissible and admissible on the reachable states is important (e.g., orbit search). I would prefer defining a different term over redefining the existing one. Sievers and Helmert (JAIR 2021) use "forward-consistent" and "forward-admissible" for these concepts. Likewise, the term "dead-end" is used in different ways in the literature. Another common interpretation is that dead-ends are states without direct successors.

In Definition 4 the condition v_c \notin V is unclear. Variables v_c should never be in V, i.e., the names "v_c" should be new. Otherwise, it is not clear if the existing variable has the correct semantics.

The observation that a small number of small conjunctions can improve a potential heuristic by a lot has been made before for perfect heuristics (Corrêa and Pommerening ICAPS 2019). I don't think this limits the novelty of the paper as their approach was different and they did not use the resulting heuristics in practice, but it should be discussed as related work.


Minor comments
- line 77 and 78: dom(V) -> dom(v)
- line 80: sets of variables V
- line 164: a fact from X (saying "one" is also true but emphasizes the wrong aspect)
- line 184: missing math mode
- line 212: singular-plural mismatch
- line 243-250: The sentence is too long. Also, since the sentence start with saying you follow up on Steinmetz and Hoffmann's work, it would be more interesting what they used, rather than saying what Haslum used.
- line 279: the opposite implies that o is inapplicable, not that c is false.
- line 303: where only c is true, only c' is true, and where both are true.
- line 335: same length and cost
- line 408: If eff(o) changes a variable from c away from c, then v_c is certainly 0 afterwards but that doesn't necessarily mean it had to be 1 before.
- line 497-478: doesn't this depend on p?
- line 510: let us assume
- line 538: an admissible
- line 555: the Pi^C or the Pi^C_exact compilation
- line 559: running the search
- line 560: a heuristic
- line 567: the reachable state space
- line 590: The next question
- line 642: tends to
questions: questions: 1. Should the proofs for Theorems 7 and 12 also consider reachable but dead states? If so, what is the argument that consistency/admissibility is maintained for them? If not, why is this covered by the existing proofs?
2. It would be interesting to compare the size of generated conjunctions on tasks where coverage improved to the average on all tasks. If those tasks are at the high end of the global distribution, this would suggest that generally, we would like larger/more conjunctions but can only afford to compute enough of them on those tasks. If they are distributed in roughly the same way as the global distribution, it would confirm that small conjunctions are sufficient.

Post rebuttal:
Thank your for your answers. I agree with the updated proof and raised my score for soundness.
strength_weakness: strength_weakness: Clarity - The main weakness of this paper is related to the clarity of the two compilations. 
The description of the two encodings is hard to follow, and I could only understand the general idea of the compilation. This is partially because I’m not familiar with the FDR representation. However, I believe that the presentation would benefit from a couple of revisions:
    - I would separate the base compilation from the optimization that uses mutex sets. 
    - I suggest adding a complete example of the compilation (e.g., a simple example with a couple of conjunctions and one operator)

Regarding the contributions, it is not clear the relation between the mutex pruning used in this paper and the mutex pruning used in previous works (see question 2).

Novelty and significance - the contributions seem a bit incremental, given that \Pi^C already exists, and the practical usefulness of \Pi^C_exact is not outstanding in terms of coverage improvement.
questions: questions: 1) Can you clarify how the two portfolios P^C and P^C_exact work?

2) What are the differences between the mutex pruning you propose and the mutex pruning adopted by Keyder, Hoffmann, and Haslum (2014)?

3) Keyder, Hoffmann, and Haslum (2014) also point out that there exists a linear encoding that uses conditional effects for encoding the set of conjunctions. Would it be possible to adopt this encoding to compute potential heuristics? Maybe by compiling away conditional effects using the polynomial compilation by Nebel (2000) (On the Compilability and Expressive Power of Propositional Planning Formalisms)
strength_weakness: strength_weakness: The major weaknesses of the paper are related to the clarity of the notation (there are multiple dependency levels in the notation with almost no examples, which makes it hard to follow and do the proof-check), and also regarding the experiments, where the compilations do not seem to contribute much for coverage (however, they contribute to the informativeness of the computed heuristic).

Parts of the paper that I found hard to follow: 
- Definition 4, the point (4)
- Equations V^{f,0} and expre(o,f,p)
- Second half of the proof of proposition 11

Some other minor details:
- After partial state def., when using |...| explain that denotes the number of facts.
- Sometimes, the letter p is used as a proposition, while in this work is a partial state, this could be confusing.
- Line 159, this line is true only if M represents the set of all possible mutexes (a comment could help, otherwise prove it).
- Line 603, "restart" -> "repeat"?
- Figure 1 caption is not very clear.
- Table 2 focuses on symbolic search with operator potentials but they are shallowly explained in the paper.
questions: questions: Q1. Lines 175-177, does this make each operator preconditions to be non-empty? i.e. if they are originally empty, do you need some kind of extra dummy precondition=
Q2. Lines 295, "facts from X" or "conjunctions from X"?
Q3. Is it correct to say the set of mutexes M is approximated? how hard is to compute that set (i.e. is the complexity of Alg. 1)? how hard is to check the membership of a partial state into that set?
Q4. Fig. 1, does this mean that \Pi^C_{exact} computes higher potential heuristic values in the initial states than \Pi^C, and \Pi^C computes higher values than \Pi?