Landmark Heuristics for Lifted Classical Planning

1 Introduction

Heuristic search is a dominant paradigm in planning (e. g. [Hoffmann and Nebel, 2001; Helmert and Domshlak, 2009; Richter and Westphal, 2010; Seipp, 2019]). Yet, this success is based on grounded task representations, in contrast to the actual PDDL input which is lifted, specifying predicates and action schemas parameterized with variables ranging over a finite universe of objects. The grounded representation has size exponential in the arity (number of arguments) of the PDDL predicates and action schemas. This effectively limits current heuristic search planning to planning tasks whose grounded representation is small enough to be feasible. It has been frequently observed that, for various applications, this is not naturally the case (e. g. [Hoffmann et al., 2006; Koller and Hoffmann, 2010; Koller and Petrick, 2011; Haslum, 2011; Matloob and Soutchanski, 2016]).

Lifted planning methods do not require to ground the entire task representation as a pre-process. This has received attention throughout the history of AI planning (e. g. [Penberthy and Weld, 1992; Russell and Norvig, 1995; Younes and Simmons, 2003]. Heuristic search planning, however, has begun to address lifted planning only recently.

Corrˆea et al. [2020] have devised an effective lifted forward search mechanism, grounding actions on demand in state expansion, in the Power Lifted Planner (PWL) through a connection to database queries. But how to transfer the wealth of known planning heuristics, which are based on reachability analyses over the grounded task representation? A simple option is goal counting, hGC(s) := |{g | g goal fact and not true in s}| which does not require such an analysis. All other approaches explored thus far are delete relaxation heuristics [Bonet and Geffner, 2001; Hoffmann and Nebel, 2001], which ignore negative action effects (the "delete lists") and have been addressed in the lifted setting through object symmetries [Ridder and Fox, 2014], a link to database technology [Corrˆea et al., 2021] and through a further relaxation which splits the predicates into unary predicates [Lauer et al., 2021].

Here we contribute a third family of lifted heuristics, which has been very successful in grounded planning, but is - so far - not available in the lifted setting: heuristics based on landmarks [Hoffmann et al., 2004]. Landmarks (LMs) are facts that have to be true at some point along every plan, or actions that need to be contained in every plan. Given a set L of LMs, goal distance is estimated by the number of unseen LMs. Landmark heuristics have been widely explored in planning [Karpas and Domshlak, 2009; Helmert and Domshlak, 2009; Richter and Westphal, 2010], in various forms and extensions, including ones incorporating disjunction and leveraging cost partitioning for admissibility. They are suited also for lifted planning, as the set L can be computed once before search, limiting the computational overhead incurred by the required reachability analysis. Especially a search guided by a combination of delete relaxation heuristics and LMs as used by the (grounded) LAMA system [Richter et al., 2008] has proven to be very effective in practice.

We introduce two methods to extract lifted LMs by adapting methods known from grounded planning [Hoffmann et al., 2004; Richter et al., 2008]. We combine a heuristic based on these LMs with the lifted delete relaxation heuristic by Corrˆea et al. [2021] to a system similar to LAMA. Our experiments show that (while only using LMs is less effective) this combination outperforms the state of the art in lifted planning, making landmark heuristics a valuable tool in this area.

2 Preliminaries

We first give some background on lifted planning, and introduce lifted landmarks afterwards.

2.1 Lifted Planning

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 an arity k and every occurrence in Π has k parameters, written P(x1, . . . , xk) where the xi are variables; we write X for the set of all variables used in Π. Parameters can be grounded (instantiated) with objects O. We write P(u1, . . . , uk) to denote a partially grounded predicate along with its arguments ui ∈ X ∪ O. If ui ∈ O for all i then P(u1, . . . , uk) is a ground predicate or atom, which we write as p. By P O we denote the set of all ground atoms in Π. States (in particular the initial state) are sets of ground atoms. The goal also is a set of ground atoms.

An action schema A is a tuple (XA, pre(A), add(A), del (A)) with a set of parameter variables XA as well as precondition, add list, and delete list, all of which are sets of predicates parameterized with variables from XA. The arity of A is |XA|. We can instantiate action schemas by replacing each x ∈ XA by some o ∈ O to obtain ground actions a. The set of ground actions, or actions for short, is AO .

Action a is applicable in state s if pre(a) ⊆ s. Applying a to s results in the state (s \ del (a)) ∪ add(a). A plan for Π is a sequence π of ground actions that is iteratively applicable in I and results in a state s′ such that G ⊆ s′ .

2.2 Landmarks

We next give limited background on landmarks as needed in this paper. We then introduce a simple generalization to the lifted (partially grounded) setting.

The Grounded Case. We first consider "fact landmarks" and "action landmarks". A ground atom p is a landmark of Π if, for every plan π for Π, there exists a state s traversed by π where p ∈ s. A ground action a is a landmark of Π if, for every plan π = (a1, . . . , an) for Π, there exists an index i with ai = a.

We also require notions of orderings between landmarks. For the following ordering definition, consider the execution of a plan as a sequence (s0, a1, s2, a3, . . . an-1, sn) of actions ai and states si resulting from executing the plan with s0 = I and si+1 the state resulting from the application of ai in si-1. Let a be an action LM, f be a fact landmark, and p and q be state or action landmarks of Π. Then:

• p is ordered before q (written p → q), when in every plan for Π, p is fulfilled (contained in the state, or executed, respectively) strictly before q is fulfilled;
• f is ordered directly before q (written f →D q) if in every plan, when q is fulfilled (added to the state, or executed, respectively) f holds.
• a is ordered directly before q (written a →D q) if in every plan, when q is fulfilled (added or executed) a has been executed at the preceding action step.

2.3 Lifted Landmarks

As we ground only partially in our landmark extraction methods, we naturally end up with partially grounded landmarks:

Definition 1 A partially grounded predicate P(u1, . . . , uk) is a lifted landmark of Π if there exists a ground instance p of P(u1, . . . , uk) that is a landmark of Π.

We remark that, apart from being natural algorithmically in lifted landmark extraction, Definition 1 also carries some novelty for grounded planning. It captures a simple special case of disjunctive landmarks [Hoffmann et al., 2004; Helmert and Domshlak, 2009], which is extremely compact and easy to extract. Consider e. g. an object o that needs to be transported with one of a fleet of trucks: the lifted landmark in(o, x) compactly represents the fact that o will have to be inside one of the trucks at some point.

3 Landmark Extraction

Deciding whether a ground atom is a landmark is PSPACEcomplete in grounded planning, because the decision is closely linked to solvability: intuitively, something is a landmark iff the task cannot be solved without it. There is however a wealth of landmark extraction methods based on sufficient criteria, finding some but not necessarily all LMs. A key trick is to consider delete relaxation, where solvability - and therewith the landmark-decision question - can be decided in time polynomial in the size of the grounded encoding. We adapted two such methods to the lifted setting: necessary subgoals and landmarks based on Domain Transition Graphs.

3.1 Necessary Subgoals

Our first method was introduced by Hoffmann et al. [2004] for the grounded case. It is based on a simple form of backchaining: starting at the goal atoms g, consider all actions a adding g, and intersect their preconditions ⋂a pre(a); clearly, any p ∈ ⋂a pre(a) is a landmark ordered directly before g, p →D g; iterate the process on p until no more new landmarks can be derived.

For example, in Blocksworld, holding(A) and clear(B) are necessary subgoals for on(A,B), and in turn clear(A) and armfree() are necessary subgoals for holding(A).

In the lifted setting, we also start at the ground goal atoms g, but in general the subgoals considered take the form of partially grounded predicates P(u1, . . . , uk). Given such a P(u1, . . . , uk), we consider all action schemas A = (XA, pre(A), add(A), del(A)) where P occurs in add(A). We partially ground each A as needed to match the objects ui ∈ O instantiating the subgoal, obtaining a partially grounded action of the form A(v1, . . . , vm) with vi ∈ XA ∪ O. We then intersect the preconditions of these A(v1, . . . , vm), but only on the predicates: we produce a new subgoal from every predicate Q that occurs in all preconditions. Let these preconditions be Q(v11, . . . , vm1), . . . , Q(v1n, . . . , vmn). Then, the new subgoal is Q(w1, . . . , wn) where

where the xi are arbitrary variables. We then iterate the process as before.

Q(w1, . . . ,wn) represents a least commitment where we instantiate only those parameters agreed upon by all preconditions. 1 Hence, the extraction process is sound:

Proposition 1 The subgoals Q(w1, . . . ,wn) computed as above are lifted landmarks of Π.

Proof: The goal atoms trivially are lifted landmarks. In each subsequent step of the algorithm, assume as induction hypothesis that the subgoal P(u1, . . . , uk) addressed is a lifted landmark. Then every plan must make a ground instance p of P(u1, . . . , uk) true. The ground action a doing so must be a ground instance of a partially grounded action A(v1, . . . , vm) considered by the algorithm. But then, by construction, a has a precondition instantiating Q(w1, . . . , wn), showing the claim.

3.2 FAM-Cut Landmarks

Our second method is inspired by a method from grounded planning based on Domain Transition Graphs (DTGs), e.g. used by the LAMA system [Richter et al., 2008, p. 3].

In grounded planning, the basic propositional representation is (usually) compiled to a finite domain representation before planning, i.e., one where variables have a finite range of values (see, e.g. the Fast Downward system [Helmert, 2006]). Consider e.g. a simple transport domain. Here, a package might either be at a location (e.g. a city), or in a transporter and in a single state it will be at exactly one such place: the values are mutually exclusive, they form a mutex group. Such structures are detected in a preprocessing step.

DTGs. A DTG is a directed graph capturing all transitions between values of such a variable x. Values of x form its nodes, while edges between the nodes capture transitions between the values, i.e., actions. [Richter et al., 2008, Def. 2].

DTG-based LMs. Given a landmark fg consisting of a single fact (initially a fact from the goal definition) not contained in the initial state, one can obtain landmarks by determining which parts (nodes or edges) of the DTG need to be passed on every way from the initial value f0 of this variable to the goal value (or, the other way around, which elements need to be cut to make the goal unreachable). Richter et al. iteratively remove nodes v from the DTG and test reachability of fg starting from f0: when f0 and fg have been connected before removing v but are not without v, all paths from f0 to fg pass v, and it forms a LM [Richter et al., 2008, p. 3].

FAM-Cut-LMs. We introduce a similar method for lifted planning. It is based on Lifted Fact-Alternating Mutex (FAM groups) as introduced by Fiˇser [2020]: a lifted FAM group is a tuple ν = (V fix [ν], V cnt [ν], atoms(ν)) with V fix [ν] ∩ V cnt [ν] = ∅. For the set of atoms atoms(ν) = {P1(v1 1 , . . . , v1 k1 ), . . . , Pl(vl1 , . . . , vlkl )}, all variables are from V fix [ν] ∪ V cnt [ν].

1 Note that, if Q appears n > 1 times within a single precondition, then we could actually construct n lifted landmarks, and indeed combinations across similar choices in other preconditions. This possibility did not seem relevant in the benchmarks we consider here, but it may be an interesting avenue for future work.

The semantics are the following: For a given assignment of fixed variables, the full grounding of the counted variables forms a mutex group [Fiˇser, 2020].

Analogously to DTG landmarks, we generate FAM-cut LMs in the following way: Given a known fact LM g (initially a fact from the goal definition), we identify the respective FAM group and its value in the initial state fI = PI (vI 1 , . . . , vI kI ). Now we build a graph that - similar to the ground DTG - captures all transitions from fI to g. The transitions are induced by the actions of the task. There are three ways atoms of a FAM group can be contained in an action definition:

1. It contains the atom in its preconditions (but not in the effects)
2. It contains the atom in its delete effects (and maybe but not necessarily in its preconditions)
3. It contains the atom in its preconditions, delete, and add effects

Case 1 does not change the value, we can ignore it. Case 2 results in a dead end in our transition graph: it deletes the value, but from the properties of FAM groups, we know that there cannot be an action adding it without having it also in its preconditions (otherwise we could use it to add a second value). Thus, case 2 will not contribute to the transitions from the initial state to the landmark either. What we are interested in is case 3: actions where atoms from the FAM group are contained in the precondition, the delete effects, and in the add effects, since they form value transitions in our graph. It should be noted that there might be more that one combination of precondition, add, and delete effects from a single action contributing transitions in the graph.

Now we build our graph capturing all value transitions in the FAM group. We start in fI = PI(vI 1 , . . . , vI kI ) and build it in a forward manner until it converges. We identify all actions from case 3 and for each add a transition to the graph. For each action, we only bind the parameter variables contained in PI(vI 1 , . . . , vI kI ). So the graph can contain partially grounded nodes.

Figure 1 shows the graph for a transport domain, where package 0 that is currently at a city loc 1 must be delivered to a target position. Each unassigned variable (starting with "?") might be any object of the particular type, i.e., we are (as before) generating a special type of disjunctive landmarks.

We now start LM generation by first building the set of nodes unifiable with our known landmark g, which we call G. If G includes fI, we return the empty set of landmarks. Else, we generate the set C of incoming edges of G, which forms our candidate for a disjunctive action landmark. However, it might contain edges not connecting I with G. Therefore we test which edges from C have to be cut to make G unreachable from I. The resulting set forms our first disjunctive action landmark Li. We add the starting nodes from edges in Li to G and continue the process until we have reached fI.

Theorem 1 The generated cuts {L1, . . . , Ln} form disjunctive action landmarks for Π.

Proof: We first need to show that our graph represents all transitions of that particular FAM group. Consider it does not, then there must be an action adding one of its values not represented in the graph. However, due to the properties of FAM groups, every such action must also delete a value, as given above in case 3. Since we constructed the graph using these actions up to convergence, we know that every transition is represented and our graph contains all transitions in that FAM group. Thus, every cut between I and G must be passed to reach a goal value when starting from the initial state, including our cuts. As a result, one of the actions in our cut must be in every plan, and the cuts form landmarks.

We intersect the preconditions of the resulting disjunctive action LMs as done for necessarily subgoal extraction. This results in new fact LMs, these are used for FAM-based extraction. This process is continued until no new LMs are found.

3.3 Ordering Relations

The above extraction methods deliver ordering relations as a side effect: → relations for FAM-Cut landmarks, →D relations for necessary subgoals. For FAM-Cut landmarks, the extracted ordering conditions are weaker → conditions since actions belonging to different FAM groups may be interleaved. For necessary sub-goals, if Q(w1, . . . ,wn) was extracted as a joint precondition for P(u1, . . . , uk), then we know that some ground instance q of Q(w1, . . . , wn) must be true directly before the ground instance p of P(u1, . . . , uk) that will be used in the plan. Therefore, if no such q was made true yet, then we know that p has not been made true yet either and so must still be made true (even if some other ground instance of P(u1, . . . , uk) was already true). In this sense, the →D relations carry over to the lifted setting, and (as discussed in Section 4) we use them as before.

4 Landmark-based Heuristics

The basic idea behind landmark heuristics is simple as outlined in the introduction: hLM(s) := |{p ∈ L | p must still be fulfilled}|.

The notion of "must still be fulfilled" however is a bit subtle to spell out: 1. this is path-dependent as we need to know which landmarks have already been fulfilled in the past; 2. we must take into account that something may already have been fulfilled but must be made true again. These issues have been amply addressed in the literature on grounded planning. Here we adapt the LM COUNT heuristic [Richter and Westphal, 2010], which is simple, and canonical in terms of being part of a state-of-the-art system. The heuristic is defined as

where πs = 〈s0, . . . , sn〉 is the search path (the sequence of states) up to s = sn, and the ingredients are:

• Accepted landmarks: Acc(πs) is the set of all p ∈ L such that either p ∈ Acc(〈s0, . . . , sn-1〉), or p ∈ s and for all q that are transitively ordered before p we have q ∈ Acc(〈s0, . . . , sn-1〉).

We adapt this definition to lifted landmarks P(u1, . . . , uk) simply by replacing state-membership tests "p ∈ s?" with tests checking whether there exists a ground atom p of P(u1, . . . , uk) so that p ∈ s.

• Required-again landmarks: Req(πs) is the set of all p ∈ L \ s where either p ∈ G ∪ (L \ Acc(πs)) or p is ordered p →D q directly before q ∈ Req(πs).

Analogously we extend the definitions to lifted disjunctive action landmarks Li by replacing the state-membership test with a check whether the grounded operator used to reach s is an instantiation of one of the actions in Li.

Observe that, thanks to the definition of Req(πs), the resulting heuristic function dominates goal counting.

We extend the search of PWL to a LAMA-like approach [Richter and Westphal, 2010], i.e., to a multi-queue heuristic search. It uses two heuristics to guide the search, in our case hLM and the lifted hLadd [Corrˆea et al., 2021]. To exploit the strength of both heuristics, separate open lists are maintained. Whenever a new state is expanded, it is evaluated with both heuristics and added to both queues. Further, each heuristic has a preferred-operator queue into which states are added if they are reached applying a preferred operator.

Preferred operators are a concept used by certain heuristic functions (e.g. the FF system [Hoffmann and Nebel, 2001]): they return actions that are promising to lead towards a goal state, e.g. because they have been included in the relaxed plan (in case of FF). This concept is also used by the currently best-performing lifted heuristic [Corrˆea et al., 2021] and it is a main reason for its performance. For LM COUNT, we consider an operator to be preferred if a new landmark is fulfilled in the resulting state. When choosing the next state to be expanded, the search decides between the queues based on a numeric priority. All queues initially have a priority of 0, after a state is removed from a queue, its priority is decreased by 1. Whenever a state drawn from a preferred operator queue has a better heuristic estimate than all previous states, the priority of all preferred operator queues is increased by 1000, increasing the use of preferred operators.

5 Experiments

We implemented our heuristics in the Power Lifted (PWL) planner [Corrˆea et al., 2020] 2 . All configurations use greedy best first search (GBFS). We compare against goal counting (hGC), the lifted add heuristic with (hLadd po) and without (hLadd ) preferred operators [Corrˆea et al., 2021] and the bestperforming configurations of Lauer et al. [2021], goal count using unary relaxation heuristic as tiebreaker, with (hGC,ur-d ) and without (hGC,ur ) disambiguation of static predicates. hLadd computes the add heuristic based on the lifted model and might need runtime exponential in the size of the lifted input model. hGC,ur splits the original predicates from the domain in 1-ary predicates before heuristic calculation, resulting in a computation in polynomial time. Like ours, these heuristics are implemented in PWL.

2 The code can be found at: https://github.com/minecraft-saar/ powerlifted

For our system we included 8 configurations: We combine necessary subgoal landmarks with GBFS to the configurations hLNS→ and hLNS ; where the former uses landmark ordering information and the latter does not. The same is done for the FAM landmarks, denoted hLFAM→ and hLFAM . Then, we also use the LAMA-style search instead of GBFS, resulting in the configurations hLNS LAMA , hLNS→ LAMA , hLFAM LAMA , and hLFAM→ LAMA .

We further report results for the grounded Fast Downward (FD) system [Helmert, 2006] with the goal counting and hFF [Hoffmann and Nebel, 2001] heuristics. The experiments were run on a cluster of machines with Intel Xeon E5-2650 CPUs with a clock speed of 2.30GHz.Timeout and memory limits were set to 30 min and 4GB respectively for all runs.

We use the benchmark set used by Lauer et al. [2021] that was introduced to evaluate lifted planners. It explores different reasons for being hard to ground: large action-schema arity, large predicate arity, and large object universe.

Table 1 gives the coverage results. Of our new lifted landmark heuristics, configurations using the FAM landmarks perform slightly worse than necessary subgoals. The LAMAlike search (hLNS LAMA and hLNS→ LAMA ) drastically improves performance compared to simple goal counting, especially for the necessary subgoal landmarks. The resulting systems reach the highest overall coverage in our experiments.

The ordering constraints of landmarks do not improve coverage, we attribute this to the overhead generated by their tracking and the fact that the orderings that are produced as a byproduct of the landmark extraction methods are only very basic. When comparing against hLadd po, we can see that the landmarks heuristics on their own fall behind. But the LAMA-style search outperforms both the hLadd po and the other landmark heuristics. The performance gain can especially be seen in the domains Childsnack and Rovers.

The unary relaxation heuristics hUR and hUR-d perform best on problems with high predicate arity, but worse on the others, especially those with large object universe.

The scatter plots presented in Figure 2 (left and middle) compare the runtime of the LAMA search to hLadd po. It can be seen that the usage of both kinds of landmarks systematically decreases the runtime. The same holds when comparing expanded search nodes (Fig. 2 (right) compares hLNS LAMA and hLadd po).

Compared to the runtime of the planner, the time spend for landmark generation is small. For the necessary subgoal landmarks, the mean generation time per domain is below 100ms (with a variance of less than 200ms) for all domains except for those with large object universes. Among these, generation in the Rovers domain takes the longest with a mean generation time of 550ms and a variance of 40ms. Among the FAM-Cut Landmarks the mean generation time is generally about 200ms with a variance of up to 40ms, with Rovers again being the exception. Here the mean generation time is 2.7 seconds with a variance of 3.5 seconds, with the longest generation taking 7.5 seconds.

6 Conclusion

Lifted heuristic search planning has been neglected but is currently taking up speed. Landmarks are a natural candidate for the design of heuristics in this setting, and our results clearly show their promise. We presented two methods to extract landmarks from the lifted planning model. While their usage in simple landmark count heuristics performs worse than the currently best-performing lifted heuristics, our evaluation shows that they are especially valuable when combined with the lifted add heuristics to a system similar to the grounded LAMA planning system. The resulting system outperforms all other configurations in our evaluation.

Acknowledgements

Gef¨ordert durch die Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 232722074 - SFB 1102 / Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project-ID 232722074 - SFB 1102