Rational Deployment of Multiple Heuristics in IDA

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