Towards Rational Deployment of Multiple Heuristics in A*

IJCAI 2013

TL;DR

This paper introduces "Lazy A" and "Rational Lazy A" to reduce the computational cost of using multiple heuristics in the A* search algorithm. By intelligently delaying or selectively computing expensive heuristics, these methods achieve significant speedups while maintaining optimality, outperforming existing approaches on various benchmarks.

What Problem Does This Paper Address?

The A* search algorithm is a cornerstone of pathfinding and planning, relying on a heuristic function ($h(n)$) to guide its search towards the goal. When multiple admissible heuristics are available, a common strategy is to use the maximum of these heuristics ($h_{max}(n) = max(h_1(n), h_2(n), ...)$). While this approach guarantees optimality, it can be computationally expensive if calculating any single heuristic is time-consuming. The core problem this paper addresses is how to leverage the power of multiple heuristics without incurring prohibitive computational overhead, specifically by reducing the time spent evaluating these heuristics.

Methods

The paper proposes two main algorithmic enhancements to A*:

  • Lazy A (LA): This approach evaluates heuristics one at a time, lazily. When a node is generated, only the cheapest heuristic ($h_1$) is computed. The more expensive heuristic ($h_2$) is only computed when the node is about to be expanded (i.e., when it's at the top of the OPEN list). This saves computation time for nodes that are never expanded or for which $h_1$ is already sufficient. LA* maintains the same optimality guarantees as using the maximum heuristic.
  • Rational Lazy A (RLA): This method builds upon LA by introducing a "rational meta-reasoning" component. RLA makes a decision at the point where LA would compute $h_2$: it can either compute $h_2$ (like LA) or "bypass" the computation and expand the node immediately. This bypass is a trade-off: it saves heuristic computation time but might lead to more node expansions and evaluations of $h_1$. The decision is based on a myopic value-of-information criterion, estimating the probability that $h_2$ will be "helpful" (i.e., lead to pruning a significant portion of the search space). RLA* aims to minimize expected regret, balancing heuristic computation cost against potential search time savings.

The paper also discusses technical optimizations like "OPEN bypassing" (OB) and "Heuristic Bypassing" (HBP), which further refine these lazy evaluation strategies.

Datasets

The paper evaluates its proposed methods on two main types of benchmarks:

  • Weighted 15-puzzle: A variant of the classic puzzle where tile movement costs are proportional to the tile's number.
  • Planning Domains: A suite of standard planning problems, utilizing heuristics like the admissible landmarks heuristic ($h_{LA}$) and the landmark cut heuristic ($h_{LMCUT}$).

No new benchmarks were introduced; instead, existing, well-established problem sets were used to demonstrate the effectiveness of the algorithms.

Key Insights and Ideas

  • The "Good Node" Concept: LA* identifies "good nodes" – nodes for which $h_1$ is sufficient and $h_2$ computation can be skipped. This is a key source of savings, especially when $h_2$ is significantly more expensive than $h_1$.
  • Rational Trade-off: RLA* formalizes the decision of whether to compute an expensive heuristic. It recognizes that sometimes expanding more nodes with a cheaper heuristic can be faster than computing a more informative but costly one.
  • Myopic Value of Information: The core of RLA*'s decision-making is a simplified, forward-looking estimation of how much benefit computing $h_2$ will provide, balancing immediate cost against future gains.
  • Domain-Specific Performance: The effectiveness of LA and RLA is shown to be highly dependent on the domain and the relative costs and informativeness of the heuristics. Domains with large differences in heuristic computation times and non-uniform operator costs benefit the most.

Key Results

  • LA* vs. AMAX: LA achieves significant speedups over AMAX (which computes all heuristics) by avoiding unnecessary $h_2$ computations, particularly in domains where $h_2$ is much more expensive. For example, in planning domains, LA saved an average of 28% of $h_2$ computations in the weighted 15-puzzle.
  • RLA vs. LA: RLA further improves upon LA by selectively skipping $h_2$ computations even when LA would perform them. This leads to further speedups, achieving state-of-the-art performance on several benchmarks. In the weighted 15-puzzle, RLA achieved a runtime of 0.371 times that of A* with a single heuristic.
  • Planning Domain Performance: In planning domains, RLA consistently solved the most problems and achieved the fastest planning times, outperforming A, AMAX, and Sel-MAX (another heuristic selection method).
  • Robustness: While not always the absolute fastest, LA and RLA are shown to be very robust and generally perform close to the best methods.

Limitations and Future Work

  • Heuristic Consistency: The effectiveness of some optimizations like HBP relies on heuristic consistency, which is not always present in modern planning heuristics.
  • Myopic Decision-Making: RLA*'s rational decision-making is "myopic," meaning it doesn't consider future decisions beyond the current step. A more sophisticated, long-term planning approach could potentially yield further improvements.
  • Generalization: The current work focuses on two heuristics. Extending RLA* to handle more than two heuristics is a natural next step.
  • Meta-Reasoning: The paper frames RLA within a broader rational meta-reasoning framework, suggesting that similar principles could be applied to control decisions in other variants of A and other search algorithms.

The authors conclude that LA and RLA are effective methods for reducing heuristic computation costs, with RLA* offering a rational trade-off that leads to superior performance in many scenarios.

Summary updated

BibTeX
@inproceedings{2013towards,
  title = {{Towards Rational Deployment of Multiple Heuristics in A*}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2013},
}
Figure