Rational Deployment of Multiple Heuristics in IDA*
  Recent advances in metareasoning for search has shown its usefulness in
improving numerous search algorithms. This paper applies rational metareasoning
to IDA* when several admissible heuristics are available. The obvious basic
approach of taking the maximum of the heuristics is improved upon by lazy
evaluation of the heuristics, resulting in a variant known as Lazy IDA*. We
introduce a rational version of lazy IDA* that decides whether to compute the
more expensive heuristics or to bypass it, based on a myopic expected regret
estimate. Empirical evaluation in several domains supports the theoretical
results, and shows that rational lazy IDA* is a state-of-the-art heuristic
combination method.
