Learning to Search and Searching to Learn for Generalization in Planning
2026-05-25 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors study how to make AI better at solving new and bigger puzzles by combining traditional planning techniques with learning. They create a system where a special neural network guides a smart search, and the results of the search help improve the network through learning. This approach lets the AI solve complex puzzles from scratch and even handle much larger problems than it was trained on without needing to search. Their method works well on various puzzle types and shows strong ability to generalize to new challenges.
Deep Reinforcement LearningCombinatorial GeneralizationClassical PlanningBest-First SearchA* SearchRelational Graph Neural NetworkQ-learningHeuristicZero-shot GeneralizationSparse Rewards
Authors
Michael Aichmüller, Yannik Hesse, Hector Geffner
Abstract
Combinatorial generalization remains a central challenge in Deep Reinforcement Learning (DRL). Classical planning provides a simple yet challenging setting to study this problem through explicit relational descriptions, without requiring learning from perception. In sparse-reward domains, standard RL exploration via real-time search is ineffective, and learning-based planning methods often rely on expert demonstrations, hindsight relabeling, or random walks from the goal state. In contrast, planners rely on best-first search methods such as $\mathrm{A}^\star$ to solve problems from scratch. We propose a self-improving $\mathrm{WA}^\star$ learning framework in combination with a value heuristic represented by a Relational Graph Neural Network: the heuristic guides search, and the resulting search data updates the heuristic via $Q$-learning. This loop yields heuristics that can function as general policies and solve new instances even without search, where DRL otherwise fails, as we show on puzzles such as Sokoban, PushWorld, The Witness, and the 2023 International Planning Competition benchmarks. Notably, we demonstrate strong zero-shot generalization: For example, heuristics trained on Blocksworld instances with fewer than 30 blocks successfully solve instances with 488 blocks without search.