Towards Rational Deployment of Multiple Heuristics in A*
This work addresses efficiency in heuristic computation for A* search, which is incremental as it builds on existing methods to optimize performance in domains like planning and pathfinding.
The paper tackles the problem of reducing time spent computing multiple admissible heuristics in A* search by introducing Lazy A* and rational lazy A*, which lazily evaluate heuristics and use meta-reasoning to decide when to compute expensive ones. Empirical results show these methods are state-of-the-art for heuristic combination.
The obvious way to use several admissible heuristics in A* is to take their maximum. In this paper we aim to reduce the time spent on computing heuristics. We discuss Lazy A*, a variant of A* where heuristics are evaluated lazily: only when they are essential to a decision to be made in the A* search process. We present a new rational meta-reasoning based scheme, rational lazy A*, which decides whether to compute the more expensive heuristics at all, based on a myopic value of information estimate. Both methods are examined theoretically. Empirical evaluation on several domains supports the theoretical results, and shows that lazy A* and rational lazy A* are state-of-the-art heuristic combination methods.