Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6853064 | Artificial Intelligence | 2018 | 64 Pages |
Abstract
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 IDAâ. We discuss LazyAâ and LazyIDAâ, variants of Aâ and IDAâ, 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 lazyAâ and rational lazyIDAâ. We also present different methods for estimating the parameters necessary for making such decisions. An empirical evaluation in several domains supports the theoretical results, and shows that the rational variants, rational lazy Aâ and rational lazy IDAâ, are better than their non-rational counterparts.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Erez Karpas, Oded Betzalel, Solomon Eyal Shimony, David Tolpin, Ariel Felner,