Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning

1 Introduction

Heuristic search is a dominant paradigm for effective planning (e. g. [Hoffmann and Nebel, 2001; Helmert and Domshlak, 2009; Richter and Westphal, 2010; Seipp, 2019]). Polynomial-time computable heuristic functions are an essential ingredient to this success, and have been extensively investigated since 20 years. A particularly important technique is the delete relaxation [Bonet and Geffner, 2001], which ignores negative effects (in a propositional encoding), essentially pretending that state variables accumulate their values rather than switching between them. Most state-ofthe-art satisficing planning systems (which do not prove optimality of the solution returned) still use the delete relaxation or extensions thereof today (e. g. [Helmert et al., 2011; Keyder et al., 2014; Domshlak et al., 2015; Cenamor et al., 2016]).

Virtually all of these approaches however suffer from the fact that "polynomial-time" is relative to the size of a grounded task representation. This is in contrast to the actual PDDL input of the planning system, which is lifted, specifying predicates and action schemas parameterized with variables ranging over a finite universe of objects. The grounded representation size is exponential in the size of that input, specifically in the arity of the predicates and action schemas. This is not a practical problem when the grounded representation is small enough to be feasible. Yet in a variety of application scenarios that is not so (e. g. [Hoffmann et al., 2006; Koller and Hoffmann, 2010; Koller and Petrick, 2011; Haslum, 2011; Matloob and Soutchanski, 2016]).

Lifted planning has always been considered (e. g. [Penberthy and Weld, 1992; Younes and Simmons, 2003]), and indeed was dominant in the early 90s [Russell and Norvig, 1995]. There has been little progress however on transferring the wealth of known heuristic functions to the lifted setting. The only previous attempt considered the delete relaxation and leveraged symmetries to reduce the grounding blow-up in relaxed planning [Ridder and Fox, 2014]. Later works devised lifted domain analyses to reduce task size [R¨oger et al., 2018; Sievers et al., 2019; Fiˇser, 2020].

Here we take a more radical approach, applying an additional relaxation to obtain a heuristic that runs in time polynomial in the size of the PDDL input. Our relaxation splits the predicates P(x1, . . . , xn) in the PDDL input task Π into smaller predicates Pi(xi1 , . . . , xiK ) of arity K, where {i1, . . . , iK} ⊆ {1, . . . , n} and |{i1, . . . , iK}| = K. Specifically, every occurrence of P is replaced by the conjunction of Pi for all size-K subsets of P's parameters. The size of the resulting lifted planning task Π|K is exponential only in K, hence polynomial for fixed K. This is a relaxation in conjunction with the delete relaxation, in the sense that every plan for Π is a delete-relaxed plan for Π|K. We show that computing a delete-relaxed plan for Π|K is still NP-hard (in PDDL input size) for K ≥ 2, but is polynomial-time for K = 1. We implement a heuristic function for K = 1, and we devise an optimization that leverages some K = 2 information from static predicates.

We implement our heuristic on top of the Power Lifted Planner recently introduced by Corrˆea et al. [2020], which grounds predicates and actions lazily during the forward search process. Standard International Planning Competition (IPC) benchmarks are not suited for evaluation as they are designed to challenge search rather than the grounding process. The only benchmarks currently available to challenge grounding are the ones by Areces et al. [2014], which contain action schemas of large arity (their work was about splitting large action schemas into several smaller ones). Correa et al. used these benchmarks. Here we go beyond this by exploring different reasons for being hard-to-ground: (a) large action-schema arity; (b) large predicate arity, which entails large action-schema arity but may have other consequences; (c) large object universe, which can be problematic even for small action/predicate arity. For (a) we use Areces et al.'s benchmarks; for (b) we generalize two IPC domains (Visitall and Childsnack) that have a naturally scalable dimensionality parameter; for (c) we generate larger instances of some IPC benchmark domains in a spirit similar to one experiment reported about by Ridder and Fox [2014]. For both (b) and (c), we take care to generate huge instances that are however within (and just beyond) reach of current lifted planners, in a manner similar to typical benchmark design in the IPC [Long and Fox, 2003; Hoffmann et al., 2006; Gerevini et al., 2009; Coles et al., 2012; Vallati et al., 2018; Torralba et al., 2021]. The design of this benchmark suite tailored to the evaluation of lifted planning is another contribution of our work. Our experiments show that our new polynomial-time lifted heuristic functions can improve the state of the art on these benchmarks, in particular through combination with goal counting.

2 Background

A lifted planning task is a tuple Π = (P, O, A, I, G) where P is a set of (first-order) predicates, A is a set of action schemas, O is a set of objects, I is the initial state, and G is the goal. Predicates P ∈ P have a tuple of parameter variables XP , and we write P(x1, . . . , x|XP |) whenever we want to explicitly declare them. The arity of P is |XP |. We denote individual parameters with x, y, z ∈ XP . We can instantiate a predicate, i.e., replace the set of parameters by objects fromO or other variables by applying a substitution. If all variables have been replaced by objects, then P is a ground predicate or atom. The set of ground atoms of P, resulting from all possible substitutions of variables in XP by objects in O, is denoted P O . By P O we denote the set of all ground atoms in the task. The initial state and goal are sets of ground atoms.

An action schema a = (Xa, pre(a), add(a), del(a)) is a tuple with a set of parameter variables Xa, as well as preconditions, add list, and delete list, all of which are sets of predicates in P instantiated by substituting each of their variables by some element in Xa ∪ O. As with predicates, the arity of a is |Xa|, and we can instantiate action schemas by replacing each x ∈ Xa by some o ∈ O to obtain ground actions. The set of ground actions (or actions for short) is AO . Note that, as the arity of predicates and action schemas is not bounded, P O and AO are of size exponential in the size of Π.

A ground action a is applicable in a state s if pre(a) ⊆ s. The resulting state of applying a on s is (s \ del(a)) ∪ add(a). A sequence of actions a1, . . . , an is applicable in a state s if there exists a sequence of states s0, . . . , sn such that s0 = s, and si is the result of applying ai in si-1 for all i ∈ [1, k]. We deal with the problem of finding a plan for an arbitrary planning task Π, that is, a sequence of ground actions applicable in I and resulting in some sn such that G ⊆ sn.

The delete-relaxation consists of ignoring the delete list del(a) of all action schemas. The FF heuristic [Hoffmann and Nebel, 2001] estimates the distance from any state s as the length of a relaxed plan, which can be computed in polynomial time in the size of the ground task.

Previous work by Corrˆea et al. [2020] has shown that evaluating whether there exists an instantiation of an action schema that is applicable on a state is closely connected to the problem of resolving conjunctive queries in database theory [Ullman, 1989]. A database DB = (D,R) has a domain D and a set of relations R over D, such that each Ri ∈ R is a set Ri ⊆ Dar(Ri) where ar(Ri) is the arity of Ri. Following planning nomenclature, sDB = ⋃Ri∈R Ri is a state over a set of predicates PDB = {Pi | Ri ∈ R} and objects ODB = D.

A conjunctive query Q over a database DB consists of a set of variables XQ and set of predicates Pi ∈ R instantiated with objects in D and/or variables in XQ. Q corresponds to the problem of finding a substitution of variables in XQ by objects in D such that all atoms in the query belong to the database. The preconditions of an action schema can be seen as a conjunctive query that corresponds to finding which instantiations of the action schema are applicable in sDB. Evaluating conjunctive queries (hence, lifted successor generation) is NP-hard in general [Chandra and Merlin, 1977], but it is tractable for acyclic conjunctive queries [Yannakakis, 1981]. We say that an action schema has acyclic preconditions if the corresponding conjunctive query is acyclic. For a detailed introduction, we refer the reader to the work by Corrˆea et al. [2020].

As running example we will use an extension of the Visitall IPC domain, where an agent must visit all tiles in a 2D grid. We generalize this to d-dimensional hypercube grids with side length l, and we permit goals requiring to visit a subset of the locations. Figure 1 sketches the encoding of our running example for d = 3.

The positions in the hypercube are tuples of indices in Nl = {i ∈ N | 1 ≤ i ≤ l}. The set of all positions is Ndl . Similar to the original domain, the player is at some position in the beginning and can move to adjacent positions. Note that we specify a separate move- action schema for each dimension, so that we need to encode adjacency only over the numbers {1, . . . , l} (next predicate), not over positions (number tuples) as in the standard benchmark. Furthermore, instead of requiring the player to visit all positions, the requirement is to visit a subset of positions G ⊆ Ndl . This example's grounded representation is exponential in d (which equals maximal predicate arity) as it needs to enumerate all possible positions so |P O | ≥ ld . The same blowup occurs in the lifted task in case all positions need to be visited, i.e. if G = Ndl . Yet if the number of goal positions is polynomial in d, then the ground task is exponentially larger than the lifted task.

P ={at(x, y, z), visited(x, y, z), next(x, x′ )} O={1, . . . , l} I ={at(1, 1, 1)} ∪ {next(i, j) | 1 ≤ i, j ≤ l, |i - j| = 1} G = {visited(3, 2, 4)} A={move-x(x, y, z, x′ ), move-y(x, y, z, y′ ), move-z(x, y, z, z′ )} where move-x(x, y, z, x′ ): pre : {at(x, y, z), next(x, x′ )} add : {at(x′ , y, z), visited(x′ , y, z)} del : {at(x, y, z)}

3 Complexity of Lifted Relaxed Planning

It is well known that a relaxed plan can be computed in polynomial time in the size of the ground task [Bonet and Geffner, 2001; Hoffmann and Nebel, 2001]. In lifted planning, however, there are (at least) two sources of hardness:

1. The number of ground actions |AO | is exponential in lifted task size. This might incur exponential effort in determining applicable actions, a key step underlying all known relaxed planning algorithms.
2. The number of ground atoms |P O | also is exponential in lifted task size. Hence both trivial upper bounds on relaxed plan length - number of ground atoms, number of ground actions - are not polynomial in this setting.

Indeed, delete-relaxed planning on lifted planning tasks was shown to be EXPTIME-complete [Erol et al., 1995]. To better understand the sources of complexity at play here, we consider two further restrictions, and show that the problem is still hard (1) even if the predicate arity is restricted to be constant and (2) even if checking action applicability can be performed efficiently.

The first result follows directly from results of recent work on the problem of lifted successor generation [Corrˆea et al., 2020], which showed an equivalence to answering conjunctive queries, viewing action-schema preconditions as queries over the state. Answering such a query is hard if it is cyclic in a certain sense. We can use this insight for a simple reduction from query answering to planning, in which a relaxed plan exists iff an applicable action exists in the initial state iff the answer to a query is true.

Theorem1. It is NP-hard to decide relaxed plan existence in lifted planning, even if predicate arity is constant.

Proof. We use a reduction from conjunctive queries, which are NP-hard even with 2-arity predicates [Chandra and Merlin, 1977]. Let Q be a conjunctive query over a database DB. Consider a task ΠQ = (P,O,A, I, G) where P = PDB ∪ {goal} (goal is a 0-arity predicate), I = sDB, G = {goal}, and A = {a} with Xa = XQ, pre(a) = Q, add(a) = {goal}. Then ΠQ is (relaxed) solvable if and only if some instantiation of a is applicable on I: i.e., if the conjunctive query Q is not empty.

For our second result, we encode a counter with n binary variables, where the plan is to count from 0 to 2n -1. No-

P = {at1(x), at2(x), at3(x), v1(x), v2(x), v3(x), n1(x), n2(x)} O={1, . . . , l} I={at1(1), at2(1), at3(1)} ∪ {n1(i), n2(j) | i, j ∈ [1, l]} G = {v1(3), v2(2), v3(4)} A={move-x(x, y, z, x′ ), move-y(x, y, z, y′ ), move-z(x, y, z, z′ )} where move-x(x, y, z, x′ ) : pre : {at1(x), at2(y), at3(z), n1(x), n2(x′ )} add : {at1(x′ ), at2(y), at3(z), v1(x′ ), v2(y), v3(z)} del : {at1(x), at2(y), at3(z)}

tably, this can be done with extremely simple action schemas, in particular ones with acyclic precondition queries, so that this source of complexity is independent from the previous one:

Theorem 2. There exist families of lifted planning tasks {Π1,Π2, . . . } with acyclic action-schema preconditions where delete-relaxed plans have exponential length.

Proof. We define Πn as (Pn,O,An, In, Gn) where O = {o0, o1}, Pn = {P(x1, . . . , xn)}, In = {P(o0, . . . , o0)}, Gn = {P(o1, . . . , o1)}, and An = {a1, . . . , an}. The action schemas are ai(x1, . . . , xi-1) for 1 ≤ i ≤ n (note that a1 has no parameters), with pre(ai) = {P(x1, . . . , xi-1, o0, o1, . . . , o1)} and add(ai) = {P(x1, . . . , xi-1, o1, o0, . . . , o0)}. Every relaxed plan has to achieve 2n - 1 ground atoms, applying 2n - 1 actions.

4 K-ary Predicate Splitting

To simplify the computation of relaxed plans at a lifted level, we apply a relaxation based on splitting each n-ary predicate into several K-ary predicates where K < n is a parameter for our approach. For a given K, the splitting operation (|K) replaces the predicate by ( nK) sub-predicates that correspond to all possible combinations of K parameters. For example, consider the predicate at(x, y, z) from our example in Figure 1. Then, at|1 = {at1(x), at2(y), at3(z)} and at|2 = {at1(x, y), at2(y, z), at3(x, z)}. The same operation can be applied to ground atoms in the initial state or goal as well as to action schemas by applying it to pre, add and del (e.g. see Figure 2). We also define this operation over sets of predicates, action schemas, etc, as the union of applying (|K) to each individual in the set, e.g., P|K = ⋃P∈P {P|K}.

Based on this splitting operation, we define the K-ary relaxation of a lifted planning task.

Definition 1 (K-ary Relaxation). Let Π = (P,O,A, I, G) be a lifted planning task and K be a constant. We define the K-ary relaxed task Π|K as a task (P|K, O, A|K, I|K, G|K).

Obviously, plans for Π|K are not necessarily plans for Π, so this is an approximation. Observe that, together with the delete relaxation, it is an over-approximation and thus indeed constitutes a relaxation:

Theorem 3. Let Π = (P,O,A, I, G) be a lifted planning task, K be a constant, and Π|K = (P|K, O, A|K, I|K, G|K) be the K-ary relaxed task. Then every plan for Π is a deleterelaxed plan for Π|K.

Proof. Every plan for Π is a delete-relaxed plan for Π, so it suffices to show that delete-relaxed plans are preserved in Π|K. Let a1, . . . , an be a delete-relaxed plan for Π, let I = s0, s1, . . . , sn be the (relaxed) states traversed by that plan in Π, and let I|K = s′0 , s′1 , . . . , s′n be the states traversed by that plan in Π|K. We show, by induction over i, that (1) ai|K is applicable in s′i-1 and (2) s′i = si|K. For the base case i = 0, (1) is empty and (2) holds by construction. For the inductive case, say the claim holds for i - 1. Then s′i-1 = si-1|K, so (1) ai|K is applicable in s′i-1 by construction of pre(ai|K). Regarding (2),

si|K= [si-1 ∪ add(ai)]|K [Def. of action application] = [si-1]|K ∪ [add(ai)]|K [Prop. of set projection] = s′i-1 ∪ [add(ai)]|K [Induction Hypothesis] = s′i-1 ∪ add(ai|K) [Def. of a|K] = s′i [Def. of action application]

Importantly, the same is not true without the delete relaxation: we do not have a guarantee that every plan for Π is a (non-delete-relaxed) plan for Π|K. This is because, when deleting P|K in Π|K, we may delete split atoms associated also with other instantiations of the same predicate. For example, in a state that contains both P(a, b) and P(a, c), an action that deletes P(a, b) in Π deletes P1(a) in Π|1, so that the outcome state in Π|1 does not contain P(a, c)|1. 1

Regarding the complexity of delete-relaxed planning in Π|K, all predicates in Π|K have a bounded arity of at most K. So the length of a relaxed plan for Π|K is polynomial in the size of Π and the complexity source identified by Theorem 2 disappears. The complexity source identified by Theorem 1 remains valid though for K ≥ 2, as answering conjunctive queries is NP-hard even in this case. Indeed, the action schemas resulting from 2-ary predicate splitting have cyclic preconditions. So deciding whether a relaxed plan for Π|K exists remains hard in general. Here we exploit the case K = 1, unary predicate splitting, where as we shall see next relaxed plans can be computed in polynomial time.

5 Unary Relaxed Planning

Even though the number of ground actions in the unary-split task Π|1 is still exponential in the size of Π, delete-relaxed plans for Π|1 can be computed in polynomial time.

The unary relaxation heuristic (hur , Alg. 1) accomplishes this, in a manner analogous to the computation of relaxed plans in ground tasks [Hoffmann and Nebel, 2001]. It constructs a best-supporter function that maps each ground atom in Π|1 to a ground action. Starting at the initial state, the algorithm iteratively computes a larger set of reachable atoms Input: Planning Task: Π = (P, O, A, I, G)

1 Higher-arity predicates can be compiled into binary predicates equivalently, i. e., without information loss. This compilation however requires the introduction of an ID (a new object) for every ground atom, and is thus of size exponential in the lifted encoding.

Algorithm 1: Unary Relaxed Plan Computation (hur )

Output: Relaxed Plan for Π|1 or "Unsolvable" 1 F0 ← I|1 2 i ← 0 3 do 4 i ← i + 1 5 Fi ←Fi-1 6 foreach P(o) ∈ P|O1 \ Fi-1 do 7 bs [P (o)] ← GetBestSupporter(Π, P (o), Fi-1) 8 if bs[P(o)] ̸=None then 9 Fi ← Fi ∪ {P (o)} 10 while G|1 ̸⊆ Fi ∧Fi ̸= Fi-1 11 if G|1 ⊆ Fi then 12 return ExtractRelaxedPlan(Π, bs) 13 else return "Unsolvable" 14 function GetBestSupporter(Π, P(o), F): 15 foreach a(x1, . . . , xn) ∈ A|1, i ∈ {1, . . . , n}, s.t. P (xi) ∈ add(a) do /* ∃o1, . . . , on ∈ O s.t. oi = o ∧ pre(a(o1, . . . , on)) ⊆ F */ 16 foreach j ∈ {1, . . . , n} do 17 Oj ← {o} if j = i else O 18 foreach Q(xj ) ∈ pre(a) do 19 Oj ←Oj ∩ {o′ | Q(o′ ) ∈ F} 20 if ∀j∈[1,n]Oj ̸= ∅ then 21 return any a(o1, . . . , on) s.t. oj ∈ Oj 22 return None 23 function ExtractRelaxedPlan(Π, bs): 24 queue ← G|1 \ I|1 25 plan ← 〈〉 26 while queue ̸= ∅ do 27 f ← queue.pop() 28 if bs[f] ̸∈ plan then 29 plan.append(bs [f ]) 30 queue ← queue ∪ pre(bs [f ]) \ I|1 31 return reverse(plan)

Fi, enabling in each iteration the preconditions of best supporter actions for new atoms. All atoms in the ith layer, Fi, are reachable by applying an action whose preconditions have been reached in the previous layers. In other words, among all possible supporters, we choose one whose precondition has minimal hmax value in Π|1 [Bonet and Geffner, 2001].

The key to polynomial-time behavior is that, in contrast to the algorithms commonly used on ground tasks, we do not enumerate applicable ground actions in each step. Instead, we merely keep track of a best supporter for each ground atom. There are polynomially many ground atoms in Π|1, and it turns out we can identify best supporters efficiently. Namely, the function GetBestSupporter iterates over action schemas instead of ground actions. We consider action schemas a(x1, . . . , xn) ∈ A where P(xi) ∈ add(a). Then, we check for each parameter j ̸= i separately with which objects can xj be instantiated such that the action preconditions are contained in F. The check in line 20 evaluates to true iff ∃o1, . . . , oj-1, oj+1, . . . , on ∈ O such that pre(a(o1, . . . , oi-1, o, oi+1, . . . , on)) ⊆ F, i. e., iff there exists an instantiation of a that achieves the atom P(o) and whose precondition is contained in F. This holds because, all preconditions being unary, the objects able to instantiate each parameter can be checked independently.

Once the best supporters have been chosen, relaxed plan extraction (ExtractRelaxedPlan) can easily be done in polynomial time. We process atoms one by one, starting with the goal atoms, inserting best-supporter actions into the relaxed plan and adding their preconditions to the atoms queue.

Theorem 4. Algorithm 1 runs in time polynomial in the size of Π, and returns a delete-relaxed plan for Π|1 iff such a plan exists.

Proof. If Algorithm 1 returns a plan, then it is a valid relaxed plan for Π|1. This plan achieves all goals, as it contains bs[f] for all f ∈ G|1, and f ∈ add(bs[f]). It is applicable in I as, for every action included in the plan, a supporting action will be inserted for every precondition not already true in I.

If the algorithm terminates without finding a relaxed plan (i.e., the main loop ends due to Fi = Fi-1) then the last Fi contains all reachable ground atoms, so some goal atom is unreachable from I, meaning that no plan exists.

The algorithm runs in time polynomial in the size of Π. Those "for each" loops in Algorithm 1 that iterate over elements of the lifted task Π obviously perform a polynomial number of iterations. The same is true for all other loops because the number of ground atoms |P|O1 | is polynomial in |Π|. This is immediate for the loop in line 6, as it simply iterates over the elements in P|O1 . Similarly, the main do-while loop in line 10 has at most one iteration per ground atom because in each iteration at least one new ground atom is added to Fi (or else the loop stops immediately). Regarding the relaxed plan extraction, the loop in line 26 iterates over the elements in the goal, G|1 and the preconditions of all selected best supporters. Note that there is at most one supporter for each ground atom in P|O1 , so at most polynomially many atoms are inserted in the queue.

Our implementation of Algorithm 1 has an additional tiebreaking for the choice in line 21, selecting the object in Oj whose preconditions Q(o) for all Q(Xj) ∈ pre(a) where inserted first (i.e., achieved in an earlier layer). The intuition is that the preconditions of those best supporters are easier to achieve from the initial state, leading to better relaxed plans. Note that, as in the FF heuristic, the relaxed plans are not guaranted to be optimal, therefore hur is not an admissible heuristic.

In our running example, all (unary) atoms are reachable in layer F1. The resulting relaxed plan is move-x(1, 1, 1, 3), move-y(1, 1, 1, 2), move-z(1, 1, 1, 4), so that hur (I) = 3. Note that this is a valid relaxed plan for the unary task from Figure 2.

6 Disambiguation with Static Predicates

We next devise an optimization leveraging static predicates to obtain a better heuristic function. To motivate this, consider again the running example in Figures 1 and 2. Under unary relaxation, the heuristic value is at most 3 · |G|1|, regardless of which positions need to be visited in the goal, because we can move from any coordinate to any other coordinate (e.g., move-x(1, 1, 1, 3) is applicable in the initial state, going from x-coordinate 1 to 3 in a single step). This happens because we split not only the at predicate, but also the next predicate used to determine which numbers are adjacent to each other.

Ideally, we would like to at least obtain something resembling Manhattan distance, still separating the dimensions (by splitting the at and visited predicates), but capturing movements within each dimension correctly. To achieve the latter, we must preserve the adjacency information in next. It turns out that this is indeed possible while still keeping the computational cost at bay, i. e., while preserving independence across the parameters of each action schema.

We modify the GetBestSupporter function in Algorithm 1, through a refined version of object collection at each position j in the second foreach loop. Say we need to support the atom P(o), with action schema a(x1, . . . , xn) and i ∈ {1, . . . , n} such that P(xi) ∈ add(a). Our modification replaces the full set of objects O assigned to Oj in line 17 by a more restricted set Oa(xi=o),j. That set contains only those objects which, when xi is instantiated with o, can instantiate xj while satisfying the static predicates. Precisely, let Pst be the set of static predicates, i.e., Pst ∈ P such that Pst ̸∈ add(a) for any a ∈ A. For any a ∈ A and xi, xj ∈ Xa, we denote the set of static preconditions of a and pairs of subindices that correspond to xi and xj in the precondition by prest(a, xi, xj). Formally, prest(a, xi, xj) = {〈Pst , k, l〉 | Pst ∈ Pst , Pst(x′1 , . . . , x′m) ∈ pre(a), x′k = xi, x′l = xj}. In our example, prest(move-x, x, x′ ) = {〈next, 1, 2〉} as there is a precondition with the static predicate next having x as first and x′ as second argument. Then, Oa(xi=o),j := ⋂〈Pst ,k,l〉∈pre st (a,xi,xj) {o′ ∈ O | ∃o1, . . . , om s.t. Pst (o1, . . . , om) ∈ I, ok = o, ol = o′ }. We denote the resulting heuristic function with hur-d .

For example, say we need to achieve at1(3), and consider move-x(x, y, z, x′ ) with x′ = 3. In the previous version of Algorithm 1, the set of objects associated with the first argument j = 1 will be simply O, allowing to move to 3 from anywhere. In our refined algorithm, that object set is {2, 4} due to the static precondition next(x, x′ ). The relaxed plan for our running example then is move-x(1, 1, 1, 2), move-x(2, 1, 1, 3), move-y(1, 1, 1, 2), move-z(1, 1, 1, 2), move-z(1, 1, 2, 3), move-z(1, 1, 3, 4), resulting in heuristic value hur-d (I) = 6.

Note that this is only a (tractable) approximation of the set of instantiations valid according to the static predicates when using predicate splitting with K = 2 for static predicates and K = 1 for the rest. We are instantiating each parameter independently, and therefore the set of objects associated with each parameter can be computed in polynomial time, at expenses of admitting instantiations that would not satisfy the static preconditions in the original problem or even within the K = 2 relaxation. Note further that one could apply this disambiguation to non-static predicates as well. But that would require to re-compute the set of objects, not only for every state during search, but also at each iteration of the algorithm, for each layer Fi. Restricting the disambiguation to static predicates, in contrast, allows us to pre-compute the sets of objects for each action schema, object, and parameter position once before the search starts, with respect to I instead of F .

7 Experiments

We implemented hur and the static disambiguation variant hur-d on top of the Power Lifted (PWL) planner [Corrˆea et al., 2020], which uses Breadth First Search (BFS) and Greedy Best-First Search (GBFS) with goal counting (hgc ) [Fikes and Nilsson, 1971]. Apart from GBFS with hur /hur-d , we also consider a combination with goal counting, using our heuristic for tie-breaking [R¨oger and Helmert, 2010] among nodes with the same hgc value. We also compare against the other existing lifted heuristic search planner, L-RPG [Ridder and Fox, 2014]. For additional reference, we report results for grounded planning, running Fast Downward's (FD) [Helmert, 2006] GBFS with the hgc and hFF [Hoffmann, 2001] heuristics. In all runs of PWL the successor generator based on Yannakakis' algorithm [Yannakakis, 1981] was selected. The experiments were run on a cluster of machines with Intel Xeon E5-2650 CPUs with a clock speed of 2.30GHz using the Lab framework [Seipp et al., 2017]. Timeout and memory limits were set to 30 minutes and 4GB respectively for all runs. All source code, experimental results and benchmarks are publicly available [Lauer et al., 2021].

7.1 Benchmark Design

We contribute a new benchmark set for lifted planning, exploring different reasons why a planning task may be hard to ground: (a) large action-schema arity; (b) large predicate arity, which entails large action-schema arity but may have other consequences; and (c) large object universe, which can be problematic even for small arity domains.

Our benchmarks of category (a) are simply the ones previously used to evaluate hard-to-ground planning [Areces et al., 2014; Corrˆea et al., 2020]. These consist of three domains: Genome Edit Distance (GED) [Haslum, 2011], Organic Synthesis [Masoumi et al., 2015] and Pipesworld-Tankage [Hoffmann et al., 2006]. We include GED here for historical reasons only: the encodings supported by the PWL planner are actually not that hard to ground, and Fast Downward's preprocess succeeds on all its instances. 2

We design new benchmarks for categories (b) and (c). We extend standard IPC domains, aiming for large instances that are hard to ground, but with simple enough goals such that some instances can be solved by current lifted planners. We scale the instances by parameters controlling task size and goal complexity, allowing us to observe how the performance of different planners is affected.

2 Other encodings of GED are harder to ground, but they use advanced PDDL features unsupported by PWL and our planner.

For (b), we create new variants of Visitall and Childsnack, which have a naturally scalable dimensionality parameter that controls predicate arity. The Visitall extension is our running example. We create instances with d ∈ {3, 4, 5} dimensions. For each of these cases we control the difficulty of instances by changing the number of goal locations from 1 to 3 and their relative position with respect to the starting location, close or far. For each of these categories we create 10 instances by scaling the size of the hypercube, starting at l = 6 and increasing l in each instance by 2 (for d = 5), 4 (for d = 4), or 6 (for d = 3) to reach hard instances in all categories.

In Childsnack one has to prepare sandwiches, where some children may eat only certain kind of ingredients (e.g. glutenfree) [Fuentetaja and de la Rosa, 2016]. The dimensionality parameter n is the number of contents on each sandwich (modeled as a predicate P(s, c1, . . . , cn)), which is normally fixed but which we scale here. Each child has preferences, e.g., allowing only tomatoes and salad. We create different variants scaling the number of children (3, 5, and 7), which is also the number of goals. In each category, we scale task size by increasing the amount of contents available, as well as more generous preferences for the children.

Finally, for (c) we include huge instances of IPC Blocksworld, Logistics, and Rovers, keeping the goal simple enough so that some tasks are within reach for current lifted planners (Ridder and Fox [2014] ran a similar experiment, but the benchmarks are not publicly available).

For Blocksworld, we scale the number of blocks from 100 to 1900, increasing by 200 blocks per instance. In the initial state, all blocks are placed on the table (we experimented with arbitrary initial states but were unable to find instances too hard to ground yet within reach of lifted planners). For Logistics, all tasks contain one city, one airplane, one truck, and ten packages. We scale the number of locations starting with 1000 and increasing by 250 in each instance. For Rovers, we generated tasks with a single rover, one objective and one camera. We scale the number of waypoints starting from 1000 and increasing by 500 in each instance.

7.2 Results

Table 1 shows coverage results. L-RPG is not competitive, which must be interpreted with care given the implementation differences. We remark that, as intended in our design, our heuristic functions are very fast. Indeed, the node generation rate (number of generated states per second) is almost up to the standards of goal counting: on average across all benchmark tasks, hgc is only 1.37 times faster than hur (max 3.34) and 1.67 times faster than hur-d (max 3.47).

In Organic Synthesis, plans are usually short, and most of the complexity lies in successor generation, to the effect that all PWL configurations have the same coverage. In GED and Pipesworld, our heuristics are not informative. This is partly due to a general weakness of delete relaxation here (hgc is better than hFF in grounded planning), but partly stems from the information loss in unary splitting.

In our new benchmarks, grounding is hardly possible throughout. In Visitall, expectedly hgc performs reasonably well when goals are close ("clo"), but not when they are far. Our new heuristics all do better, but particularly with disambiguation. Interestingly, the tie-breaking combination with hgc works best by far, hinting that our heuristics are unstable and profit from the clear progress identified by reaching more goal atoms. The picture in Childsnack is similar, except here there is no "goal location distance" parameter that we could scale, and hgc is hopeless throughout. Finally, results in the large IPC domains are mixed. In Logistics, our new heuristics are uninformative and fall far behind hgc . In Blocksworld and Rovers we obtain substantially better search information however. In Rovers, hur achieves best results, the only case where disambiguation is systematically detrimental.

8 Conclusion

Delete-relaxation heuristics are paramount in classical planning, yet take exponential time in the size of the lifted planning task input. To address this, we have introduced additional relaxations to achieve polynomial-time behavior. We focused on a heuristic that is extremely fast to compute on any lifted task, the unary relaxation, which splits all predicates into unary predicates. Our results with this first simple technique are highly promising and already show that the state of the art can be improved.

However, this barely explores the possibilities of our framework. Exciting avenues opened by this research are, for example, larger tractable fragments of predicate splitting, flexible splitting onto arbitrary sets of parameter tuples, clever methods for choosing such sets, etc.

Acknowledgments

This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project-ID 232722074 - SFB 1102.