Trees of Shortest Paths vs. Steiner Trees: Understanding and Improving Delete Relaxation Heuristics

1 Introduction

Heuristic search using a non-admissible approximation of the optimal solution to the delete relaxation has proven to be one of the most effective methods in planning. Some of the most informative heuristics for the delete relaxation are the additive heuristic [Bonet and Geffner, 2001], the relaxed plan heuristic [Hoffmann and Nebel, 2001], and a recent variant, the setadditive heuristic, which is based on the recursive computation of relaxed plans [Keyder and Geffner, 2008]. Since solving the delete relaxation optimally is an intractable problem, these heuristics introduce independence assumptions: either that the cost of achieving two goals is the sum of the costs of achieving each, or that the relaxed plan for achieving them is the union of the plans for achieving each. While these assumptions make the problem simple and tractable, their implications are not well understood, though they have a critical impact on the performance of planners.

In order to illustrate the impact of the independence assumption, consider the problem shown in Figure 1, where an agent at L0 must perform two tasks t1 and t2, each available at the locations indicated. Clearly, the best plan is to perform t2 at L2 and t1 at L3; moreover, the same plan is best in the delete relaxation. However, no current planning heuristic computes such a relaxed plan. Due to the independence

H´ector Geffner

ICREA & Universitat Pompeu Fabra 08003 Barcelona, SPAIN

hector.geffner@upf.edu

assumption embedded in most estimators, what is computed is the union of the plan for getting to L1 or L3 to perform t1 and the plan for getting to L2 to perform t2. Since these subgoals are achieved independently, the cheaper location L1 is preferred for t1 rather than the more expensive location L3. The result is not just an inaccurate estimate: if the agent can move one unit at a time, it will find that the actions of moving to the left or to the right are both 'helpful', yet that neither results in a state with a lower heuristic value.

The question that we address here is whether a better estimator for the delete relaxation is possible, in particular, one that is not bound by the independence assumption. Optimally solving the delete relaxation h+ is intractable [Bylander, 1994], yet as we will show, other options are available. We will draw on concepts from graph theory to better understand the properties of the approximations to h+ computed by current heuristics, and discuss how these approximations can be improved. We show for example that these heuristics compute the tree-of-shortest-paths approximation to the intractable Steiner Tree Problem (STP), closely related to the Minimum Spanning Tree (MST) problem, while h+ captures the optimal cost. However, a simple criterion for eliminating some non-optimal solutions to the STP can be adapted to the planning setting to give a local iterative improvement algorithm for relaxed plans.

The paper is organized as follows: We first review existing heuristics and consider a planning encoding of the STP. We then use the analysis of this problem to formulate a procedure for improving relaxed plans and test it experimentally over several benchmark domains.

2 Delete-Relaxation Heuristics

We consider planning problems P = 〈F, I, O, G〉 expressed in STRIPS, where F stands for the set of fluents, I,G ⊆ F the initial and goal situations, and O the actions, with precondition, add, and delete lists Pre(a), Add(a), and Del(a) respectively, all of which are subsets of F. For each action a ∈ O, we assume a non-negative cost c(a) so that the cost of a plan π = 〈a1, . . . , an〉 is c(π) = ∑ni=1 c(ai). The cost of a problem, denoted by c∗ (P), is the cost of the best (minimum cost) plan for P .

The delete relaxation P + of P is the same problem but with the delete lists Del(a) assumed empty for all actions. Since computing c∗ (P +) = h+ is intractable, heuristics approximate this value by introducing independence assumptions. In the additive heuristic, h(p; s) denotes the estimated cost of achieving a fluent p from s, and is given by:

where h(a; s) stands for an estimate of the cost of applying action a in s, and a(p; s) is a best support of fluent p in s:

where O(p) = {a ∈ O | p ∈ Add(a)}. The heuristic estimate of the cost of achieving the goal G from s is

Equations 2 and 4 make explicit the independence assumption in the additive heuristic and give it its name: the cost of achieving a set of goal or precondition fluents is estimated as the sum of the costs of achieving each.

A close variant of the additive heuristic is the max heuristic hmax, where the summation in equations (2) and (4) is replaced by max. hmax is admissible but less informed than the additive heuristic [Bonet and Geffner, 2001]. The close connections between these heuristics and the relaxed plan heuristic introduced in FF [Hoffmann and Nebel, 2001] have been discussed recently, and it has been shown how relaxed plans πadd(s) and πmax(s) can be obtained from the additive and max heuristics by collecting the best supports a(p; s) captured by (3) recursively backwards from the goal [Keyder and Geffner, 2008]. Such relaxed plans can be used to yield a tighter approximation of h+ by using the sum ∑a∈π(s) cost(a) instead of (4), avoiding counting actions more than once. Moreover, the construction of such relaxed plans is cost-sensitive, and for uniform costs πmax(s) is equivalent to πFF(s), the relaxed plan computed by FF using the relaxed planning graph. In these formulations, and more explicitly, in the set-additive heuristic where relaxed plans are computed recursively [Keyder and Geffner, 2008], the independence assumption takes a slightly different form: rather than taking the cost of achieving a set of subgoals to be the sum of the costs of achieving each one, they take the relaxed plan for them to be the union of the relaxed plans for each.

In problems where actions have a single precondition, all these heuristics yield optimal estimates for all individual atoms p in the delete relaxation (in the case of FF, under the assumption of uniform action costs); yet these estimates are not optimal for goals containing multiple atoms. The common feature of all of these heuristics is that they are 'greedy':

they never pay a higher cost to achieve a subgoal even when this could decrease the cost of achieving the set of all subgoals. In the next section, we analyze this problem further by considering a planning problem that encodes a well known problem in graph theory whose optimal cost is captured by h+.

3 Relaxed Plans and Steiner Trees

In order to arrive at a deeper understanding of the weaknesses of current heuristics, we consider a subclass of planning problems with single preconditions and no deletes: those that encode instances of the Steiner Tree Problem (STP). The STP S = 〈W,R〉 is the problem of finding a minimum cost tree in an undirected graph W = 〈V,E〉 that spans a set of target nodes R ⊆ V , called a Steiner Tree. Here we refer to a tree spanning the set of target nodes R while not necessarily being minimal as a Candidate Steiner Tree (CST). When R = V , the STP is the MST problem, yet the STP is intractable [Proemel and Steger, 2002], while the MST problem can be solved efficiently by greedy algorithms such as Prim's [Cormen et al., 1989]. Prim's algorithm starts with a set N containing initially an arbitrary node in V , and constructs the MST by iteratively selecting a cheapest edge (n, n′ ) in the graph W such that n is in N (spanned already) and n′ is not, until N = V .

As an illustration, the ST for the graph shown in Figure 2 and the targets R = {n0, n1, n2} is the tree composed of the edges (n0, n3), (n3, n1), and (n3, n2) and has cost 8.

The STP can be encoded in a straighforward way as a planning problem PS = 〈F, I,O,G〉 without deletes. For this, we define the set of fluents as F = V , the initial state as I = {n0} for some n0 ∈ R (which therefore must be spanned), the goal as G = R, and introduce actions an,n′ and an′ ,n for each (undirected) edge (n, n′ ) in E with costs c(an,n′) = c(n, n′ ), where c(n, n′ ) is the cost of the edge (n, n′ ) and an,n′ is an action with precondition n and effect n′ . An optimal plan π∗ for PS can then be interpreted as an ST Tπ∗ = {(n, n′ ) | an,n′ ∈ π∗ }. Denoting the cost of an STP S as c∗ (S) we have that:

Theorem 1. The Steiner Trees for the problem S = 〈W,R〉 are equivalent to the optimal plans for PS and c∗ (S) = c∗ (PS) = c∗ (P + S ).

While the optimal delete-relaxation heuristic h+ captures the optimal cost of the resulting planning problem, all of the heuristics considered above compute the shortest path to each of the target nodes. The relaxed plans that they yield therefore correspond to trees of shortest paths [Cormen et al., 1989]. For example, for the STP shown in Figure 2 with targets R = {n0, n1, n2}, the heuristics produce a relaxed plan that captures the shortest path from n0 to n1 and the shortest path from n0 to n2, for a total cost of 10.

The cost of a tree of shortest paths is not a good approximation to the cost of an STP. Yet many polynomial-time algorithms that compute better approximations exist [Charikar et al., 1998; Robins and Zelikovsky, 2000]. We cannot build directly on these algorithms, however, as the graphs that underlie the delete relaxations of arbitrary planning problems are directed hypergraphs, rather than undirected graphs. However, as we will show below, it is possible to obtain better relaxed plans by borrowing some of the underlying ideas.

Solving the STP S = 〈W, R〉 with W = 〈V, E〉 turns out to be equivalent to the problem of finding a set of Steiner Points Q ⊆ V \ R such that the cost of the MST over the graph induced in W by Q ∪ R is minimized. It is easy to see that this MST is then a solution to S. This suggests a fast test to eliminate a tree T spanning a set of nodes N, R ⊆ N, from consideration: if T is not an MST over the graph induced by N, T can be replaced in polynomial time by the MST that spans the same nodes with less cost. Furthermore, these improvements can be done incrementally as follows. Pick an edge e = (n, n′ ) in T and remove it from T . Then check whether there is an edge e′ = (n′′ , n′′′ ) such that c(e′ ) < c(e), n′′ ∈ v(T1), and n′′′ ∈ v(T2), where T1 and T2 are the two connected components in T \ e. If such an edge can be found, then T1 ∪ T2 ∪ e′ is a spanning tree of lower cost for the same set of nodes as T. When no further edges can be replaced, it can be shown that the resulting tree is an MST over the set of nodes that it spans. For the graph shown in Figure 3a where R = {n3, n4}, this simple improvement procedure leads us to replace the edge 〈n0, n1〉 with 〈n2, n1〉.

As our overall goal is not to find an MST over the set of nodes spanned by a Candidate Steiner Tree (CST) but rather to approximate the cost of the STP S as closely as possible, we observe that this algorithm can be improved further. In particular, rather than improving the cost of T by replacing a single edge, we can try to replace a path P = 〈n1, . . . , nk〉, where k ≥ 2, 〈ni, ni+1〉 ∈ T for 1 ≤ i ≤ k - 1, and ni /∈ R for 1 < i < k. T \ P then also consists of two disjoint connected components T1 and T2, with n1 ∈ v(T1) and nk ∈ v(T2). If a path P ′ = 〈n′1 , . . . , n′l 〉 such that n′1 ∈ T1, n′l ∈ T2, and c(P ′ ) < c(P) can be found, a new CST of lower cost results from replacing P with P ′ : T ′ = T1 ∪ T2 ∪ P ′ . This more powerful improvement procedure generalizes the one above that works only on edges, and may change the set of Steiner points Q of the CST.

The iterative procedure below for improving the cost of relaxed plans can be understood as a generalization of this procedure with relaxed plan fragments playing the role of paths.

4 The Local Steiner Tree (LST) Improvement Procedure

The graphs induced by the delete relaxations of most planning problems differ from the undirected graphs discussed until now in two important respects. First, the delete-relaxation graph is directed, its edges (actions) having source nodes (preconditions) and target nodes (add effects). Second, it is actually a hypergraph, as both precondition and add sets may have cardinality greater than 1. Solving the delete relaxation optimally is therefore the problem of optimal directed hyperpath finding [Ausiello et al., 1992]. Here we develop a technique inspired by the idea of the delete relaxation as an STP, yet applicable in this more general setting.

In what follows, we assume the presence of a dummy End action with zero cost, whose preconditions G1, . . . , Gn are the goals of the problem, and whose effect is a new dummy atom G. This allows us to express the relaxed plan from the state s, π(s), as the relaxed plan for G, π(G; s). We interpret relaxed plans as sets of action-fluent pairs 〈a, p〉 where a is the selected best supporter of p in s, i.e. a(p; s) = a. Relaxed plans are computed by recursively collecting the atoms and their best supporters backwards from the goal G, stopping the recursion at atoms appearing in s. Below we abuse notation slightly by allowing relaxed plans to represent both this set of pairs and the set of actions appearing in them; the corresponding set of fluents is denoted by F(π).

To improve the cost of a relaxed plan π(s) = π(G; s), we pick a fluent y ∈ F(π(s)) and split the set of actions π(s) into three disjoint subsets. π-(y; s) is the set of actions that are required only in order to achieve y, and corresponds to the path P to be replaced in the algorithm discussed earlier. π+(y; s) is the set of actions that depend on y being made true in order to be applied, and corresponds to one of the connected components that results from removing a path from a tree. Finally, π0 (y; s) is the set of actions that are neither used exclusively in order to achieve y nor depend on its being made true, and corresponds to the other connected component. We then check whether it is possible to improve the part of the plan that is exclusively for y, π-(y; s) in the context of the rest of the plan. This is accomplished by computing a relaxed plan π(y; s′ ) for y in a new state s′ that extends s with atoms that are supported by π0 (y) while leaving unchanged the best supports in π+(y; s) and π0 (y; s). As before, if the cost c(π(y; s′ )) is lower than c(π-(y; s)), then a better relaxed plan for π(G; s) results from replacing π-(y; s) with π(y; s′ ). The idea is shown in Fig. 3b along with the graph where the same idea was used to improve a Candidate Steiner Tree.

For a relaxed plan π(G; s) and a fluent y ∈ F(π(s)), the three sets above can be defined as follows:

To compute π-(y; s), we first extract a plan for G in s that assumes the fluent y, denoted π(G; s|y). This is done with a simple modification to the relaxed plan extraction procedure that returns the empty plan for y whenever it is encountered as a precondition. We then have that π-(y; s) = π(G; s) \ π(G; s|y). π+(y; s) is obtained by calling a recursive procedure on the goal fluent G that determines the portion of the relaxed plan for a fluent that is dependent on y. π0 (y; s) is computed in the manner implied by its definition.

The new relaxed plan π(y; s′ ) for y is obtained from an extension s′ of the state s that contains all fluents {p | a(p; s) ∈ π0 (y; s)}. The improved plan π′ (G; s) is then given by the union of π0 (y; s), π+(y; s) and π(y; s′ ), the new fragment that replaces π-(y; s). π′ (G; s) is well formed and has no cycles, as all fluents appearing in F(π+(y; s)) are excluded in the computation of π(y; s′ ) by removing them from the add lists of all actions, preventing actions that depend on them from being assigned as supports in s′ .

The pseudocode for a single iteration of the resulting method for improving the cost of relaxed plans is shown in Algorithm 1. The improvement algorithm is repeatedly called until it returns false, at which point the improved relaxed plan πlst(s) is obtained in the usual way by recursion backwards from the goal G collecting the best supports.

Algorithm 1 LST Procedure for improving relaxed plan π(s).

for y ∈ F (π(G; s)) do Compute π-(y; s), π+(y; s), π0 (y; s) s′ = s ∪ {p | a(p; s) ∈ π0 (y; s)} D = {p | a(p; s) ∈ π+(y; s)} Compute π(y; s′ ) with Add(a) := Add(a) \ D for all a if Cost(π(y; s′ )) < Cost(π-(y; s)) then for q ∈ F(π(y; s′ )) do a(q; s) = a(q; s′ ) end for return true end if end for return false

5 Example

Here we illustrate the functioning of the relaxed plan improvement algorithm on a problem involving soft goals

[Smith, 2004; Sanchez and Kambhampati, 2005]. It has been shown that soft goals p with utility u(p) > 0 that no action deletes can be compiled away by the introduction of extra fluents p′ that become normal (hard) goals of the problem, and two actions forgo(p) and collect(p) that add p′ : the first with no preconditions and cost u(p), the second with precondition p and cost 0 [Keyder and Geffner, 2007]. 1 We consider an example with soft goals as previous greedy heuristics tend to do poorly in this context.

The problem is shown in Figure 4. The agent begins at location A, and there are two packages available to gather from the map, each with an associated reward as shown. The relaxed plan π(s) generated by the additive heuristic for the initial state s = {(at A)} is:

where the End action is omitted. This relaxed plan achieves the two goals, p′1 and p′2 , with the cheapest plan for each when considered independently. Yet since the agent will move to locations B and C in order to pick up p1, it also makes sense to pick up p2 as the additional cost incurred to reach location D is 2, and there is a soft goal that is achievable there with reward 3. The set F(π(s)) generated by the above plan is

The only fluent in this set that can be improved with the LST procedure is p′2 . The subsets of π(s) then become

This gives s′ = {(at A), (at B), (at C), (have p1), (p′1 )}, from which we compute π(p′2 ; s′ ):

which has a cost of 2 compared to the cost of π-(p′2 ; s) which was 3. The supporters for the relevant fluents are then replaced, resulting in the new relaxed plan with cost 6, compared to the cost of the original relaxed plan, 7:

No further improvements are possible at this point, so the procedure terminates, returning the new relaxed plan.

6 Experimental Results

We evaluated the performance of two heuristics on ten different domains. Nine of these domains were from the most recent international planning competition (IPC6). The tenth domain is a compiled soft goals domain [Keyder and Geffner, 2007], similar to the Rovers domain from IPC3.

1 A slightly different compilation is required when soft goals can be deleted, for details, see [Keyder and Geffner, 2007].

The two heuristics used were the costs of the relaxed plan extracted according to the best supporters as determined by the additive heuristic, and the cost of the same plan as improved by the LST procedure. In the following graphs, these two heuristics are denoted by ha and hlst respectively. The search algorithm used was greedy best-first search with delayed evaluation and two open lists, one containing only states arrived at through helpful actions [Helmert, 2006]. The helpful actions used were those adding at least one precondition of some action in the relaxed plan. The planners were evaluated using the same time and memory settings as IPC6, with a timeout of 1800 seconds and a memory limit of 2GB. The experiments were run on Xeon Woodcrest computers with clock speeds of 2.33 GHz.

The use of the LST procedure significantly impacts results in three domains: parcprinter, elevators, and softgoals. In all of these domains, the number of nodes expanded decreases by orders of magnitude (Figures 6a,6b,6c). In the elevators and softgoals domains, plan cost also decreases significantly (Figures 5a, 5b). In the parcprinter domain, solutions found by both heuristics have equal cost, yet hlst increases coverage from 16 to 24 problems out of 30 due to the much lower number of nodes evaluated to find a solution.

In domains in which no improvement is observed, the LST procedure decreases coverage slightly due to the increased overhead, and the number of nodes evaluated and solution cost are roughly equal for all problems. Total coverage across all domains studied, however, is higher with the LST procedure than for the base heuristic ha (Table 1).

There is a wide variation in the correlation between improvement to relaxed plan cost and improvement to overall plan cost. While the correlation is high in the domains in which the greatest improvement to plan quality is observed, the greatest improvement to relaxed plan cost occurs in the pegsol domain, in which the LST procedure leads to no appreciable change in overall plan quality (Table 1).

7 Summary

Current heuristic estimators in planning approximate the optimal cost h+ of the delete relaxation by introducing independence assumptions over either estimated costs or relaxed plans. This assumption results in a 'greedy' estimator that attempts to minimize the cost of achieving individual fluents rather than sets. We have analyzed this problem by considering the Steiner Tree problem, where current heuristics yield the tree-of-shortest-paths approximation, and have developed a method for improving relaxed plans inspired by its properties. The results obtained from the resulting heuristic over several domains are encouraging and suggest that less greedy approximations to the optimal but intractable h+ heuristic may be both desirable and cost-effective.

Acknowledgments

We thank the anonymous reviewers for their helpful comments. H. Geffner is partially supported by grant TIN200615387-C03-03 fromMEC/Spain.