Abstract
Traditional graph search algorithms rely heavily on manually designed heuristics to guide the search process efficiently. This paper introduces an online learning framework that automatically constructs powerful composite heuristics from a set of simple, elementary features. By employing a Passive-Aggressive regression approach, the algorithm learns from its own search history, progressively refining its distance estimates. Experimental results across route planning and puzzle-solving domains demonstrate significant reductions in search effort while maintaining near-optimal path quality.
Introduction
In the field of artificial intelligence, pathfinding and graph search are foundational tasks. The efficiency of these searches is largely determined by the quality of the heuristic function used. A heuristic provides an estimate of the cost to reach a goal; an accurate heuristic can drastically prune the search space. However, designing effective heuristics often requires significant domain expertise and manual tuning.
The Problem: Combining Heuristics
A common approach to improving search is to use multiple simple heuristics and take their maximum value. While this ensures admissibility, it often fails to capture the synergistic information present in different features. For instance, in a multi-dimensional grid, individual axis-aligned heuristics may significantly underestimate the true diagonal distance. The challenge lies in finding a way to weight and combine these elementary "abstractions" into a more accurate, dominant heuristic function.
Methodology: Online Learning to Search
The proposed Online Learning to Search algorithm bridges the gap between classical search and online learning. The core of the method is a linear composition of elementary heuristics:
$$h(v, g) = T(w \cdot \phi(v, g))$$
where $\phi$ represents a vector of features, $w$ is a weight vector, and $T$ is a transfer function.
The Feedback Loop
The algorithm operates in a sequence of rounds. After each search task is completed, it performs a retrospective analysis. By conducting an offline search from the goal back to the visited nodes, the system identifies the "ground truth" distances.
Passive-Aggressive Updates
To adjust the weights $w$, the algorithm identifies the node with the largest discrepancy between the estimated and true distance. It then applies a Passive-Aggressive (PA) regression update. This update minimizes the error for that specific node while ensuring the weight vector $w$ changes minimally, preserving the knowledge gained in previous rounds.
Experimental Evaluation
The algorithm was evaluated on three distinct domains: route planning, the TopSpin puzzle, and the classic 8-puzzle.
Key Results
The results consistently showed that the learned heuristics significantly outperformed standard baselines in terms of search efficiency (nodes visited) with minimal impact on path length:
- Route Planning: The learned heuristic visited only 56 nodes, compared to 143 for Dijkstra and 113 for standard aerial distance.
- TopSpin: The search effort was reduced to 88 nodes, down from 201 using a "Maximum Value" combination.
- 8-Puzzle: The algorithm surpassed the human-designed Nilsson’s Sequence, visiting 15.77 nodes on average versus 45.90.
Discussion and Conclusion
The "Online Learning to Search" framework demonstrates that weighting individual abstractions is superior to simple maximization. By treating the search process as a source of training data, the agent effectively "learns the metric" of its environment. While the method requires a sequence of tasks and some offline computation for feedback, it offers a powerful way to automate the discovery of efficient search heuristics in complex domains. Future work may focus on real-time updates during a single search and adapting to dynamic environments.
Summary updated