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.
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."
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