Heuristic Subset Selection in Classical Planning

1 Introduction

The A* algorithm [Hart et al., 1968] finds cost-optimal solutions to state-space planning problems when invoked with an admissible heuristic (a function that never overestimates the optimal solution cost for any state). There are various ways of generating admissible heuristics, e.g., pattern databases (PDBs) [Culberson and Schaeffer, 1998; Edelkamp, 2001], but the quality of such heuristics varies greatly.

One way of improving the quality of admissible heuristics is by maximizing over a set of them, an operation that yields an admissible heuristic which can overall be much more accurate than the original underlying heuristics. Ideally, one would generate a large number (say thousands) of admissible heuristics and maximize over them, because a larger set of heuristics increases the chance of having, for any given state, a more accurate heuristic estimate. However, evaluating thousands of heuristics would take too long to compute. We address this problem by proposing a method that carefully selects a subset ⇣ 0 of heuristics from a large pool ⇣ and then maximizes over ⇣ 0 . In other words, the final heuristic used to guide A*, hmax, is defined by hmax(s↪ ⇣ 0 ) = maxh2⇣ 0 h(s). Our approach is computationally efficient while still benefitting from the most helpful heuristics in the large pool.

We treat the problem of selecting a subset ⇣ 0 of ⇣ as an optimization problem, and present optimization methods for minimizing an approximation of A*'s search tree size (number of nodes generated by A*, denoted as J) and for minimizing an approximation of A*'s running time (denoted as T ) while solving a planning task (J and T are defined in Section 4).

We present Greedy Heuristic Selection (GHS), a hillclimbing procedure that adds heuristics from ⇣ to ⇣ 0 one at a time and halts when adding another heuristic does not improve the objective function. GHS needs to efficiently estimate the value of the objective function for a possibly large number of heuristic subsets. We adapt two existing prediction algorithms to quickly provide estimates of J and T for any subset ⇣ 0 of ⇣, namely, the method presented by Barley et al. [2014] and the one presented by Chen [1992].

Using the problems from the 2011 International Planning Competition (IPC), we empirically evaluate GHS in optimal classical planning problems while minimizing J , T , and maximizing the sum of heuristic values in the state space. Our experiments show that the subsets chosen by our algorithm can be far superior, in terms of coverage, to defining hmax over the entire collection ⇣ and to state-of-the-art methods. In particular, an optimization procedure that minimizes a combination of J and T outperforms all other approaches tested.

2 RelatedWork

The system most similar to GHS is RIDA* [Barley et al., 2014]. RIDA* also selects a subset from a pool of heuristics to guide the A* search. RIDA* starts with an empty subset and tries all subsets of size one before trying subsets of size two and so on. RIDA* stops after evaluating a fixed number of subsets. While RIDA* is able to select from a pool with tens of heuristics, GHS is able to select from a pool with thousands of heuristics. We show empirically GHS's advantage from being able to evaluate a larger pool of heuristics.

Rayner et al. [2013] present an optimization procedure that is similar to ours. In contrast with our work, Rayner et al. limited their experiments to a single objective function that sought to maximize the sum of the heuristic values in the state space. Moreover, their method performs a uniform sampling of the reachable state space, and we are unaware of a general way of doing this in domain-independent planning. In this paper we adapt Rayner et al.'s approach to planning by using Chen's [1992] Stratified Sampling as its sampling procedure. Our empirical results show that GHS minimizing T substantially outperforms this adaptation of Rayner et al.'s approach in domain-independent planning.

The methods GA-PDB [Edelkamp, 2007] and iPDB [Haslum et al., 2007] also combine a set of PDB heuristics. GA-PDB uses a genetic algorithm to maximize the average value of the resulting heuristic function. iPDB is based on the KRE prediction formula [Korf et al., 2001]

and it also uses the average heuristic value as a metric for deciding which PDBs to combine into a heuristic. Seipp et al. [2015] presented optimization procedures also aiming at maximizing the average heuristic value in the reachable state space while creating potential heuristics [Pommerening et al., 2015]. In contrast with these works, the methods we introduce use richer prediction models such as Stratified Sampling [Chen, 1992] to select a subset of heuristics while minimizing J and T. Domshlak et al. [2012] introduced Selmax, a method for deciding which heuristic to use to evaluate a given node during search. Selmax evaluates only a few heuristics and their experiments consider sets with two heuristics; we consider sets with thousands of heuristics.

3 Background

An SAS+ planning task [B¨ackstr¨om and Nebel, 1995] is a 4tuple r = hV↪O↪ I↪ Gi. V is a set of state variables. Each variable v 2 V has a finite domain Dv. A state is an assignment of a value in Dv to each v 2 V, so that the set of all states is V = Dv1 ⇥· · ·⇥Dv♣V♣ . O is a set of operators, where each operator o 2 O is a triple hpreo↪ posto↪ costoi specifying the preconditions, postconditions (effects), and non-negative cost of o. Operator o is applicable to state s if s and preo agree on the assignment of values to variables in Vpreo . The effect of o, when applied to s, is to set the variables in Vposto to the values specified in posto and to set all other variables to the value they have in s, resulting in a new generated state. We call the children of state s the states generated by applying the effects of each applicable operator of s (denoted as children(s)). Furthermore, s is expanded when all its children are generated. G is the goal condition, an assignment of values to a subset of variables, VG. A state is a goal state if it agrees on the assignment of values to the variables in VG. I is the initial state, and the planning task, r, is to find an optimal (least-cost) sequence of operators leading from I to a goal state. We denote the optimal solution cost of r as C ⇤ . We are interested only in optimal solutions. A heuristic h(s) estimates the cost of a solution path from s to a goal. h is consistent iff h(s)  c(s↪ t) + h(t) for all states s and t, where c(s↪ t) is the cost of the cheapest path from s to t.

Given a set of consistent heuristics ⇣ = ¶h1↪ h2↪ · · · ↪ hM♦, the heuristic hmax(s↪ ⇣) = maxh2⇣h(s) is also consistent. When describing our methods we assume all heuristics to be consistent. We define fmax(s↪ ⇣) = g(s)+hmax(s↪ ⇣), where g(s) is the cost of the current path from I to s. We denote as g⇤ (s) the cost of the least-cost path from I to s and note that g(s) = g⇤ (s) when A* using a consistent heuristic expands s. An A* search tree is defined by the states generated by A* using a consistent heuristic while solving a problem r. In this paper we use the terms state and node interchangeably.

4 Greedy Heuristic Selection

We introduce Greedy Heuristic Selection (GHS) an algorithm able to find good solutions to the following problem,

where is either J or T (formally defined below).

Algorithm 1 Greedy Heuristic Selection

Input: problemr, set of heuristics ⇣ Output: heuristic subset ⇣ 0 ✓ ⇣

• 2: while ⇣ 0 6= ⇣ do
• 1: ⇣ 0 ;

• 5: return ⇣ 0
• 4: if (⇣ 0 [ ¶h♦↪r) ≥ (⇣ 0 ↪r) then
• 6: ⇣ 0 ⇣ 0 [ ¶h♦
• 7: return ⇣ 0

Algorithm 1 shows GHS, which receives as input a problem r, a set of heuristics ⇣, and it returns a subset ⇣ 0 ✓ ⇣. In each iteration i GHS selects a heuristic h from ⇣ and adds h to ⇣ 0 , where h is the heuristic that when individually combined with ⇣ 0 reduces the most. GHS returns ⇣ 0 once it can no longer reduce the value of (line 4) or when ⇣ = ⇣ 0 (line 2).

Next, we describe two functions we consider: an approximation of J, and an approximation of T . Although often one is interested in minimizing a planner's running time, we believe that J is also an important metric to be considered. This is because planners often run out memory before running out of time while solving planning problems, and J could serve as a good proxy for memory usage of A*-based planners.

4.1 Approximation of A*'s Search Tree Size

The first objective function we consider is J(⇣ 0 ↪r), an upper bound on the size of the search tree A* generates while solving planning problem r using hmax(⇣ 0 ),

where Ss with fmax(s↪⇣ 0 )C⇤ children(s) is a multiset, as in an A* search the same state could be generated multiple times. J(⇣ 0 ↪r) assumes that A* expands all states s with fmax(s↪ ⇣ 0 )  C ⇤ before expanding a goal state. We write J(⇣ 0 ) or simply J instead of J(⇣ 0 ↪r) whenever ⇣ 0 and r are clear from the context. We present in this paper two methods for approximating J. We now show that J(⇣ 0 ↪ r) is minimal, for the subset ⇣ 0 returned by GHS.

Theorem 1 Let the heuristics in ⇣ 0 as well as h ◁2 ⇣ 0 be consistent heuristics. We have that J(⇣ 0 [ ¶h♦)  J(⇣ 0 ).

where the inequality follows from the fact that hmax(s↪ ⇣ 0 [ ¶h♦) ≥ hmax(s↪ ⇣ 0 ) for all s. ⇤

Corollary 1 J(⇣↪r)  J(⇣ 0 ↪r) for any ⇣ 0 ✓ ⇣.

Lemma 1 Let r be a planning problem with optimal solution cost C ⇤ , A a set of consistent heuristic functions, and B ✓ A. If J(A↪r) < J(B↪r), then there exists an element h 2 A such that J(B [ ¶h♦↪ r) < J(B↪ r).

Proof. If J(A↪r) < J(B↪r), then by the definition of J there is a state s such that fmax(s↪A) > C ⇤ and fmax(s↪B)  C ⇤ . Thus, there is a heuristic h 2 A such that h(s) > C ⇤ - g⇤ (s) ≥ hmax(s↪ B). Then, hmax(s↪ B [ ¶h♦) > C ⇤ - g⇤ (s) follows from the definition of hmax, and consequently J(B [ ¶h♦↪ r) < J(B↪ r). ⇤

Theorem 2 Given a set ⇣ of consistent heuristics, GHS returns a subset ⇣ 0 of ⇣ for which J(⇣) = J(⇣ 0 ).

Proof. GHS stops when no h 2 ⇣ satisfies J(⇣ 0 [ ¶h♦) < J(⇣ 0 ). Thus, J(⇣) < J(⇣ 0 ) cannot be true (Lemma 1). Since J(⇣) is minimal (Corollary 1), J(⇣ 0 ) = J(⇣). ⇤

4.2 Approximation of A*'s Running Time

Another we consider is T(⇣ 0 ↪r), an approximation to the running time of A* when using hmax(⇣ 0 ) for solving r.

where thmax(⇣ 0 ) is the heuristic evaluation time of hmax(⇣ 0 ), and tgen is the node generation time. We assume thmax(⇣ 0 ) and tgen to be constant throughout the state space for a given domain and heuristic. This is reasonable to assume for several heuristics, e.g., PDBs, and several types of problem domains. We write T(⇣ 0 ) or simply T instead of T(⇣ 0 ↪r) whenever ⇣ 0 and r are clear from the context.

T(⇣ 0 ↪r) represents only an approximate model of the A* running time. For an exact computation we would have to also account for other factors such as the time spent in operations on A*'s open list. However, it is usually hard to approximate the running time of such operations because they could vary during the search. Nevertheless, T captures the computational cost of the heuristic function being employed, which we expect to dominate the running time of planning systems.

Next we show that if all h 2 ⇣ have the same evaluation time th, then the subset ⇣ 0 GHS returns is guaranteed to have the lowest T-value amongst all subsets of size ♣⇣ 0 ♣ or larger.

Theorem 3 Let ⇣ be a set of consistent heuristics. If thi = thj for any hi↪ hj 2 ⇣, then GHS yields a subset ⇣ 0 of ⇣ with T(⇣ 0 ↪r)  T(⇣ 00 ↪r) for any ⇣ 00 ✓ ⇣ with ♣⇣ 0 ♣  ♣⇣ 00 ♣.

Proof.

The first inequality follows from thmax(⇣ 0 )  thmax(⇣ 00 ) (because ♣⇣ 0 ♣  ♣⇣ 00 ♣ and th is constant for any h 2 ⇣), the second from J(⇣ 0 ↪ r) being minimal (Theorem 2). ⇤

5 Estimating Tree Size and Running Time

In practice GHS uses approximations ˆ J of J and ˆ T of T instead of their exact values. This is because computing J and T exactly could be as expensive as solving r.

We investigate two methods for estimating ˆ J and ˆ T, Culprit Sampling (CS) [Barley et al., 2014] and Stratified Sampling (SS) [Chen, 1992]. Both CS and SS must be able to quickly estimate the values of ˆ J(⇣ 0 ) and ˆ T(⇣ 0 ) for any subset ⇣ 0 of ⇣ so that they can be used in GHS's optimization process. This is achieved by estimating f-culprits and b-culprits.

Definition 1 (f-culprit) Let ⇣ = ¶h1↪ h2↪ · · · ↪ hM♦ be a set of heuristics. The f-culprit of a node n in an A* search tree is defined as the tuple F(n) = hf1(n)↪ f2(n)↪ · · · ↪ fM(n)i, where fi(n) = g(n) + hi(n). For any tuple F, the counter CF denotes the total number of children of nodes n in the search tree with F (n) = F .

Definition 2 (b-culprit) Let ⇣ = ¶h1↪ h2↪ · · · ↪ hM♦ be a set of heuristics and b a lower bound on the solution cost of r. The b-culprit of a node n in an A* search tree is defined as the tuple B(n) = hy1(n)↪ y2(n)↪ · · · ↪ yM(n)i, where yi(n) = 1 if g(n)+hi(n)  b and yi(n) = 0, otherwise. For any binary tuple B, the counter CB denotes the total number of children of nodes n in the search tree with B(n) = B. 1

We now describe how CS and SS estimate f - and b-culprits and how the culprits can be used to quickly estimate ˆ J (⇣ 0 ) and ˆ T(⇣ 0 ) for any subset ⇣ 0 of ⇣.

5.1 Culprit Sampler (CS)

CS runs an A* search bounded by a user-specified time limit and then compresses the information obtained in the A* search (i.e., the f-values of all nodes expanded according to all heuristics h in ⇣) into b-culprits, which are later used for computing ˆ J. The f-culprits are needed for computing the b-culprits, as we explain below. The maximum number of fculprits and b-culprits in an A* search tree equals the number of nodes in the tree expanded by the time-bounded A* search. However, in practice the total number of f- and b-culprits is usually much lower than the number of nodes in the tree.

Given r, ⇣, and a user-specified time limit, CS samples the A* search tree as follows.

1. CS runs A* using hmax(s↪ ⇣) for one fourth of the userspecified time limit. We denote as OPEN the set of states in the A*'s open list when A* halts.
2. In the remainder of its running time, CS randomly selects a state s from OPEN and computes hmin(s↪ ⇣) = minh2⇣ h(s) for s, as well as for every node s0 in s's subtree for which fmin(s↪ ⇣) = fmin(s0 ↪ ⇣), where fmin(s↪ ⇣) = hmin(s↪ ⇣)+g(s). For each node sampled in this procedure, we store its f-culprit and its counter. We use hmin because A* using hmin(s↪ ⇣) expands node s if it were to expand s with any h 2 ⇣ individually.
3. Let fmaxmin be the largest f-value according to hmin encountered in CS's sampling procedure. We compute the set B of b-culprits and their counters based on the f-culprits and on the value of fmaxmin. This is done by iterating over all f-culprits once.
4. CS is run only once in GHS's execution. The value of ˆ J(⇣ 0 ↪r) for any subset ⇣ 0 of ⇣ is then computed by iterating over all b-culprits B and summing up the relevant values of CB. The relevant values of CB represent the number of

1 The vector B(n), and thus the values of CB for any B, depend on the bound b, which we assume to be fixed.

nodes A* would generate in a search bounded by b if using hmax(⇣ 0 ). This computation is written as, ˆ J(⇣ 0 ↪r) = PB2B W(B) ↪ where W(B) is 0 if there is a heuristic in ⇣ 0 whose y-value in B is zero (i.e., there is a heuristic in ⇣ 0 that prunes all nodes compressed into B), and CB otherwise.

In addition to computing ˆ J, the value of ˆ T requires approximations of th for all h 2 ⇣ and of tgen. These values are measured in a separate process, before executing CS, by sampling a small number of nodes fromr's start state.

5.2 Stratified Sampling (SS)

Chen [1992] presented Stratified Sampling (SS), a method for estimating the search tree size of backtracking search algorithms. In this section we briefly describe Chen's SS. For a detailed description of SS, see Lelis et al. [2013].

SS approximates any function ' = Pn2S z(n) ↪ where S is the set of nodes in a search tree and z is a function assigning a numerical value to a node. ' represents a numerical property of the tree. For GHS, z(n) = ♣children(n)♣, so that ' is the number of nodes generated by the search procedure.

SS works by sampling the search tree with a procedure similar to randomwalks. SS's sampling procedure is limited by a value d. That is, SS does not expand node n if f(n) > d. Each sample of SS is called a probe. Chen proved that as the number of probes grows large, SS's estimate of ' converges to its exact value. As Lelis et al. [2014b] showed, SS does not detect duplicate nodes in its sampling procedure. Hence, as A* does not expand duplicates, SS's predictions usually overestimates A*'s search tree size. We show empirically that SS is still able to allow GHS to select good subsets.

Similar to CS, we define a time limit for SS and use an iterative-deepening approach to ensure an estimate of ˆ J and ˆ T before reaching the time limit. SS's sampling is initially limited by the h-value of the start state (d = hmax(I↪ ⇣)). After p probes, if there is still time, we double the value of d. The values of ˆ J and ˆ T are given by the prediction produced for the last d-value in which SS finishes all p probes. If SS cannot finish all p probes during its first iteration, ˆ J and ˆ T are given by the prediction from the incomplete first iteration.

SS must also estimate the values of ˆ J(⇣ 0 ) and ˆ T(⇣ 0 ) for any subset ⇣ 0 of ⇣. This is achieved by using SS to estimate b-culprits (see Definition 2) instead of the search tree size directly. Similar to CS, SS uses hmin of the heuristics in ⇣ to decide when to prune a node while sampling. This ensures that SS expands a node n if A* employing at least one of the heuristics in ⇣ would expand n according to bound d.

6 The Hybrid Approach

In this section we introduce an approach called Hybrid, that minimizes both ˆ J and ˆ T while using SS and CS. That is, Hybrid uses GHS+SS to select a subset of heuristics from a pool ⇣1 composed of heuristics with the same evaluation time. We call the selection of a subset of ⇣1 the first selection. Once the first selection ⇣ 0 ✓ ⇣1 is made, Hybrid tests all possible combinations of the resulting hmax(⇣ 0 ) with heuristics from another pool ⇣2, composed of heuristics with possibly different evaluation times, while minimizing ˆ T as estimated by CS.

We call this step the second selection.

The intuition behind Hybrid is to apply GHS with its strongest settings, i.e., according to Theorems 2 and 3, the subset ⇣ 0 GHS chooses in the first selection is minimal with respect to ˆ J and minimal amongst all subsets whose size is equal or larger than ♣⇣ 0 ♣ with respect to ˆ T (all h 2 ⇣1 have the same evaluation time). After such a selection is made, we reduce all heuristics in ⇣1 to a single heuristic hmax(⇣ 0 ). Then, if ⇣2 has only a few heuristics, we are able to select from ¶hmax(⇣ 0 )♦ [ ⇣2 the exact subset that minimizes ˆ T. In our experiments ⇣1 may have thousands of heuristics, depending on the problem instance, while ⇣2 has always only two.

We use SS instead of CS in the first selection because the former is able to make better subset selections while minimizing ˆ J, as shown in Section 7.1. Finally, as indicated in our experiments shown in Section 7.2, CS is more effective if one is interested in minimizing ˆ T while selecting from a pool of heuristics with different evaluation times. That is why we use CS as a predictor for Hybrid's second selection.

7 Empirical Evaluation

The practical effectiveness of GHS depends on its ability to find good approximations ˆ J and ˆ T and on the quality of ⇣. In order to verify its practical effectiveness, we have implemented GHS in Fast Downward [Helmert, 2006] and tested the A* performance using subsets of heuristics selected by GHS while minimizing different objective functions.

We run two sets of experiments. In the first set we verify whether the approximations ˆ J and ˆ T provided by CS and SS allow GHS to make good subset selections. In the second set of experiments we test the effectiveness of GHS by measuring the total number of problem instances solved by A* using the heuristic subset selected by GHS.

In our experiments we first generate and store in memory all heuristics in ⇣, and only then we use GHS to select a subset ⇣ 0 of ⇣. The process of generating ⇣ is limited by 1GB of memory and 600 seconds. The sampling procedure is bounded by a 300-second time limit for both CS and SS.

SS requires one to define an equivalence relation of the nodes in the search tree. In our experiments we consider nodes equivalent if they have the same f-value. This equivalence relation has shown to be effective in guiding SS in other application domains [Lelis et al., 2013; 2014a]. We use the number of SS probes p = 500 in all our experiments.

We ran our experiments on the 2011 IPC instances instead of the 2014 instances because the former do not have domains with conditional effects, which are currently not handled by the regression search that builds PDB heuristics. The 2011 IPC benchmark has 280 instances of 14 different domains (20 instances per domain). All experiments are run on 2.67 GHz machines with 4 GB, and are limited to 1,800 seconds of running time. We use the preprocessor described by Alc´azar and Torralba [2015] for mutex detection in all planners tested.

7.1 Empirical Evaluation of ˆ J and ˆ T

GHS is guaranteed to return a subset ⇣ 0 that minimizes J. We now test whether the ˆ J-values provided by CS and SS allow GHS to make good subset selections. This test is made by comparing J(⇣ 0 ) with the number of nodes generated by A* while using hmax(⇣), which is minimal.

In contrast with objective function J, there is no easy way to find the minimum of T in general. We experiment then with the special case in which all heuristics in ⇣ have the same evaluation time. This way, if GHS selects a subset ⇣ 0 which is optimal with respect to J, then we know that ⇣ 0 has the lowest T -value amongst all subsets of size ♣⇣ 0 ♣ or larger (Theorem 3).

We collect values of J(⇣) and J(⇣ 0 ) as follows. For each instance r in our test set we generate a set of PDB heuristics using the GA-PDB algorithm [Edelkamp, 2007] as described by Barley et al. [2014] (we call each PDB generated by this method a GA-PDB). We chose to use only GA-PDBs in this experiment as they all have nearly the same evaluation time. The number of GA-PDBs generated is limited in this experiment by 600 seconds and 1GB of memory. The GA-PDBs generated form our ⇣ set. GHS then selects a subset ⇣ 0 of ⇣. Finally, we use hmax(⇣ 0 ) and hmax(⇣) to independently try to solve r. We call the system which uses A* with hmax(⇣) the Max approach. For GHS we allow 1,200 seconds in total for both selecting ⇣ 0 and for running A* with hmax(⇣ 0 ), and for Max we allow 1,200 seconds for running A* with hmax(⇣). Since we used 600 seconds to generate the heuristics, both Max and GHS were allowed 1,800 seconds in total for solving each problem. We test both CS and SS.

We refer to the approach that runs A* guided by a heuristic subset selected by GHS using CS as GHS+CS. Similarly, we write GHS+SS when SS is used as predictor.

Table 1 shows the average ratios of J(⇣ 0 ) to J(⇣) for both SS and CS in different problem domains. The value of J, for a given problem instance, is computed as the number of nodes generated up to the largest f -layer which is fully expanded by all approaches tested (Max, GHS+SS, and GHS+CS). We only present results for instances that are not solved during GHS's CS sampling process. The column "n" shows the number of instances used to compute the averages of each row. We also show the average number of GA-PDBs generated (♣⇣♣) and the average number of GA-PDBs selected by GHS (♣⇣ 0 ♣). We see that for most of the problems GHS, using either CS or SS, is selecting a near-optimal subset of ⇣. For example, in Tidybot GHS selects only a few heuristics out of thousands when using either SS or CS, and the resulting A* search tree size is optimal for both approaches.

The exceptions in Table 1 are the ratios for Elevators, Parcprinter, and Woodworking. In all three domains GHS+SS failed to make good heuristic selections because SS was not able to sample "deep enough" into the problem's search tree. For instance, for the Elevators instance SS was able to perform only 245 probes with the initial f-boundary within the time limit of 300 seconds. GHS+CS is able to make better selections for this instance because it is able to sample deeper into the search tree. For the Parcprinter instance as well as the Woodworking instances neither SS nor CS are able to sample deep enough to make good heuristic selections. These results suggest that SS could benefit from an adaptive approach for choosing SS's number of probes. For example, for the Elevators instance SS could have performed better by sampling deeper into the tree with fewer probes. We intend to investigate this direction in future works.

In general SS is able to sample deeper than CS into the search tree, which allowed GHS+SS to solve more instances in this experiment. In total, out of the 280 instances, GHS+SS solved 199 instances, while GHS+CS solved 194, and Max 182 (these numbers are not shown in Table 1).

7.2 Comparison with Other Planning Systems

The objective of this second set of experiments is to compare GHS with state-of-the-art planners. Our evaluation metric is coverage, i.e., number of problems solved within a 1,800second time limit, which includes the time to generate ⇣, select ⇣ 0 , and run A* using hmax(⇣ 0 ). The ⇣ set of heuristics is composed of a number of different GA-PDBs, a PDB heuristic produced by the iPDB method [Haslum et al., 2007] and the LMCut heuristic [Pommerening and Helmert, 2013]. The generation of GA-PDBs is limited by 600 seconds and 1 GB of memory. We use one third of 600 seconds to generate GAPDBs with each of the following maximum numbers of entries: ¶2 · 104 ↪ 2 · 105 ↪ 2 · 106 ♦. Our approach generates up to thousands of GA-PDBs. We use exactly the same ⇣ set for Max and all GHS approaches.

7.3 Systems Tested

GHS is tested for minimizing ˆ J (Size) and ˆ T (Time). We also use GHS to maximize the sum of heuristic values in the state space (Sum), as suggested by Rayner et al. [2013]. Rayner et al. assumed that one could uniformly sample states in the state space in order to estimate the sum of the heuristic values for a given heuristic subset, which in general cannot be done in domain-independent planning. Thus, we adapted Rayner et al.'s method by using SS to estimate the sum of heuristic values in the search tree rooted at r's start state. Below, Size+SS refers to the approach that uses A* guided by a heuristic selected by GHS while minimizing a ˆ J provided by SS. We name other combinations of objective functions and prediction algorithms in a similar way (e.g., Time+CS).

In addition to testing all combinations of prediction algorithms (CS and SS) and objective functions (Time, Size) we also experiment with Hybrid using a pool ⇣1 composed solely of GA-PDB heuristics, and ⇣2 of iPDB and LMCut.

We compare the coverage of the GHS approaches with the following state-of-the-art planners, RIDA* [Barley et al., 2014], two variants of StoneSoup (StSp1 and StSp2) [Helmert et al., 2011], two versions of Symba (SY1 and SY2) [Torralba, 2015]. We also independently run A* with the following heuristics: maximum of all heuristics in ⇣ (Max), iPDB, LMCut, and Merge & Shrink (M&S) as described by Nissim et al. [2011]. Table 2 presents the results.

7.4 Discussion of the Results

The system that solves the largest number of instances is Hybrid (219 in total). Its combination of the strengths of both SS and CS has proven particularly effective on the Barman domain where Hybrid's first selection contains good subsets of GA-PDBs and its second selection recognizes when it must not add the iPDB and LMCut heuristics to the first selection. As a result, Hybrid solves more problems on this domain than any other GHS approach.

Time+CS also performs well-it solves 214 problems. Hybrid and Time+CS are superior to all other approaches tested. When minimizing ˆ J or maximizing Sum, GHS tends to add accurate heuristics to the selected subset, irrespective of their evaluation time. Thus, GHS frequently selects LMCut which is often the heuristic that most reduces the search tree size and most increases the sum of heuristic values. However, LMCut is computationally expensive, and often the search is faster if LMCut is not in ⇣ 0 . Both Hybrid and Time+CS often recognize when LMCut should not be in ⇣ 0 because they account for the heuristics' evaluation time.

Interestingly, while Time+CS solves 214 instances, Time+SS solves only 200. We conjecture that this is due to SS not detecting duplicate nodes during sampling and thus substantially overestimating A*'s running time. As a result, similarly to the Size and Sum approaches, Time+SS often mistakenly adds the accurate but expensive LMCut heuristic in cases where A* would be faster without LMCut.

RIDA* is the most similar system to GHS; it selects a subset of heuristics by using an evaluation method similar to CS. Starting with an empty subset, it evaluates all subsets of size i before evaluating subsets of size i + 1. This limits RIDA*

to considering only tens of heuristics in its pool. Specifically, RIDA* uses 42 GA-PDBs, iPDB, and LMCut in its pool. By contrast, GHS may consider thousands of heuristics.

Selecting from large sets of heuristics can be helpful, even if most of the heuristics in the set are redundant with each other-as is the case with the GA-PDBs. The process of generating GA-PDBs is stochastic, thus one increases the chances of generating a helpful heuristic by generating a large number of them. GHS is an effective method for selecting a small set of informative heuristics from a large set of mostly uninformative ones. This is illustrated in Table 2 on the Transport domain. Compared to systems which use multiple heuristics (StSp 1 and 2, and RIDA*), Hybrid solves the largest number of Transport instances, which is due to the selection of a few key GA-PDBs.

The best GHS approach, Hybrid, substantially outperforms Max; Hybrid solves 20 more instances than Max. Finally, Hybrid and Time+CS outperform all other approaches tested, with RIDA* being the closest competitor with 210 instances solved.

8 Concluding Remarks

In this paper we presented GHS, a greedy optimization algorithm that chooses a subset from a pool of thousands of heuristics. We used GHS to select a subset of heuristics while minimizing an approximation of A*'s search tree size ( ˆ J) and an approximation of A*'s running time ( ˆ T)-two objective functions we proposed in this paper. In addition to the two objective functions we proposed, we also experimented with an objective function that accounts for the sum of heuristic values in the state space (Sum). We tested two methods, CS and SS, for estimating the values of the objective functions tested. Several previous works used Sum (or variations of it) for constructing heuristics (e.g., [Haslum et al., 2007; Edelkamp, 2007; Rayner et al., 2013; Seipp et al., 2015]). Our experiments on optimal domain-independent problems showed that GHS using a hybrid approach that minimizes a combination of ˆ J and ˆ T outperformed all other approaches tested, including the approach that maximizes Sum.

9 Acknowledgements

The authors gratefully thank an anonymous referee of an earlier version of this paper for suggesting important improvements to the theoretical contributions of this work.

Financial support for this research was in part provided by Brazil's CAPES (Science Without Borders), FAPEMIG, CNPq, and Canada's NSERC (Discovery Grant program and Canada Research Chairs program).

This material is based upon work supported by the Air Force Office of Scientific Research, Asian Office of Aerospace Research and Development (AOARD) under award number FA2386-15-1-4069. Any opinions, finding, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Air Force.