--- title: "Landmark Heuristics for Lifted Classical Planning" authors: - "Julia Wichlacz" - "Daniel Höller" - "Jörg Hoffmann" doi: "10.24963/ijcai.2022/647" url: "https://ijcai.org/proceedings/2022/647" pdf: "https://ijcai.org/proceedings/2022/0647.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "4665-4671" track: "Main Track" keywords: - "Planning and Scheduling: Planning Algorithms" - "Planning and Scheduling: Search in Planning and Scheduling" --- # Landmark Heuristics for Lifted Classical Planning Julia Wichlacz, Daniel Höller, Jörg Hoffmann *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 4665-4671. DOI: [10.24963/ijcai.2022/647](https://doi.org/10.24963/ijcai.2022/647) ## Abstract While state-of-the-art planning systems need a grounded (propositional) task representation, the input model is provided "lifted", specifying predicates and action schemas with variables over a finite object universe. The size of the grounded model is exponential in predicate/action-schema arity, limiting applicability to cases where it is small enough. Recent work has taken up this challenge, devising an effective lifted forward search planner as basis for lifted heuristic search, as well as a variety of lifted heuristic functions based on the delete relaxation. Here we add a novel family of lifted heuristic functions, based on landmarks. We design two methods for landmark extraction in the lifted setting. The resulting heuristics exhibit performance advantages over previous heuristics in several benchmark domains. Especially the combination with lifted delete relaxation heuristics to a LAMA-style planner yields good results, beating the previous state of the art in lifted planning. ## Full text ## 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. Figure 1: Lifted DTG generated based on a FAM group. When building the graph, we check whether static preconditions of actions fully determine the value of a variable and set such values (here: the capacity in the actions). ![Image](https://ijcai.org/proceedings/2022/fulltext/647/image_000000_5b839c908d49d039a8fc1f4cebb1a0faff253fb46740cba46e8b614f2ef4302f.png) 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 Table 1: Coverage results (best results highlighted in boldface). hLNS and hLNS→ are the LM heuristics based on necessary subgoals, without vs. with ordering relations; hLFAM and hLFAM→ are based on FAM-Cuts, without vs. with ordering relations; Heuristics annotated with LAMA use a LAMA style search. |AO |and |P O |show average grounding size for those instances that can be grounded (#ground). | max. - P A |AO | |P O | hGC hFF hUR | ar- - ity | #ground | | Grounded (FD) | Grounded (FD) | Grounded (FD) | Grounded (FD) | hLadd | hLadd po | | hUR-d | hGC | Lifted hLFAM→ | Lifted hLFAM→ - hLNS | Lifted hLFAM→ - hLNS→ | Lifted hLFAM→ - hLNS | Lifted hLFAM→ - LAMA LAMA | Lifted hLFAM→ - hLNS→ | Lifted hLFAM→ - hLFAM | Lifted hLFAM→ - hLFAM→ | Lifted hLFAM→ - hLFAM | Lifted hLFAM→ - hLFAM | Lifted hLFAM→ - hLFAM | Lifted hLFAM→ - hLFAM | Lifted hLFAM→ - hLFAM | Lifted hLFAM→ - hLFAM | Lifted hLFAM→ - hLFAM | |----------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------|---------------------|--------------------------------------------------------|-------------------------------|-------------------------------------------------------------|---------------------|---------------------|---------------------------|----------------------------------|-------------|-------------------------|-----------------------------|--------------------|--------------------------|----------------------------|-----------------------------------|----------------------------------|----------------------------|-------------------------|--------------------------|----------------------------------|-------------------------|-------------------------|-------------------------|-------------------------|----------------------------|-------------------------| | (a) Large action schema arity | | | | | | | | | | | | | | | | | | | | | LAMA | | | | | LAMA | | | ged (156) 2 | | 3 | 156 | 32585 1206 | 32585 1206 | 156 | 62 | 92 | 137 | 156 | | 156 | 156 | 156 | 146 | 150 125 | 155 | 155 | 142 | | 141 | 141 | 141 | 141 | 141 | 141 | 141 | | ged-split (156) 2 2 | | 156 | | 4602 734 | 4602 734 | 156 | 35 | 24 | 102 | 156 | | 156 | 156 | 154 | 110 | 141 | 82 155 | 149 | 133 | | 116 | 116 | 116 | 116 | 116 | 116 | 116 | | organic-synthesis-alk (18) organic-synthesis-mit (18) | 2 16 | | 15 | 24475 74 | 24475 74 | 15 | 15 2 | 18 | 18 | 18 18 | | 18 18 | 18 18 | 18 18 | 18 18 | 18 | 18 12 18 13 | 12 13 | 12 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | | organic-synthesis-org (20) | 2 2 31 | 31 | 2 1 | 2946 36 | 2946 36 | | 2 1 | 18 8 | 18 11 | 9 | 9 | | 10 | 10 | 10 | 18 10 | 10 6 | 6 | | 7 | 12 7 | 12 7 | 12 7 | 12 7 | 12 7 | 12 7 | 12 7 | | pipesworld (50) | 3 12 | 16 | 119907 | 137784 806 232 | 137784 806 232 | 1 16 | 13 | 20 | 24 | 12 | 11 | | 22 | 20 | 20 | 32 | 30 19 | 17 | | 29 | 26 | 26 | 26 | 26 | 26 | 26 | 26 | | Sum (418) 346 346 128 180 310 369 368 380 376 375 369 283 360 352 336 315 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (b) Large predicate arity: Visitall and Childsnack | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 3-dim-close-g1 (10) | 3 | 4 | 140832 48386 | 140832 48386 | | 7 | 7 | 10 | 10 | 10 | 10 | 8 | | 8 | 8 10 | 10 | | | | | | | 8 | 8 | 10 | 10 | 10 | | 3-dim-close-g2 (10) | 3 | 4 | 7 | 7 | | 7 | 7 | 8 | 9 | 9 | 9 | | 6 | 5 | 5 | 9 | | 5 | 5 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | | 3-dim-close-g3 (10) | 3 | 4 | 7 140832 48388 7 140832 48390 | 7 140832 48388 7 140832 48390 | | 7 | 7 | 8 | 10 | 9 | 9 | | 7 | | 7 | 7 | 9 | 9 9 | 5 | 5 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | | 3-dim-far-g1 (10) | 3 | 4 | 7 140832 | 7 140832 | 48386 | 7 | 7 | 9 | 10 | 1 | 10 | 0 | | 0 | 0 | 10 | 10 0 | 10 | | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | | 3-dim-far-g2 (10) | 3 | 4 | 7 140832 | 7 140832 | 48388 | 7 | 7 | 7 | 10 | | 2 | 7 | 0 | 0 | 0 | 0 | 8 | | 9 | 0 | | | | 8 | 0 | 8 | 9 | | 3-dim-far-g3 (10) | 3 | 4 | 7 140832 | 7 140832 | 48390 | 7 | 7 | 6 | 8 | 2 | 6 | 0 | | | | 0 8 | 8 | 0 | 0 | 10 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | | 4-dim-close-g1 (10) 4-dim-close-g2 (10) | 4 4 | 5 5 | 3 122005 | 3 122005 | 33143 33145 | 3 3 | 3 3 | 10 9 | 10 10 | 10 10 | 10 10 | 6 | 8 | 6 | 8 | 6 10 8 | 10 10 | 6 8 | 6 8 | 10 | 10 10 | 10 10 | 10 10 | 10 10 | 10 10 | 10 10 | 10 10 | | 4-dim-close-g3 (10) | 4 | 5 | 3 122005 3 122005 | 3 122005 3 122005 | 33147 | 3 | 3 | 7 | 9 | | 7 | 6 5 | | | 5 | 5 | 9 9 | 10 | 5 | | 9 9 | 5 | 5 | 5 | 5 | 5 | 5 | | 4-dim-far-g1 (10) | 4 | 5 | 122005 33143 | 122005 33143 | | 3 | 3 | 4 | 5 | 1 | 10 | 0 | | | 0 | 0 | 6 | | 0 | | | | | 0 0 | 6 3 | 6 | 6 | | 4-dim-far-g2 (10) | 4 | 5 | 3 3 122005 33145 | 3 3 122005 33145 | | 3 | 3 | 3 | 5 | 2 | 7 | | 0 | 0 | | 0 | | 6 3 | | 3 | | 0 | 3 | 3 | 3 | 3 | 3 | | 4-dim-far-g3 (10) 5-dim-close-g1 | 4 5 | 5 6 | 3 122005 2 | 3 122005 2 | 33147 | 3 | 3 2 | 3 | 4 | 2 10 | 4 | 0 10 | 9 | 0 9 | 0 9 | 3 10 | 3 | 0 | | 10 | 3 | | 0 9 | 9 | 10 | 4 10 | 4 10 | | 5-dim-close-g2 (10) | (10) 5 5 | 6 | 2 | 2 | 175760 40546 175760 40548 | 2 | 2 2 | 10 7 | 10 10 | 9 | 8 | 7 | | 6 | 6 | | 10 | 10 | | | | 5 8 | 5 | 10 | | 10 | 10 | | 5-dim-close-g3 (10) | | 6 | 2 175760 | 2 175760 | 40550 | 2 | 2 2 | | 10 | 10 | 9 10 | | 8 | 8 | | 8 | | 10 | 8 | 0 | 4 | 10 | 10 | 10 | 10 | 10 | 10 | | 5-dim-far-g1 (10) | 5 | 6 | 2 175760 | 2 175760 | 40546 | 2 | | | 9 3 | 4 | 2 | 0 | | | 0 | 0 | 10 | 4 | 4 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | | 5-dim-far-g2 (10) 5-dim-far-g3 (10) | 5 | 6 | 2 | 2 | 175760 40548 | 2 40550 2 | 2 2 | 2 2 | 4 4 | 2 2 | 6 6 | 0 0 | 0 | 0 | | 0 | 3 | 3 | 3 | | 3 | 0 0 | 0 0 | 3 | 3 | 3 | 3 | | Visitall Sum (180) | 5 | 6 5 6 | 2 175760 72 141947 | 2 175760 72 141947 | | 44039 72 | 72 | 117 | 142 | | 100 147 | 64 | | 62 | | 0 62 | 135 | 136 | | 59 | 59 | 136 | 3 136 | 3 136 | 3 136 | 3 136 | 3 136 | | n1-g3 (12) | 2 | 5 | 12 | 12 | 513 | 138 12 | 12 | 12 | | 12 | 12 | 12 | | 12 | 11 | | 11 | 12 | 12 | 12 | 11 12 12 | 12 12 | 12 12 | 12 12 | 12 12 | 12 12 | 12 12 | | n1-g5 (12) n1-g7 (12) | 2 2 | 5 5 | 12 1930 12 | 12 1930 12 | 5011 | 218 298 | 5 12 2 4 | | 4 2 | 12 6 | 12 6 | 12 8 | 2 | 3 | 2 2 | 2 | 2 | 12 2 12 1 | | 12 | 10 | 12 | 12 | 12 | 12 | 10 | 12 | | n2-g3 (12) | 3 | 6 | 12 | 12 | 9758 | 159 | 5 7 | 4 | 12 | | 11 | 12 | 3 | 3 | | 3 | 12 | | 12 | | | | 2 | 2 | 2 | 2 | 2 | | n2-g5 (12) | | | 12 | 12 | 74405 | | 2 2 | | | 3 | 3 | 12 | 1 | 1 | | 6 | 6 | | 0 | | | | 0 | 12 5 | 12 5 | 12 5 | 12 5 | | n2-g7 (12) | 3 3 | 6 6 | 11 | 11 | 232344 | 253 332 | 0 2 | | 2 1 | 2 | 1 | 1 0 | | 0 | | 1 0 | | 2 | 2 | 0 | 0 | | | 2 | 2 | 2 | 2 | | n3-g3 (12) n3-g5 (12) | 4 | 8 | | | 65520 | 273 | 3 5 0 | | 3 | 9 | 6 | 11 6 | 2 0 | 1 | | 1 | | 12 | 1 0 | | 11 | 11 | 11 | 11 | 11 | 11 | 11 | | n3-g7 (12) | 4 4 | 8 8 | 12 7 3 | 12 7 3 | 221398 259615 | 364 363 | 1 0 0 | 1 1 | | 2 1 | 1 0 | 0 | 0 | 0 0 | 0 0 | 12 3 | | 0 0 | 3 0 | 0 0 | 2 0 | 2 0 | 2 0 | 2 0 | 2 0 | 2 0 | 2 0 | | n4-g3 (12) n4-g5 (12) | 5 | 10 | 10 | 10 | 176161 | 819 348 | 0 4 0 | 2 | | 6 1 | 6 11 | 0 0 | | 0 | 0 | 10 | 0 | | 10 | | | 0 0 | | 9 | 0 | 8 | 8 | | n4-g7 (12) | 5 5 | 10 | 1 376905 0 104 | 1 376905 0 104 | - | - | 0 0 | | 0 0 | 0 | 2 | 0 | | | 0 0 | 0 | 0 | | 0 0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | | | 10 | 85659 | 85659 | | | 0 | | 0 66 | 0 | 0 | | | | | 0 | 0 | 81 | | 0 17 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | Childsnack Sum (144) | 5 | 10 | | | 307 | 29 | 49 | 32 | | | 87 | 23 | | 20 | 0 20 | 81 | | 17 | 75 | | | | | | | | | | object blocksworld-g2 (10) 2 blocksworld-g3 | 2 (10) 2 2 | 2 2 | 2 100000 2 | 2 100000 2 | (c) 100000 50602 100000 50602 100000 50602 | Large 50602 1 0 0 0 | 0 1 0 | 1 0 0 | 2 1 | 63 universe | 6 6 0 | 0 0 0 0 | 1 0 0 | 6 | 0 0 | 2 0 1 | 6 0 0 | 8 0 | 2 0 | 2 | 74 2 2 | 74 2 2 | 74 2 2 | 74 2 2 | 74 2 2 | 74 2 2 | 74 2 2 | | blocksworld-g4 (10) blocksworld-g5 (10) logistics-g1 2 logistics-g2 2 logistics-g3 2 logistics-g4 2 rovers-g2 2 rovers-g4 1 rovers-g6 1 rovers-g8 1 Sum 16 Total Sum | 2 (10) 2 (10) 2 (10) 2 (10) 2 (10) 3 (10) 3 (10) 3 (10) 3 (120) (826) | 2 2 4 4 4 4 6 6 6 6 | 2 2 2 1282377 2 1284629 2 1286881 2 1289133 2 1 1 1 21 | | 2252 3379 4506 5633 5316 2531 4041 2006 4983 2026 3753 2965 | 14 461 | 2 2 2 2 2 1 1 1 265 | 0 1 1 0 0 10 1 0 0 14 343 | 1 0 10 10 10 10 10 10 5 4 73 591 | 16 548 | 0 0 0 0 0 0 5 2 2 1 624 | 0 0 0 0 0 0 10 3 2 0 21 487 | 5 5 4 4 1 0 0 0 20 | 0 5 5 4 4 5 2 1 1 32 490 | 0 0 5 5 4 4 5 2 0 0 24 481 | 1 1 10 10 10 10 10 10 10 6 81 666 | 0 0 10 10 10 10 10 10 7 4 71 571 | 0 0 5 5 5 5 5 2 1 1 35 471 | | | 1 1 10 10 10 10 10 10 9 6 81 465 | | 0 0 5 5 5 5 5 2 1 1 37 | | 626 606 | 0 10 10 10 10 10 10 9 6 79 | | ![Image](https://ijcai.org/proceedings/2022/fulltext/647/image_000001_f6f628aaa1478de6024100f81e9377f8cca743a68d540430c4e800a76c8322e9.png) ![Image](https://ijcai.org/proceedings/2022/fulltext/647/image_000002_3f70c934a3f515d46e6d5a7835245eddf5346808c0bce6492c7a595da8584bc8.png) Figure 2: Scatter plots comparing two algorithms. The respective algorithms are given on the axis. The left and middle figures show the runtime and the right figure shows expansions. ![Image](https://ijcai.org/proceedings/2022/fulltext/647/image_000003_5ef3a0c40c22d503c9b465e55ac89dc960988d8f3c98fc466ed9c624abc083c4.png) 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 ## References 1. 2: +at package_0 ?v2) (1: +in package_0 ?v1) (pick_up ?v1 ?v2 package_0 capacity_0 ?v3) (drop ?v1 ?v2 package_0 capacity_0 ?v4) (0: +at package_0 city_loc_1) (pick_up ?v1 city_loc_1 package_0 capacity_0 ?v5) References 2. [Bonet and Geffner, 2001] Blai Bonet and Héctor Geffner. Planning as heuristic search. Artificial Intelligence, 129(1- 2):5-33, 2001. 3. [Corrêa et al., 2020] Augusto B. Corrêa, Florian Pommeren- ing, Malte Helmert, and Guillem Francès. Lifted succes- sor generation using query optimization techniques. In Proceedings of the 30th International Conference on Auto- mated Planning and Scheduling (ICAPS'20), pages 80-89. AAAI Press, 2020. 4. [Corrêa et al., 2021] Augusto B. Corrêa, Florian Pommeren- ing, Malte Helmert, and Guillem Francès. Delete- relaxation heuristics for lifted classical planning. In Pro- ceedings of the 31st International Conference on Auto- mated Planning and Scheduling (ICAPS'21), pages 94- 102. AAAI Press, 2021. 5. [Fišer, 2020] Daniel Fišer. Lifted fact-alternating mutex groups and pruned grounding of classical planning prob- lems. In Proceedings of the 34th AAAI Conference on Ar- tificial Intelligence (AAAI'20), pages 9835-9842. AAAI Press, 2020. 6. [Haslum, 2011] Patrik Haslum. Computing genome edit dis- tances using domain-independent planning. In Proceed- ings of the SPARK Workshop, 2011. 7. [Helmert and Domshlak, 2009] Malte Helmert and Carmel Domshlak. Landmarks, critical paths and abstractions: What's the difference anyway? In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09), pages 162-169. AAAI Press, 2009. 8. [Helmert, 2006] Malte Helmert. The Fast Downward plan- ning system. Journal of Artificial Intelligence Research, 26:191-246, 2006. 9. [Hoffmann and Nebel, 2001] Jörg Hoffmann and Bernhard Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253-302, 2001. 10. [Hoffmann et al., 2004] Jörg Hoffmann, Julie Porteous, and Laura Sebastia. Ordered landmarks in planning. Journal of Artificial Intelligence Research, 22:215-278, 2004. 11. [Hoffmann et al., 2006] Jörg Hoffmann, Stefan Edelkamp, Sylvie Thíebaux, Roman Englert, Frederico Liporace, and Sebastian Trüg. Engineering benchmarks for planning: the domains used in the deterministic part of IPC-4. Journal of Artificial Intelligence Research, 26:453-541, 2006. 12. [Karpas and Domshlak, 2009] Erez Karpas and Carmel Domshlak. Cost-optimal planning with landmarks. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), pages 1728-1733, 2009. 13. [Koller and Hoffmann, 2010] Alexander Koller and Jörg Hoffmann. Waking up a sleeping rabbit: On natural- language sentence generation with FF. In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10), pages 238-241. AAAI Press, 2010. 14. [Koller and Petrick, 2011] Alexander Koller and Ronald Pet- rick. Experiences with planning for natural language gen- eration. Computational Intelligence, 27(1):23-40, 2011. 15. [Lauer et al., 2021] Pascal Lauer, Álvaro Torralba, Daniel Fiser, Daniel Höller, Julia Wichlacz, and Jörg Hoffmann. Polynomial-time in PDDL input size: Making the delete relaxation feasible for lifted planning. In Proceedings of the 30th International Joint Conference on Artificial Intel- ligence (IJCAI'21), pages 4119-4126. IJCAI org., 2021. 16. [Matloob and Soutchanski, 2016] Rami Matloob and Mikhail Soutchanski. Exploring organic synthesis with state-of-the-art planning techniques. In Proceedings of the SPARK Workshop, pages 52-61, 2016. 17. [Penberthy and Weld, 1992] J. Scott Penberthy and Daniel S. Weld. UCPOP: A sound, complete, partial order planner for ADL. In Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Confer- ence (KR'92), pages 103-114. 18. Morgan Kaufmann, 1992. 19. [Richter and Westphal, 2010] Silvia Richter and Matthias Westphal. The LAMA planner: Guiding cost-based any- time planning with landmarks. Journal of Artificial Intel- ligence Research, 39:127-177, 2010. 20. [Richter et al., 2008] Silvia Richter, Malte Helmert, and Matthias Westphal. Landmarks revisited. In Proceedings of the 23rd National Conference of the American Associa- tion for Artificial Intelligence (AAAI'08), pages 975-982. AAAI Press, 2008. 21. [Ridder and Fox, 2014] Bram Ridder and Maria Fox. Heuristic evaluation based on lifted relaxed planning graphs. In Proceedings of the 24th International Confer- ence on Automated Planning and Scheduling (ICAPS'14), pages 244-252. AAAI Press, 2014. 22. [Russell and Norvig, 1995] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 1995. 23. [Seipp, 2019] Jendrik Seipp. Pattern selection for optimal classical planning with saturated cost partitioning. In Pro- ceedings of the 28th International Joint Conference on Ar- tificial Intelligence (IJCAI'19, pages 5621-5627, 2019. 24. [Younes and Simmons, 2003] Håkan L. S. Younes and Reid G. Simmons. VHPOP: versatile heuristic partial or- der planner. Journal of Artificial Intelligence Research, 20:405-430, 2003.