Cost-Optimal Planning with Landmarks

1 Introduction

Landmarks for deterministic planning are (possibly logically compound) facts that must take place at some point in every plan for a given planning task [Porteous et al., 2001; Porteous and Cresswell, 2002; Hoffmann et al., 2004]. For example, if a goal in a Blocksworld task is to have block A stacked on block B, and initially this does not hold, then clear(B) must hold at some point for the goal to be achieved, and thus it is a landmark for that task. Goals are trivially landmarks, and thus on(A,B) is a landmark as well. We can also infer that clear(B) must be achieved before stacking A on B, establishing an ordering between these two landmarks.

The two issues with planning landmarks are how to discover them, and how to exploit them. Even for propositional landmarks only, sound and complete discovery of all such landmarks is known to be PSPACE-complete [Porteous et al., 2001]. Still, many landmarks can often be efficiently discovered, e.g., by a polynomial time reasoning over relaxed planning graphs [Hoffmann et al., 2004], and/or domain transition graphs of multi-valued state variables [Richter et al., 2008].

Once discovered, landmarks can be extremely helpful in guiding the search for a plan. In particular, Hoffmann et al. [2004] suggest a local-search procedure that iteratively searches for sub-plans to landmarks "needed earliest", and this instead of searching directly for a plan to the problem's goal. An empirical evaluation by the same authors has shown a substantial speed-up compared to the otherwise identical planner that does not use landmarks. However, the higher greediness of this approach typically results in longer plans, and the iterative search for subgoals may sometimes lead to incompleteness of otherwise complete planners [Hoffmann et al., 2004]. Recently, Richter et al. [2008] proposed a novel way of using a set of landmarks as a pseudo-heuristic within a satisficing heuristic search. This technique allowed both reducing the length of the generated plans, as well as improving success rate both with respect to the iterative approach of Hoffmann et al., and with respect to other stateof-the-art satisficing planners. In particular, the LAMA planner by Richter and Westphal utilizing such a landmarks-based heuristic search was the clear winner of the Sequential Satisficing Track at the 2008 International Planning Competition.

In this work, we depart from satisficing planning, and consider planning landmarks through the lens of cost-optimal planning needs. We suggest a method for deriving admissible estimates from a set of planning landmarks, with its instances varying from easy to compute, to, in some sense, optimally accurate. The resulting heuristics are what we call multi-path dependent. We present a simple best-first search that exploits such heuristics, and finds optimal solutions more efficiently than standard A∗ . Experimentally, we show that our heuristics paired with the suggested best-first search procedure are at the state-of-the-art of cost-optimal heuristic search planning, and also offer an unprecedented scalability of the estimate's accuracy in the size of the planning tasks.

2 Notation and Background

We consider planning in the SAS+ formalism [B¨ackstr¨om and Nebel, 1995]; a SAS+ description of a planning task can be automatically generated from its PDDL description [Helmert, 2009]. A SAS+ task is given by a 5-tuple Π = 〈V, A, s0, G, C〉. V = {v1, . . . , vn} is a set of state variables, each associated with a finite domain dom(vi), where (assuming name uniqueness) the union of the variable domains F = ⋃i dom(vi) is the set of facts . Each complete assignment s to V is called a state; s0 is an initial state, and the goal G is a partial assignment to V . A is a finite set of actions, where each action a is a pair 〈pre(a), eff(a)〉 of partial assignments to V called preconditions and effects, respectively. Each action a ∈ A has a non-negative cost C(a).

An action a is applicable in a state s ∈ dom(V ) iff pre(a) ⊆ s, and applying such a changes the value of each state variable v to eff(a)[v] if eff(a)[v] is specified. The resulting state is denoted by sllbracketarrbracket; by sllbracket〈a1, . . . , ak〉rrbracket we denote the state obtained from sequential application of the (respectively applicable) actions a1, . . . , ak starting at state s. Such an action sequence is a plan if G ⊆ sllbracket〈a1, . . . , ak〉rrbracket.

Let Π = 〈V, A, s0, G, C〉 be a planning task, φ be a propositional logic formula over facts F, π = 〈a1, . . . , ak〉 be an action sequence applicable in s0, and 0 ≤ i ≤ k. Following the terminology of Hoffmann et al., we say that φ is true at time i in π iff s0llbracket〈a1, . . . , ai〉rrbracket |= φ, φ is first added at time i in π iff φ is true in π at time i, but not at any time j < i, and φ is a landmark of Π iff in each plan for Π, it is true at some time. In addition to knowing landmarks, it is sometimes useful to know in which order they should be achieved on the way to the goal. Hoffmann et al. define different types of potentially useful orderings. In particular, landmark φ is said to be greedy-necessarily ordered before landmark ψ iff, for each action sequence applicable in s0, if ψ is first added in π at time i, then φ is true in π at time i - 1.

While landmarks can be any formulas over facts, we restrict our attention to disjunctions of facts, and use notation φ ⊆ F to denote "disjunction over the fact subset φ of F". This restriction covers all the landmark discovery procedures suggested in the literature. Porteous et al. show that deciding if just a single fact is a landmark, as well as deciding an ordering between two fact landmarks, are PSPACE-complete problems. Therefore, practical methods for finding landmarks are either incomplete or unsound. In what follows we assume access to a sound such procedure; in particular, in our evaluation we use LAMA's sound landmark discovery procedure, introduced by Richter et al. [2008]. The actual way of discovering landmarks and orderings is tangential to our contribution. Hence, in what follows we assume that a planning task Π is simply given to us with a landmark structure 〈L, Ord〉, where L is a set of Π's landmarks, and Ord is a set of typed orderings over L, containing, in particular, the greedy-necessary ordering over L.

3 Admissible Landmark Heuristics

Deriving heuristic estimates from landmarks has been proposed by Richter et al. [2008] who estimate the goal distance of a state s, reached via a sequence of actions π from the initial state, by the number of landmarks L(s, π) yet to be achieved from s onwards. Specifically, if the search starts with the landmark structure 〈L,Ord〉, then

where Accepted(s, π) ⊆ L and ReqAgain(s, π) ⊆ Accepted(s, π) are the sets of accepted and required again landmarks, respectively. A landmark is accepted if it is true at some time along π. An accepted landmark is required again if (i) it does not hold in s, and (ii) it is ordered greedynecessarily before some landmark which is not accepted.

The estimate |L(s, π)| is not a proper heuristic in the usual sense, but rather path-dependent; it is a function of both an evaluated state s, and a path from s0 to s. However, |L(s, π)| can still be used like a state-dependent heuristic in best-first search. In particular, combined with some other helpful techniques, it has been successfully used by the LAMA planner at the Sequential Satisficing Track of the IPC-2008 competition.

3.1 Action Cost Sharing by Landmarks

It is not hard to verify that the estimate |L(s, π)| is not admissible. For instance, in a Blocksworld task, let L(s, π) = {crane-empty, on(A,B)}. While |L(s, π)| = 2, it is possible a single action stack(A,B) reaches the goal from s. However, below we show that the gap between the estimate |L(s, π)| and admissibility is not that hard to close.

Considering the landmarks through the actions that can possibly achieve them, let cost(φ) be a cost assigned to each landmark φ, and cost(a, φ) be a cost "assigned" by the action a to φ. Suppose also that these (all non-negative) costs satisfy

where each action subset ach(φ|s, π) ⊆ A (in particular) contains all the actions that can possibly be used to directly achieve landmark φ along a goal-achieving suffix of π, and, reversely, L(a|s, π) = {φ | φ ∈ L(s, π), a ∈ ach(φ|s, π)}. Informally, Eq. 2 enforces partitioning of each action cost among the landmarks this action can possibly establish, and verifies that the cost of each landmark φ is no greater than the minimum cost assigned to φ by its possible achievers. The set ach(φ|s, π) ⊆ A for a disjunctive landmark φ can be simply estimated by the set of all actions achieving some element of φ. In our evaluation we use the (initial-state dependent and efficiently computable) set of "possible", and its subset of "first-time possible", achievers of φ [Porteous and Cresswell, 2002]. If φ ̸∈ Accepted(s, π), then we set ach(φ|s, π) to the first-time possible achievers of φ, and otherwise to the possible achievers of φ. In any event, action cost sharing is all we need to derive from L(s, π) an admissible estimate of the goal distance.

Proposition 1 Given a set of action-to-landmark and landmark costs satisfying Eq. 2, hL(s, π) = cost(L(s, π)) = ∑φ∈L(s,π) cost(φ) is an admissible estimate of the goal distance h∗ (s).

The (simple) proof is omitted due to space constraints. Proposition 1 leaves the choice of the actual action-cost partitioning open. The most straightforward choice here is probably uniform cost sharing in which each action partitions its costs equally among all the landmarks it can possibly achieve, that is, cost(a, φ) = C(a)/|L(a|s, π)|. The advantage of such a uniform cost sharing is the efficiency of its computation. However, the induced action-cost partition can be sub-optimal. For instance, consider a planning task with a landmark set {p1, . . . , pk , q} such that the only possible achiever of each pi is a unit-cost action ai with eff(ai) = {pi , q}. For 1 ≤ i ≤ k, the uniform cost sharing assigns here cost(ai , pi) = cost(ai , q) = 0.5, which gives cost(pi) = cost(q) = 0.5, and thus hL(s, π) = k/2 + 0.5. In contrast, the optimal cost sharing would assign, for all 1 ≤ i ≤ k, cost(ai , pi) = 1 and cost(ai , q) = 0, implying cost(pi) = 1, cost(q) = 0, and thus hL(s, π) = k.

The good news, however, is that such an optimal cost sharing can be computed in poly-time by (i) compiling Eq. 2 into strictly linear constraints by a trivial elimination of the minimization, and (ii) solving a linear program induced by these constraints and the objective max ∑φ∈L(s,π) cost(φ). In addition, this cost sharing scheme alleviates an annoying shortcoming of ad hoc (e.g., uniform) cost sharing schemes, and satisfies monotonicity along the inclusion relation of the landmark sets L(s, π). It is not hard to verify that, for any two sets of landmarks L and L′ such that L ⊆ L′ , the LP-based cost sharing ensures cost(L′ ) ≥ cost(L) by the very virtue of being optimal, and thus yields at least as informative heuristic estimate with L′ as with L. This property is appealing as it allows separating landmark discovery and landmark exploitation without any loss of accuracy, leaving the phase of discovery with the simple principle of "more landmarks can never hurt". In contrast, the simple yet ad hoc uniform cost sharing cannot guarantee such monotonicity. For instance, the uniform cost sharing in the example above but without landmark q yields hL(s, π) = k, while with q it results in hL(s, π) = k/2 + 0.5.

3.2 Action Landmarks

The LP-based "admissibilization" of the landmark sets L(s, π) is optimal, but this, of course, only when the landmark costs are estimated with respect to solely Eq. 2. Any additional information about landmarks may help improving the accuracy of the estimate. One type of such information corresponds to action landmarks [Zhu and Givan, 2004; Vidal and Geffner, 2006]. Similarly to landmarks over facts, an action a is an action landmark of a planning task Π iff it is taken along every plan for Π. A sufficient and efficiently testable condition for a being an action landmark is that a relaxed planning task without a is not solvable.

Now, let U(s, π) be a set of pre-discovered action landmark that were not used along the path π to the evaluated state s. By the definition of landmarks, we know that all these actions must occur at some time after s, and thus we should account for their cost in the heuristic estimate of (s, π). A simple way of incorporating this information into the cost sharing mechanism as above is what we call action landmark covering: First, sum up the cost of all the unused action landmarks U(s, π), then remove from the landmark set L(s, π) all the landmarks achievable by the actions in U(s, π), and only then perform the regular action cost sharing over the remaining landmarks. The resulting heuristic estimate is hLA(s, π) = cost(LU(s, π)) + ∑a∈U(s,π) C(a), where LU(s, π) = L(s, π) \ ⋃a∈U(s,π) L(a|s, π), and cost(LU(s, π)) is computed using a cost sharing as in Eq. 2.

Proposition 2 Given a planning task, a set of its landmarks, and a set of its action landmarks, for any state s, and any path π to s, we have hLA(s, π) being an admissible estimate of the goal distance h∗ (s), dominating hL(s, π) under any admissible cost sharing scheme as in Eq. 2.

The intuition behind the (only technically tedious) proof is that Eq. 2 implies C(a) ≥ cost(L(a|s, π)), and thus enforcing a to be the only achiever of L(a|s, π) can only increase the overall estimate. The admissibility follows from a being an action landmark.

Action landmark covering of hLA(s, π) is especially helpful when practical considerations of reducing per-search-node computations force us to give up on the more accurate yet relatively costly LP-based cost sharing, and settle for a low cost, ad hoc cost sharing scheme such as the uniform one. In such cases, the main benefit of action landmark covering may actually happen to be indirect. For instance, consider our running example with a landmark set {p1, . . . , pk , q} such that the only achiever of each pi is a unit-cost action ai with eff(ai) = {pi , q}. In Section 3.1 we show that the uniform cost sharing results in hL(s, π) = k/2 + 0.5. However, if an action ai is known to be an action landmark, then the cost sharing for hLA(s, π) is performed only over LU(s, π) = {p1, . . . , pi-1, pi+1, . . . , pk}, providing us with cost(LU(s, π)) = k - 1, and thus hLA(s, π) = k. In other words, the action landmark covering may contribute not only via full accounting for the action landmark costs, but also via indirect elimination of some "action cost eroders" such as the landmark q in our example. This example actually is not just schematic as, e.g., a very much similar picture occurs with the crane-empty landmark in Blocksworld tasks. Later we empirically illustrate that the impact of action landmark covering appears substantial in many domains.

4 FromPath toMulti-Path Dependence

Let us now return to the definition of the path-dependent set L(s, π) in Eq. 1. Both LAMA's heuristic |L(s, π)|, and the admissible heuristics hL and hLA, exploit information provided by the path π to better estimate the goal distance from s. Suppose now that we are given a set of paths from s0 to s; such a set of paths can in particular be discovered anyway by any systematic, forward-search procedure. Proposition 3 shows that such a set of paths can be much more informative than any of its individual components.

Proposition 3 Let Π be a planning task with a landmark set L, s be a state of Π, P be a set of paths from s0 to s, and πg be a goal achieving path from s. For each path π ∈ P:

1. πg achieves all landmarks in L \ Accepted(s, π).

2. πg applies all actions in U(π, s).

The proof is straightforward: Assume a landmark φ is achieved by a path π ∈ P but not by a path π′ ∈ P. The latter implies that all the extensions of π′ should still achieve φ, and the extensions of π′ are exactly the extensions of π. The same argument applies with unused action landmarks.

Proposition 3 immediately leads to multi-path dependent versions of hL and hLA. Given a set of landmarks L, and a set of paths P from s0 to s, let

where Accepted(s,P) = ⋂π∈P Accepted(s, π), and ReqAgain(s,P) ⊆ Accepted(s,P) is specified as before by s and the greedy-necessary orderings over L. Given that, the multi-path dependent versions of hL and hLA straightforwardly reflect their path-dependent counterparts as

The improvement in accuracy in switching to multi-path landmark heuristics can be substantial. For instance, if we have access to two paths to s, each suggesting that half of the landmarks have been achieved, yet they entirely disagree on the identity of the achieved landmarks, then the estimate of the (still admissible) multi-path dependent heuristic might be twice as high as this of the path-dependent heuristic.

Finally, utilizing multi-path dependent estimates for optimal search requires adapting the standard A∗ search procedure. In fact, a slight adaptation of A∗ is desirable even in case of such path-dependent heuristics. Designed for statedependent estimates, A∗ computes h(s) for each state s only when s is first generated. This will still guarantee optimality with path-dependent estimates as well, yet, if π and π′ are the current and a new discovered paths from s0 to s, respectively, then we may have h(s, π′ ) > h(s, π). That is, a new discovered path may better inform us about the goal distance from s. We can slightly modify A∗ to compute the heuristic value each time a new path to a state is discovered, and utilize the highest estimate discovered so far. This, of course, preserves search admissibility, and potentially reduces the number of expanded nodes. Note that this does not contradict "optimal efficiency" of the basic A∗ as the latter holds only for monotonic, state-dependent heuristics [Dechter and Pearl, 1985].

The modification of A∗ for multi-path dependent heuristics is very much similar in spirit. Each time a new path to state s is discovered, it is stored in the list of such paths P(s), and h(s,P(s)) is evaluated. Of course, storing all paths to s is generally infeasible, and the algorithm is usable only in cases where the relevant information carried by P(s) can be captured and stored compactly. In fact, the adaptation of A∗ to path-dependent heuristics as above constitutes such a special case of all the relevant information of a set of paths being the maximal value of the heuristic estimates induced by them individually. Nicely, the multi-path dependent landmark heuristics hL and hLA also constitute a usable special case as above. In our variant of A∗ , referred later as LM-A∗ , we associate each state s with the landmark sets L(s,P(s)) and U(s, P(s)) as in Eq. 3. When a new path π to s is discovered (and extends P(s)), the respective sets are incrementally updated to L(s, P(s)∪{π}) and U(s, P(s)∪{π}) by exploiting the monotonicity of the union and intersection set operators.

5 Experimental Evaluation

Encouraging results obtained with landmark-based heuristics in satisficing planning do not necessarily imply that optimal search with landmark-based heuristics will also work well in practice. To evaluate the practical usefulness of the constructs presented above, we implemented both our admissible heuristics and the LM-A∗ search procedure on the infrastructure of the Fast Downward planner [Helmert, 2006], and used the landmark discovery of LAMA [Richter et al., 2008]. We conducted an empirical study on a wide sample of planning domains from the international planning competitions 19982006. All experiments were run on 3GHz Intel E8400 CPU; the time and memory limits were 30 minutes and 1.5 GB. The reported times do not include the PDDL to SAS+ translation as it is common to all planners, and is tangential to the issues considered in our study.

There are three issues on the agenda of our study. First, we evaluate the marginal contributions of both action landmark covering and using LM-A∗ , that is, hLA vs. hL, and LM-A∗ vs. A∗ . Here we focus on the hLA heuristic based on the uniform cost sharing. While it is potentially less informative than hLA under the LP-based cost sharing, our implementation of the latter was too costly to be applied at every search node under the time limit of 30 minutes. Moreover, our selective tests indicated that, while LP-based cost sharing substantially improves the accuracy of hL, its contribution to action-landmark-covering hLA is typically insignificant. (In Section 3.2 we discuss the key reason for that.)

The left part of Table 1 (up to and including the shaded column LM-A∗ +hLA) compares LM-A∗ using hLA with both A∗ using the same heuristic, as well as LM-A∗ using hL. Table 1 depicts the results obtained over BLOCKSWORLD, LOGISTICS, DEPOTS, and SATELLITE, which represent well the picture obtained across all the considered domains. The table lists only tasks that have been solved by one of the planners. Empty entries in the table denote tasks that were not solved by the respective technique. First, note that LM-A∗ with hLA outperforms the standard A∗ using the same heuristic both quantitatively and qualitatively, solving 15%, 43%, and 53% more tasks in BLOCKSWORLD, LOGISTICS, and DEPOTS, respectively. Only in SATELLITE LM-A∗ does not depart far from A∗ . The performance gain from switching within LM-A∗ from hL to the more accurate hLA was also non-negligible: With hLA we were able to solve two more tasks than with hL, with savings in time and the number of expanded nodes per task reaching 70%. Note that there was no difference between hL and hLA in LOGISTICS, but that is not surprising because the SAS+ representation of LOGISTICS is unary-effect, and action landmark covering cannot help in such domains with unitcost actions.

Next we check whether a heuristic planner based on LM-A∗ with hLA is competitive with the state of the art of forwardsearch cost-optimal planning. To answer this question, we perform a comparison to two baseline approaches, namely blind search (A∗ with a heuristic function which is 0 for goal states and 1 otherwise) and A∗ with the hmax heuristic [Bonet and Geffner, 2001]. We also compare to A∗ with "flexible abstraction" (FA) heuristics of Helmert, Haslum, and Hoffmann [2007]. We use FA under the linear abstraction strategy suggested by the same authors, and under two fixed bounds on the size of the abstraction, 104 and 105 . From our literature survey, FA appears to be one of the best-performing forwardsearch planners. To allow a fairly unbiased comparison, all the heuristics were implemented within the same planning system, and our LM-A∗ was implemented on top of the same A∗ implementation.

The right part of Table 1 (from and including the shaded column LM-A∗ + hLA) compares LM-A∗ with hLA with the four referent planners over the same four domains as above. It is clear from the table that hLA substantially outperforms both blind search and hmax, and it is generally competitive with both FA-104 and FA-105 . For a macro picture, Table 2 summarizes our full experimental results for (LM-A∗ with) hLA and (A∗ with) FA-104 over tasks from 18 domains solved by at least one of these two planners. The summary is in terms of the number of solved tasks, as well as the averaged runtime and number of expanded nodes. On 7 domains hLA solved more tasks than FA-104 , on 5 domains it was the other way around, and on 6 domains they solved exactly the same instances. The aggregation of the results in the last line of the table also shows that hLA solved slightly more tasks in total, and (on average) expanded fewer nodes and required less time on tasks solved by both planners. Of course, any empirical results on this or another concrete set of benchmarks should be taken very carefully, without over-interpretation. However, we can certainly observe that our landmarks-based approach favorably competes with the current state of the art for cost-optimal planning.

In the third part of our study we check the promise of hLA beyond the currently solvable tasks. Many possible developments may in the future push the envelope of "what is feasible" in optimal planning, and some of these developments (in, e.g., reducing the amount of symmetry in optimal search) will be tangential to the accuracy of the heuristics in use. In Figure 1 we compare the heuristic values provided by hLA and FA-104 to the initial states of all tasks in BLOCKSWORLD, LOGISTICS, DEPOTS, and SATELLITE. (For many of these tasks, the cost of the optimal solution is currently not even known.) It is not hard to see from the plots that FA-104 is more accurate on the initial states with smaller goal distances; these typically correspond to smaller tasks, and for these, the abstraction of FA-104 usually induces perfect or close to perfect estimates. However, as the goal distance grows, hLA quickly takes over, and substantially dominates FA-104 on the larger tasks. Hence, the scalability of hLA's accuracy appears to be excellent, at least in comparison to the (in itself, very accurate) flexible-abstraction heuristic of FA-104 .

Acknowledgments

The work of both authors is partly supported by the Israel Science Foundation (ISF) grant 890015 and C. Wellner Research Fund. The authors wish to thank Silvia Richter for her assistance with LAMA, and Shaul Markovitch and Malte Helmert for many useful discussions.