Learning Admissible Heuristics via Cost Partitioning

Computer Science > Artificial Intelligence [Submitted on 3 Jun 2026] Learning Admissible Heuristics via Cost Partitioning Hugo Barral, Quentin Cappart, Marie-José Huguet, Sylvie Thiébaux Admissible heuristics are essential for optimal planning, yet learning them remains challenging due to the risk of overestimation. Cost partitioning combines multiple abstraction heuristics while preserving admissibility, but computing optimal partitions online is expensive. We propose a framework that learns to infer admissible cost partitions by leveraging the Lagrangian dual equivalence between cost partitioning and multiplier prediction. Planning states and patterns are encoded as labelled graphs, and an action-centric variant of the Weisfeiler-Leman algorithm extracts structural feature vectors. A deep architecture with axial self-attention and a softmax output layer maps these features to cost weights that satisfy the partition constraints by construction, ensuring admissibility. Experiments demonstrate reduced node expansions compared to suboptimal partitioning baselines while maintaining strict admissibility. To our knowledge, this is the first machine-learned heuristic guaranteed to be admissible. Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2606.04597 [cs.AI]   (or arXiv:2606.04597v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2606.04597 Focus to learn more Submission history From: Quentin Cappart [view email] [v1] Wed, 3 Jun 2026 08:35:04 UTC (43 KB) Access Paper: view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)