LP Heuristics over Conjunctions: Compilation, Convergence, Nogood Learning

1 Introduction

In classical planning, LP heuristics approximate cost-to-goal through linear constraints. The state equation heuristic [van den Briel et al., 2007a; Bonet, 2013] formulates LP constraints over the number of action occurrences needed. Apart from integrating additional sources of information [Bonet and van den Briel, 2014; Pommerening et al., 2014], a successful approach are potential heuristics [Pommerening et al., 2015; Seipp et al., 2015], based on the dual of the state equation. The solution of that dual LP defines weights for variable values. Computed just once on the initial state, these weights define a consistent heuristic function for the entire state space.

Another research line uses variable-value (fact) conjunctions to improve approximations [van den Briel et al., 2007b]. The compilation ΠC renders a set C of conjunctions explicit, forcing delete relaxed plans to converge to real plans in the limit, i. e., for suitable C [Haslum, 2009; 2012; Keyder et al., 2014]. This leads to powerful heuristics, and in particular enables sound forward-search nogood learning, where the heuristic is iteratively refined based on the dead-end states encountered [Steinmetz and Hoffmann, 2017].

Here, we consider LP heuristics over conjunctions. This is not novel per se: partial variable merges enhance the state equation heuristic by constraints over conjunctions [Bonet and van den Briel, 2014]; potential heuristics can be defined over conjunctions as well [Seipp et al., 2016a; Pommerening et al., 2017]. We contribute new results pertaining to the use of the ΠC compilation, to convergence properties, and to the exploitation of convergence for nogood learning.

Seipp et al. [2016a] examined the size of conjunctions needed for a potential heuristic to find a plan without search. Pommerening et al. [2017] designed potential heuristics over arbitrary sets of conjunctions. While they provide an efficient construction method for potential heuristics over fact pairs, they also showed that the construction over fact triples is already computationally hard. Here, we show that for tasks in transition normal form (TNF) [Pommerening and Helmert, 2015], partial variable merges are strictly dominated by the compilation ΠC , and that both render the state equation heuristic equal to h∗ for suitable C. We show that consistent potential heuristics can be constructed from ΠC . 1 We show that, together with a (trivial to compute) upper bound U ∗ ∈ R on h∗ (s) for solvable s, one can choose C so that the ΠC potential heuristic equals h∗ .

We exploit these properties, motivated by the success of LP heuristics in the Unsolvability-IPC [Seipp et al., 2016b], in forward-search nogood learning. Convergence is essential here: Nogood learning using a heuristic h requires a refinement method that, given a dead-end state s not pruned by h so far, guarantees to refine h into h′ that prunes s. We design such a refinement method for LP heuristics, choosing new conjunctions suitable for the state equation and hence also the potential heuristic. Experiments on IPC benchmarks show significant performance improvements in several domains.

Throughout the paper, we omit many technical details. We refer the reader to the TR [Steinmetz and Hoffmann, 2018].

2 Preliminaries

We consider planning tasks in FDR notation [B¨ackstr¨om and Nebel, 1995; Helmert, 2009]. A task is a tuple Π =

1 This does not contradict Pommerening et al.'s [2017] hardness result as ΠC may grow exponentially in |C|. From this perspective, our result can be viewed as a way of identifying feasible potential heuristics over conjunctions: where ΠC is small.

〈V,A, sI, s∗〉. V is a set of variables v, each associated with a finite domain Dv. A state is a complete assignment to V . sI is the initial state. The goal s∗ is a partial variable assignment. A is a finite set of actions. Each action a ∈ A is associated with a precondition prea and an effect eff a, both partial variable assignments, and a non-negative cost costa ∈ R+0 . We assume that prea(v) ̸= eff a(v) when both are defined.

A fact is a variable-value pair p = 〈v, dv〉. For partial variable assignments P, we denote by V(P) the set of variables for which P is defined. For variables v ̸∈ V(P ), we also write P(v) = ⊥. We often treat (partial) variable assignments P as sets of facts {〈v, P(v)〉 | v ∈ V(P)}. We say that two assignments P and P ′ are compatible, written P||P ′ , if for all v ∈ V(P ) ∩ V(P ′ ) we have P (v) = P ′ (v).

An action a is applicable in a state s if prea ⊆ s, and the application results in the state sJaK where sJaK(v) = eff a(v) if v ∈ V(eff a) and sJaK(v) = s(v) otherwise. Action sequences π = 〈a1, . . . , an〉 are applied iteratively, and the outcome state is denoted sJπK. If s∗ ⊆ sJπK, then π is a plan for s. A plan for Π, or just plan, is a plan for sI. The cost of π is ∑ni=1 costai . A plan is optimal if its cost is minimal among all plans. If there is no plan for s, then s is a dead-end. If sI is a dead-end, we say that Π is unsolvable.

The set of all states in Π is denoted S. A heuristic is a function S ↦→ R+0 ∪ {∞}. The perfect heuristic h∗ assigns each state s the cost of an optimal plan for s, or ∞ if s is a dead-end. A heuristic h is admissible if h(s) ≤ h∗ (s) for all s ∈ S; h is consistent if, whenever a ∈ A is applicable in s, we have h(s) ≤ h(sJaK) + costa.

A notation for regression, defined in the usual way, will be convenient. The regression of P over a is regr(P, a) = (P \ eff a)∪prea if eff a∩P ̸= ∅ and eff a||P and (P \eff a)||prea; otherwise, regr(P, a) = ⊥.

We will sometimes consider transition normal form (TNF) [Pommerening et al., 2015]. This imposes that (TNF1) V(eff a) ⊆ V(prea) for all a ∈ A, 2 and (TNF2) V(s∗) = V. Every task can be transformed into TNF in polynomial time.

We next introduce the ΠC compilation. We follow Haslum [2012], with small modifications suiting our context.

A conjunction c is a partial variable assignment. To represent a set C of conjunctions explicitly in a given task Π, the ΠC compilation introduces a new Boolean variable πc for each c ∈ C; abusing notation, we identify πc with the fact 〈πc, 1〉. For a partial assignment P, P C := P ∪{〈πc, 1〉 | c ∈ C, c ⊆ P} ∪ {〈πc, 0〉 | c ∈ C, c ∦ P} augments P with the conjunctions it contains as well as the negation of the conjunctions it conflicts with. A set of conjunctions C ⊆ C is compatible if all c, c′ ∈ C are pairwise compatible.

Definition 1. Let Π = 〈V, A, sI , s∗〉 be a task, and C be a set of conjunctions. Then ΠC := 〈V C ,AC , sCI , sC∗ 〉 where V C = V∪{πc | c ∈ C} and AC contains an action aC for every pair a ∈ A and compatible C ⊆ C such that: (1) for all c ∈ C, regr(c, a) ̸= ⊥, and (2) for every c′ ∈ C, if regr(c′ , a) ̸= ⊥ and regr(c′ , a) ⊆ (prea ∪ ⋃c∈C regr(c, a)), then c′ ∈ C. The action aC is given by (i) preaC = [prea ∪ ⋃c∈C regr(c, a)]C ,

2 This differs slightly from the TNF definition in literature where V(pre a ) = V(eff a ) is required. We do so for simplicity only. All our results apply directly to the original version as well.

Intuitively, aC represents an occurrence of a that makes all c ∈ C true. For this to happen, the regression of each c over a must be true beforehand, as per (i). As per (ii), a conjunction c′ potentially invalidated by a is false afterwards. Condition (2) assures consistency: if an occurrence aC always makes true a conjunction c, then πc must be set to true necessarily.

With the possible C being subsets of C, |AC | may grow exponentially in |C|. This can be ameliorated (but not overcome entirely) with mutex information [Keyder et al., 2014]. Compatibility of C as postulated here is a special case thereof.

Plan equivalence between Π and ΠC can be easily shown by adapting Haslum's [2012] proof to our slightly modified ΠC definition. An extension of this equivalence result to individual transitions will become handy later on:

Lemma 1. For every Π and every C, it holds that every consistent heuristic h for Π is consistent in ΠC , and vice versa every consistent heuristic h for ΠC is consistent in Π.

Proof (sketch). Since every transition in ΠC has a corresponding transition in Π, the first direction is easy. For the other direction, the definition of ΠC ensures, for every state s and every applicable action a, that there exists an action occurrence aC of a such that (sJaK)C = sC JaC K. Hence, consistency in ΠC implies also consistency in Π.

3 The State Equation Heuristic

We introduce the state equation heuristic, and discuss its extensions to deal with conjunctions.

3.1 Definitions

The state equation (SEQ) describes a relation between variable-value changes, the net-changes, that every plan must satisfy. A fact p = 〈v, dv〉 is produced by an action a if eff a(v) = dv; p is consumed by a if prea(v) = dv and v ∈ V(eff a). Let s be any state, π be any plan for s, and p be any fact. Every consumption of p along π requires its production beforehand. If p is true in s, then p can be consumed once more than it is produced. If p must be true after the application of π, then p must be produced more often than it is consumed. So, let Countπa be the number of occurrences of action a in π. Denote by Prod(p) (Cons(p)) the set of all actions that produce (consume) p. Then the SEQ for p is

where ∆p(s) = 1 if p ̸∈ s and p ∈ s∗; ∆p(s) = -1 if p ∈ s and p ̸∈ s∗; and ∆p(s) = 0 otherwise.

The state equation heuristic hSEQ is defined via an LP. The LP contains one variable Counta ∈ R+0 for every action a. For every fact p the LP contains the constraint given by Equation (1) for p, choosing the right hand side ∆p(s) according to the state s for which hSEQ(s) is being computed. The objective function is to minimize ∑a∈A Counta · costa. If the LP has an optimal solution, then hSEQ(s) gives the respective the objective value. Otherwise hSEQ(s) = ∞. As every plan must satisfy Equation (1) for every p, hSEQ is admissible.

An important weakness of the state equation heuristic is that prevail conditions of actions, i. e., preconditions prea(v) where v ̸∈ V(eff a), are disregarded completely.

Example 1. Consider the transportation example in Figure 1.

There are two variables t and p, indicating the position of the truck respectively package. The truck can move freely on the depicted map through move actions. The package can be loaded or unloaded at the current truck position. All actions have cost 1. The initial state is given by sI = {〈t = B〉, 〈p = A〉}, the goal is s∗ = {〈p = C〉}. The hSEQ value for this state is 2, accounting only for loading and unloading the package. Truck movements are not counted since loading and unloading the package prevail the truck position.

3.2 The State Equation over Conjunctions

The weakness just discussed can be addressed by considering net-changes over conjunctions instead of single facts.

Example 2. Consider the set of conjunctions C = {c1, c2} for c1 = {〈t = A〉, 〈p = A〉} and c2 = {〈t = C〉, 〈p = T 〉}. Loading the package at A now requires and consumes πc1 , and unloading the package at C consumes πc2 . To produce πc1 , the truck has to move to location A. To produce πc2 , the truck has to move to C. Further, to satisfy Equation (1) for t = B, the truck needs to move back from A to B. This results in the perfect heuristic value 5; indeed, hSEQ[ΠC ](sI) = 5.

Bonet and van den Briel [2014] designed partial variable merges to extend hSEQ to conjunctions. We now compare this technique to the computation of hSEQ in ΠC , and we show convergence of both to h∗ for Π in TNF. For space reasons, we give a summary only. The TR contains the details.

Like the ΠC -compilation, partial variable merges consider a set of conjunctions C. But conjunctions c, c′ ∈ C are put into relation only when they instantiate the same variables, V(c) = V(c′ ). Hence the name "partial variable merges": Bonet and van den Briel start from the simpler idea of premerging entire variable subsets V ⊆ V, extending Π by a new variable representing this product; they improve over that idea by considering only particular value tuples within the product. As a result, their LP encoding grows polynomially in |C|, but might lose information relative to ΠC because no constraints are included across (conjunctions over) different variable subsets V, V ′ .

Specifically, partial variable merges are based on notions of potential producers and consumers, i. e., actions whose applications can achieve respectively invalidate c: PProd(c) = {a ∈ A | regr(c, a) ̸= ⊥} and PCons(c) = {a ∈ A | c ∦ eff a, c||prea}. This complication arises because the impact of an action a on a conjunction c depends on the context in which a is applied: on the action occurrence.

While ΠC enumerates possible action occurrences, variable merges handle each subset of C sharing the same variables V

separately. Denote by Π|V the product of V (which corresponds to the projection of Π onto V ). To represent those Π|V states P where P ̸∈ C, an abstract state ⊤ is introduced. The transitions within Π|V are abstracted by inserting ⊤ whenever the start or end state of a transition is not contained in C. Equation (1) for a conjunction c is then defined by summing over a ∈ PProd(c) respectively a ∈ PCons(c), with a separate occurrence-counter variable Countx→x′ a for every abstract transition x → x′ induced by a. Finally, these separate counters are related back to the main action counters by adding the constraint that the sum over Countx→x′ a is ≤ Counta. We denote the resulting heuristic by hCSEQ .

Theorem 1. For every Π in TNF, every set of conjunctions C, and every state s, it holds that hSEQ[ΠC ](s) ≥ hCSEQ(s).

Proof (sketch). Let Seq[ΠC ] be the LP underlying hSEQ[ΠC ](s), and SeqC that underlying hCSEQ(s). Every solution to Seq[ΠC ] can be transformed into a solution to SeqC, with equal objective value. The proof is technical but straightforward.

Theorem 2. There exists families of Π and C s.t., to obtain hC′ SEQ ≥ hSEQ[ΠC ], C ′ must be exponentially larger than C.

Proof (sketch). This happens, e. g., in a transportation example where n packages must be transported from B to A, and truck-load capacity is 1. In hSEQ[ΠC ], considering all conjunctions of size up to 3 makes visible that no two packages can be in the truck at the same time, yielding hSEQ[ΠC ] = h∗ . The partial variable merges in hCSEQ , however, cannot account perfectly for the interactions across packages unless all of them are considered jointly in the same Π|V .

For general tasks Π, the relation between hSEQ[ΠC ] and hCSEQ is however not so clear anymore. Complications stem from actions a affecting variables v without precondition on v. ΠC cannot relate the consumption of any conjunction c where v ∈ V(c) with a's action occurences. In contrast, hCSEQ can do so by enumerating the missing preconditions through different transitions. The TR contains an example.

We now turn to convergence properties. It is easy to show that partial variable merges can force hCSEQ to converge.

Theorem 3. For every planning task Π with V(s∗) = V, there exists a set of conjunctions C s.t. hCSEQ = h∗ .

Proof (sketch). A suitable C is C := S. The LP underlying hCSEQ then boils down to an LP encoding of shortest paths in the state space graph.

Corollary 1. For every planning task Π in TNF, there exists a set of conjunctions C s.t. hSEQ[ΠC ] = h∗ .

4 Potential Heuristics

Equation 1 depends on the state s considered. So SEQ based heuristics need to solve an LP in every search state. Potential heuristics solve an LP only once, in the initial state. The LP solution is used to compute weights (potentials) that, when combined in a linear fashion, define an admissible heuristic.

Formally, assume a given set C of conjunctions. A potential heuristic hPot C,w is then defined by a weight function w : C ↦→

R, with hPot C,w (s) = ∑c∈C,c⊆s w(c). The computational cost of evaluating such a heuristic on a state s is small. But how to find a suitable w guaranteeing admissibility?

For singleton conjunctions, Pommerening et al. [2015] designed an LP encoding guaranteeing consistency and value ≤ 0 on goal states (goal-awareness), which implies admissibility. Pommerening et al. [2017] extended this LP to general conjunctions. For pairs of facts, the size of their LP encoding is still polynomially bounded in the size of Π. For arbitrary conjunctions, however, the LP representation may require an exponential number of variables. In fact, Pommerening et al. [2017] have shown that for conjunctions of size larger than two, the construction of desired potential heuristics is computationally hard. Here we explore this direction further. We show that, for arbitrary C, the ΠC compilation can be used to compute consistent and goal-aware potential heuristics. We analyze the convergence properties of this approach.

4.1 Potential Heuristics Over Arbitrary C

We show that Pommerening et al.'s [2015] approach for singleton conjunctions, applied to ΠC , yields the desired w.

We assume that Π is in TNF. hPot C,w is consistent if ∑c∈C,c⊆s w(c) ≤ ∑c∈C,c⊆sJaK w(c)+costa, or equivalently ∑c∈C,c⊆s,c̸⊆sJaK w(c) - ∑c∈C,c̸⊆s,c⊆sJaK w(c) ≤ costa. If all conjunctions are singletons, c = {p}, then because of (TNF1) this inequality is equivalent to

Moreover, by (TNF2) there is only a single goal state. So the weights w ensure goal-awareness if

These equations define an LP, that we denote Pot[Π], whose variables represent the weights w. Any solution to Pot[Π] yields an admissible potential heuristic.

The objective function in Pot[Π] can be freely chosen. Various possible objectives have been explored [Seipp et al., 2015]. Here, we employ two of these: (O1) maximizing the heuristic value of an individual state s (through maximizing the weights of the conjunctions true in s); and (O2) maximizing the average heuristic value over all states (through maximizing the sum of all weights normalized by the frequency of the conjunctions). (O1) yields a connection to state equation heuristics. We use (O2) to encode the perfect heuristic as a potential heuristic. (Weight maximization requires an upper bound in the presence of dead-ends; we will discuss this as part of convergence in Section 4.2.)

The LP-based weight computation above requires Π to be in TNF. We use the standard transformation method [Pommerening and Helmert, 2015] to obtain a TNF version ΠCTNF from ΠC . Pommerening and Helmert [2015] have shown that this TNF transformation does not affect consistent and goalaware fact potential heuristics, i. e., a fact potential heuristic is consistent and goal-aware for ΠC if and only if it is for ΠCTNF . In other words, every w computed from Pot[ΠCTNF ] gives a consistent and goal-aware potential heuristic hPot C,w for ΠC . Lemma 1 leads to the desired result:

Theorem 4. Let Π be any task, and C be any set of conjunctions. Let w be any solution to Pot[ΠCTNF ]. Then hPot C,w is consistent and goal-aware in Π.

In other words, we can compute an admissible potential heuristic for any conjunction set C via a detour to ΠCTNF .

Pommerening et al.'s [2017] hardness result is reflected in the worst-case growth of ΠCTNF . But for cases where ΠCTNF grows polynomially in |C|, Theorem 4 shows that a desired potential heuristic can be computed in polynomial time. In this sense, Theorem 4 identifies a sufficient criterion for the efficient construction of potential heuristics.

It should be noted that not every admissible potential heuristic over conjunctions C can be constructed from Pot[ΠCTNF ]. This is the case because Equation (2) in Pot[ΠCTNF ] does no longer form a necessary condition for the consistency in Π: Pot[ΠCTNF ] enforces consistency over occurences aC where C does not fully specify the action application context, while this context is always completely defined when considering Π's transitions. The TR contains a detailed example.

4.2 Convergence

Does there always exist C for which hPot C,w obtained from Pot[ΠCTNF ] is perfect? The answer is "yes", under objective (O2) maximizing the average heuristic value. The presence of dead-end states causes complications though.

Obviously, the value h∗ (s) = ∞ for a dead-end s cannot be produced as part of the solution to an LP. Instead, the weights in the LP may diverge: Pot[Π] is not guaranteed to have a solution optimal for (O2). To see this, consider that no transition path starting from a dead-end ever reaches the goal; so, for conjunctions c true only in dead-ends, the weight can be made arbitrarily high while still satisfying consistency. Intuitively, the LP encoding imposes constraints on solution paths over conjunctions, and diverges where such a path does not exist. For that reason, Seipp et al. [2015] introduce a modified LP with the additional constraints w(c) ≤ U , where U ∈ R is a parameter. We denote that LP by Pot[Π, U].

Intuitively, U is a cut-off value on the cost of solutions considered in the LP. Convergence is achieved below U:

Theorem 5. Let Π be any task in TNF, and U ∈ R+0 . Then there exists a set C of conjunctions s.t., with w being a solution to Pot[ΠCTNF ,U] optimal for (O2), hPot C,w (s) = h∗ (s) for all states s with h∗ (s) ≤ U.

Proof (sketch). A set of conjunctions satisfying the claim is again C := S, the set of all states in the task. Pot[ΠCTNF ,U] then boils down to an LP encoding of paths in the state space of Π, with Equation 2 bounding the value of a state by its successor states. Objective (O2) makes sure that, up to U, the exact shortest path length is returned.

A simple trick now suffices to obtain h∗ globally. We pessimistically interpret the cut-off U as a dead-end indicator, defining hPot C,w,U (s) := hPot C,w (s) if hPot C,w (s) < U and hPot C,w,U (s) := ∞ otherwise. We then need to choose a cutoff that will never apply on solvable states, U > h∗ (s) for all s with h∗ (s) < ∞. This is the case for U ∗ := (∏v∈V |Dv| · maxa∈A costa ) + 1.

Corollary 2. Let Π be any task in TNF. Then there exists a set C of conjunctions s.t., with w being a solution to Pot[ΠCTNF ,U ∗ ] optimal for (O2), hPot C,w,U ∗ = h∗ .

For the simpler purpose of detecting all dead-end states, it is not necessary to use the exceedingly large constant U ∗ . Following previous work on potential heuristics for dead-end detection [Seipp et al., 2016b], we instead consider the task Π0 identical to Π except that all actions are assigned cost 0. Clearly, h∗ [Π0](s) = ∞ iff h∗ (s) = ∞, i. e., h∗ [Π0] detects all dead-ends in Π. But all solvable states s have h∗ [Π0](s) = 0, so setting U ∗ to any number > 0 results in hPot C,w,U ∗ that converges to h∗ [Π0] as per Corollary 2. We will denote potential heuristics constructed this way as uPot C,w .

4.3 Relation to the State Equation

Pommerening et al. [2015] have shown that Pot[Π] under objective (O1) for a state s is the dual of the state equation LP for s. By the strong duality theorem for linear programs, the two heuristics therefore have identical values on s.

Beyond individual states, the heuristics differ though: on states other than s, the potential heuristic merely gives a lower bound on hSEQ(s). In fact, there exist tasks and conjunction sets where no potential heuristic hPot C,w equals hSEQ[ΠC ] on all states. The TR specifies such an example.

5 Refining the State Equation

We have shown that LP heuristics converge to h∗ for suitable conjunctions C. As an application of this property, for the rest of the paper we consider proving unsolvability, through nogood learning (dead-end detection) using LP heuristics. This is motivated by the success of LP heuristics in the Unsolvability-IPC [Seipp et al., 2016b]. Convergence is essential as the heuristic must be able to represent arbitrary sets of dead-end states in the limit.

The key step in nogood learning with a heuristic h is refinement: given a dead-end state s not pruned by h so far, refine h into h′ that prunes s. Whether this can be done, and how to best do it in practice, depends crucially on which heuristic h is used. Steinmetz and Hoffmann [2017] have shown how to select new conjunctions for critical-path heuristics. Here we introduce a new refinement method selecting conjunctions suitable to refine the state equation.

To provide an overview, we next describe the forms of nogood learning we use in our experiments. Then we introduce our refinement method.

5.1 Nogood Learning

We start with C containing the singleton conjunctions. We experiment with three different forms of nogood learning:

CISeq : Proves the task unsolvable on the initial state. We iteratively apply refinement, adding new conjunctions into C, until hSEQ[ΠC ](sI) =∞.

CSSeq : Forward-search nogood learning as per Steinmetz and Hoffmann [2017], using hSEQ[ΠC ]. A depthoriented search calls refinement when backtracking out of a state s then known to be a (undetected) dead-end. The refined hSEQ[ΠC ] may generalize to dead-ends not yet encountered, reducing the future search space.

CSPot : Similar to CSSeq, but using potential heuristics. We maintain a collection of such heuristics. The refinement steps work as before, finding a larger set C suitable for hSEQ[ΠC ]; but now we also add a new potential heuristic uPot C,w (optimal under (O1) for s considered in the refinement) into the collection. To check whether a new state is a dead-end, only the potential heuristics are evaluated, which does not require any LP solving.

5.2 Refinement Method

We assume Π to be in TNF. Let C be any set of conjunctions, and s any dead-end where hSEQ[ΠC ](s) ̸= ∞. We need to extend C to C ′ ⊇ C such that hSEQ[ΠC′ ](s) = ∞. We do so by iteratively finding a conjunction x ̸∈ C whose SEQ constraint is not satisfied by a current LP solution. We set C := C ∪ {x}. If hSEQ[ΠC ](s) = ∞, we stop; else, we iterate. By Corollary 1, the termination condition must hold eventually.

It remains to show how to choose x. Denote by Seq[ΠC ] the LP underlying hSEQ[ΠC ](s). The refinement is based on a concrete solution Count to Seq[ΠC ]. Consider (1) the ΠC actions selected by Count, i. e., {aC ∈ AC | CountaC > 0}. Additionally consider (2) two auxiliary actions as and a∗, representing in ΠC the current state and the goal, i. e., preas = ∅, eff as = sC , prea∗ = sC∗ , and eff a∗ = ∅. We denote by ACCount the actions of (1) and (2). Our key observation is that we can find an action aC0 0 ∈ ACCount whose precondition is not supported by ACCount : (*) for all aC ∈ ACCount , regr(pre aC0 0 , aC ) ̸⊆ preaC . (Recall that the actions in ΠC represent action occurrences in the original task, carrying the context of application.)

We show (*) as follows. Consider the graph with nodes ACCount and edges aC → aC0 0 for every aC0 0 and aC where regr(pre aC0 0 , aC ) ⊆ preaC . In this graph, every path from as to a∗ would correspond to a plan for s. Since s is a dead-end, such path cannot exist. Hence there exists at least one node which is not connected to as. If (*) is not satisfied for any aC0 0 , then every node must have an incoming edge. But then, those actions in ACCount that are disconnected from as must form at least one cycle, i. e., omitting the "C" superscripts for readability, there must be a1, . . . , an ∈ ACCount \ {as} s.t. regr(preai+1 , ai) ⊆ preai and regr(prea1 , an) ⊆ prean . As Π is in TNF, every fact produced along a1, . . . , an is also consumed, and vice versa. Thus we can obtain another feasible solution Count′ to the LP such that ai ̸∈ ACCount′ for at least one i, by reducing the values Countai appropriately. Repeatedly applying this step will eventually remove all cycles, leaving us with the desired action aC0 0 .

Let P now denote the precondition of aC0 0 , projected onto the original variables V. Consider ΠC′ for C ′ = C ∪ {P}, and the πP -variable corresponding to P. Since Π is in TNF, 〈πP , 1〉 is consumed by aC0 0 . However, by (*) Count does not include any action that produces 〈πP , 1〉. In other words, Count violates the constraint corresponding to 〈πP , 1〉 in Seq[ΠC′ ]. Hence P ̸∈ C and we can set x := P .

We employ two optimizations. 1) we minimize P , starting with x = P and greedily removing facts p from x so long as the necessary properties are preserved. 2) we consider not a single aC0 0 , but all actionswith that profile, and add a conjunction x for each. This results in fewer refinement iterations.

6 Experiments

Our implementation is in Fast Downward (FD) [Helmert, 2006]. We use the UIPC'16 benchmarks, as well as unsolvable resource-constrained (RCP) benchmarks [Nakhost et al., 2012; Steinmetz and Hoffmann, 2017]. All experiments were run on machines equipped with Intel Xeon E5-2660 CPUs, with runtime (memory) limits of 30 minutes (4 GB).

Similar to earlier works on the ΠC -compilation [Keyder et al., 2014], we cope with the worst-case explosion by imposing a size limit M on the ratio |AC |/|A|. Once ΠC reaches the limit M, we disable the generation of new conjunctions. We experimented with M ∈ {2, 4, 8, . . . , 1024,∞}, where for M = ∞ the size of ΠC is not limited.

Figure 2 sheds light on an implementation detail that turns out to be important. Optimization 1) described in the previous section leaves open the order in which to remove facts p from x. We make this choice by fixing a variable order a priori. That order has a large impact on performance. Figure 2 compares the results for CISeq and x = ∞, for five randomly generated orders, picking the per-instance best, median, and worst variable order. The variance in coverage is large.

To counteract this brittleness, all our configurations in what follows combine the five variable orders, maintaining for each a separate conjunction set. Refinement works on all these sets, interleaving the individual refinement steps and stopping as soon as any of them succeeds. As can be seen in Figure 2 ("seeds combined"), this performs almost as well as the hypothetical per-instance best configuration. Considering fewer orders negatively affects coverage. Coverage remains stable for up to 10 orders, but starts to drop off eventually due to the additional overhead introduced with every order.

Table 1 shows our main coverage results, comparing our techniques to baselines and the state of the art. Here, hC is the forward-search nogood learning algorithm of Steinmetz and Hoffmann [2017]; PDB is a component of Aidos [Seipp et al., 2016b], the winner of UIPC'16, evaluated separately to consider algorithms rather than systems.

Consider first the comparison of our algorithms to the baselines, Seq and Pot in Table 1, that use the same heuristics but over the singleton conjunctions only, without any refinement. On the UIPC benchmarks, Seq and Pot dominate in the Unsolvable Resource-Constrained Planning (RCP) Benchmarks overall, but are outperformed by our techniques in DocumentTransfer, NoMystery, and Rovers. On the RCP benchmarks, our techniques are vastly better. These observations hold regardless of our configuration, with the single exception of CISeq in UIPC Rovers. We remark that the bad performance of our methods in the BagGripper and BagTransport domains is only due to the overhead of maintaining five different conjunction sets (cf. above); when maintaining a single set C, we get the same coverage here as Seq respectively Pot.

Considering hSEQ on the initial state only, without vs. with learning (the rightmost two columns), shows that the learned larger conjunctions yield a dramatic increase in unsolvabilitydetection power, despite the quick-or-not-at-all performance profile observed in Figure 2. Indeed, the number of conjunctions needed to prove sI unsolvable here is typically small. The maximal ratio |C|/ ∑v∈V |Dv| required is 1.66.

Comparing to the state of the art, UIPC NoMystery is the only domain where the coverage of (the best of) our new methods is strictly higher (by the smallest margin, +1) than that of any competitor. The main advantage of our methods is that they combine both, the strength of LP heuristics on the UIPC benchmarks, and that of conjunction-learning on RCP benchmarks: they are the only configurations with near-top performance in both benchmark categories. The "∑∑" row of Table 1 illustrates this (but should be taken with a grain of salt given the different numbers of instances per domain).

Comparing our configurations against each other, forwardsearch nogood learning consistently outperforms proving unsolvability on the initial state. The large limits M = 256 and M = ∞ are almost consistently worse than M = 128. Somewhat surprisingly, potential heuristics hardly ever improve over the state equation. Figure 3 elucidates the latter.

CSSeq has the edge in search space size, due to its higher pruning power; while potential heuristics are faster. Yet the former effect tends to be larger than the latter one.

7 Conclusion

LP heuristics yield powerful approximations in planning. We contributed insights on their definition over conjunctions, pertaining to the natural approach of using the ΠC compilation, its relation to previous techniques, convergence, and nogood learning via conjunction refinement.

Interesting avenues for future work are, e. g., conjunction refinement for optimal planning during A∗ search, and conjunction refinement for satisficing planning targeted at Seipp et al.'s [2016a] descending and dead-end avoiding heuristics.

Acknowledgments

We thank the anonymous reviewers, whose comments helped to improve the paper. This work was partially supported by the German Research Foundation (DFG), under grant HO 2169/5-1, as well as by the German Federal Ministry of Education and Research (BMBF) through funding for CISPA, under grant no. 16KIS0656.