Rational Deployment of Multiple Heuristics in IDA*
This work addresses a specific bottleneck in heuristic search algorithms for AI planning and optimization, offering an incremental improvement over existing combination methods.
The paper tackles the problem of efficiently combining multiple admissible heuristics in IDA* search by introducing a rational metareasoning approach that decides when to compute expensive heuristics based on expected regret, resulting in a state-of-the-art method with empirical support across domains.
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.