Trajectory-Aware Heuristic Learning for Combinatorial Search

Learning effective value heuristics for combinatorial search is difficult, as prior methods rely on surrogate supervision or costly downstream search to assess progress. We introduce a trajectory-aware probabilistic framework that models uncertainty in cost-to-go labels instead of treating them as fixed targets. Heuristic learning is cast as inference over state trajectories using an HMM-style model, where estimated depth-change dynamics define transitions and forward-backward inference yields soft supervision. To evaluate heuristic quality without search, we propose a large-scale local ranking metric that measures a model's ability to order neighboring states. On the Rubik's Cube, our approach consistently improves local ranking accuracy and downstream search performance under matched computational budgets.

This paper studies how to train machine-learning heuristics that guide search algorithms for hard puzzles. Random scrambles are easy to generate, but their length is not the same as the true shortest solution length, which makes training noisy. We model the unknown distance-to-goal along a trajectory as a hidden variable and use probabilistic inference to create more reliable training targets. We also introduce CubeLocalRank, a search-free benchmark that tests whether a heuristic correctly ranks nearby puzzle states. The resulting heuristics improve search performance on Rubik’s Cube benchmarks and transfer to larger puzzle domains.