Learning from Multiple Heuristics

Mehdi Samadi, Ariel Felner, Jonathan SchaefferAAAI 2008

Abstract

Traditional search algorithms like A* often rely on a single admissible heuristic or the maximum of several heuristics to ensure optimality. However, this approach fails to exploit the complex correlations between multiple overlapping heuristics. This paper presents a novel framework that uses Artificial Neural Networks (ANNs) to combine multiple heuristics into a single, more accurate estimate of the optimal solution cost. By employing a Penalty-Enhanced loss function, the system achieves significant reductions in search effort—up to 100x speedups—while maintaining near-optimal solution quality across various puzzle domains.

Introduction

In single-agent search problems, such as pathfinding or the Rubik's Cube, heuristics provide essential guidance by estimating the cost to reach a goal state. When multiple heuristics are available, the standard practice is to use their maximum value to maintain admissibility. While this ensures an optimal solution, it ignores potential additive information from correlated heuristics. This research explores how machine learning, specifically feed-forward neural networks, can learn to synthesize these multiple "sensors" into a superior guidance function.

Methodology

The core of the proposed approach is treating heuristic combination as a machine learning problem.

Heuristics as Input Features

For any given state, a vector of $k$ heuristic values is generated. These values might come from different Pattern Databases (PDBs) or simpler metrics like Manhattan Distance. These heuristics often represent different partitions of the problem state, providing overlapping perspectives on the remaining cost to the goal.

Partitioning tiles into pattern databases (A, B, C) which serve as input features for the neural network.

Penalty-Enhanced ANN (PE-ANN)

Standard neural networks minimize mean squared error, which treats overestimations and underestimations equally. In search, overestimation (inadmissibility) can lead to sub-optimal solutions. To address this, the authors introduced a "Penalty-Enhanced" (PE) loss function. This asymmetric function penalizes overestimations more severely, biasing the network toward producing values that are "mostly admissible."

The asymmetric error function used in PE-ANN to bias the network towards admissibility by penalizing overestimations more heavily.

Training Strategies

For large-scale problems like the 24-puzzle, where generating optimal training data is computationally expensive, the authors utilize "relaxed domains." The network is trained on a simplified version of the problem, and the learned weights are then applied to the full problem as a robust lower bound.

Experimental Results

The ANN-based approach was tested on several classic benchmarks:

  • 15-Puzzle: Achieved a 16-fold reduction in node expansions compared to state-of-the-art admissible PDBs, with solution quality within 4% of optimal.
  • Towers of Hanoi (16-disc): Demonstrated a staggering 115-fold reduction in tree size.
  • 24-Puzzle: The PE-ANN improved search time by over 3,000 times compared to standard additive PDBs, with only a marginal 0.6% increase in solution cost.

The results indicate that the ANN acts as a highly compressed, intelligent lookup table, capturing the non-linear interactions between heuristics that simple linear combinations or max-functions miss.

Conclusion

This work demonstrates that the trade-off between strict admissibility and search efficiency is highly favorable. By using ANNs to learn from multiple heuristics, search agents can achieve massive performance gains with minimal loss in solution quality. Future work includes exploring online learning techniques like Temporal Difference (TD) learning to allow agents to refine their heuristics during the search process.

Summary updated

BibTeX
@inproceedings{samadi2008learning,
  author = {Mehdi Samadi and Ariel Felner and Jonathan Schaeffer},
  title = {{Learning from Multiple Heuristics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure