To Max or Not to Max: Online Learning for Speeding Up Optimal Planning

Carmel Domshlak, Erez Karpas, Shaul MarkovitchAAAI 2010 · DOI

Introduction

In the field of cost-optimal planning, the efficiency of the $A^*$ search algorithm is heavily dependent on the quality of its admissible heuristics. Heuristics that are more "informative"—providing estimates closer to the true cost to the goal—can significantly prune the search space. However, a fundamental "utility trade-off" exists: more informative heuristics are often more computationally expensive to calculate.

A common approach to improve accuracy is to use the point-wise maximum of several heuristics ($max(h_1, h_2, ...)$). While this maximizes pruning power, it introduces a computational bottleneck, as every heuristic must be evaluated at every state. This paper introduces Selective Max ($sel_h$), an online learning framework designed to achieve the benefits of multiple heuristics while minimizing the overhead of redundant computations.

The Selective Max ($sel_h$) Approach

The core idea of $sel_h$ is to treat heuristic selection as a classification problem solved dynamically during the search. Instead of computing all available heuristics, the planner predicts which one will be the most informative for the current state. This is based on the "Oracle Hypothesis": if a perfect oracle existed, it would always choose the heuristic that yields the highest value for a given state.

Decision Rule and Learning

The authors derive a formal decision rule based on an idealized tree-search model. It suggests computing a more expensive heuristic ($h_2$) only if the expected reduction in search depth compensates for the additional computation time ($t_2$) relative to a cheaper heuristic ($t_1$). Specifically, if $l$ is the expected reduction in depth, the rule is $l > \log_b(t_2/t_1)$, where $b$ is the branching factor.

To implement this, $sel_h$ employs a Naive Bayes classifier trained on state variables. The authors found that the SAS+ (Finite Domain Representation) of planning tasks provides superior features for learning compared to standard STRIPS, as it groups related propositions into single variables, reducing noise. The process involves:

  1. Initial Probing: A short pre-search phase using stochastic hill-climbing to gather initial training data.
  2. Selective Execution: During $A^*$, if the classifier is confident (exceeding a threshold $\rho$), only the predicted "best" heuristic is computed.
  3. Active Learning: If confidence is low, both heuristics are computed, the maximum is used for search, and the resulting data point is used to update the classifier online.

This adaptive mechanism allows the planner to exploit the specific structure of the problem instance as it is discovered, with a total overhead of only about 2% of search time.

Experimental Evaluation

The methodology was tested on 22 domains from the International Planning Competitions (IPC) 1998–2006, including benchmarks like Logistics, Blocks-World, and Airport. The experiments focused on two state-of-the-art heuristics: the landmark-based $h_{LA}$ and the more expensive landmark-cut heuristic $h_{LM-CUT}$.

Key Results

The results indicate that $sel_h$ successfully balances the accuracy-computation trade-off. It consistently outperformed individual heuristics and their standard maximum in both coverage and speed.

Solved instances vs. timeout for various heuristic configurations.

As shown in the performance curves, $sel_h$ (represented by the black squares) maintains a higher number of solved instances across various timeout limits compared to $h_{LA}$, $h_{LM-CUT}$, and their static maximum ($max_h$). This demonstrates the robustness of the approach across different time constraints.

Summary of average time and total problems solved.

Quantitatively, $sel_h$ solved a total of 460 problems, surpassing $max_h$ (454) and the individual heuristics. Furthermore, it demonstrated a significant reduction in average search time. For problems solved by all methods, $sel_h$ averaged 24.53 seconds, nearly twice as fast as the 41.39 seconds required by the $max_h$ approach.

Discussion and Future Work

The success of $sel_h$ highlights that the "best" heuristic is often state-dependent. In many domains, the classifier frequently switches between heuristics depending on the region of the search space.

Future research directions include refining the decision rule to better account for non-tree search spaces and exploring more sophisticated feature engineering, such as features derived from relaxed plans. Additionally, there is potential in learning to identify "surely expanded" states—those far from the goal that will be expanded regardless of the heuristic value—to skip computation entirely in those regions.

Summary updated

BibTeX
@inproceedings{domshlak2010max,
  author = {Carmel Domshlak and Erez Karpas and Shaul Markovitch},
  title = {{To Max or Not to Max: Online Learning for Speeding Up Optimal Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7741},
}
Figure