Subset Selection of Search Heuristics

1 Introduction

The heuristic function - which we also simply call the heuristic - is an estimate of the cost or distance between two states. When used in search, a strong heuristic can improve solution quality, speed, and can render intractable problems tractable.

The literature describes several approaches to heuristic construction, including pattern databases [Culberson and Schaeffer, 1998], memory-based heuristics [Sturtevant et al., 2009], regressors [Ernandes and Gori, 2004], and metric embeddings [Rayner et al., 2011], each capable of generating multiple different heuristic functions based on input parameters. When multiple heuristics are available, it is common to query each and somehow combine the resulting values into a better estimate. However, under constraints on lookup time or memory, it may be that only a subset of a much larger pool of candidate heuristics can be used during search. Groups of heuristics can interact with each other in subtle ways, which makes selecting the best subset among them challenging.

In this paper, we formulate selecting heuristic subsets as an optimization problem. The loss function we aim to minimize is inspired by search effort, and is independent of the type of heuristics in the candidate set. When the candidate heuristics are admissible, this loss can be translated into a submodular and monotonic utility function; these properties imply that greedy selection is near-optimal. We also introduce a sample utility function under which greedy selection retains provable Michael Bowling University of Alberta Edmonton, AB, Canada T6G 2E8 bowling@cs.ualberta.ca optimality if the heuristics are consistent. An empirical evaluation of our approach shows it to be capable of outperforming existing methods. We further use our approach to accurately benchmark a promising new type of true-distance heuristic, which gives valuable insight into the problem of constructing heuristics for highly directed search graphs.

2 Background

Research spanning the past two decades shows a progression toward building heuristics automatically, often in ways that enforce the key properties of admissibility and consistency. When heuristics are so readily constructed, an accompanying subset selection problem is inevitable.

One common motivation for heuristic construction is to solve otherwise intractable search problems. Here, pattern databases (PDBs) have arguably made the greatest impact [Culberson and Schaeffer, 1998]. The problem of selecting heuristic subsets is prevalent here, with it having been observed that many small PDBs can be more effective together than a single monolithic PDB [Holte et al., 2006].

In other cases, the heuristic function is constructed to expedite the solution of arbitrarily many future problems. These cases are a motivating force behind our work, with example applications including GPS navigation and video game pathfinding. Several algorithms have been proposed in this context for selecting heuristic subsets, but most lack an optimality criterion or are tied to a specific type of heuristic function. For example, one recent approach draws a connection between heuristic construction and manifold learning [Weinberger et al., 2005] and represents heuristic information as distances between points in Euclidean space [Rayner et al., 2011]. Principal components analysis can be used to select an optimal, variance-preserving subset of this distance information, but that approach is exclusive to Euclidean heuristics.

Another popular approach is to precompute true distances to a landmark [Goldberg and Werneck, 2003], which can be thought of as selecting a subset of all distance information [Sturtevant et al., 2009]. These methods can be viewed as special cases of Lipschitz embeddings [Bourgain, 1985] in which distances are computed to the nearest of a set of landmarks. Many selection algorithms have been devised for these, both as heuristics [Goldberg and Harrelson, 2005; Fuchs, 2010] and as metric embeddings [Linial et al., 1995], but these too cannot be applied to other types of heuristics.

3 Subset Selection of Search Heuristics

We consider the problem of choosing a good subset H of a set of candidate heuristics C = {h1, . . . , h|C|}. We assume the heuristics in H are to be combined with a set of default heuristics D by maximizing over the values across both H and D. For states i and j, we denote this heuristic lookup as:

In the simplest case, D contains only the zero heuristic, which gives 0 for any pair of states queried. We further assume any default or candidate heuristic hx ∈ D∪C is non-negative and admissible (i.e., never overestimating),

where δ(i, j) is the true distance between states i and j.

3.1 Optimization Problem

We formalize the heuristic subset selection problem as an optimization problem:

The constraint |H| = d simply limits the capacity of H to a fixed-size subset of C, and the loss L(H) is a scalar quantity summarizing the quality of a given subset H.

We relate loss to eventual search effort. An optimal search algorithm must expand any state encountered whose heuristic is low enough to suggest it may be on an optimal path to the goal [Bagchi and Mahanti, 1983], so a well-suited loss is the weighted sum of the errors between the resulting heuristic values and the true distances, for all pairs across n states:

The non-negative weight matrix W ∈ Rn×n is a free parameter, and it can be flexibly defined to specify the relative importance of each pair of states, perhaps based on knowledge of frequent start and goal locations.

We can rewrite this loss as an equivalent utility function U. First, all of the heuristics in H ∪D are admissible, so for all states i and j, hH (i, j) ≤ δ(i, j). Therefore we can remove the absolute value from line 4 and split the sum: 1

The leftmost term on line 6 does not depend on H, so minimizing L(H) is equivalent to maximizing the term on the right. We introduce the corresponding utility function,

where α is a normalizing constant that has no effect on the choice of H, but ensures that U(∅) = 0. α is defined as a weighted sum of the contributions of the default heuristics:

1 Note i and j always iterate from 1 to n as on line 4.

All told, we arrive at a specific utility maximization problem:

Unfortunately, there is unlikely to be an efficient algorithm to find a globally optimal solution to this problem.

Proposition 1 The optimization problem (9) is NP-hard. 2

Proof. We sketch a reduction from the NP-complete Vertex Cover problem over an undirected graph (V,E). This is the problem of finding a subset of d graph vertices T ⊆ V such that all edges in E are incident to at least one vertex in T .

By definition, heuristics describe values between pairs of vertices in a search graph. A special case of this is a function that only returns 1 between a vertex and its neighbors, and 0 for any other query. Thus, to reduce vertex cover, we define C as a set of heuristics C = {hv : v ∈ V } where each hv ∈ C gives a value of 1 between vertex v and its neighbors, and 0 otherwise. If a subset of d such heuristics captures all edge costs, then there is a vertex cover of size d as well. □

3.2 Approximation Algorithm

Despite Proposition 1, greedy selection will yield a solution to the optimization problem (9) with a strong near-optimality guarantee. This is because U is submodular and monotonic.

Submodularity is a diminishing returns property. It aptly describes settings where marginal gains in utility start to diminish due to saturation of the objective, such as with sensor placement and monetary gain. Let A ⊆ B ⊊ S, let x ∈ S\B, and let φ be a function over 2S . φ is submodular if:

That is, the same element newly added to a subset and its superset will lead the subset to gain at least as much in value as the superset. Intuitively, the utility function U(H) and submodularity are a good fit, since adding a new heuristic to H will not newly cover any of the heuristic values that H already covers. We prove this formally in the following lemma.

Lemma 1 U is submodular.

Proof. Let A and B be sets of heuristics with A ⊆ B, and let hc ∈ C be a particular but arbitrary candidate heuristic function which is in neither A nor B (i.e., hc ∈ C \ B). We can reproduce the inequality on line 10 as follows:

Line 12 twice expands the definition of utility (7) with the α terms cancelling, and line 13 rewrites this difference of sums as a sum of differences between hc and hA together versus hA alone. Line 14 equates this to a sum of the positive differences between hc and hA, where (x)+ = max{0, x}. Line 15 holds since hc's individual gains over hA∪B cannot exceed its gains over hA. But A ∪ B = B, proving submodularity. □

2 A distinct result is the NP-hardness of ALT's preprocessing phase under an edge-covering objective [Bauer et al., 2010].

Monotonicity is the notion that adding an element to a set never leads to a decrease in value. Let A ⊆ B ⊆ S be sets and let φ be a function over 2S . φ is monotonic if φ(A) ≤ φ(B). Since U(H) only measures the sum of the heuristics - and not, for example, the cost per heuristic lookup or the memory consumed - no heuristic added to H can decrease utility.

Lemma 2 U is monotonic.

Proof. Let A and B be sets of heuristics with A ⊆ B. We must show that U(A) ≤ U(B).

Where line 18 assumes non-negativity of the heuristics and the entries in W; thus proving monotonicity. □

Together, submodularity and monotonicity are exploitable properties that reveal simple approximation algorithms to hard problems. A reference including details for speeding up greedy selection under such functions is by Krause and Golovin [2012]. In particular, Lemmas 1, 2, and a key result by Nemhauser et al. [1978] lead us to the following result:

Theorem 1 Initialize H0 = ∅ and incrementally add heuristics by greedy selection from a set of admissible heuristics C,

U(Hd) is greater than a factor of (1-1/e) ≈ 0.63 of optimal. A similar bound has been observed alongside the problem of selecting heuristics [Fuchs, 2010]. However, it applies to an edge covering measure of utility that can only be used with a specific type of heuristic, and does not incorporate an arbitrary default heuristic. While we compare to such an edge covering objective later, we stress that Theorem 1 applies to any - possibly heterogeneous - set of candidate heuristics C for which our measure of utility can be efficiently determined.

4 Sample Utility

Greedy selection can be further sped up by measuring utility with a simpler approximation to U. The approach we consider is to sum the heuristic values between only a sample of the states. Intuitively, if this sample is well distributed, then the heuristics between sample states should be strongly correlated with the heuristics between all states.

4.1 A Partitioning Approach

One of the many possible ways to implement sampling is to partition the state space into m mutually exclusive and collectively exhaustive regions, represented by sets of state indices, Z1, . . . , Zm. Within each region, a single sample state is nominated, zi ∈ Zi. From these we define sample utility as

where the weight between sample states p and q is the sum of the weights between the states in partitions Zp and Zq,

or Wpq = |Zp| |Zq| if W specifies a uniform weighting, and

is a normalizing constant ensuring U(∅) = 0.

Choosing the best partitioning is an optimization problem unto itself, and a study of different ways to do so is left to future work. When we use sampling in our experiments, we incrementally select sample states to cover the largest number of uncovered states; a state is covered if it is within t steps of a sample. When all states are covered, we define partitions by assigning states to the nearest sample state as measured in an undirected version of the search graph, where the costs between states are replaced with δ(i, j) ← min {δ(i, j), δ(j, i)}. We note the similarity of this approach to specifying canonical heuristics [Sturtevant et al., 2009] and choosing pathfinding subgoals [Bulitko et al., 2012].

4.2 Optimality Analysis

In this section we analyze the effect sampling has on optimality with respect to the true utility function (7). The foundation of this analysis is heuristic consistency. If each default and candidate heuristic hx ∈ D ∪ C is consistent, 3 i.e.,

then we can use local distance information in the search graph to bound the difference between U(H) and U(H) for any H.

Lemma 3 The sample utility's error is bounded by the weighted sum of the distances between samples and states in the same partition, i.e., ∀H ∈ 2C , |U(H)-U(H)| ≤ ϵ with:

Proof. Since the partitions are mutually exclusive and collectively contain all states, we can write U(H) equivalently as a sum over pairs of states between pairs of partitions: 4

Since the heuristics in H are consistent, it must be true for arbitrary indices p, q, r, and s that:

Reversing the consistency inequality, we similarly have:

3 Consistency also implies admissibility.

4 Note p and q always iterate from 1 to m, and r and s always iterate over the state indices in Zp and Zq as on line 25.

Substituting lines 29 and 31 into line 27 establishes an upper bound on U(H) as follows:

By separating the terms that refer to the heuristics from those that do not refer to the heuristics, we can rewrite line 33 and recover the definitions of W, U and ϵ:

where the last two terms of line 34 are identical but with transposed indices, together equating to ϵ; thus proving U(H) ≤ U(H) + ϵ. The lower bound proceeds similarly, and together these bounds give |U(H) - U(H)| ≤ ϵ. □

Lemma 3 suggests we could use a modified greedy algorithm to optimize U and still retain an approximation guarantee to optimal under U [Krause and Guestrin, 2005]. However, this modification entails a polynomial increase in the number of iterations over the candidate set, which may be unacceptable when the set is large. Fortunately, solutions of known optimality under U are provably optimal under U.

By duplicating the reasoning in Lemmas 1 and 2, we assert that the sample utility function U is both submodular and monotonic. It follows as in Theorem 1 that greedy maximization under U will find a solution that scores greater than a factor of (1-1/e) of U's optimal value. Together with Lemma 4 (described in Appendix A) we obtain the following result:

Theorem 2 InitializeH0 = ∅, and incrementally add heuristics by greedy selection from a set of consistent heuristics C,

U(Hd) is within a factor of (1 - 1/e) of optimal, implying U(Hd) is within a factor of (1-1/e) U(Hd)-ϵ U(Hd)+ϵ-ϵ/e of optimal.

Under the assumption that both U(H) and ϵ can be efficiently computed, it is therefore easy to determine an optimality bound on H post factum. Note that this bound improves as U(H) increases (i.e., as we add more heuristics to the set H).

5 Experiments

We test our approach of greedy utility maximization under U and U on optimal search with A∗ [Hart et al., 1968]. We focus on selecting true-distance heuristics, using the number of nodes expanded during search as a general performance measure. First, we compare our approach to existing methods on two undirected search domains. Next, we use our approach to accurately benchmark a new type of heuristic for directed domains, showing encouraging results over alternative heuristics. In each case our approach requires less than three hours to complete, even on the largest search graphs we consider.

5.1 Undirected Search Graphs

We first apply our approach to the selection of differential heuristics, or DHs [Sturtevant et al., 2009], for undirected search graphs. A single DH consists of the precomputed distances from each state to a specific landmark state p and, from these distances, hp(i, j) = |δ(i, p) - δ(j, p)| gives consistent heuristics. A search graph with n states defines n candidate DHs. Since every DH occupies the same amount of memory, a cardinality constraint doubles as a constraint on memory.

Word Search

In these search problems, states are four letter words from an English dictionary. A word can be changed into another by substituting one letter at a time, resulting in 54, 752 edges across 4, 820 states. To turn coal into gold, for instance, one could take the path 〈coal; goal; goad; gold〉. Euclidean heuristics were recently shown to outperform DHs that used the Farthest selection algorithm [Goldberg and Harrelson, 2005] on precisely this search graph [Rayner et al., 2011]. However, it was unclear whether this was a failure of DHs, or of the particular algorithm that was used to select them. This distinction is to be emphasized: a strong class of heuristics may be undervalued in the absence of a good selection algorithm.

This motivates testing whether DHs are powerful enough to outperform Euclidean heuristics when driven by our approach of greedy utility maximization under U (note we do not sample utility with U here). We reproduce the experimental parameters of the earlier work by testing sets of 6 and 18 DHs, and use the same Euclidean heuristics of dimension 6 and 18. The default heuristic is the zero heuristic.

The results across 10,000 problems are shown in Figure 1. Greedy utility maximization (MaxU) gives a set of 6 DHs that are still not competitive with a 6-dimensional Euclidean heuristic. However, 18 greedily chosen DHs dominate their Euclidean counterpart across all solution lengths. Meanwhile, the DHs placed using the Farthest algorithm excel only on a minority of the longest paths. This is expected of Farthest, since such paths tend to start or end on the landmark states.

Game Maps

Next we consider standard pathfinding benchmarks [Sturtevant, 2012] defined on grid-based maps from BioWare's Dragon Age: Origins. The agent can move cardinally at cost 1 or diagonally at cost 1.5 among open grid cells, as long as doing so does not cut the corner of any closed grid cell. We consider all benchmark problems on fully connected maps with between 168 and 18,890 states, using the travel cost assuming no closed cells as the default heuristic.

We compare three selection algorithms. The first is greedy utility maximization under U, where the partitions are defined using a radius of 1 when a map has less than 10,000 states, and a radius of 2 otherwise. Second, we consider a greedy edge-covering approach [Fuchs, 2010]. This measure of utility is also submodular monotonic, so a comparison is warranted. To improve its efficiency and facilitate an even comparison, we modify this approach to use the same sample states as used by U. Third, we use the Farthest algorithm, which tends to be very effective on the benchmark problems. Each approach is used to define sets of 3 and 10 DHs.

Figure 2 shows our approach achieving a marked improvement over both algorithms on the vast majority of problems. Even though all three approaches have access to the default heuristic during search, our approach benefits from explicitly incorporating it into how the heuristic subset is chosen.

5.2 Directed Search Graphs

Since our approach can be applied to any class of heuristics, an important practical use is to compare competing classes of heuristics on a level playing field. In the following, we compare three kinds of heuristics for directed search graphs.

A search graph is directed if, for any two states i and j, δ(i, j) ̸= δ(j, i). DHs can still generate consistent heuristics on such graphs if the distances are computed on an undirected version of the graph with δ(i, j) ← min{δ(i, j), δ(j, i)}, but we will also consider a new approach of directed differential heuristics (DDHs). DDHs use a pivot state p too, but each pivot defines two distinct heuristic functions. If distances are computed to the pivot, h←-p (i, j) = (δ(i, p)-δ(j, p))+. If they are computed from the pivot, h-→p (i, j) = (δ(p, j)-δ(p, i))+. A search graph with n states defines 2n DDHs, all consistent. DDHs are essentially a decoupling of the heuristics used by the ALT algorithm [Goldberg and Harrelson, 2005], which always stores both the to and from distances for each pivot. However, given fixed memory, the space of possible DDH subsets encapsulates and is exponentially larger than the space of possible ALT subsets. Nevertheless, the greedy algorithm will only experience a doubling in effort.

Each of these - DHs, DDHs, and ALT heuristics - has a defining drawback. A DH built on the undirected graph risks being based on inaccurate distances; a DDH suffers from returning 0 for at least half of the state pairs; and a single ALT heuristic occupies twice the memory of any one DH or DDH. We stress that the optimality bound on our approach readily applies in each case, despite these major idiosyncrasies.

Turning in Place

In our first comparison of these three heuristics, we add a state variable to the Dragon Age map, LAK101D, to describe the agent's current heading. The agent can advance along its current heading or turn left and right in 45 degree increments, as depicted in Figure 3. This results in 7,342 directed edges across 2,544 states. The cost to advance is 1, and the cost to turn is a variable which offers control over the difference in cost between an action and its reverse. The default heuristic is the travel cost assuming no closed cells and no cost to turn.

We explore how the cost to turn affects the performance of sets of 1 and 2 ALT heuristics, and sets of 2 and 4 DH and DDH heuristics. Each set is selected using greedy utility maximization without sampling (that is, we directly measure utility using U), and each set uses the same amount of memory. The results across 10,000 benchmark problems are shown in Figure 4. The search problems become more expensive to solve as the cost to turn increases, but DDHs seem least affected by this. A tradeoff between DHs and DDHs is also evident: when the cost to turn is small, 2 DHs are preferred over 2 DDHs, but this changes as the cost increases.

Platformer

The last test domain is defined on a grid of three types of cells: platforms, ladders, and mid-air. Examples are shown in Figure 6. If the agent is on a platform or ladder, it can move left and right, or up and down onto ladders. If the agent occupies a mid-air state, it automatically moves down one cell per turn, but can optionally control its descent left or right. The default heuristic is the number of steps assuming the agent can travel freely between any adjoining cells. This domain is modelled on a popular genre of video games which has received relatively little attention as a pathfinding benchmark, but is an extreme example of a cost structure that occurs in domains with actions that are difficult to reverse.

We define a random platformer on a 200 × 200 grid with 16,248 accessible states. The states are partitioned into regions whose radius is approximately 2, and greedy maximization of U is used to choose sets of 1 and 2 ALT heuristics, and sets of 2 and 4 DH and DDH heuristics. Figure 5 shows the results on 10,000 random problems. These results reveal DHs to be ineffective at representing costs in this domain, due to the disparity between the cost of an action and its reverse. Meanwhile, we also see the DDH subsets consistently outperforming their ALT counterparts. With the knowledge that both are near-optimal under the same objective, we can infer that DDHs are well worth considering as an alternative class of search heuristics in domains with highly directed costs.

6 Conclusion

This paper introduced a novel approach to the widespread problem of selecting search heuristics. We showed that greedy selection is nearly optimal under a natural measure of utility, and furthermore that provable optimality is not sacrificed when utility is measured on just a sample of the states. These two points rely on the admissibility and consistency of the heuristics respectively, properties that are commonly satisfied by many existing classes of heuristic functions.

Our empirical study emphasizes the importance of optimality under a well-motivated objective. In particular, our method of approximate utility maximization redeemed an underperforming class of heuristics in one domain, outcompeted existing selection algorithms in another, and was instrumental in a pilot study of a promising new type of heuristic which excels in directed domains. The work in this paper has the potential to be extended in several new directions, such as by defining new measures of utility, more efficient sampling methods, and wider application to domains where heuristic subset selection defies domain expertise.

Acknowledgments

We are grateful to several anonymous reviewers who provided valuable feedback. This research was supported by NSERC and Alberta Innovates Technology Futures.

A Post FactumBound on Optimality

Lemma 4 Let θ and φ be set functions over 2S with

for some ϵ, and finite maxima at cardinality d denoted

For any set G with |G| = d, G's optimality with respect to φ is tied to its optimality with respect to θ:

Proof. The bound given on line 39 implies that θ∗ and φ∗ must also have bounded difference: θ∗ - ϵ ≤ φ(arg(θ∗ )) ≤ φ∗ . This reveals an inequality relating θ∗ to φ(G),

which lets us bound the optimality of θ(G) as