On Using Admissible Bounds for Learning Forward Search Heuristics

Carlos Núñez-Molina, Masataro Asai, Pablo Mesejo, Juan Fernández-OlivaresIJCAI 2024

Abstract

In classical planning, learning search heuristics from data often relies on Mean Squared Error (MSE) loss, which implicitly assumes a standard Gaussian distribution of errors. This assumption ignores critical domain knowledge, such as the non-negativity of costs and the existence of admissible lower bounds. We propose a distributional estimation approach that models heuristics using Truncated Gaussian distributions. By incorporating admissible bounds as constraints, our method ensures that learned heuristics are mathematically consistent with known limits. Evaluation across several International Planning Competition domains shows that our approach yields more accurate heuristics and superior search performance, solving more problems with fewer node evaluations than standard baselines.

Introduction

Heuristic functions are central to efficient AI search, providing estimates of the cost to reach a goal from a given state. While recent work has focused on learning these functions using machine learning, standard training regimes often fail to leverage the mathematical properties of heuristics. Specifically, using MSE as a loss function is statistically equivalent to assuming that the heuristic follows a standard Gaussian distribution. This is problematic because heuristics are naturally bounded: costs cannot be negative, and symbolic "admissible" heuristics (like $h^{LMcut}$) provide guaranteed lower bounds on the true cost. Ignoring these bounds during training results in noisy, often inadmissible predictions that do not fully exploit available domain knowledge.

Methodology: Distributional Estimation with Truncated Gaussians

To address these limitations, we shift from point-estimation to distributional estimation based on the Principle of Maximum Entropy. Instead of a standard bell curve, we model the heuristic as a Truncated Gaussian (TN) distribution. This distribution is constrained by a lower bound ($l$) and/or an upper bound ($u$).

Visual comparison of the standard Normal distribution $N(x|0,1)$ and various Truncated Gaussian distributions $TN(x|\mu, \sigma, l, u)$ with different bounds.

In our framework, we use an existing, efficiently computable admissible heuristic (e.g., $h^{LMcut}$) as the lower bound $l$. This ensures the model "knows" the cost cannot be lower than this value. Rather than minimizing MSE, we minimize the Negative Log-Likelihood (NLL) of the Truncated Gaussian. This requires the model to predict both a mean ($\mu$) and a standard deviation ($\sigma$), allowing it to capture uncertainty about the remaining cost. For search algorithms like Greedy Best-First Search, we use the analytical mean of the TN distribution as the heuristic value, which naturally respects the bounds even if the raw neural network output does not.

Experimental Evaluation

We evaluated the TN approach on four classic planning domains: BlocksWorld, Ferry, Gripper, and VisitAll. Training data was generated by solving small instances optimally to obtain the ground truth cost ($h^*$), with $h^{LMcut}$ providing the admissible lower bounds. We compared our TN-based heuristics against standard Gaussian (MSE) models across multiple architectures, including Neural Logic Machines and STRIPS-HGN.

Key Results

The TN models consistently outperformed standard MSE-based models in both accuracy and search efficiency. In terms of accuracy, TN models achieved significantly lower MSE on test sets; for instance, in the ferry domain, the standard model's error was over 118, while the TN model maintained an error of 8.63.

Comparison of search performance (solved ratio) and search effort (average node evaluations) between the proposed TN approach and standard baselines.

As shown in the results table, the TN-based heuristics solved a higher ratio of instances (coverage) and required significantly fewer node evaluations. In the blocks domain, the TN model solved 88% of problems compared to 79% for the standard model, while evaluating roughly half as many nodes. Furthermore, the learned TN heuristics significantly outperformed the state-of-the-art symbolic $h^{FF}$ heuristic in every domain tested.

Discussion and Future Work

Our results highlight that incorporating prior knowledge through constraints is more effective than simply trying to "copy" a symbolic heuristic. By using admissible bounds as a floor, the model can focus on learning the gap between the symbolic bound and the optimal cost. This leads to faster convergence during training and better search guidance.

Future work will explore the use of upper bounds (e.g., from known suboptimal plans) and the application of this framework to Reinforcement Learning, where value functions are often learned in environments with known but ignored bounds. Additionally, the predicted standard deviation $\sigma$ offers a path toward "likely-admissible" heuristics for optimal search algorithms like A*.

Summary updated

BibTeX
@inproceedings{nunezmolina2024using,
  author = {Carlos Núñez-Molina and Masataro Asai and Pablo Mesejo and Juan Fernández-Olivares},
  title = {{On Using Admissible Bounds for Learning Forward Search Heuristics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure