查看文章

The obvious way to use several admissible heuristics in searching for an optimal solution is to take their maximum. In this paper, we aim to reduce the time spent on computing heuristics within the context of A⁎ and I D A⁎. We discuss Lazy A⁎ and Lazy I D A⁎, variants of A⁎ and I D A⁎, respectively, where heuristics are evaluated lazily: only when they are essential to a decision to be made in the search process. While these lazy algorithms outperform naive maximization, we can do even better by intelligently deciding when to compute the more expensive heuristic. We present a new rational metareasoning based scheme which decides whether to compute the more expensive heuristics at all, based on a myopic regret estimate. This scheme is used to create rational lazy A⁎ and rational lazy I D A⁎. We also present different methods for estimating the parameters necessary for making such decisions. An empirical …