Toward Rational Deployment of Multiple Heuristics in A

1 Introduction

The A∗ algorithm [Hart et al., 1968] is a best-first heuristic search algorithm guided by the cost function f(n) = g(n) + h(n). If the heuristic h(n) is admissible (never overestimates the real cost to the goal) then the set of nodes expanded by A∗ is both necessary and sufficient to find the optimal path to the goal [Dechter and Pearl, 1985].

This paper examines the case where we have several available admissible heuristics. Clearly, we can evaluate all these heuristics, and use their maximum as an admissible heuristic, a scheme we call A∗MAX . The problem with naive maximization is that all the heuristics are computed for all the generated nodes. In order to reduce the time spent on heuristic computations, Lazy A∗ (or LA∗ , for short) evaluates the heuristics one at a time, lazily. When a node n is generated, LA∗ only computes one heuristic, h1(n), and adds n to OPEN. Only when n re-emerges as the top of OPEN is another heuristic, h2(n), evaluated; if this results in an increased heuristic estimate, n is re-inserted into OPEN. This idea was briefly mentioned by Zhang and Bacchus (2012) in the context of the MAXSAT heuristic for planning domains. LA∗ is as informative as A∗MAX , but can significantly reduce search time, as we will not need to compute h2 for many nodes. In this paper we provide a deeper examination of LA∗ , and characterize the savings that it can lead to. In addition, we describe several technical optmizations for LA∗ .

LA∗ reduces the search time, while maintaining the informativeness of A∗MAX . However, as noted by Domshlak et al. (2012), if the goal is to reduce search time, it may

Ariel Felner

ISE Department Ben-Gurion University, Israel felner@bgu.ac.il

Erez Karpas

Faculty of IE&M Technion, Israel karpase@gmail.com

be better to compute a fast heuristic on several nodes, rather than to compute a slow but informative heuristic on only one node. Based on this idea, they formulated selective max (SelMAX), an online learning scheme which chooses one heuristic to compute at each state. Sel-MAX chooses to compute the more expensive heuristic h2 for node n when its classifier predicts that h2(n) - h1(n) is greater than some threshold, which is a function of heuristic computation times and the average branching factor. Felner et al. (2011) showed that randomizing a heuristic and applying bidirectional pathmax (BPMX) might sometimes be faster than evaluating all heuristics and taking the maximum. This technique is only useful in undirected graphs, and is therefore not applicable to some of the domains in this paper. Both Sel-MAX and Random compute the resulting heuristic once, before each node is added to OPEN while LA∗ computes the heuristic lazily, in different steps of the search. In addition, both randomization and Sel-MAX save heuristic computations and thus reduce search time in many cases. However, they might be less informed than pure maximization and as a result expand a larger number of nodes.

We then combine the ideas of lazy heuristic evaluation and of trading off more node expansions for less heuristic computation time, into a new variant of LA∗ called rational lazy A∗ (RLA∗ ). RLA∗ is based on rational meta-reasoning, and uses a myopic value-of-information criterion to decide whether to compute h2(n) or to bypass the computation of h2 and expand n immediately when n re-emerges from OPEN. RLA∗ aims to reduce search time, even at the expense of more node expansions than A∗MAX .

Empirical results on variants of the 15-puzzle and on numerous planning domains demonstrate that LA∗ and RLA∗ lead to state-of-the-art performance in many cases.

2 Lazy A∗

Throughout this paper we assume for clarity that we have two available admissible heuristics, h1 and h2. Extension to multiple heuristics is straightforward, at least for LA∗ . Unless stated otherwise, we assume that h1 is faster to compute than h2 but that h2 is weakly more informed, i.e., h1(n) ≤ h2(n) for the majority of the nodes n, although counter cases where h1(n) > h2(n) are possible. We say that h2 dominates h1, if such counter cases do not exist and h2(n) ≥ h1(n) for all nodes n. We use f1(n) to denote g(n) + h1(n). Like-

Algorithm 1: Lazy A∗

Input: LAZY-A∗ 1 Apply all heuristics to Start 2 Insert Start into OPEN 3 while OPEN not empty do 4 n←best node from OPEN 5 if Goal(n) then 6 return trace(n) 7 if h2 was not applied to n then 8 Apply h2 to n 9 insert n into OPEN 10 continue //next node in OPEN 11 foreach child c of n do 12 Apply h1 to c. 13 insert c into OPEN 14 Insert n into CLOSED 15 return FAILURE

wise, f2(n) denotes g(n) + h2(n), and fmax(n) denotes g(n) +max(h1(n), h2(n)). We denote the cost of the optimal solution by C ∗ . Additionally, we denote the computation time of h1 and of h2 by t1 and t2, respectively and denote the overhead of an insert/pop operation in OPEN by to. Unless stated otherwise we assume that t2 is much greater than t1 + to. LA∗ thus mainly aims to reduce computations of h2.

The pseudo-code for LA∗ is depicted as Algorithm 1, and is very similar to A∗ . In fact, without lines 7 - 10, LA∗ would be identical to A∗ using the h1 heuristic. When a node n is generated we only compute h1(n) and n is added to OPEN (Lines 11 - 13), without computing h2(n) yet. When n is first removed from OPEN (Lines 7 - 10), we compute h2(n) and reinsert it into OPEN, this time with fmax(n).

It is easy to see that LA∗ is as informative as A∗MAX , in the sense that both A∗MAX and LA∗ expand a node n only if fmax(n) is the best f-value in OPEN. Therefore, LA∗ and A∗MAX generate and expand and the same set of nodes, up to differences caused by tie-breaking.

In its general form A∗ generates many nodes that it does not expand. These nodes, called surplus nodes [Felner et al., 2012], are in OPEN when we expand the goal node with f = C ∗ . All nodes in OPEN with f > C∗ are surely surplus but some nodes with f = C ∗ may also be surplus. The number of surplus nodes in OPEN can grow exponentially in the size of the domain, resulting in significant costs.

LA∗ avoids h2 computations for many of these surplus nodes. Consider a node n that is generated with f1(n) > C∗ . This node is inserted into OPEN but will never reach the top of OPEN, as the goal node will be found with f = C ∗ . In fact, if OPEN breaks ties in favor of small h-values, the goal node with f = C ∗ will be expanded as soon as it is generated and such savings of h2 will be obtained for some nodes with f1 = C ∗ too. We refer to such nodes where we saved the computation of h2 as good nodes. Other nodes, those with f1(n) < C∗ (and some with f1(n) = C ∗ ) are called regular nodes as we apply both heuristics to them.

A∗MAX computes both h1 and h2 for all generated nodes, spending time t1 +t2 on all generated nodes. By contrast, for good nodes LA∗ only spends t1, and saves t2. In the basic implementation of LA∗ (as in algorithm 1) regular nodes are inserted into OPEN twice, first for h1 (Line 13) and then for h2 (Line 9) while good nodes only enter OPEN once (Line 13). Thus, LA∗ has some extra overhead of OPEN operations for regular nodes. We distinguish between 3 classes of nodes: (1) expanded regular (ER) - nodes that were expanded after both heuristics were computed.

1. surplus regular (SR) - nodes for which h2 was computed but are still in OPEN when the goal was found.
2. surplus good (SG) - nodes for which only h1 was computed by LA∗ when the goal was found.

The time overhead of A∗MAX and LA∗ is summarized in Table 1. LA∗ incurs more OPEN operations overhead, but saves h2 computations for the SG nodes. When t2 (boldface in table 1) is significantly greater than both t1 and to there is a clear advantage for LA∗ , as seen in the SG column.

3 Enhancements to Lazy A∗

Several enhancements can improve basic LA∗ (Algorithm 1), which are effective especially if t1 and to are not negligible.

3.1 OPEN bypassing

Suppose node n was just generated, and let fbest denote the best f-value currently in OPEN. LA∗ evaluates h1(n) and then inserts n into OPEN. However, if f1(n) ≤ fbest, then n will immediately reach the top of OPEN and h2 will be computed. In such cases we can choose to compute h2(n) right away (after Line 12 in Algorithm 1), thus saving the overhead of inserting n into OPEN and popping it again at the next step (= 2 × to). For such nodes, LA∗ is identical to A∗MAX , as both heuristics are computed before the node is added to OPEN. This enhancement is called OPEN bypassing (OB). It is a reminiscent of the immediate expand technique applied to generated nodes [Stern et al., 2010; Sun et al., 2009]. The same technique can be applied when n again reaches the top of OPEN when evaluating h2(n) ; if f2(n) ≤ fbest, expand n right away. With OB, LA∗ will incur the extra overhead of two OPEN cycles only for nodes n where f1(n) > fbest and then later f2(n) > fbest.

3.2 Heuristic bypassing

Heuristic bypassing (HBP) is a technique that allows A∗MAX to omit evaluating one of the two heuristics. HBP is probably used by many implementers, although to the best of our knowledge, it never appeared in the literature. HBP works for a node n under the following two preconditions: (1) the operator between n and its parent p is bidirectional, and (2) both heuristics are consistent [Felner et al., 2011].

Let C be the cost of the operator. Since the heuristic is consistent we know that |h(p) - h(n)| ≤ C. Therefore, h(p) provides the following upper- and lower-bounds on h(n) of h(p) - C ≤ h(n) ≤ h(p) + C. We thus denote h(n) = h(p) - C and h(n) = h(p) + C.

To exploit HBP in A∗MAX , we simply skip the computation of h1(n) if h1(n) ≤ h2(n), and vice versa. For example, consider node a in Figure 1, where all operators cost 1, h1(a) = 6, and h2(a) = 10. Based on our bounds h1(b) ≤ 7 and h2(c) ≥ 9. Thus, there is no need to check h1(b) as h2(b) will surely be the maximum. We can propagate these bounds further to node c. h2(c) = 8 while h1(c) ≤ 8 and again there is no need to evaluate h1(c). Only in the last node d we get that h2(d) = 8 but since h1(c) ≤ 9 then h1(c) can potentially return the maximum and should thus be evaluated.

HBP can be combined in LA∗ in a number of ways. We describe the variant we used. LA∗ aims to avoid needless computations of h2. Thus, when h1(n) < h2(n), we delay the computation of h2(n) and add n to OPEN with f(n) = g(n) + h2(n) and continue as in LA∗ . In this case, we saved t1, delayed t2 and used h2(n) which is more informative than h1(n). If, however, h1(n) ≥ h2(n), then we compute h1(n) and continue regularly. We note that HBP incurs the time and memory overheads of computing and storing four bounds and should only be applied if there is enough memory and if t1 and especially t2 are very large.

4 Rational Lazy A∗

LA∗ offers us a very strong guarantee, of expanding the same set of nodes as A∗MAX . However, often we would prefer to expand more states, if it means reducing search time. We now present Rational Lazy A* (RLA∗ ), an algorithm which attempts to optimally manage this tradeoff.

Using principles of rational meta-reasoning [Russell and Wefald, 1991], theoretically every algorithm action (heuristic function evaluation, node expansion, open list operation) should be treated as an action in a sequential decision-making meta-level problem: actions should be chosen so as to achieve the minimal expected search time. However, the appropriate general meta-reasoning problem is extremely hard to define precisely and to solve optimally.

Therefore, we focus on just one decision type, made in the context of LA∗ , when n re-emerges from OPEN (Line 7). We have two options: (1) Evaluate the second heuristic h2(n) and add the node back to OPEN (Lines 7-10) like LA∗ , or (2) bypass the computation of h2(n) and expand n right way (Lines 11 -13), thereby saving time by not computing h2, at the risk of additional expansions and evaluations of h1. In order to choose rationally, we define a criterion based on value of information (VOI) of evaluating h2(n) in this context.

The only addition of RLA∗ to LA∗ is the option to bypass h2 computations (Lines 7-10). Suppose that we choose to compute h2 - this results in one of the following outcomes: 1: n is still expanded, either now or eventually.

2: n is re-inserted into OPEN, and the goal is found without ever expanding n.

Computing h2 is helpful only in outcome 2, where potential time savings are due to pruning a search subtree at the expense of the time t2(n). However, whether outcome 2 takes place after a given state is not known to the algorithm until the goal is found, and the algorithm must decide whether to evaluate h2 according to what it believes to be the probability of each of the outcomes. We derive a rational policy for when to evaluate h2, under the myopic assumption that the algorithm continues to behave like LA∗ afterwards (i.e., it will never again consider bypassing the computation of h2).

The time wasted by being sub-optimal in deciding whether to evaluate h2 is called the regret of the decision. If h2(n) is not helpful and we decide to compute it, the effort for evaluating h2(n) turns out to be wasted. On the other hand, if h2(n) is helpful but we decide to bypass it, we needlessly expand n. Due to the myopic assumption, RLA∗ would evaluate both h1 and h2 for all successors of n.

Table 2 summarizes the regret of each possible decision, for each possible future outcome; each column in the table represents a decision, while each row represents a future outcome. In the table, td is the to time compute h2 and re-insert n into OPEN thus delaying the expansion of n, te is the time to remove n from OPEN, expand n, evaluate h1 on each of the b(n) ("local branching factor") children {n′ } of n, and insert {n′} into the open list. Computing h2 needlessly wastes time td. Bypassing h2 computation when h2 would have been helpful wastes te + b(n)td time, but because computing h2 would have cost td, the regret is te + (b(n) - 1)td.

Let us denote the probability that h2 is helpful by ph. The expected regret of computing h2 is thus (1 - ph)td. On the other hand, the expected regret of bypassing h2 is ph(te + (b(n) - 1)td). As we wish to minimize the expected regret, we should thus evaluate h2 just when:

or equivalently:

If phb(n) ≥ 1, then the expected regret is minimized by always evaluating h2, regardless of the values of td and te. In these cases, RLA∗ cannot be expected to do better than LA∗ . For example, in the 15-puzzle and its variants, the effective branching factor is ≈ 2. Therefore, if h2 is expected to be helpful for more than half of the nodes n on which LA∗ evaluates h2(n), then one should simply use LA∗ .

For phb(n) < 1, the decision of whether to evaluate h2 depends on the values of td and te:

Denote by tc the time to generate the children of n. Then:

By substituting (4) into (3), obtain: evaluate h2 if:

The factor ph 1-phb(n) depends on the potentially unknown probability ph, making it difficult to reach the optimum decision. However, if our goal is just to do better than LA∗ , then it is safe to replace ph by an upper bound on ph. Note that the values ph, t1, t2, tc may actually be variables that depend in complicated ways on the state of the search. Despite that, the very crude model we use, assuming that they are setting-specific constants, is sufficient to achieve improved performance, as shown in Section 5.

We now turn to implementation-specific estimation of the runtimes. OPEN in A∗ is frequently implemented as a priority queue, and thus we have, approximately, to = τ logNo for some τ, where the size of OPEN is No. Evaluating h1 is cheap in many domains, as is the case with Manhattan Distance (MD) in discrete domains, to is the most significant part of te. In such cases, rule (5) can be approximated as 6:

Rule (6) recommends to evaluate h2 mostly at late stages of the search, when the open list is large, and in nodes with a higher branching factor.

In other domains, such as planning, both t1 and t2 are significantly greater than both to and tc, and terms not involving t1 or t2 can be dropped from (5), resulting in Rule (7):

The right hand side of (7) grows with b(n), and here it is beneficial to evaluate h2 only for nodes with a sufficiently large branching factor.

5 Empirical evaluation

We now present our empirical evaluation of LA∗ and RLA∗ , on variants of the 15-puzzle and on planning domains.

5.1 Weighted 15 puzzle

We first provide evaluations on the weighted 15-puzzle variant [Thayer and Ruml, 2011], where the cost of moving each tile is equal to the number on the tile. We used a subset of 36 problem instances (out of the 100 instances of Korf (1985)) which could be solved with 2Gb of RAM and 15 minutes timeout using the Weighted Manhattan heuristic (WMD) for h1. As the expensive and informative heuristic h2 we use a heuristic based on lookaheads [Stern et al., 2010]. Given a bound d we applied a bounded depth-first search from a node n and backtracked when we reached leaf nodes l for which g(l) +WMD(l) > g(n) +WMD(n) + d. f-values from leaves were propagated to n.

Table 3 presents the results averaged on all instances solved. The runtimes are reported relative to the time of A∗ with WMD (with no lookahead), which generated 1,886,397 nodes (not reported in the table). The first 3 columns of Table 3 show the results for A∗ with the lookahead heuristic for different lookahead depths. The best time is achieved for lookahead 6 (0.588 compared to A∗ with WMD). The fact that the time does not continue to decrease with deeper lookaheads is clearly due to the fact that although the resulting heuristic improves as a function of lookahead depth (expanding and generating fewer nodes), the increasing overheads of computing the heuristic eventually outweights savings due to fewer expansions.

The next 4 columns show the results for LA∗ with WMD as h1, lookahead as h2, for different lookahead depths. The Good1 column presents the number of nodes where LA∗ saved the computation of h2 while the h2 column presents the number of nodes where h2 was computed. Roughly 28% of nodes were Good1 and since t2 was the most dominant time cost, most of this saving is reflected in the timing results. The best results are achieved for lookahead 8, with a runtime of 0.527 compared to A∗ with WMD.

The final columns show the results of RLA∗ , with the values of τ, ph, t2 calibrated for each lookahead depth using a small subset of problem instances. The Good2 column counts the number of times that RLA∗ decided to bypass the h2 computation. Observe that RLA∗ outperforms LA∗ , which in turn outperforms A∗ , for most lookahead depths. The lowest time with RLA∗ (0.371 of A∗ with WMD) was obtained for lookahead 10. That is achieved as the more expensive h2 heuristic is computed less often, reducing its effective computational overhead, with some adverse effect in the number of expanded nodes. Although LA∗ expanded fewer nodes, RLA∗ performed much fewer h2 computations as can be seen in the table, resulting in decreased overall runtimes.

5.2 Planning domains

We implemented LA∗ and RLA∗ on top of the Fast Downward planning system [Helmert, 2006], and experimented with two state of the art heuristics: the admissible landmarks heuristic hLA (used as h1) [Karpas and Domshlak, 2009], and the landmark cut heuristic hLMCUT [Helmert and Domshlak, 2009] (used as h2). On average, hLMCUT computation is 8.36 times more expensive than hLA computation. We did not implement HBP in the planning domains as the heuristics we use are not consistent and in general the operators are not invertible. We also did not implement OB, as the cost of OPEN operations in planning is trivial compared to the cost of heuristic evaluations.

We experimented with all planning domains without conditional effects and derived predicates (which the heuristics we used do not support) from previous IPCs. We compare the performance of LA∗ and RLA∗ to that of A∗ using each of the heuristics individually, as well as to their max-based combination, and their combination using selective-max (SelMAX) [Domshlak et al., 2012]. The search was limited to 6GB memory, and 5 minutes of CPU time on a single core of an Intel E8400 CPU with 64-bit Linux OS.

When applying RLA∗ in planning domains we evaluate rule (7) at every state. This rule involves two unknown quantities: t2 t1 , the ratio between heuristic computations times, and ph, the probability that h2 is helpful. Estimating t2 t1 is quite easy - we simply use the average computation times of both heuristics, which we measure as search progresses.

Estimating ph is not as simple. While it is possible to empirically determine the best value for ph, as done for the weighted 15 puzzle, this does not fit the paradigm of domainindependent planning. Furthermore, planning domains are very different from each other, and even problem instances in the same domain are of varying size, and thus getting a single value for ph which works well for many problems is difficult. Instead, we vary our estimate of ph adaptively during search. To understand this estimate, first note that if n is a node at which h2 was helpful, then we computed h2 for n, but did not expand n. Thus, we can use the number of states for which we computed h2 that were not yet expanded (denoted by A), divided by the number of states for which we computed h2 (denoted by B), as an approximation of ph. However, A B is not likely to be a stable estimate at the beginning of the search, as A and B are both small numbers. To overcome this problem, we "imagine" we have observed k examples, which give us an estimate of ph = pinit, and use a weighted average between these k examples, and the observed examples - that is, we estimate ph by ( A B · B + pinit · k)/(B + k). In our empirical evaluation, we used k = 1000 and pinit = 0.5.

Table 4 depicts the experimental results. The leftmost part of the table shows the number of solved problems in each domain. As the table demonstrates, RLA∗ solves the most problems, and LA∗ solves the same number of problems as Sel-MAX. Thus, both LA∗ and RLA∗ are state-of-the-art in cost-optimal planning. Looking more closely at the results, note that Sel-MAX solves 10 more problems than LA∗ and RLA∗ in the freecell domain. Freecell is one of only three domains in which hLA is more informed than hLMCUT (the other two are nomystery-opt11 and visitall-opt11), violating the basic assumptions behind LA∗ that h2 is more informed than h1. If we ignore these domains, both LA∗ and RLA∗ solve more problems than Sel-MAX.

The middle part of the Table 4 shows the geometric mean of planning time in each domain, over the commonly solved problems (i.e., those that were solved by all 6 methods). RLA∗ is the fastest overall, with LA∗ second. It is important to note that both LA∗ and RLA∗ are very robust, and even in cases where they are not the best they are never too far from the best. For example, consider the miconic domain. Here, hLA is very informative and thus the variant that only computed hLA is the best choice (but a bad choice overall). Observe that both LA∗ and RLA∗ saved 86% of hLMCUT computations, and were very close to the best algorithm in this extreme case. In contrast, the other algorithms that consider both heuristics (max and Sel-MAX) performed very poorly here (more than three times slower).

The rightmost part of Table 4 shows the average fraction of nodes for which LA∗ and RLA∗ did not evaluate the more expensive heuristic, hLMCUT , over the problems solved by both these methods. This is shown in the good columns. Our first observation is that this fraction varies between different domains, indicating why LA∗ works well in some domains, but not in others. Additionally, we can see that in domains where there is a difference in this number between LA∗ and RLA∗ , RLA∗ usually performs better in terms of time. This indicates that when RLA∗ decides to skip the computation of the expensive heuristic, it is usually the right decision.

Finally, Table 5 shows the total number of expanded and generated states over all commonly solved problems. LA∗ is indeed as informative as A∗MAX (the small difference is caused by tie-breaking), while RLA∗ is a little less informed and expands slightly more nodes. However, RLA∗ is much more informative than its "intelligent" competitor - SelMAX, as these are the only two algorithms in our set which selectively omit some heuristic computations. RLA∗ generated almost half of the nodes compared to Sel-MAX, suggesting that its decisions are better.

5.3 Limitations of LA∗ : 15 puzzle example

Some domains and heuristic settings will not achieve time speedup with LA∗ . An example is the regular, unweighed 15puzzle. Results for A∗MAX and LA∗ with and without HBP on the 15-puzzle are reported in Table 6. HBP1 (HBP2) count the number of nodes where HBP pruned the need to compute h1 (resp. h2). OB is the number of nodes where OB was helpful. Bad is the number of nodes that went through two OPEN cycles. Finally, Good is the number of nodes where computation of h2 was saved due to LA∗ .

In the first experiment, Manhattan distance (MD) was divided into two heuristics: ∆x and ∆y used as h1 and h2. Results are averaged over 100 random instances with average solution depth of 26.66. As seen from the first two lines, HBP when applied on top of A∗MAX saved about 36% of the heuristic evaluations. Next are results for LA∗ and LA∗+HBP. Many nodes are pruned by HBP, or OB. The number of good nodes dropped from 28% (Line 3) to as little as 11% when HBP was applied. Timing results (in ms) show that all variants performed equally. The reason is that the time overhead of the ∆x and ∆y heuristics is very small so the saving on these 28% or 11% of nodes was not significant to outweigh the HBP overhead of handling the upper and lower bounds.

The next experiment is with MD as h1 and a variant of the additive 7-8 PDBs [Korf and Felner, 2002], as h2. Here we can observe an interesting phenomenon. For LA∗ , most nodes were caught by either HBP (when applicable) or by OB. Only 4% of the nodes were good nodes. The reason is that the 7-8 PDB heuristic always dominates MD and is always the maximum among the two. Thus, 7-8 PDB was needed at early stages (e.g. by OB) and MD itself almost never caused nodes to be added to OPEN and remain there until the goal was found.

These results indicate that on such domains, LA∗ has limited merit. Due to uniform operator cost and the heuristics being consistent and simple to compute, very little space is left for improvement with good nodes. We thus conclude that LA∗ is likely to be effective when there is significant difference between t1 and t2, and/or operators that are not bidirectional and/or with non-uniform costs, allowing for more good nodes and significant time saving.

6 Conclusion

We discussed two schemes for decreasing heuristic evaluation times. LA∗ is very simple to implement and is as informative as A∗MAX . LA∗ can significantly speed up the search, especially if t2 dominates the other time costs, as seen in weighted 15 puzzle and planning domains. Rational LA∗ allows additional cuts in h2 evaluations, at the expense of being less informed than A∗MAX . However, due to a rational tradeoff, this allows for an additional speedup, and Rational LA∗ achieves the best overall performance in our domains.

RLA∗ is simpler to implement than its direct competitor, Sel-MAX, but its decision can be more informed. When RLA∗ has to decide whether to compute h2 for some node n, it already knows that f1(n) ≤ C ∗ . By contrast, although SelMAX uses a much more complicated decision rule, it makes its decision when n is first generated, and does not know whether h1 will be informative enough to prune n. Rational LA∗ outperforms Sel-MAX in our planning experiments.

RLA∗ and its analysis can be seen as an instance of the rational meta-reasoning framework [Russell and Wefald, 1991]. While this framework is very general, it is extremely hard to apply in practice. Recent work exists on meta-reasoning in DFS algorithms for CSP) [Tolpin and Shimony, 2011] and in Monte-Carlo tree search [Hay et al., 2012]. This paper applies these methods successfully to a variant of A∗ . There are numerous other ways to use rational meta-reasoning to improve A∗ , starting from generalizing RLA∗ to handle more than two heuristics, to using the meta-level to control decisions in other variants of A∗ . All these potential extensions provide fruitful ground for future work.

7 Acknowledgments

The research was supported by the Israeli Science Foundation (ISF) under grant #305/09 to Ariel Felner and Eyal Shimony and by Lynne and William Frankel Center for Computer Science.